Rescue Cipher: MPC-Friendly Encryption

The Rescue cipher provides symmetric encryption for private inputs sent to Arcium's Multi-Party Computation (MPC) network. Operating over the Curve25519 prime field ($p = 2^{255} - 19$), Rescue is specifically designed for arithmetization-oriented cryptography and MPC-friendly computation.

Arcium Implementation Details: For comprehensive implementation details, see Arcium's Cryptographic Specifications.

---

Cipher Overview

Field Selection

Rescue operates over the finite field $\mathbb{F}_p$ where:

$$p = 2^{255} - 19$$

This prime is the same field used by the x25519 elliptic curve Diffie-Hellman protocol, enabling seamless integration between key exchange and symmetric encryption without field conversions.

Design Rationale

Arithmetization-Oriented: Rescue is designed for efficient evaluation in:

• Multi-Party Computation (MPC) protocols
• Zero-Knowledge proof systems
• Threshold cryptography schemes

MPC-Friendly Properties:

• Low multiplicative depth
• Efficient secret sharing
• Minimal communication overhead in MPC protocols
• Native field arithmetic without bit decomposition

---

Key Derivation

x25519 Key Exchange

Prior to encryption, a x25519 elliptic curve Diffie-Hellman (ECDH) key exchange is performed between the client and the Arcium cluster:

1. Client: Generates ephemeral keypair $(sk_{\mathrm{client}}, pk_{\mathrm{client}})$
2. Cluster: Has public key $pk_{\mathrm{cluster}}$
3. Shared Secret: Client computes: $$s = \mathrm{x25519}(sk_{\mathrm{client}}, pk_{\mathrm{cluster}})$$

The shared secret $s$ is natively an element of $\mathbb{F}_p$ (the Curve25519 field).

Rescue Key Derivation

The encryption key is derived from the shared secret using the Rescue-Prime hash function:

$$k = \mathrm{RescuePrime}(s)$$

Hash Function Specifications:

• Field: $\mathbb{F}_{2^{255}-19}$
• Rate: 7 field elements
• Capacity: 5 field elements
• State Width: $m = 12$ (rate + capacity)
• Output: Truncated to 5 field elements
• Security Level: 256 bits (against collision, pre-image, and second pre-image attacks)

Security Benefit: Hashing the shared secret with Rescue-Prime increases the min-entropy of the derived key, providing defense-in-depth against potential weaknesses in the ECDH output.

---

Rescue Cipher Construction

Cipher Family and Key Schedule

Unlike typical block ciphers where the key directly affects the encryption operation, Rescue uses the key to select a specific cipher instance from the family of all possible Rescue ciphers.

Key Schedule: The derived key $k$ modifies the round constants of the Rescue permutation, effectively instantiating a unique cipher from the Rescue family that is keyed to the specific shared secret.

This approach provides:

1. Key-dependent randomization of the cipher structure
2. Related-key attack resistance through structural variation
3. Domain separation between different key contexts

Block Cipher Parameters

State Configuration:

• State Width: $m = 5$ field elements
• Security Level: 128 bits
• Number of Rounds: 10 (minimum recommended for $m=5$ with 128-bit security)

Rationale for $m=5$: This is the smallest state width that achieves the minimum recommended number of rounds (10) for 128-bit security given the fixed field and security parameters.

Counter Mode (CTR) Operation

Rescue is used in Counter (CTR) mode for stream cipher operation, enabling encryption of arbitrary-length data.

---

Encryption Algorithm

State Structure

For each block, the cipher state is constructed as:

$$\mathrm{State} = [\mathrm{nonce}, i, 0, 0, 0]$$

where:

• $\mathrm{nonce}$: 16 random bytes (converted to field element) provided by the user
• $i$: Counter value (increments for each block)
• $0, 0, 0$: Three zero-padding field elements

State Dimensions: $\mathrm{State} \in \mathbb{F}_p^5$ (5-dimensional vector over $\mathbb{F}_p$)

Encryption Process

Input:

• Symmetric key: $k$ (derived from x25519 ECDH + Rescue-Prime hash)
• Nonce: $\mathrm{nonce}$ (16 random bytes, converted to field element)
• Plaintext: Sequence of field elements $\mathbf{m} = (m_0, m_1, \ldots, m_{\ell-1})$ where each $m_i \in \mathbb{F}_p$

Process:

For each plaintext block at position $i$ (where $i = 0, 1, \ldots, \lceil \ell/5 \rceil - 1$):

1. Construct state:

   $$S_i = [\mathrm{nonce}, i, 0, 0, 0]$$

2. Generate keystream block:

   $$K_i = \mathrm{Rescue}_k(S_i)$$

   where $\mathrm{Rescue}_k$ is the keyed Rescue permutation (with round constants derived from $k$)

3. Extract keystream elements: $K_i = (k_{i,0}, k_{i,1}, k_{i,2}, k_{i,3}, k_{i,4})$

4. Encrypt plaintext elements: For each position $j$ in the block (up to 5 elements):

   $$c_{5i+j} = m_{5i+j} + k_{i,j} \pmod{p}$$

Output:

The ciphertext consists of the nonce and all encrypted field elements: $(\mathrm{nonce}, c_0, c_1, \ldots, c_{\ell-1})$

Decryption Process

Input:

• Symmetric key: $k$ (same key used for encryption)
• Ciphertext: $(\mathrm{nonce}, c_0, c_1, \ldots, c_{\ell-1})$

Process:

For each ciphertext block at position $i$:

1. Reconstruct state:

   $$S_i = [\mathrm{nonce}, i, 0, 0, 0]$$

2. Regenerate keystream block:

   $$K_i = \mathrm{Rescue}_k(S_i)$$

3. Decrypt ciphertext elements: For each position $j$ in the block:

   $$m_{5i+j} = c_{5i+j} - k_{i,j} \pmod{p}$$

Output:

The decrypted plaintext: $(m_0, m_1, \ldots, m_{\ell-1})$

---

Security Analysis

Security Model

The Rescue cipher in CTR mode provides IND-CPA (Indistinguishability under Chosen Plaintext Attack) security under the assumption that:

1. Rescue is a secure PRP (Pseudorandom Permutation) with keyed round constants
2. Nonces are never reused for the same key
3. x25519 ECDH provides secure key exchange (computational Diffie-Hellman assumption)
4. Rescue-Prime hash is a secure PRF for key derivation

Security Levels

Security Proof Sketch

Theorem: Rescue in CTR mode is IND-CPA secure.

Proof Outline:

1. ECDH Security: Under the computational Diffie-Hellman assumption, the shared secret $s$ is indistinguishable from random to any adversary not knowing the private keys.

2. Key Derivation Security: The Rescue-Prime hash acts as a PRF, so the derived key $k = \mathrm{RescuePrime}(s)$ is computationally indistinguishable from a uniformly random key.

3. PRP to PRF Conversion: By the PRP/PRF switching lemma, for $q \ll 2^{m \cdot \log_2 p / 2}$ queries, the Rescue permutation is indistinguishable from a random function.

4. CTR Mode Security: Given a PRF-like keystream generator, CTR mode provides IND-CPA security through a standard reduction (similar to the Poseidon cipher proof).

5. Combined Security: The composition of secure primitives (ECDH + hash + PRP + CTR) maintains security through sequential composition. ∎

Note: For detailed information about Umbra's threat model and MPC security guarantees, see the MPC Threat Model documentation.

---

Critical Security Requirements

Nonce Uniqueness

Requirement: The nonce must be globally unique for each encryption under the same key.

Generation:

• Use 16 cryptographically random bytes
• Convert to field element in $\mathbb{F}_p$
• Never reuse nonces for the same key

Consequences of Reuse:

If the same nonce is used twice with the same key, the keystream blocks will be identical:

$$K_i = \mathrm{Rescue}_k([\mathrm{nonce}, i, 0, 0, 0])$$

This allows an adversary to compute:

$$c_{5i+j} \oplus c'_{5i+j} = m_{5i+j} \oplus m'_{5i+j}$$

leaking the XOR of the two plaintexts, completely breaking confidentiality.

Key Freshness

Ephemeral Keys: Each encryption session should use a fresh x25519 ephemeral keypair to ensure forward secrecy.

Key Rotation: Long-lived cluster keys should be rotated periodically to limit exposure window.

Nonce Security Bound

For random nonce selection from $\mathbb{F}_p$, the birthday bound gives collision probability:

$$\Pr[\text{nonce collision}] \approx \frac{q^2}{2p} \approx \frac{q^2}{2^{256}}$$

For $q < 2^{128}$ encryptions, collision probability remains negligible.

---

Integration with Arcium MPC Network

Client-Side Encryption

Workflow:

1. Key Exchange:

   • Client generates ephemeral x25519 keypair
   • Retrieves Arcium cluster's public key
   • Computes shared secret via ECDH

2. Key Derivation:

   • Hash shared secret with Rescue-Prime
   • Derive 5-element key vector

3. Encryption:

   • Generate 16-byte random nonce
   • Encrypt private inputs using Rescue-CTR
   • Send $(pk_{\mathrm{client}}, \mathrm{nonce}, \mathrm{ciphertext})$ to cluster

MPC-Side Decryption

Threshold Decryption:

The Arcium cluster can use threshold cryptography with the Rescue cipher:

1. Shared Key: The cluster's private key is secret-shared among MPC nodes
2. Collaborative ECDH: Nodes collaboratively compute the shared secret without reconstructing the private key
3. MPC-Friendly Decryption: Rescue's algebraic structure enables efficient threshold decryption in MPC

Advantages:

• No single node has access to decrypted private inputs
• Privacy-preserving computation on encrypted data
• Efficient in MPC protocols due to low multiplicative depth

---

Performance Characteristics

Computational Cost

Per Block Encryption (5 field elements):

• Rescue permutation evaluations: 1
• Field additions: 5 (one per element)
• Round operations: 10 rounds (per block)

MPC Efficiency

Communication Complexity:

• Rescue's algebraic structure minimizes MPC communication rounds
• Low multiplicative depth reduces interaction in threshold protocols
• Native field operations avoid expensive bit decomposition

Comparison: Rescue vs. Traditional Ciphers in MPC

Rescue is ~20-30× more efficient than traditional ciphers in MPC contexts.

---

Implementation Considerations

Field Element Conversion

Byte-to-Field Conversion:

The 16-byte nonce must be converted to a field element in $\mathbb{F}_{2^{255}-19}$:

1. Interpret 16 bytes as little-endian 128-bit integer $n$
2. Reduce modulo $p$: $\mathrm{nonce} = n \bmod (2^{255} - 19)$
3. Ensure canonical representation (fully reduced)

Note: Since $16 \times 8 = 128 < 255$, no reduction is typically needed for random nonces.

State Initialization

Ensure the state is properly padded with zeros. The state array contains the nonce (field element from 16 random bytes), counter (u64 converted to field element), followed by zero-padded field elements.

Error Handling

Decryption with Wrong Key:

• Decryption always succeeds computationally
• Produces random-looking plaintext
• Application layer must verify semantic correctness

---

Security Parameters Summary

---

Formal Security Parameters: Rescue-Prime Hash

The Rescue-Prime hash function used for key derivation provides:

Configuration:

• Field: $\mathbb{F}_{2^{255}-19}$
• State Width: $m = 12$ (rate = 7, capacity = 5)
• Output: 5 field elements (truncated)
• Security Target: 256 bits

Security Guarantees:

According to the Rescue specification (Section 2.2), this configuration offers 256 bits of security against:

• Collision attacks: Finding $x_1 \neq x_2$ where $H(x_1) = H(x_2)$
• Pre-image attacks: Given $y$, finding $x$ where $H(x) = y$
• Second pre-image attacks: Given $x_1$, finding $x_2 \neq x_1$ where $H(x_1) = H(x_2)$

Field Size Requirement: These guarantees hold for any field of size at least 102 bits. Since $2^{255} - 19 > 2^{102}$, the security properties are satisfied.

---

Practical Usage Guidelines

Client Implementation

Encryption Checklist:

1. ✓ Generate fresh x25519 ephemeral keypair for each session
2. ✓ Retrieve valid Arcium cluster public key
3. ✓ Generate 16 cryptographically random bytes for nonce
4. ✓ Never reuse nonces for the same session key
5. ✓ Derive key using Rescue-Prime hash of shared secret
6. ✓ Use proper field arithmetic (modulo $2^{255} - 19$)
7. ✓ Include nonce with ciphertext
8. ✓ Transmit client public key to enable cluster decryption

Cluster Implementation

Decryption Checklist:

1. ✓ Validate client public key is on the curve
2. ✓ Perform threshold ECDH to derive shared secret
3. ✓ Derive key using Rescue-Prime hash
4. ✓ Extract nonce from ciphertext
5. ✓ Decrypt using Rescue-CTR
6. ✓ Validate semantic correctness of decrypted data

Security Best Practices

Do:

• Use secure random number generators for nonces and ephemeral keys
• Implement constant-time field arithmetic to prevent timing attacks
• Validate all inputs (curve points, field elements)
• Use authenticated encryption if integrity is required (add MAC)

Don't:

• Reuse nonces under the same key
• Use static ECDH keys without key rotation
• Trust decrypted data without semantic validation
• Implement custom cryptographic primitives without expert review

---

Conclusion

The Rescue cipher provides efficient, MPC-friendly symmetric encryption for Arcium's confidential computing network. Operating over the Curve25519 field with 128-bit security, Rescue enables:

• Seamless integration with x25519 key exchange
• Efficient MPC evaluation with low communication overhead
• Provable IND-CPA security under standard cryptographic assumptions
• Native field arithmetic without expensive bit operations

This makes Rescue the optimal choice for encrypting private inputs to Multi-Party Computation protocols while maintaining both security and efficiency.

For detailed implementation specifications and test vectors, refer to the Arcium Cryptographic Documentation.