Poseidon Cipher: Symmetric Encryption

Building on the PRF security of Poseidon, we construct a symmetric encryption scheme that operates natively over the BN254 scalar field. This cipher is specifically designed for encrypting field elements in zero-knowledge circuits while maintaining provable semantic security.

---

Cipher Construction

Basic Primitive

The Poseidon cipher transforms the Poseidon PRF into a stream cipher using a counter-mode construction. For a given one-time key $k$ and counter $i$, both elements of $\mathbb{F}_p$ (BN254 scalar field), we define the keystream generator:

$$\mathrm{KeyStream}(k, i) = \mathrm{Poseidon}(k, i)$$

Encryption Algorithm

Input:

• One-time key: $k \in \mathbb{F}_p$ (must be fresh and unique for this encryption)
• Plaintext: A sequence of $\ell$ field elements where $\mathbf{m} = (m_0, m_1, \ldots)$ and each $m_i \in \mathbb{F}_p$

Process:

For each plaintext field element $m_i$ at position $i$ (where $i$ ranges from $0$ to $\ell - 1$):

1. Compute the keystream element:

   $$s_i = \mathrm{Poseidon}(k, i)$$

2. Compute the ciphertext element via additive blinding (one-time-pad style):

   $$c_i = m_i + s_i \pmod{p}$$

Output:

The ciphertext: $(c_0, c_1, \ldots)$

The key $k$ must be securely communicated to the recipient through a separate channel (e.g., Diffie-Hellman key exchange, key encapsulation mechanism).

Decryption Algorithm

Input:

• One-time key: $k \in \mathbb{F}_p$ (the same key used for encryption)
• Ciphertext: $(c_0, c_1, \ldots)$ where each $c_i$ is an encrypted field element

Process:

For each ciphertext element $c_i$ at position $i$:

1. Regenerate the keystream element:

   $$s_i = \mathrm{Poseidon}(k, i)$$

2. Recover the plaintext element:

   $$m_i = c_i - s_i \pmod{p}$$

Output:

The decrypted plaintext: $(m_0, m_1, \ldots)$

---

Critical Security Requirement: One-Time Key Usage

Why Key Reuse Breaks Security

If the same key $k$ is used to encrypt two different plaintexts $\mathbf{m}$ and $\mathbf{m}'$, an adversary can compute:

$$c_i - c'_i = (m_i + s_i) - (m'_i + s_i) = m_i - m'_i$$

This directly leaks the additive difference of the plaintexts, completely breaking confidentiality. The attacker learns the relationship between the two messages without needing to know the key.

Consequences of Key Reuse

How to Ensure One-Time Usage

The one-time key requirement is satisfied by deriving fresh keys for each encryption using:

1. Diffie-Hellman Key Exchange: Derive a unique shared secret per transaction
2. Key Derivation Function (KDF): Derive encryption keys from a master secret with unique context
3. Ephemeral Key Generation: Generate a fresh random key for each encryption, encrypt it to the recipient's public key

Example: ECDH-based Key Derivation

For each encryption to recipient with public key $P_{\text{recipient}}$:

1. Generate ephemeral keypair $(sk_e, pk_e)$
2. Compute shared secret: $\mathrm{shared} = sk_e \cdot P_{\text{recipient}}$
3. Derive one-time key: $k = \mathrm{Hash}(\mathrm{shared})$
4. Encrypt message with $k$
5. Transmit $(pk_e, c_0, c_1, \ldots)$

The recipient reconstructs $k$ using their private key and the ephemeral public key.

---

Formal Security Model

Security Definition: IND-CPA Security

A symmetric encryption scheme is IND-CPA (Indistinguishability under Chosen Plaintext Attack) secure if no probabilistic polynomial-time adversary can distinguish between encryptions of two chosen plaintexts.

Experiment: IND-CPA game with adversary $\mathcal{A}$ and challenge bit $b$

1. Setup: Generate fresh one-time key $k \leftarrow \mathbb{F}_p$
2. Challenge:
   • Adversary $\mathcal{A}$ submits two equal-length plaintexts: $\mathbf{m}^0$ and $\mathbf{m}^1$
   • Challenger encrypts $\mathbf{m}^b$ with the fresh key $k$ and returns ciphertext $(c_0, c_1, \ldots)$
3. Output: Adversary outputs guess $b'$ from $\{0, 1\}$

Definition: The encryption scheme is IND-CPA secure if for all PPT adversaries $\mathcal{A}$, the advantage is negligible:

$$\left| \Pr[b' = 1 | b = 0] - \Pr[b' = 1 | b = 1] \right| \leq \mathrm{negl}(\lambda)$$

where $\lambda$ is the security parameter (128 bits for our instantiation).

---

Security Proof

Theorem: IND-CPA Security of Poseidon Cipher

Statement: The Poseidon cipher construction is IND-CPA secure under the assumption that Poseidon is a secure PRF and each key is used exactly once.

Proof:

We prove security via a sequence of game hops, showing that no PPT adversary can distinguish the Poseidon cipher from an ideal one-time-pad construction.

Game 0 (Real World): The adversary interacts with the real Poseidon cipher using a fresh one-time key $k$.

Game 1 (PRF Replacement): Replace the PRF $\mathrm{Poseidon}_k(i)$ with a truly random function $R(i)$ for all queries.

Claim: Games 0 and 1 are computationally indistinguishable under the PRF security of Poseidon.

Justification:

Suppose there exists an adversary $\mathcal{A}$ that distinguishes Game 0 from Game 1 with non-negligible advantage $\epsilon$. We construct a PRF distinguisher $\mathcal{D}$ that breaks the PRF security of Poseidon.

$\mathcal{D}$ receives oracle access to either $\mathrm{Poseidon}_k(\cdot)$ or a random function $R(\cdot)$:

1. When $\mathcal{A}$ requests encryption of plaintext $\mathbf{m} = (m_0, m_1, \ldots)$:

   • For each position $i$ in the plaintext:
     • Query oracle on $i$ to get $s_i$
     • Compute $c_i = m_i + s_i$
   • Return $(c_0, c_1, \ldots)$ to $\mathcal{A}$

2. $\mathcal{D}$ outputs whatever $\mathcal{A}$ outputs

If the oracle is $\mathrm{Poseidon}_k$, then $\mathcal{D}$ perfectly simulates Game 0. If the oracle is $R$, then $\mathcal{D}$ perfectly simulates Game 1.

Therefore, the probability difference between the two games is bounded by the PRF advantage of Poseidon. By the PRF security of Poseidon, this advantage is negligible.

Game 1 Analysis (Information-Theoretic Security):

In Game 1, the keystream elements $s_i = R(i)$ are uniformly random and independent field elements.

For the challenge ciphertext:

$$c_i = m^b_i + R(i)$$

Since $R(i)$ is uniformly random in $\mathbb{F}_p$ and independent of the plaintext, each $c_i$ is uniformly distributed over $\mathbb{F}_p$ regardless of which plaintext $\mathbf{m}^b$ was encrypted.

Information-Theoretic Argument:

The ciphertext reveals no information about which plaintext was encrypted. For any ciphertext $\mathbf{c}$:

$$\Pr[\mathbf{c} | \mathbf{m}^0] = \Pr[\mathbf{c} | \mathbf{m}^1]$$

This holds because there exists exactly one keystream sequence that maps $\mathbf{m}^0$ to $\mathbf{c}$, and exactly one keystream sequence that maps $\mathbf{m}^1$ to $\mathbf{c}$, and both occur with equal probability.

Therefore, in Game 1:

$$\Pr[b' = 1 | b = 0] = \Pr[b' = 1 | b = 1] = \frac{1}{2}$$

and the adversary's advantage is exactly 0.

Conclusion:

Combining the game hops, the IND-CPA advantage of any adversary against the Poseidon cipher is bounded by the PRF advantage of Poseidon, which is negligible. Therefore, the Poseidon cipher is IND-CPA secure when keys are used exactly once. ∎

---

Security Properties Summary

Confidentiality

Guarantee: Under the PRF assumption for Poseidon and with strict one-time key usage, the cipher provides semantic security:

• Ciphertexts leak no information about plaintexts
• Computationally indistinguishable from random field elements
• Security level: 128 bits (matching Poseidon PRF security)

Integrity

Important: This cipher provides no integrity protection. An adversary can:

• Flip arbitrary bits in ciphertexts (resulting in predictable plaintext changes)
• Reorder ciphertext blocks
• Replay old ciphertexts

Recommended: For applications requiring integrity, use an authenticated encryption construction (e.g., encrypt-then-MAC with Poseidon-based MAC).

Malleability

The cipher is additively malleable: given ciphertext $c_i = m_i + s_i$, an adversary can produce a valid encryption of $m_i + \delta$ by computing $c'_i = c_i + \delta$.

This property can be:

• A vulnerability in applications requiring non-malleability
• A feature in zero-knowledge applications requiring homomorphic properties

---

Performance Characteristics

Computational Cost

For encrypting $\ell$ field elements:

• Poseidon evaluations: $\ell$ (one per counter value)
• Field additions: $\ell$ (one per plaintext element)
• Constraint cost (in ZK circuits): Dominated by Poseidon constraints

For width-2 Poseidon (one input), typical constraint count is ~150-200 R1CS constraints per hash.

Comparison to Alternatives

The Poseidon cipher is ~100× more efficient than traditional ciphers in ZK circuits due to its algebraic design.

---

Practical Usage Guidelines

Key Generation

• Method: Sample $k$ uniformly from $\mathbb{F}_p$ using a cryptographically secure random number generator
• Uniqueness: Each key must be freshly generated or derived for each encryption
• Derivation: When using key derivation, ensure unique context/salt per encryption

Key Distribution

Since each key is one-time use, the key must be securely communicated alongside or before the ciphertext:

Error Handling

• Decryption always succeeds: Since there's no authentication, decryption with wrong key produces random-looking plaintext
• Applications must verify semantic correctness: Use application-layer checks (e.g., check that decrypted values are in expected range)

---

Formal Security Parameters

---

Conclusion

The Poseidon cipher instantiation provides provably secure symmetric encryption for field elements under the PRF assumption of Poseidon. The critical requirement is that each key must be used exactly once - this is a fundamental security property, not merely a best practice. When this requirement is satisfied, the cipher achieves 128-bit semantic security. Its native field arithmetic makes it ideal for use in zero-knowledge proof systems, offering computational efficiency far exceeding traditional ciphers.