Poseidon as a PRF: Security Proofs

This document provides a comprehensive cryptographic security analysis of Poseidon as a Pseudorandom Function (PRF), which serves as the foundation for the security of our key derivation schemes and encrypted data structures.

---

Poseidon Hash Function

Poseidon is a cryptographic hash function specifically designed for efficiency in zero-knowledge proof systems and Multi-Party Computation (MPC) contexts. It operates over finite fields and uses a substitution-permutation network (SPN) with a carefully chosen S-box to minimize the number of constraints in arithmetic circuits.

Implementation Parameters

Our implementation uses the standard circom Poseidon library with parameters derived from the official Poseidon whitepaper (Grassi et al., 2019):

• Field: BN254 (254-bit prime field)
• S-box: $x^5$ (minimizes R1CS constraints)
• Target Security Level: 128 bits
• Full Rounds: 8 (as specified in Table 2 of the whitepaper)
• Partial Rounds: Width-dependent (as specified in Table 8 of the whitepaper)
• Round Constants: Generated using the official Hadeshash implementation
• Width: Varies by use case (typically 2-4 field elements)

Parameter Source: All round numbers, constants, and matrices (C, S, M, P) are computed according to the recommendations in the Poseidon whitepaper and implemented using the standard circom-crypto library, ensuring peer-reviewed and widely-audited cryptographic parameters.

Design Properties

• Algebraic Construction: Operates natively over prime fields
• ZK-Friendly: Optimized for minimal constraints in arithmetic circuits (S-box $x^5$ requires only 1 constraint per application)
• MPC-Compatible: Low multiplicative complexity for efficient MPC protocols
• Provable Security: Based on well-studied cryptographic primitives and algebraic attacks

---

Security Model: Poseidon as a PRF

A Pseudorandom Function (PRF) is a family of functions that are computationally indistinguishable from truly random functions.

Definition: Pseudorandom Function

A function family $F: \mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}$ is a secure PRF if for all probabilistic polynomial-time (PPT) distinguishers $\mathcal{D}$:

$$\mathrm{Adv}^\mathrm{PRF}_F(\mathcal{D}) = \left| \Pr[\mathcal{D}^{F_k} = 1] - \Pr[\mathcal{D}^{R} = 1] \right| \leq \mathrm{negl}(\lambda)$$

where $\lambda$ is the security parameter, $k$ is a uniformly random key from $\mathcal{K}$, and $R$ is a truly random function from $\mathcal{X}$ to $\mathcal{Y}$.

Poseidon PRF Security

Assumption: Poseidon, when keyed appropriately, satisfies the PRF security definition.

Implication: Given oracle access to $\text{Poseidon}_k(\cdot)$ for a uniformly random secret key $k$, no PPT adversary can distinguish the outputs from those of a truly random function, except with negligible probability.

---

Security Parameters for BN254

The BN254 elliptic curve field is used in our implementation, providing the following security parameters:

Field Prime

$$p = 21888242871839275222246405745257275088548364400416034343698204186575808495617$$

This is a 254-bit prime number that defines the finite field $\mathbb{F}_p$ over which Poseidon operates.

Security Levels

The circom Poseidon implementation with BN254 and S-box $x^5$ is configured to provide 128-bit security against the best known algebraic attacks and statistical attacks.

Pre-image Resistance

Definition: Given a hash output $y$, it is computationally infeasible to find any input $x$ such that $\text{Poseidon}(x) = y$.

Security Level: $2^{128}$ operations

Rationale: The number of rounds and internal state size are chosen such that the best known algebraic attacks (including Gröbner basis attacks and interpolation attacks) require at least $2^{128}$ operations. While the field size is 254 bits, the practical security level is determined by the resistance to algebraic attacks, not just the output space size.

Formal Statement: For any PPT adversary $\mathcal{A}$:

$$\Pr[y \leftarrow \text{Poseidon}(x); x' \leftarrow \mathcal{A}(y) : \text{Poseidon}(x') = y] \leq 2^{-128} + \text{negl}(\lambda)$$

Practical Bound:

$$2^{128} \approx 3.4 \times 10^{38} \text{ operations}$$

Second Pre-image Resistance

Definition: Given an input $x_1$ and its hash output $y = \text{Poseidon}(x_1)$, it is computationally infeasible to find a different input $x_2 \neq x_1$ such that $\text{Poseidon}(x_2) = y$.

Security Level: $2^{128}$ operations

Formal Statement: For any PPT adversary $\mathcal{A}$:

$$\Pr[x_1 \leftarrow \mathcal{X}; x_2 \leftarrow \mathcal{A}(x_1) : x_1 \neq x_2 \land \text{Poseidon}(x_1) = \text{Poseidon}(x_2)] \leq 2^{-128} + \text{negl}(\lambda)$$

Collision Resistance (Birthday Paradox)

Definition: It is computationally infeasible to find any two distinct inputs $x_1 \neq x_2$ such that $\text{Poseidon}(x_1) = \text{Poseidon}(x_2)$.

Security Level: $2^{64}$ operations (due to the birthday paradox)

The Birthday Paradox:

For a hash function with $n$-bit security, the expected number of evaluations needed to find a collision is approximately $2^{n/2}$ due to the birthday paradox.

For Poseidon configured with 128-bit security, the collision resistance is 64 bits:

$$2^{64}$$

Why the Birthday Paradox Applies:

When evaluating the hash function $q$ times, we obtain $q$ outputs. The probability of at least one collision among these $q$ outputs follows the birthday paradox formula.

When $q \approx 2^{64}$, the collision probability becomes significant (approximately 0.5), which is the square root of the security level $2^{128}$.

Formal Statement: For any PPT adversary $\mathcal{A}$ making $q$ queries, the probability of finding a collision is bounded by the birthday paradox: approximately $q^2 / 2^{129}$ (plus negligible terms from the underlying permutation security).

Practical Bound:

$$2^{64} \approx 1.8 \times 10^{19} \text{ operations}$$

Note on Field Size vs Security Level: While the BN254 field is 254 bits, the security level of Poseidon is determined by the number of rounds and resistance to algebraic attacks, not the field size alone. The configuration targets 128-bit security, resulting in 64-bit collision resistance due to the birthday bound.

---

Practical Security Analysis

Computational Feasibility

Current Computational Capability:

• The most powerful supercomputers can perform approximately $2^{68}$ operations per year
• Bitcoin network hash rate: approximately $2^{92}$ SHA-256 hashes per year

Security Margins:

Important Note on Collision Resistance:

At $2^{64}$ operations, collision attacks are theoretically within the realm of possibility with:

• Large-scale distributed computing efforts
• Nation-state level resources
• Future quantum computers

However, for our protocol's use case:

1. ITK Isolation: Each ITK uses a unique secret (MVK) and timestamp, making generic collision attacks irrelevant
2. Domain Separation: Different domains prevent cross-context collisions
3. Limited Attack Surface: An adversary would need to find collisions for specific secret keys they don't possess
4. Practical Infeasibility: The cost-benefit analysis makes such attacks economically infeasible

Even with exponential growth in computational power (Moore's Law):

• Collision attacks: Already within theoretical reach, but irrelevant to protocol security
• Pre-image attacks: ~90 years at current doubling rate (18 months)

Storage Requirements for Collision Attacks

To mount a collision attack using the birthday paradox with probability $p = 0.5$:

Number of hash values to store: Approximately $2^{64}$ (square root of the security level)

Storage per hash value: 32 bytes (256 bits)

Total storage required:

$$2^{64} \times 32 \text{ bytes} = 2^{69} \text{ bytes} \approx 590 \text{ exabytes}$$

For comparison:

• Total global data storage (2023): approximately $10^{21}$ bytes (1000 exabytes)
• Storage required: ~590 exabytes (59% of global storage)

While this is technically feasible for a well-resourced adversary, such attacks are:

1. Economically infeasible for the value protected by individual transactions
2. Protocol-irrelevant due to keyed operation with secret MVKs
3. Domain-separated preventing cross-context exploitation

---

Formal Security Guarantees

Theorem: PRF Security of Poseidon

Statement: Under the algebraic group model and the assumption that the Poseidon permutation is a pseudorandom permutation (PRP), Poseidon is a secure pseudorandom function.

Security Bound: For any PPT adversary $\mathcal{A}$ making at most $q$ queries, the PRF advantage is bounded by:

1. The birthday bound (approximately $q^2 / 2^{129}$ for 128-bit security)
2. The security of the underlying Poseidon permutation as a PRP

For $q \ll 2^{64}$ and the secure permutation design, the overall advantage is negligible.

---

Conclusion

The circom Poseidon implementation over BN254 with S-box $x^5$ provides the following security levels:

Security Guarantees:

• 128-bit security against pre-image attacks
• 64-bit security against generic collision attacks (birthday bound)
• Effective 128-bit security in PRF mode with secret keys (protocol use case)

Protocol-Specific Considerations:

The 64-bit collision resistance is sufficient for our protocol because:

1. Keyed PRF Operation: Collisions require knowledge of secret MVK
2. Domain Separation: Different contexts use different domains
3. Unique Per-Transaction: Each ITK uses unique timestamp
4. Limited Attack Value: Breaking one ITK doesn't compromise others
5. Economic Infeasibility: Cost of attack exceeds value of targets

These security levels make Poseidon suitable as the cryptographic foundation for our protocol's key derivation and encryption schemes.