The Zcash ArboretumThe Complete Arboretum PDF

7 Key agreement

Two parties who have never met share no secret, and the adversary of this section intends to keep it that way. She owns the channel between them. As an eavesdropper she records the two group elements they exchange and tries to distinguish the key they derive from a random string—a key she can distinguish is a key whose every later use leaks. As an active attacker she does better than listen: she intercepts each party’s contribution, substitutes her own, and runs one honest-looking session with each victim, so that both “secure channels” terminate at her desk and she reads and rewrites every message in transit—forging, as we shall prove, without violating any hardness assumption at all. And on a public ledger her seat is permanent: every note ciphertext is published for ever, and she may scan them all at leisure, holding each against every address she can enumerate. This section builds the machinery that denies her all three postures: the Diffie–Hellman protocol atop the exponentiation asymmetry of Section 2; the static/ephemeral taxonomy that turns an interactive exchange into a one-shot flow; the key-agreement scheme abstraction that the deployed code programs against; passive security, which we prove equal to the DDH advantage exactly; the man-in-the-middle attack and the three external mechanisms of authentication; the elliptic-curve instantiation with its validation duties; the hybrid composition with a key-derivation function and an AEAD; key privacy, which keeps a ciphertext silent about its recipient; and the deployed endpoint, shielded-note delivery as hybrid public-key encryption carried in band on the ledger.

7.1 The Diffie–Hellman protocol

The raw material is the asymmetry established in Section 2. In a cyclic group G=⟨g⟩ of order q, the map

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

is a group isomorphism—it carries addition of exponents to multiplication of elements—that is cheap to evaluate, at O⁢(log⁡q) group operations by repeated squaring, but believed infeasible to invert in the groups this volume uses: inverting it is precisely the discrete logarithm problem (Definition 2.2). Everything in this section depends only on the group structure and the hardness of certain problems in it, never 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’s observation is that the asymmetry alone already lets two strangers manufacture a shared secret in public.

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 b⁢a=a⁢b because integer multiplication is commutative, and exponents may be read modulo q because g has order q. □

The shared secret ga⁢b is thus a well-defined function of the transcript (A,B): it can be computed by anyone who knows one of the two private keys, and—conjecturally—by no one who knows only the public shares. Making that conjecture precise, and seeing exactly how much it buys, is the business of §7.4. First, a structural precaution.

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

If G has small subgroups, an adversary can exploit them: by substituting for a public share an element of small order she 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 natural 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

Nothing in Construction 7.1 says how long a key pair lives, and the protocol changes character with the answer.

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, and all three matter to what follows.

  • •

    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 exactly 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 never-varying 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.

The static–ephemeral case is the conceptual bridge from key exchange, an interactive protocol, to public-key encryption, a one-shot algorithm. A static public key B=gb functions exactly as an encryption public key: anyone can derive a secret shared with its owner by sending a single ephemeral share. The rest of the section develops that bridge until, by §7.9, it carries deployed traffic.

7.3 The key-agreement scheme abstraction

Deployed code does not manipulate exponents; it programs against an interface. We therefore package the non-interactive (static–ephemeral) pattern as a scheme with named algorithms, so that later constructions—and the deployed note-encryption machinery—can invoke key agreement without caring which group sits underneath.

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).

The Zcash note-encryption machinery programs against precisely 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”; the zcash_note_encryption crate’s Domain trait’s ka_derive_public, ka_agree_enc, and ka_agree_dec operate on abstract associated types, and Orchard’s implementation of derive_public in the orchard crate receives the base gd as a parameter). Those bases are put to work in §7.9, and the address machinery that produces them is detailed in the Ironwood Guide (§“Diversified addresses”). What matters here is that the interface still invokes an abstract key agreement and never inspects the underlying group—which is why the same construction has transported across three groups, from Sprout’s Curve25519 to Sapling’s Jubjub to 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 at all: 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 does generalise to any KEM—the encapsulation ciphertext plays the role of the ephemeral public key—but at the cost of changing the interface the surrounding logic programs against.

7.4 Passive security and the Diffie–Hellman assumptions

The weakest adversary is the eavesdropper: she reads the channel but does not alter it, and her entire view of an honest session is the transcript (ga,gb). Both formalisations of her task were laid down in §2.2. 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 was established in §2.3 (Theorems 2.7 and 2.8), together with the pairing-based separation of DDH from CDH (Example 2.9). The distinction is not pedantry. Hardness of CDH asserts only that the whole secret cannot be computed; keying a symmetric cipher requires that the secret be indistinguishable from a uniform group element, so that no individual bit or predicate of it leaks. The following classical break shows the gap is real in the most familiar group.

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 a⁢b, 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 needs no pairings; the oldest group in the subject exhibits it. The cure 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 the leak vanishes. This is one of the two reasons—the other being Pohlig–Hellman—that DDH is only ever assumed in prime-order groups.

With the assumption in place, passive security is not merely implied by DDH; it is DDH, advantage for advantage. We state the game in the volume’s tradition and prove the identification.

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 she 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. What should the group deliver to that function? Hardness of CDH guarantees the secret is hard to produce in full, but not that it lacks efficiently predictable structure: the Legendre leak of Remark 7.9 is exactly such structure. Hardness of DDH guarantees the secret is as good as 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, a route made precise in Theorem 7.24. Either way the design goal is the same: a derived symmetric key indistinguishable from uniform, because that is the hypothesis every theorem of Section 6 consumes.

7.5 Active attacks and the role of authentication

Passive security is the most the bare protocol can offer, and the gap between it and what a channel needs is best exhibited as a construction. The adversary now controls the wire.

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. She 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, she 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.

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 in fact shared 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 her own exponent m and received both A and B, so she 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, editing at will in between. □

The lesson deserves stating structurally: passive security concerns the secrecy of the shared secret; active security additionally requires the authenticity of the public shares. Confidentiality of a channel is worthless if the channel is established with the wrong party. The bare protocol (Construction 7.1) provides no authentication—nothing in ga or gb testifies to who sent it—so the remedy must bind each public share to its sender’s identity, letting the recipient reject a substituted share. Every such binding is external to the key exchange itself.

Remark 7.15 (Three mechanisms supply authentication).

All 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 her 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 toward B already authenticates Bob to Alice: only the holder of b can complete it. Note the direction: 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 security goal remains the passive guarantee of Theorem 7.11; authentication is a separable layer composed around the exchange, not a property of the group operation.

7.6 Elliptic-curve Diffie–Hellman

The development so far is deliberately group-agnostic; we now instantiate it on the groups the deployed protocol actually uses. 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+a⁢x+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⁢(log⁡x) point additions by double-and-add. Elliptic-curve Diffie–Hellman is the transliteration.

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)=[a⁢b]⁢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 dress: the group is abelian, and ℤ acts on ⟨P⟩ through ℤ/q⁢ℤ because [q]⁢P=𝒪, so [x]⁢([y]⁢P)=[x⁢y]⁢P for all integers x,y. Hence Agree⁢(a,[b]⁢P)=[a⁢b]⁢P=[b⁢a]⁢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 pitfalls, 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 runs happily 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 sidestep the cofactor issue entirely: with h=1 there is no small subgroup to hit, and only the on-curve check remains. The deployed arithmetic enforces exactly that check at deserialisation, as documented in Proposition 2.27, whose compressed encoding cannot even represent a point off the curve.

7.7 Hybrid public-key encryption

Three obstacles separate the Diffie–Hellman shared group element from a usable encryption scheme. First, the shared secret is a structured group element—a curve point with coordinates satisfying an equation—not a uniform string of key bits. Second, the exchange by itself transports no message: it manufactures a secret, and stops. Third, we want the static–ephemeral non-interactive flow of §7.2, so that the recipient need not be online. All three are resolved by one composition: key agreement for the secret, a key-derivation function for uniformity, an authenticated cipher for the message—hybrid public-key encryption (HPKE). The two symmetric ingredients were built in Section 6; we recall them in the specialised shape the composition needs.

Definition 7.20 (KDF, recalled and specialised).

A key-derivation function here 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)=[e⁢b]⁢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.

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)=[b⁢e]⁢P=[e⁢b]⁢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: she 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=[e⁢b]⁢P, K=KDF⁢(S,𝑐𝑜𝑛𝑡𝑒𝑥𝑡), and c=EncK⁢(N,𝑎𝑑,mβ). Say 𝒜 wins a game when her 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,𝑐𝑜𝑛𝑡𝑒𝑥𝑡)=([e⁢b]⁢P,𝑐𝑜𝑛𝑡𝑒𝑥𝑡): until that query, the oracle’s value there is a uniform string she has never seen, which is precisely what Game 1 hands out. But producing S=[e⁢b]⁢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 [e⁢b]⁢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 genuine 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; we state the loose bound because it is what plain CDH buys, and honesty about the loss is part of the bound.

Game 1 analysed. The AEAD key is now 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|=12⁢Advae⁢(𝒞).

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 traded away, but not for 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 trade 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 (Every ingredient is necessary).

Dropping any piece 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 XOR-malleability of Section 6’s stream ciphers is total. 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 buys only the sender-side guarantee that the key derives from no stored secret of the sender.

7.8 Key privacy

Theorem 7.24 answers the eavesdropper and leaves the scanner untouched. Her posture is different: she holds a published ciphertext against every public key she can enumerate and asks not what it says but to whom. Confidentiality is silent on the question—a scheme may hide the message perfectly and still stamp the recipient’s key on every ciphertext. The property that denies her is key privacy, due to Bellare, Boldyreva, Desai, and Pointcheval. We state it for a generic public-key scheme, then prove it for the bare static–ephemeral flow with the message folded in—ElGamal encryption, the shape whose key privacy the upper volumes consume.

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 [r⁢x]⁢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=a⁢b 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—nor needs, the game offering no decryption. On receiving M it replies with

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

and outputs 𝒜’s bit. If c=a⁢b, then R=[s⁢b]⁢P=[b]⁢H0 and [s]⁢Z=[s⁢a⁢b]⁢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=[s⁢c]⁢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 (What key privacy buys upstairs).

The hybrid transfers verbatim 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”): a chain scanner holding a note ciphertext against every address she can enumerate learns nothing about which one it was sent to. The second use is the group-element share 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, and Theorem 7.28 answers it. The protocol specification sets up that correspondence, modelling the group hash behind the base as a random oracle (§“𝖣𝗂𝗏𝖾𝗋𝗌𝗂𝖿𝗒𝖧𝖺𝗌𝗁𝖲𝖺𝗉𝗅𝗂𝗇𝗀 and 𝖣𝗂𝗏𝖾𝗋𝗌𝗂𝖿𝗒𝖧𝖺𝗌𝗁𝖮𝗋𝖼𝗁𝖺𝗋𝖽 Hash Functions”); the Wallet Guide states the resulting unlinkability requirement (§“Diversifier indices”).

7.9 Shielded-note delivery as deployed hybrid encryption

The chain assembled in this section is not an analogy for what the deployed protocol does; it is the deployed protocol, 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 exists precisely to accommodate it (DiversifiedTransmissionKey is derived as 𝗉𝗄𝖽=[𝗂𝗏𝗄]⁢gd); the Ironwood Guide develops the key hierarchy (§“Viewing keys”) and address encoding (§“Diversified addresses”) behind these bases. 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; RandomSeed::esk_inner applies PrfExpand::ORCHARD_ESK), 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. The nonce is fixed to zero and the associated data is empty, safe because each K keys exactly one encryption (protocol specification §“Encryption (Sapling and Orchard)”; the zcash_note_encryption crate’s encrypt_note_plaintext, which chains ka_agree_enc, kdf, and ChaCha20Poly1305 with the zero nonce; the Orchard instantiation of the Domain trait is in the orchard crate).

Chain scanners see (𝖾𝗉𝗄,c) in every shielded output, but lacking 𝗂𝗏𝗄 they learn nothing (Theorem 7.24); the recipient trial-decrypts, deriving K′=KDF⁢([𝗂𝗏𝗄]⁢𝖾𝗉𝗄,𝖾𝗉𝗄) for each incoming transaction and keeping 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 𝖾𝗉𝗄—the notes addressed to them (protocol specification §“Decryption using an Incoming Viewing Key (Sapling and Orchard)”). Non-interactivity is essential, and it is exactly the static–ephemeral flow of §7.2: 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 the man-in-the-middle substitution has nowhere to stand; and, as noted there, this authenticates the recipient rather than the sender. The complementary guarantees on the note’s contents—that the value is well-formed and conserved, that the commitment on chain matches the plaintext delivered—come not from the encryption but from the accompanying zero-knowledge proof.

The primitive toolbox now covers the delivery of a secret to a party who was never online to negotiate it. What travels alongside that ciphertext—the authorising signatures over the transaction that carries it—is the business of the next section.