The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

7 Key agreement

This section constructs Diffie–Hellman key agreement between two parties that share no prior secret and develops it into the hybrid public-key encryption by which shielded notes are delivered. It proves that the passive security of Diffie–Hellman equals the DDH advantage exactly (Theorem 7.11), that no hardness assumption on the group prevents a man-in-the-middle attack on the unauthenticated protocol (Proposition 7.14), that hybrid encryption is passively secure under CDH, with the key-derivation function modelled as a random oracle and the AEAD secure (Theorem 7.24), and that ElGamal encryption is key-private under DDH (Theorem 7.28), a property that carries over to note encryption (Remark 7.29) and hides the recipient of a ciphertext published permanently on the ledger.

7.1 The Diffie–Hellman protocol

The protocol rests on the asymmetry of Section 2. In a cyclic group G=⟨g⟩ of order q, the map

expg:ℤ/q⁢ℤ→G,x↦gx,

is a group isomorphism evaluated in O(logq) group operations by repeated squaring but believed infeasible to invert in the groups this volume uses; inverting it is the discrete logarithm problem (Definition 2.2). The section depends only on the group structure and the hardness of problems in it, not on the presentation of the group; the reference instances are a large prime-order subgroup of 𝔽p× and the elliptic-curve point groups of §7.6. Diffie and Hellman observed that this asymmetry suffices for two parties with no prior shared secret to establish one over a public channel.

Construction 7.1 (Diffie–Hellman key exchange).

Fix public parameters (G,g,q) with G=⟨g⟩ of order q, known to all parties (and to the adversary).

  1. 1.

    Alice samples a←$ℤ/qℤ uniformly, computes A=ga, and sends A to Bob.

  2. 2.

    Bob samples b←$ℤ/qℤ uniformly, computes B=gb, and sends B to Alice.

  3. 3.

    Alice computes kA=Ba; Bob computes kB=Ab.

The value kA=kB is the shared secret; the transmitted elements A and B are the public shares (public keys), and the exponents a and b are the private keys, never sent.

Proposition 7.2 (Correctness of Diffie–Hellman).

In Construction 7.1 both parties compute the same group element, kA=kB=ga⁢b.

Proof.

Unwinding the definitions,

kA=Ba=(gb)a=gb⁢a=ga⁢b=(ga)b=Ab=kB,

where ba=ab because integer multiplication is commutative, and exponents may be read modulo q because g has order q. □

The shared secret ga⁢b is a function of the transcript (A,B), computable by anyone who knows one of the two private keys and, conjecturally, by no one who knows only the public shares; §7.4 makes the conjecture precise.

Remark 7.3 (Small subgroups and the prime-order rule).

If G has small subgroups, an adversary who substitutes an element of small order for a public share confines the victim’s computed secret to a small subgroup and learns the victim’s exponent modulo a small factor of q—the Pohlig–Hellman leakage of Corollary 2.21 in protocol form. The remedy is the standing rule of Section 2: prefer G of prime order q. Then the only subgroups are {1} and G itself, every non-identity element is a generator, and no nontrivial confinement is possible. When the ambient group does not have prime order—𝔽p× has composite order p−1—one works inside a prime-order subgroup and has each recipient validate incoming elements as members: check Bq=1 and B≠1 before exponentiating. The elliptic-curve analogue of this validation appears in Remark 7.19.

7.2 Static and ephemeral keys

Construction 7.1 leaves the lifetime of a key pair unspecified, and the properties of the protocol depend on it.

Definition 7.4 (Static and ephemeral keys).

A Diffie–Hellman key pair (x,gx) is static (long-term) if it is generated once and reused across many sessions, typically published and bound to an identity; it is ephemeral if it is generated freshly for a single session and discarded immediately afterwards.

Three protocol shapes result; all three are used below.

  • •

    Ephemeral–ephemeral (DHE). Both parties use fresh keys. Once a and b are erased, no one—the parties included—can recover ga⁢b: this is forward secrecy, the guarantee that a later compromise of all stored long-term state cannot decrypt recorded past sessions, because the only secrets that ever existed were the deleted ephemerals.

  • •

    Static–ephemeral. The recipient Bob holds a static pair (b,B=gb), with B known in advance; Alice contributes a fresh ephemeral (a,A). The shared secret ga⁢b then requires no interaction from Bob at agreement time: Alice computes ga⁢b=Ba from the published B, attaches A, and sends everything in a single flow; Bob recovers ga⁢b=Ab whenever he next comes online. This is the shape of hybrid encryption (§7.7) and of shielded-note delivery (§7.9): sender online once, recipient possibly offline, no round trip.

  • •

    Static–static. Both keys are long-term, so ga⁢b is a fixed function of the two identities—the same in every session. There is no forward secrecy, and the fixed secret must be combined with fresh per-session randomness (a nonce) before it may key any symmetric scheme; using it directly would reuse one key across all time.

In the static–ephemeral shape a static public key B=gb functions as an encryption public key: anyone can derive a secret shared with its owner by sending a single ephemeral share.

7.3 The key-agreement scheme abstraction

We package the non-interactive (static–ephemeral) pattern as a scheme with named algorithms, so that later constructions, including deployed note encryption, invoke key agreement independently of the underlying group.

Definition 7.5 (Key-agreement scheme).

A (non-interactive) key-agreement scheme over a public parameter set 𝗉𝗉 consists of a private-key space 𝒮, a public-key space 𝒫, a shared-secret space 𝒦, and three algorithms:

  • •

    KeyGen(𝗉𝗉)→s, randomised, outputting a private key s∈𝒮;

  • •

    DerivePublic(𝗉𝗉,s)→p, deterministic, mapping a private key to its public key p∈𝒫;

  • •

    Agree(𝗉𝗉,s,p′)→k, deterministic, mapping one’s own private key and a counterparty’s public key to a shared secret k∈𝒦.

Correctness demands that for all 𝗉𝗉 and all s,t in the support of KeyGen(𝗉𝗉),

Agree⁢(𝗉𝗉,s,DerivePublic⁢(𝗉𝗉,t))=Agree⁢(𝗉𝗉,t,DerivePublic⁢(𝗉𝗉,s)). (1)
Construction 7.6 (Diffie–Hellman as a key-agreement scheme).

Fix 𝗉𝗉=(G,g,q) with G=⟨g⟩ of prime order q. The scheme DHG,g takes 𝒮=ℤ/qℤ (or (ℤ/qℤ)∖{0}, to avoid the degenerate case whose public key is the identity), 𝒫=𝒦=G, and

KeyGen:a←$𝒮,DerivePublic⁢(𝗉𝗉,a)=ga,Agree⁢(𝗉𝗉,a,B)=Ba.

Correctness is exactly Proposition 7.2: Agree(𝗉𝗉,s,gt)=(gt)s=gt⁢s=gs⁢t=(gs)t=Agree(𝗉𝗉,t,gs).

Remark 7.7 (The deployed interface generalises the base point).

Zcash note encryption is specified against this abstraction with one generalisation: the deployed DerivePublic takes the base point as an explicit argument rather than fixing a protocol-wide generator, so that Sapling and Orchard derive keys over per-address diversified bases (protocol specification §“Key Agreement”). Those bases are used in §7.9; the address construction that produces them belongs to a later volume. Because the interface never inspects the underlying group, the same construction has carried over across three groups: Sprout’s Curve25519, Sapling’s Jubjub, and Orchard’s Pallas.

Remark 7.8 (The abstraction boundary, and what falls outside it).

Any concrete scheme satisfying equation (1) can be swapped in without changing the surrounding logic: a prime-field group, an elliptic curve, or a post-quantum non-interactive key agreement such as the CSIDH group action. A key-encapsulation mechanism (KEM), by contrast, cannot satisfy the correctness equation: encapsulation requires the recipient’s public key before it can produce its ciphertext, so no counterparty-independent DerivePublic exists. The static–ephemeral one-flow pattern generalises to any KEM, with the encapsulation ciphertext in the role of the ephemeral public key, but only through a different interface.

7.4 Passive security and the Diffie–Hellman assumptions

A passive adversary, or eavesdropper, reads the channel without altering it; its view of an honest session is the transcript (ga,gb), and §2.2 formalises its task in two ways. The computational problem is to produce the shared secret: writing Advcdh(𝒜) for the success probability of 𝒜 in the CDH game of Definition 2.4,

Advcdh⁢(𝒜)=Pra,b⁡[𝒜⁢(ga,gb)=ga⁢b].

The decisional problem is to distinguish (ga,gb,ga⁢b) from (ga,gb,gc) with advantage Advddh(𝒜) (Definition 2.5). The hierarchy DDH≤CDH≤DLP is proved in §2.3 (Theorems 2.7 and 2.8), together with the pairing-based separation of DDH from CDH (Example 2.9).

Remark 7.9 (A concrete DDH break: the Legendre symbol).

Take G=𝔽p×, the full multiplicative group, with generator g. The Legendre symbol (hp) is efficiently computable by Euler’s criterion h(p−1)/2modp and is multiplicative (Math Guide, §“Quadratic residues and the Euler criterion”). A generator of 𝔽p× is a nonsquare, so (gap)=(−1)a: the symbol of a public share reveals the parity of its exponent. The parities of a and b determine the parity of ab, hence (ga⁢bp)=(−1)a⁢b is determined by the two observed symbols. The distinguisher computes the predicted symbol of the shared secret from (ga,gb), compares it with the symbol of the third component, and outputs “Diffie–Hellman” on a match. On a genuine triple the match is certain; on a random triple the third component’s symbol is an independent uniform sign, matching with probability 1/2. The distinguishing advantage is the constant 1/2—even though CDH in 𝔽p× is believed hard. The CDH/DDH gap therefore does not depend on pairings; it already occurs in the multiplicative group of a prime field. The remedy is the prime-order rule of Remark 7.3: in a subgroup of odd prime order q, every element h is a square (h=(h(q+1)/2)2), the symbol is identically +1, and it carries no information. This is one of the two reasons—the other being Pohlig–Hellman—that DDH is only ever assumed in prime-order groups.

Definition 7.10 (Passive security of a key-agreement scheme).

For a key-agreement scheme Σ over 𝗉𝗉 and an adversary 𝒜, the game 𝖪𝖠-𝖨𝖭𝖣Σ𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s,t←KeyGen(𝗉𝗉) independently and computes the transcript

    (DerivePublic⁢(𝗉𝗉,s),DerivePublic⁢(𝗉𝗉,t)).
  2. 2.

    It sets k0=Agree(𝗉𝗉,s,DerivePublic(𝗉𝗉,t)), samples k1←$𝒦 uniformly, draws a hidden bit β←${0,1}, and sends the transcript together with kβ.

  3. 3.

    The adversary outputs a bit β′.

The advantage is AdvΣka⁢-⁢ind(𝒜)=|Pr[β′=1∣β=0]−Pr[β′=1∣β=1]|; the scheme is passively secure if every PPT adversary’s advantage is negligible in λ.

Theorem 7.11 (Passive security of Diffie–Hellman).

For the scheme DHG,g of Construction 7.6 with KeyGen uniform on ℤ/qℤ, every adversary 𝒜 satisfies

AdvDHG,gka⁢-⁢ind⁢(𝒜)=Advddh⁢(𝒜),

identically and with running time preserved exactly. Under the DDH assumption the shared secret of an honest ephemeral–ephemeral session is therefore pseudorandom given the transcript: a passive adversary learns nothing about it that it could not have guessed about a random group element.

Proof.

The two games are the same game. In 𝖪𝖠-𝖨𝖭𝖣 for DHG,g, the transcript is (ga,gb) with a,b uniform and independent; the real key is k0=ga⁢b; and the uniform alternative k1←$G is exactly gc for uniform independent c, because expg is a bijection. The challenge (ga,gb,kβ) is thus verbatim a sample of 𝒟dh or 𝒟rand according to β—the DDH distinguishing game of Definition 2.5. The identity map converts each adversary into the other, so the advantages coincide and no running time is added. □

Remark 7.12 (Why pseudorandomness, not mere unpredictability).

Every use of a Diffie–Hellman secret in this volume feeds it into a key-derivation function to produce a symmetric key. Hardness of CDH guarantees that the secret is hard to produce in full, not that it lacks efficiently predictable structure such as the Legendre leak of Remark 7.9. Hardness of DDH guarantees that the secret is indistinguishable from a random group element (Theorem 7.11): no predicate of it is efficiently computable from the transcript. In practice one often assumes only CDH and models the hash-based KDF as a random oracle: the derived key is then uniform unless the adversary queries the oracle at the hidden shared secret (Theorem 7.24). Either way the goal is a derived symmetric key indistinguishable from uniform, the hypothesis every theorem of Section 6 consumes.

7.5 Active attacks and the role of authentication

Passive security is the strongest guarantee the bare protocol offers; the following attack by an adversary who controls the channel shows that it does not suffice for a secure channel.

Definition 7.13 (Man-in-the-middle attack on unauthenticated Diffie–Hellman).

An active adversary ℳ controlling the channel between Alice and Bob runs two independent Diffie–Hellman sessions, one with each victim. It samples m←$ℤ/qℤ and computes gm. When Alice sends A=ga intended for Bob, ℳ intercepts it and forwards gm to Bob in its place; when Bob replies B=gb, the adversary intercepts it and forwards gm to Alice. Alice computes kA=(gm)a=ga⁢m, which ℳ also computes as Am; symmetrically Bob computes kB=(gm)b=gb⁢m, which ℳ computes as Bm.

Figure 10 draws the two sessions.

Refer to caption
Figure 10: The attack of Definition 7.13. The adversary ℳ (black) intercepts the messages of Alice and Bob and substitutes gm in each direction, so that two independent Diffie–Hellman sessions run: one between Alice and ℳ (blue), with key kA=ga⁢m, and one between ℳ and Bob (green), with key kB=gb⁢m. The adversary computes both keys from its own m and the received A and B; each victim’s view is an honest run of the protocol.
Proposition 7.14 (The attack defeats unauthenticated Diffie–Hellman).

After the attack of Definition 7.13, Alice and Bob each hold a secret they believe is shared with the other but is shared instead with ℳ; and ℳ, knowing both ga⁢m and gb⁢m, can decrypt, read, modify, and re-encrypt every subsequent message in each direction, transparently to both parties. No assumption on G—not even ideal hardness of the discrete logarithm problem—prevents this.

Proof.

Correctness of Diffie–Hellman (Proposition 7.2), applied once per session, gives agreement between Alice and ℳ on ga⁢m and between Bob and ℳ on gb⁢m. The adversary knows its own exponent m and received both A and B, so it computes both secrets directly—no problem instance is ever inverted, which is why no hardness assumption is relevant. Neither victim verifies the origin of the group element they received; each transcript is a syntactically valid run of Construction 7.1, so nothing in either party’s view distinguishes the attacked execution from an honest one. With kA and kB in hand, ℳ decrypts traffic from Alice under kA, re-encrypts it under kB for Bob, and symmetrically in reverse, modifying it arbitrarily in between. □

Passive security concerns the secrecy of the shared secret; active security additionally requires the authenticity of the public shares, since confidentiality gives no protection on a channel established with the wrong party. The bare protocol (Construction 7.1) provides no authentication—nothing in ga or gb identifies its sender—so the remedy must bind each public share to its sender’s identity, letting the recipient reject a substituted share.

Remark 7.15 (Three mechanisms supply authentication).

Deployed remedies fall into three families, each external to the bare exchange.

  1. 1.

    Signed Diffie–Hellman. Each party signs its ephemeral share with a long-term signing key whose verification key is certified—by a certificate authority (a third party whose signature on the key the parties already trust) or by trust-on-first-use (accepting the first key seen and rejecting later changes). The adversary of Proposition 7.14 cannot forge Alice’s signature on gm, so the substitution is rejected. Digital signatures are the subject of Section 8; this composition is the structure of authenticated TLS.

  2. 2.

    Static keys that are themselves authenticated. If Bob’s static public key B=gb reaches Alice authentically—a trusted directory, a pinned key—then a static–ephemeral exchange towards B already authenticates Bob to Alice: only the holder of b can complete it. This authenticates the recipient, not the sender. It is the model relevant to public-key encryption, and to shielded-note delivery, where the recipient’s address is an authenticated public key (§7.9).

  3. 3.

    Out-of-band verification. The parties compare a short fingerprint of the exchanged public keys over a channel that is authentic even if low-bandwidth—digits read aloud on a call, a QR code scanned in person.

In every case the key-agreement goal remains the passive guarantee of Theorem 7.11; authentication is a separate layer composed around the exchange, not a property of the group operation.

7.6 Elliptic-curve Diffie–Hellman

This subsection instantiates the preceding constructions on the elliptic-curve groups of the deployed protocol. Recall from the Math Guide (§“Elliptic curves”) that an elliptic curve E over a field F of characteristic neither 2 nor 3 is given in short Weierstrass form y2=x3+ax+b with nonzero discriminant, and that its F-rational points E(F) form a finite abelian group under chord-and-tangent addition with the point at infinity 𝒪 as identity (Math Guide, §“The group structure of E(𝔽p)”). The group is written additively, so exponentiation g↦gx becomes scalar multiplication P↦[x]P, computable in O(logx) point additions by double-and-add.

Construction 7.16 (ECDH).

Fix an elliptic curve E/F, a base point P∈E(F) of large prime order q generating G=⟨P⟩, and cofactor h=|E(F)|/q. In the abstraction of Definition 7.5:

KeyGen:a←$ℤ/q⁢ℤ,DerivePublic⁢(a)=[a]⁢P,Agree⁢(a,Q)=[a]⁢Q.

The shared secret of parties with private keys a and b is [a]([b]P)=[ab]P=[b]([a]P). The associated hard problems are the discrete-logarithm, CDH, and DDH definitions of Section 2 (Definitions 2.2, 2.4, and 2.5) read with [x]P in place of gx—the problems ECDLP (Math Guide, §“The elliptic-curve discrete logarithm problem”), ECCDH, and ECDDH of §2.6.

Proposition 7.17 (Correctness of ECDH).

The scheme of Construction 7.16 satisfies the key-agreement correctness condition (1).

Proof.

Scalar multiplication is cyclic-group exponentiation in additive notation: the group is abelian, and ℤ acts on ⟨P⟩ through ℤ/qℤ because [q]P=𝒪, so [x]([y]P)=[xy]P for all integers x,y. Hence Agree(a,[b]P)=[ab]P=[ba]P=Agree(b,[a]P), which is condition (1). □

Remark 7.18 (Why elliptic curves).

Well-chosen elliptic-curve groups admit only the generic O(q) attacks of §2.4, whereas index calculus solves the discrete logarithm in 𝔽p× in subexponential time (Remark 2.18); a 256-bit curve therefore delivers the security level that a multi-thousand-bit prime field requires (Example 2.17). That efficiency, together with the availability of curves engineered for cheap in-circuit arithmetic, is why the Pallas curve of §2.6 underlies Orchard.

Remark 7.19 (Subgroup and curve validation).

A recipient computing [a]Q on an attacker-supplied point Q must guard against two attacks, the elliptic-curve forms of the validation duty in Remark 7.3.

  1. 1.

    Invalid-curve attack. The received coordinates may satisfy not E’s equation but that of a different, weaker curve which shares the same addition formulas (the chord and tangent slopes of the Math Guide, §“Explicit affine formulas”, involve a but never b); scalar multiplication then proceeds without error in the wrong group, whose order may be smooth. The implementation must check the curve equation on every incoming point.

  2. 2.

    Small-subgroup attack. When the cofactor h>1, an adversary submits a point Q of small order dividing h, confining [a]Q to a tiny subgroup and learning a modulo a small factor. The defences are cofactor clearing—multiply incoming points by h—or choosing a curve with h=1.

Prime-order curves such as Pallas have h=1, hence no small subgroup, and only the on-curve check remains. The deployed arithmetic enforces that check at deserialisation (Proposition 2.27): the compressed encoding cannot represent a point off the curve.

7.7 Hybrid public-key encryption

Hybrid public-key encryption (HPKE) composes three parts: key agreement in the static–ephemeral flow of §7.2, so that the recipient need not be online; a key-derivation function, which turns the shared secret, a structured group element rather than a uniform string of key bits, into a symmetric key; and an authenticated cipher, which transports the message. The two symmetric ingredients are those of Section 6, recalled below in the shape the composition needs.

Definition 7.20 (KDF, recalled and specialised).

In this section a key-derivation function is a deterministic function

KDF:𝒦×{0,1}∗→{0,1}ℓ,

mapping input keying material k∈𝒦 together with a context string to an ℓ-bit key. This specialises Definition 6.24 (§6.6) by omitting the salt and fixing the output length ℓ. For Theorem 7.24 we model the function as a random oracle (§3.4): distinct inputs then have independent uniform outputs, and security follows provided the adversary never queries the oracle at the hidden Diffie–Hellman secret and context. This is a source-specific random-oracle guarantee, not a generic claim that a deterministic function extracts uniform bits from every high-min-entropy source.

Definition 7.21 (AEAD, recalled).

An authenticated encryption scheme with associated data with key space {0,1}ℓ—matching the KDF output—is a pair (Enc,Dec) with EncK(N,𝑎𝑑,m)=c and DecK(N,𝑎𝑑,c)∈{m}∪{⊥}, where N is a nonce, 𝑎𝑑 is associated data authenticated but not encrypted, and ⊥ denotes rejection (Definition 6.13). Correctness: DecK(N,𝑎𝑑,EncK(N,𝑎𝑑,m))=m. Security is authenticated-encryption security (Definition 6.15): encryptions of any two equal-length messages are CPA-indistinguishable (Definition 6.4), and no adversary can produce a fresh ciphertext decrypting to anything but ⊥ (ciphertext integrity, Definition 6.14)— confidentiality and integrity simultaneously.

Construction 7.22 (DH-based hybrid public-key encryption).

Fix ECDH over G=⟨P⟩ of prime order q (Construction 7.16, in the interface of Definition 7.5), a secure KDF, and a secure AEAD as above. The recipient holds a static key pair (b,B=[b]P) with B published. To encrypt a message m to B:

  1. 1.

    sample an ephemeral e←$ℤ/qℤ and set Epk=[e]P;

  2. 2.

    compute the shared secret S=Agree(e,B)=[eb]P;

  3. 3.

    derive the symmetric key K=KDF(S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡), where 𝑐𝑜𝑛𝑡𝑒𝑥𝑡 includes Epk and the protocol’s labels;

  4. 4.

    output (Epk,c) with c=EncK(N,𝑎𝑑,m) for a fixed or derived nonce N—fixed is safe because each K is used once.

To decrypt (Epk,c) with b: compute S′=[b]Epk, derive K′=KDF(S′,𝑐𝑜𝑛𝑡𝑒𝑥𝑡) with Epk read from the ciphertext, and output DecK′(N,𝑎𝑑,c), which is m on an honest ciphertext; on a tampered one, ciphertext integrity makes the output ⊥ except with negligible probability. Anyone holding B can encrypt; only the holder of b can decrypt.

Figure 11 draws both directions of the construction.

Refer to caption
Figure 11: Hybrid public-key encryption, Construction 7.22. The sender (blue lane) samples the ephemeral e, publishes Epk=[e]P, agrees S=[eb]P with the recipient’s static key B, derives K from S and a context containing Epk, and encrypts m under K with nonce N and associated data 𝑎𝑑. The ciphertext (Epk,c) (grey band) is all that crosses the channel. The recipient (green lane) mirrors the sender with its secret b: S′=[b]Epk, then K′, then decryption, which returns m on an honest ciphertext and, except with negligible probability, ⊥ on a tampered one. Red marks the two secret scalars.
Theorem 7.23 (Correctness of hybrid encryption).

For every message m and every honestly generated ciphertext (Epk,c) of Construction 7.22, decryption returns m.

Proof.

Correctness of ECDH (Proposition 7.17) gives S′=[b]([e]P)=[be]P=[eb]P=[e]B=S. The KDF is deterministic and both sides supply the same context—the recipient recovers Epk from the ciphertext itself—so K′=K. Correctness of the AEAD (Definition 7.21) finishes: DecK(N,𝑎𝑑,EncK(N,𝑎𝑑,m))=m. □

Theorem 7.24 (Passive security of hybrid encryption).

Model the KDF as a random oracle (Definition 3.13) and let the AEAD be secure in the sense of Definition 6.15. Consider a passive adversary 𝒜 who sees the public key B and a single challenge ciphertext: it names two equal-length messages m0,m1, receives the encryption of mβ for a hidden uniform bit β, and guesses β, with CPA advantage Advcpa(𝒜) defined as in Definition 6.4. Under CDH in G no PPT adversary has non-negligible advantage; concretely, if 𝒜 makes at most qH random-oracle queries, then

Advcpa⁢(𝒜)≤ 2⁢qH⋅Advcdh⁢(ℬ)+Advae⁢(𝒞),

for explicit reductions ℬ against CDH and 𝒞 against the AEAD’s authenticated-encryption security (of which the proof consumes only the confidentiality half, so Advae(𝒞) is the CPA advantage of Definition 6.4 read against the AEAD), each running in essentially the same time as 𝒜.

Proof.

The proof is a game hop.

Game 0 is the real CPA game: the challenge ciphertext is (Epk,c) with Epk=[e]P, S=[eb]P, K=KDF(S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡), and c=EncK(N,𝑎𝑑,mβ). Say 𝒜 wins a game when its guess β′ equals β.

Game 1 replaces K by an independent uniform ℓ-bit string, leaving everything else unchanged.

The hop. In the random oracle model the two games proceed identically unless the adversary queries the oracle at exactly the point (S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡)=([eb]P,𝑐𝑜𝑛𝑡𝑒𝑥𝑡): until that query, the oracle’s value there is a uniform string it has never seen, which is precisely what Game 1 supplies. Producing S=[eb]P from the view (B,Epk)=([b]P,[e]P) is exactly solving CDH. The reduction ℬ embeds its CDH challenge as (B,Epk) and simulates Game 1 around it: it draws β and a uniform ℓ-bit key K itself, encrypts mβ under K to form the challenge ciphertext, and implements the oracle by lazy sampling—a fresh uniform string for each new query, the stored answer on a repeated one, so that the oracle remains a consistent function. The simulation is a perfect run of Game 1, and the critical query occurs in it with the same probability as in Game 0, the two games being identical until it happens. One obstruction remains: in a pairing-free group ℬ cannot recognise which of the queries carries [eb]P (Example 2.9 shows recognising it is the DDH-test a gap group would supply). So ℬ picks one of the at most qH queries uniformly at random and outputs its first component; whenever the critical query occurs, ℬ’s choice is correct with probability at least 1/qH. Hence

|Pr⁡[𝒜⁢ wins Game ⁢0]−Pr⁡[𝒜⁢ wins Game ⁢1]|≤qH⋅Advcdh⁢(ℬ).

The factor qH is a guessing-type security loss in the tightness taxonomy of Definition 1.22. Assuming gap-CDH—CDH hardness even given a DDH-decision oracle, which would let ℬ test each query—restores tightness; the loose bound is stated because it is the bound plain CDH yields.

Game 1 analysed. In Game 1 the AEAD key is uniform and independent of everything else in the adversary’s view, which is exactly the hypothesis of the AEAD’s confidentiality game. The reduction 𝒞 forwards (m0,m1) to its AEAD challenger, embeds the returned ciphertext as c alongside a self-generated Epk, and relays 𝒜’s guess; the AEAD challenger’s hidden bit plays β, so |Pr[𝒜 wins Game 1]−12|=12Advae(𝒞).

Accounting. The difference-form advantage of Definition 6.4 is twice the bit-guessing advantage |Pr[𝒜 wins]−12| of Definition 1.15, so the triangle inequality across the hop gives

Advcpa⁢(𝒜)≤ 2⁢(qH⋅Advcdh⁢(ℬ)+12⁢Advae⁢(𝒞))= 2⁢qH⋅Advcdh⁢(ℬ)+Advae⁢(𝒞),

the stated bound.

Alternative hypothesis. The random oracle can be replaced, but not by Definition 6.24 alone: that guarantee is stated for a uniform independent salt, which the specialised KDF of Definition 7.20 omits, and the definition denies any generic unsalted guarantee. The replacement needs an explicit hypothesis on the deployed function—the narrower premise Definition 6.24 allows for unsalted use: for a uniform group element S, the output KDF(S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡) is computationally indistinguishable from a uniform ℓ-bit string given the context. Under that hypothesis and DDH in place of CDH, Theorem 7.11 first replaces the shared secret by a uniform group element at cost Advddh, and the stated indistinguishability then replaces K by a uniform string—no oracle and no qH factor, at the price of the stronger decisional assumption on the group and an explicit pseudorandomness assumption on the KDF. □

Remark 7.25 (Necessity of each component).

Omitting any component of Construction 7.22 breaks the composition.

  • •

    Without the KDF, one would key the cipher with the raw group element S. Its bit-representation is non-uniform—curve points do not fill the encoding space—and in non-DDH groups it is partially predictable, the Legendre-symbol leakage of Remark 7.9 being the classical instance. The KDF standardises the format, extracts uniform bits, and, by folding Epk into its context, ties the derived key to this particular ephemeral share.

  • •

    Without AEAD integrity, a passively confidential but malleable cipher would let an active adversary tamper with c undetectably—the stream ciphers of Section 6 are fully XOR-malleable. Ciphertext integrity (Definition 6.14) makes any modification decrypt to ⊥ except with negligible probability, giving the symmetric payload its chosen-ciphertext robustness.

  • •

    Without the ephemeral key—a static–static variant—every message to B would begin from the same shared secret. The fresh per-message ephemeral, with Epk bound into the KDF context, gives each ciphertext separate key material, so nothing relies on nonce uniqueness under a reused key. What it does not supply is forward secrecy against later compromise of the recipient’s static key b: from a recorded Epk, an attacker who learns b recomputes [b]Epk and with it the ciphertext’s key. Erasing e provides only the sender-side guarantee that the key derives from no stored secret of the sender.

7.8 Key privacy

Theorem 7.24 bounds what an eavesdropper learns about the message, not about the recipient: a scheme may hide the message perfectly and still reveal the recipient’s key in every ciphertext, which an observer of the ledger can test against every public key it can enumerate. Key privacy, due to Bellare, Boldyreva, Desai, and Pointcheval, rules this out. We define it for a generic public-key scheme and prove it for ElGamal encryption, the bare static–ephemeral flow with the message folded in, on whose key privacy later volumes rely.

Definition 7.26 (Key privacy under chosen-plaintext attack, IK-CPA).

A public-key encryption scheme Π over 𝗉𝗉 consists of a randomised KeyGen(𝗉𝗉)→(𝗌𝗄,𝗉𝗄), a randomised Enc𝗉𝗄(m)→c, and a deterministic Dec𝗌𝗄(c) with Dec𝗌𝗄(Enc𝗉𝗄(m))=m for every key pair in the support of KeyGen and every message m. For an adversary 𝒜 the game 𝖨𝖪-𝖢𝖯𝖠Π𝒜(λ) runs as follows.

  1. 1.

    The challenger samples (𝗌𝗄0,𝗉𝗄0),(𝗌𝗄1,𝗉𝗄1)←KeyGen(𝗉𝗉) independently and sends (𝗉𝗄0,𝗉𝗄1).

  2. 2.

    The adversary outputs a message m.

  3. 3.

    The challenger draws a hidden bit β←${0,1} and sends c←Enc𝗉𝗄β(m).

  4. 4.

    The adversary outputs a bit β′.

The advantage is AdvΠik⁢-⁢cpa(𝒜)=|Pr[β′=1∣β=0]−Pr[β′=1∣β=1]|; the scheme is key-private (IK-CPA) if every PPT adversary’s advantage is negligible in λ. The message is the adversary’s own, so nothing about it is hidden; what the game hides is the key.

Construction 7.27 (ElGamal encryption).

Fix 𝗉𝗉=(G,P,q) as in Construction 7.16, written additively, and take group elements as messages; write EG for the scheme. A key pair carries its own base H: in the fixed-base variant H=P; in the per-key-base variant KeyGen samples H←$G∖{𝒪}, the generalised interface of Remark 7.7.

  • •

    KeyGen: choose H as above and x←$ℤ/qℤ; output 𝗌𝗄=x and 𝗉𝗄=(H,Y) with Y=[x]H.

  • •

    Enc(H,Y)(M): sample r←$ℤ/qℤ; output (R,C)=([r]H,[r]Y+M).

  • •

    Decx(R,C): output C−[x]R.

Correctness is the scalar identity in the proof of Proposition 7.17, valid for any base in G: [x]R=[x]([r]H)=[r]([x]H)=[r]Y, so C−[x]R=M. The scheme is the static–ephemeral flow of §7.2 with the shared secret [rx]H spent as a one-time pad on a group element; the fixed-base variant is ElGamal’s original scheme transposed from 𝔽p× to a prime-order group.

Theorem 7.28 (ElGamal is key-private under DDH).

For ElGamal over G (Construction 7.27, either base variant), every adversary 𝒜 yields two distinguishers ℬ0,ℬ1 against DDH in G (Definition 2.5, read with [x]P in place of gx as in Construction 7.16), each running in the time of 𝒜 plus one key generation and four scalar multiplications, with

AdvEGik⁢-⁢cpa⁢(𝒜)≤Advddh⁢(ℬ0)+Advddh⁢(ℬ1).

Under the DDH assumption ElGamal is therefore IK-CPA: a ciphertext is computationally independent of the public key it was made for.

Proof.

The proof is a hybrid through a game that uses no key at all. Write 𝖧0 and 𝖧1 for the IK-CPA game with β fixed to 0 and to 1, and p0,p1 for the probability that 𝒜 outputs 1 in each, so that AdvEGik⁢-⁢cpa(𝒜)=|p0−p1|. Let 𝖧∗ be the game whose challenger, after the same key generation and the same message M from 𝒜, answers with (R,C)=(U1,U2+M) for U1,U2←$G independent and uniform, and let p∗ be the corresponding probability. The challenge of 𝖧∗ is computed without reference to either key, and the triangle inequality |p0−p1|≤|p0−p∗|+|p∗−p1| reduces the claim to bounding each hop by a DDH advantage.

The hop 𝖧0→𝖧∗. The distinguisher ℬ0 receives a triple (X,Y,Z)=([a]P,[b]P,[c]P) with c=ab or c uniform. It samples s←$(ℤ/q⁢ℤ)× in the per-key-base variant and sets s=1 in the fixed-base variant, plants the challenge in key 0 as

H0=[s]⁢P,Y0=[s]⁢X=[a]⁢H0,

generates (x1,(H1,Y1)) honestly, and hands 𝒜 the pair ((H0,Y0),(H1,Y1)). For invertible s the base [s]P is uniform on G∖{𝒪}, and Y0=[a]H0 with a uniform is an honest public key whose private key a the distinguisher never learns and does not need, since the game offers no decryption. On receiving M it replies with

(R,C)=([s]⁢Y,[s]⁢Z+M)

and outputs 𝒜’s bit. If c=ab, then R=[sb]P=[b]H0 and [s]Z=[sab]P=[b]([a]H0)=[b]Y0, so (R,C) is an honest encryption under key 0 with ephemeral r=b uniform: the view of 𝒜 is exactly 𝖧0. If c is uniform, then [s]Z=[sc]P is uniform in G and independent of everything else because s is invertible, and R=[b]H0 is uniform in G and independent of everything else because H0 generates G and b is independent of a,c,s, of key 1, and of M, which 𝒜 chose before seeing R: the view is exactly 𝖧∗. Hence |p0−p∗|=Advddh(ℬ0).

The hop 𝖧∗→𝖧1 is the same with the challenge planted in key 1 and key 0 generated honestly, giving ℬ1 with |p∗−p1|=Advddh(ℬ1). Each distinguisher performs one honest key generation and the four scalar multiplications [s]P,[s]X,[s]Y,[s]Z beyond running 𝒜. Summing the two hops gives the bound. □

Remark 7.29 (Key privacy of note encryption and diversified addresses).

The hybrid argument carries over unchanged to Construction 7.22: planting the challenge in the recipient’s key and the ephemeral share exactly as above makes the shared secret S uniform, and once it is, the pair (Epk,c) with c=EncKDF⁢(S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡)(N,𝑎𝑑,m) is computed without reference to the recipient’s key—provided the KDF context names no recipient key, which it must not. The deployed KDF takes (𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍,𝖾𝗉𝗄) (§6.6): the shared secret is the keying material, the context is 𝖾𝗉𝗄 under a personalisation label, and no key of the recipient enters. The protocol specification requires the composed note-encryption scheme to be key-private (§“Key Derivation”), so that a note ciphertext reveals nothing about the address to which it was sent. Key privacy also supplies the group-element part of diversified-address unlinkability. A diversified address (Gd,𝗉𝗄𝖽)=(Gd,[𝗂𝗏𝗄]Gd) (Remark 7.30) is a per-key-base ElGamal public key, and a fresh address of the same 𝗂𝗏𝗄 over a new base Gd′ has, when that base is modelled as a uniform group element, the distribution of an encryption of 𝒪 under that key; telling which of two authorities a third address belongs to is then the IK-CPA game, whose advantage Theorem 7.28 bounds. The protocol specification sets up that correspondence, modelling the group hash behind the base as a random oracle (§“𝖣𝗂𝗏𝖾𝗋𝗌𝗂𝖿𝗒𝖧𝖺𝗌𝗁𝖲𝖺𝗉𝗅𝗂𝗇𝗀 and 𝖣𝗂𝗏𝖾𝗋𝗌𝗂𝖿𝗒𝖧𝖺𝗌𝗁𝖮𝗋𝖼𝗁𝖺𝗋𝖽 Hash Functions”); the resulting unlinkability requirement is stated in a later volume.

7.9 Shielded-note delivery as deployed hybrid encryption

Shielded-note delivery in the deployed protocol is the composition assembled in this section, run in band on the public ledger.

Remark 7.30 (Note delivery is HPKE on the ledger).

A shielded address embeds a static public key 𝗉𝗄𝖽=[𝗂𝗏𝗄]Gd on the protocol’s curve (Pallas, in Orchard), where the private scalar 𝗂𝗏𝗄 is the recipient’s incoming viewing key. The base Gd is not a protocol-wide generator but a per-address diversified base, the hash-to-curve image (§3.7) of the address’s diversifier. The generalised interface of Remark 7.7 accommodates such per-address bases; the key hierarchy and address encoding behind them belong to a later volume. The sender runs Construction 7.22 over that base, with one deployed refinement: the ephemeral scalar 𝖾𝗌𝗄 is not sampled directly but derived by 𝖯𝖱𝖥𝖾𝗑𝗉𝖺𝗇𝖽 (Remark 5.14) from the note’s random seed (ZIP 212), so that the uniform-ephemeral hypothesis of Theorem 7.24 is met through the PRF’s pseudorandomness and the recipient can later re-derive 𝖾𝗌𝗄 from the delivered seed. The sender publishes 𝖾𝗉𝗄=[𝖾𝗌𝗄]Gd in the transaction, derives

K=KDF⁢([𝖾𝗌𝗄⋅𝗂𝗏𝗄]⁢Gd,𝖾𝗉𝗄)

by the personalised BLAKE2b call of §6.6, and AEAD-encrypts the note plaintext—a version byte, the recipient’s diversifier, the value, the note’s random seed, and the memo—under K with ChaCha20-Poly1305 (Construction 6.18), attaching the ciphertext to the transaction (protocol specification §“Encryption (Sapling and Orchard)”). The nonce is fixed to zero and the associated data is empty (§“Symmetric Encryption” there), safe because each K keys exactly one encryption.

Chain scanners see (𝖾𝗉𝗄,c) in every shielded output, but lacking 𝗂𝗏𝗄 they learn nothing (Theorem 7.24). The recipient trial-decrypts: for each incoming transaction it derives K′=KDF([𝗂𝗏𝗄]𝖾𝗉𝗄,𝖾𝗉𝗄) and keeps, as the notes addressed to it, those outputs whose AEAD tag verifies and whose plaintext passes two consistency checks: the note commitment recomputed from it must match the commitment on chain, and the 𝖾𝗌𝗄 re-derived from its random seed must reproduce the published 𝖾𝗉𝗄 (protocol specification §“Decryption using an Incoming Viewing Key (Sapling and Orchard)”). By the static–ephemeral flow of §7.2, delivery is non-interactive: the recipient need never have been online when the note was sent. Authenticity of the static key—the concern of §7.5—is supplied by mechanism (2) of Remark 7.15: the address is part of the recipient’s verified payment credential, so no man-in-the-middle substitution of the key is possible; and, as noted there, this authenticates the recipient rather than the sender. The encryption hides the note’s contents but certifies nothing about them. That the value inside the note commitment is in range and is the value that enters the published value commitment comes from the accompanying zero-knowledge proof, whose statement reads no ciphertext. That the plaintext delivered matches the commitment on chain comes from the recipient’s recomputation above: by the binding of the note commitment, a plaintext that reproduces it is the one the sender committed to.

The signatures that authorise the transaction carrying the note ciphertext are the subject of the next section.