Post-Quantum Zcash

​

Daira-Emma Hopwood (ze / hir) - Electric Coin Company

​

This talk is dedicated to the trans community.

What is a “quantum computer”?

😬

• All computers using semiconductor chips fundamentally depend on quantum mechanics (and qubits are not particularly fundamental to how a QC works).

The Invariance Thesis

• “ ‘Reasonable’ machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.” [Slot and van Emde Boas 1984]
• This is also called the “strong” or “extended” Church–Turing thesis.
• If we can generate cryptographic problems that are with high probability exponentially secure (for known attacks) against a classical adversary but solvable in subexponential time on a ‘reasonable’ quantum computer, that would give evidence against the invariance thesis.
• We have a hypothetical polynomial-time quantum attack against discrete log for any group. So if elliptic curve cryptography is classically secure but quantum computers can implement that attack, then the invariance thesis is wrong (unless the polynomial hierarchy collapses).
• This isn’t just about specific algorithms being insecure — which can happen regardless.

It’s about whether we are in a fundamentally different “world” of complexity theory than otherwise.

• This is a falsifiable hypothesis ⇒ it’s science! (despite the hype)

Solving group-based problems

• In 1993, Daniel Simon was trying to prove that quantum computers could not obtain an exponential speed-up.
• Studying even very simple quantum programs, he found a counterexample (this isn’t the whole algorithm, just the quantum part):

​

​

​

• This was a huge breakthrough (for which Simon gets credit within the field, but not so much in popular accounts, many of which only credit Peter Shor or Lov Grover).
• He submitted his paper On the Power of Quantum Computation for publication in that year’s Symposium on Theory of Computing (STOC).
• The paper was rejected, as groundbreaking papers so often are.

Solving group-based problems

• Fortunately, Simon’s thesis supervisor Peter Shor noticed that Simon’s problem has a very similar structure to “hidden subgroup problems” familiar from number theory.
• These have known classically efficient reductions from problems relied on by public-key cryptography, including factoring and discrete log.
• Shor generalized the algorithm to find the order of any finite abelian group (which can be used to factor). Both papers were published together in a competing journal, FOCS 1993.
• STOC missed out on two of the most significant computer science papers of the half-century. Don’t be Reviewer 2!
• Simon’s algorithm is the key intuition needed for how quantum computers can achieve exponential speed-ups on some problems.
• Shor’s algorithms, and later variants that reduce the number of qubits needed, “just” use this idea with a different group and some number theory to solve factoring or discrete log.
• So what is Simon’s problem, and how does a quantum computer solve it?

Simon’s hidden shift problem

• Let s ∈ G be a secret value, and f an oracle function of type G → S

such that for all (x, y), f(x) = f(y) ⇔ x ⊖ y ∈ {0, s}.

Find s by querying f.

• Intuitively, we have copies of the same function with inputs shifted by s.
• Simon had G = S = {0,1}ⁿ and ⊖ as xor, and focussed on the decision problem of whether s = 0.
• If we replace {0, s} with a subgroup H (i.e. f(x) = f(y) ⇔ x and y are in the same coset of H) then we have a hidden subgroup problem, as Shor recognized.
• This problem is solvable by collision search with expected classical complexity Θ(√|G|), e.g. using cycle finding [van Oorschot and Wiener 1999].
• Less obviously, if G has a set of N subgroups whose only common element is the identity, then any classical black-box algorithm makes Ω(√N) expected queries to f.

[Childs, Lecture Notes on Quantum Algorithms; Theorem 5.1].

Oversimplified quantum theory

• The map is not the territory; I’ll try my best to avoid conflating them.
• A pure quantum state can be modelled by assigning an “amplitude” (in ℂ²), to every point in the configuration space. The vector norms of amplitudes sum to 1 over that space.
• If we instead assigned just a probability to every possible state, there would be nothing “quantum” about this; we would just have a classical probability distribution.
• What makes this “quantum” is that:
• We can operate on the state with unitary transformations. A unitary transformation preserves the property that the vector norms of amplitudes sum to 1.
• We can “measure” the state according to the Born rule: the square of a configuration’s amplitude gives the probability of seeing it. This squaring only happens on measurement.
• For our purposes it’s sufficient to assume that measuring a state destroys it.
• Quantum computers operate non-trivially on quantum states.

What is a “quantum computer”?

• Qubits are not fundamental. You can understand the basic model of quantum computation wrt an abstract configuration space, arbitrary unitary transformations, and measurements.
• Only a subset of unitary transformations are efficiently implementable, just like only a subset of mathematical functions are efficiently implementable in a computational model.
• Qubit-based quantum circuits provide a simple universal model of quantum computation (see section 4.5 of Nielsen and Chuang’s textbook). In this model:
• The state space of an idealized “quantum register” is modelled as a complex Hilbert space over the configuration space {0, 1}ⁿ (ordinary 0, ordinary 1).
• A “qubit” is, roughly, what we call a bit that can be in a superposition, or entangled with other bits. We need to model the whole quantum state, not just the state of a particular qubit. We do that (for pure states) by assigning amplitudes to each element in {0, 1}ⁿ.
• We can measure some subset of qubits. (It turns out that measurement can always, in principle, be deferred to the end of a noninteractive quantum algorithm.)

The Walsh spectrum of f

• The Walsh–Hadamard Transform is a Discrete Fourier Transform over the group ({0, 1}ⁿ, ⊕):

​

​

​

​

​

​

​

• Since each W_f(x) depends on f applied to every other x, the classical complexity of computing the Walsh spectrum would be Θ(|G| · log |G|) = Θ(2ⁿ · n). But Simon’s algorithm doesn’t do that.
• What it does (in only Θ(n) gates plus the cost of computing f), is to compute a (non-uniform) superposition over the Walsh spectrum entries.

images: T. Piesk, public domain

The overall algorithm

• Repeat Θ(n) times:
• Initialize an n-qubit register with each qubit (independently) a superposition of 0 and 1.
• Initialize a second n-qubit register with zeroes.
• Apply f to the first register with output in the second. Then apply a WHT.

​

​

​

​

• When we measure the output of that WHT, we get interference between the possible configurations (a bit like the interference pattern in a double-slit experiment) so that the outputs with non-zero probability are all of the form z such that z ∘ s = 0.
• Then we solve the system of equations z_i ∘ s = 0 for s.

About quantum interpretations

• Much of the perception of mystery about quantum physics can be attributed to bad pop-sci explanations of the various interpretations. For example:
• In MWI, the universe doesn’t “branch”. The evolution is unitary and deterministic, so there is a single evolving quantum state. MWI “just” interprets the state as a superposition of “worlds”.
• The Copenhagen interpretation is best seen as limiting itself to making claims only about situations in which the quantum system is isolated, and those in which it is very much not isolated. This calls for a programme of exploring the intermediate situations by experiment. Quantum computers are part of that. (This also applies to de­ Broglie–Bohm theory which is mathematically equivalent to Copenhagen.)
• QBism is about how Bayesian reasoning can be extended to quantum systems. This does not commit to disbelief in physical realism, any more than classical Bayesian reasoning does.
• Objective-collapse theories make differing predictions (between each other, and from MWI and Copenhagen) that we are close to testing.
• Experiments on standing-wave oil-drop models had been (inaccurately) reported as supporting pilot-wave theories, but both those experiments and the analogy have been refuted [BAL 2016].

About quantum interpretations

• Theories having lacunae — unexplained aspects or gaps in applicability — is just part of the practice of science.
• Compare with “action at a distance” in Newton’s theory of gravitation, which Newton himself thought of as an unexplained “great absurdity” [letter to Richard Bentley, 1692–3]. This was not resolved until the development of general relativity over two centuries later.
• Uncertainty about the quantum measurement problem is the same kind of uncertainty that has always happened in science; just a particularly tricky case of it.
• Compare with the evolution of understanding of heat and temperature, or of conservation of mass in chemistry.
• It is not the case that all of the interpretations are “just different ways of viewing the same thing”. Some make different predictions, and they all leave different questions open.

Are CRQCs feasible?

• The following is my opinion as a non-physicist.
• The available evidence suggests that if there is a bound on the size, weight, or complexity of systems in superposition, it’s large. For example, [Bild et al 2023] describes an experiment in which a sapphire crystal of weight 16 µg, consisting of around 10¹⁷ atoms, was put into superposition.
• At risk of oversimplifying, this indicates to me that we have no reason to believe in fundamental physical obstacles to the size or complexity of quantum computers at bounds below what would be needed for cryptographic relevance.
• The error correction problem appears to be solvable. (Google may have solved it.)
• It is fruitless to try to infer how close cryptographically relevant QCs might be from headline “number of qubits” announcements. Such announcements are aimed at drumming up attention or funding, and don’t use comparable metrics or include enough information to determine applicability to particular quantum algorithms.

Cryptographically Relevant QCs

• [BSI 2024] is a thorough survey report by the German Federal Office for Information Security. The important point here is not the numbers, but that we know what the numbers are.

Cryptographically Relevant QCs

• BSI, January 2025: “we believe that with high probability cryptographically relevant quantum computers will be available within 16 years” [i.e. 2040]
• This is toward the longer side of expert estimates, but note that it’s a maximum time (which is less useful for cryptographic engineers than a minimum).

​

• Dan Bernstein, January 2025: median estimate 2032 for public demos, 2029 for well-funded private attacks.
• These estimates are not for demos or private attacks on deployed schemes with conservative security parameters. They're for any demo or attack sufficient to show cryptographic relevance.

What about Zcash?

• This summarizes ^⚠️ Zcash’s dependence on cryptography potentially vulnerable to quantum computers:

​

​

​

​

​

​

​

​

​

​

• For more detail see my presentation “Understanding the Security of Zcash” at Zcon3.

Harvest Now, Decrypt Later attacks

• Adversaries can harvest ciphertext now, and decrypt later when they have a working quantum computer.
• It’s a blockchain, so harvesting in-band ciphertext is easy.
• For harvesting addresses, see next slide.
• The conventional wisdom has been that this should focus attention on encryption as the thing to migrate first.
• On the other hand, progress on quantum computing has been fast enough that we probably also need to start thinking about integrity (Spend authentication and Balance) as well, in parallel.

Deploying Plausibly PQ Cryptography

• The lead time on developing and deploying of cryptographic protocols is such that we essentially have no choice but to deploy PPQC before knowing whether or not there are insurmountable engineering obstacles to CRQCs.
• We need demonstrable security. A public demo of a CRQC would knock public confidence even if it can only break curves much smaller than the 255-bit curves (Pallas, Vesta, Jubjub) used in Zcash.
• The cryptographic engineering challenge is to do so:
• without introducing significant security, performance, or maintainability regressions, and
• minimizing the opportunity cost of switching to PPQC instead of making other improvements.

Encryption in Zcash

• Notes need to be privately transmitted to their recipients.
• Currently, this is done by broadcast encryption. Each potential recipient trial-decrypts each ciphertext (with each of their keys) to see if it is for them.
• For this to work, encryption has to be key-private, i.e. seeing the ciphertext does not reveal information that would narrow down which public key was used.
• ML-KEM is a post-quantum encryption algorithm, recently standardized by NIST.
• Fortunately, ML-KEM is proven to be post-quantum key-private under chosen ciphertext attack, by tight reduction to the MLWE problem, in [Maram and Xagawa 2022].
• In fact they show a stronger property, “strong pseudorandomness” or SPR-CCA. An open question about ε-injectivity of an ML-KEM component, needed for tightness of Maram and Xagawa’s “wrapper-based” proof approach, is resolved in [Ding et al 2022].
• We’ll discuss an important subtlety in a couple of slides.

Hybrid post-quantum crypto

• Is there a significant chance of introducing a vulnerability by changing to newer algorithms? Yes.
• Examples:
• SIKE and most other isogeny-based cryptography is now considered completely broken.
• The Plonky3 proof system had a soundness bug that was only fixed recently.
• The Rainbow signature scheme was badly broken after getting through to be a 3rd round finalist in NIST’s competition [Beullens 2022].
• PPQ schemes are often more complicated.
• Side-channel attacks on PPQ schemes can be more serious.
• Possible solution: combine post-quantum and pre-quantum algorithms.

Encryption combiners

• X-Wing combines ML-KEM-768 with X25519.
• We can easily adapt it to Zcash’s note encryption if we want to use Pallas instead of X25519.
• The public key and ciphertext sizes are the sum of those for the individual algorithms.
• The security properties are essentially ideal for conventional confidentiality properties.
• However, key privacy has not been analyzed for X-Wing before to my knowledge.
• If both ML-KEM-768 and X25519 are key-private, then (fairly obviously, you have to look at the detail to see this) so is X-Wing.
• But that’s not good enough.

Encryption combiners

• It is not generically true that if a combiner is IND-CCA2-secure whenever either A or B is, then it is key-private whenever A or B is.
• Counterexample: A leaks pk_A and B is key-private. Then (ct_A, ct_B) leaks pk_A.
• In particular, the proof of key-privacy in [Maram and Xagawa 2022] assumes hardness of MLWE.
• But not wanting to assume hardness of MLWE is (partly) why we’re using a combiner!
• We could EC-encrypt the ML-KEM ciphertext, maybe?
• Seems like a promising direction (the ECIES ephemeral key is statistically random and so we’re not necessarily depending on hardness of DL for key privacy).
• But it’s tricky, because chosen-ciphertext security needs a complete reanalysis.
• At this point we’re not using X-Wing, we’re rolling our own crypto.

Diversified addresses

• Zcash’s note encryption supports “diversified addresses”: addresses with the same spend authority that can be given to different counterparties, who cannot link them.
• A critical performance advantage of this scheme is that the scanner only has to trial-decrypt with a single key. It isn’t clear how to support this directly for ML-KEM.
• If we EC-encrypt the ML-KEM ciphertext, then the recipient or detection key holder could trial-decrypt the outer ciphertext, which is the scanning bottleneck. A diversified address would be (diversified EC public key, independent ML-KEM public key).
• But this interferes with post-quantum key privacy, because we would need to be able to decide which ML-KEM key to decrypt with after only decrypting the EC ciphertext, which depends on security of DL. This also only provides pre-quantum unlinkability. 😢
• Half-baked idea: Use half-ephemeral ECDH to agree an ECDH shared secret. Use the secret to get an ML-KEM “key index”. Reconstruct the ML-KEM public and private keys from the private seed and key index. Decapsulate the ML-KEM ciphertext and hash the decapsulation key together with the key index, ECDH shared secret, and ECDH ephemeral key (but not the EC public key). Use the resulting key for symmetric authenticated decryption. (This is not key-private against a DL-breaking adversary.)

Post-quantum proving systems

• Problem 1: Currently available post-quantum proving systems require proofs that are at least 50 KiB. That won’t go on-chain per transaction.
• Problem 2: We have less confidence in post-quantum proving systems (well, I do).

Can we use recursive proofs as a solution to problem 1, and combiners as a solution to problem 2?

• Problem 3: Combiners for recursive proving systems are inefficient.

Folding schemes tend to be focussed on folding within a given setting (either classical or PPQ, not both).

Post-quantum proving systems

• If Bernstein’s estimate for a public demo is even close to correct, then the timing for deploying a PPQ proving system in Zcash is very tight, because:
• it won’t be a drop-in replacement, due to the proof size issue;
• it likely will have to coexist with OrchardZSA for a time.

Edit: Quantum resilience for Orchard would help to take off some of the time pressure.

• Proposed solution:

A. Deploy recursion using Halo 2 (and get the resulting scalability improvement).

B. When a recursive PPQ scheme with the required efficiency and confidence in its security arrives, switch to using recursion with that scheme and no proof combiner.

• The line of work on lattice-based folding schemes (LatticeFold+, Arc, etc.) is very promising for B.

ZK proof system combiners

• Parallel composition: include proof of the same statement in two schemes, verify both.
• Pros:
• Knowledge sound if either scheme is knowledge sound.
• Very simple.
• Cons:
• Only ZK if both schemes are ZK. But that may not be too much of an issue:
• ZK is usually unconditional or statistical.
• When ZK breaks, it tends to break mildly, because of succinctness or use of hashing.
• Proof size is the sum of proof sizes for each scheme.
• Recursion is significantly more complicated.

Signature combiners

• Parallel composition: include signature over the same data in two schemes with independent keys, verify both.
• Signature size is the sum of signature sizes for each scheme.
• Pros:
• Unforgeable if either scheme is unforgeable.
• There is no “only ZK if both schemes are ZK”, even for signature schemes constructed from ZK proof systems. This is because we are not trying to hide the message, and the keys of each scheme are independent.
• Very simple.
• Cons:
• Verification within a circuit is more complicated.

Do we need signatures?

• In Orchard, signatures are used for spend authorization and binding.
• The purpose of the binding signatures is to ensure balance and prove knowledge of the the commitment randomness (so that output proofs cannot be replayed).
• Using a signature for this is mainly a convenience: if we have recursive proofs, then the transaction proof can do everything the binding signature is currently doing.
• Spend authorization can be included in the spend circuit, as it was in Sprout. See the next slide for how we can make that more efficient.
• Sprout had an additional “JoinSplitSig” which was to compensate for malleability of the proving system. We should instead analyze the protocol with malleability taken into account, as I did in a 2023 update to the slides of my “Understanding the Security of Zcash” presentation (see slide 15).

Do we need randomized signatures?

• The reason why Orchard and Sapling switched from proving spend authorization in the circuit to a spend auth signature, is to let hardware wallets only perform signatures.
• We could instead do spend authorization with a very small circuit, which only needs to prove knowledge of the private key for a committed public key.
• The statement is { (ask, α) : Commit^Auth(H^addr(ask)) = rk } where
• ak = H^addr(ask) is the spend authorization public key (like a_pk in Sprout)
• α is the hiding randomness (like α in Sapling and Orchard)
• rk is a hiding commitment to ak (like rk in Sapling and Orchard, checked via the Spend Authority check in the larger circuit).
• H^addr must be PPQ collision-resistant. Commit^Auth must be PPQ binding and hiding.
• This requires two hashes in the small circuit (for H^addr and Commit^Auth), per input. That might be small enough to be feasible on hardware wallets for a PPQ proving system.
• We’ve essentially constructed a PPQ randomized signature scheme.

_α

Hot-take bonus slide

• Yesterday Sean Bowe presented an idea about using recursive proofs to improve the scalability of checking for double-spends using nullifiers.
• It’s compatible with the scheme on the previous slide, because the spend authorization is independent of the rest of the note structure.
• However, Sean’s protocol uses EC scalar multiplication and is not post-quantum. Can we make it post-quantum?
• Many DL-based protocols can be adapted to lattices, so maybe yes.
• Can the protocol be described generically without relying on group operations?

Size of addresses using ML-KEM

• The raw encoding of a Unified Address with transparent, Sapling, and Orchard components is 128 bytes.
• An ML-KEM-768 public key is 1184 bytes.
• X-Wing is a hybrid KEM combining X25519 and ML-KEM-768. It has a public key size of 1216 bytes, which is what we would also expect for a hybrid using Diffie–Hellman over the Pallas curve. Adding 32 bytes for ak and encoding as a UA, that would take 2112 characters.
• The changes in Kyber between round 1 and round 2 of the NIST competition dropped compression of the public key. This is hard to undo (i.e. to apply public key compression to ML-KEM’s public key), because it is mixed up with other parameter changes.
• The best we could expect by applying this compression to ML-KEM (encoding each element of t̂ in the public key with 10 bits instead of 12, with d_t = d_u as in Kyber v1) would give a public key size of 992 bytes, but that would require an expert analysis to determine whether it was safe.

Size of addresses

Orchard + X-Wing with ML-KEM and Pallas:

u12kxg2vfl3l6jhg0sus5jyr4t223uzg2mq87s6xxcdsah9dce898kus2wl0rw785jr9tfsnk6nm424jqua4kcl0esjhdzk9xjevqysn45fjm629l5v2mv93uz5uh3jhvsttphxmztumqy8l5hmwrekhglhk46wfrw9mgz4st5hjf6e9w6f949u5hhzfucv0d79wg88jtq7twvj3dwm5cd7ksuhzk2lr6wwgwyl9r7wg00kwcfvvlq5z3rv6jl9yyj3fvl2htemjetmteg20sy00wef9xc93slf6zdq26mqtj8j2cxecxl665myr30lf4t8tjujtxyscdns6pe6d6jkg2eht9u8p2d6lerj79yfgc29m702rrkde70fuad4gx4phzeuzxy7zuy4mfph8yrm5satd83xzhynwn2rles25equr8k4jpg3m8gr87qvuw9r65y9u7p9axn8nlkkp7vxfhfj4xghd7rja60y4w4x0xs7mwefgdcyud47kvh5smuannqm8ugxf3lh9l6k4nf30gkzxlnt7cennwqmsyc3xmkq5myvg85gcxykk5whrfn6zrvctk4f77vlxkq5jkw5t39hcwu5mtph37zd80h2c2mxm8jrsjrpchxd35a9sxgwp4qhvqq6xgt9jux0eagxruep0rezgwz4pusua05us7j39mdjcznq9va0e8fxny0q95asmg5w66ax5w5wewmx5gep55ktmjtnwlnfz2lurm3dwchlh66frp5z3uv4cgade0axwz5wnklmxmmntrmncrnurvak9ln4uzsl4j70unjtd0kg9h305pd06wk0cgqrwpl77zjadx0aws9gv03uem4035mgft5wnmra4f6s7cusegl9xkvnvpdhng5wf9078evr4mrzrxl060xwp9uv93zpfa0w2dhxnvce3pj2j6fm80865qme7yrl80kcczmthj3mvrnzc9tmcka36zraavh38ddpruha27y7serw5w5af45h5c4uztqt77rf03ahy6ks0aehfj3pzknacah2wdavg9ttcv42n9mjgfzcnkv472t62t5nnqtwn5xjruzdnnewz2trj3ed9eydzspsh6gnwwdwrrr5j23ve7mklqfezlccmxujgcug9w6x4sh3wsqh6cs3mfd2tuwwuu34gkwamzxjkvmezytujqd3mw36epfkjngjh6r3wwlr67mrgaqtlkcp4e7j4t3mq2wsnznll5djjvtphap5m3uywjstxm5gjuj0mxfuams29eap28w3u0ucj6922q9w94nadyfw4r2658tkz5f455l40pekcpx80lljazmqskq6vru6ldru742g8quk9hf0qzd3yc9a93s8mr8tt824kt27uecaeqmp0ek2ss6y7cw8d74wzys8v8f294tq438436k53gy40xk9mmw4fwz6q8g86ahzgwqfkysjg0ylp2vnugqwtwh2ppwvfkfuwk8ryuylk9eh8j02ua4fhpsf6e72j22ncmu6rfqnskpx7znrphd7jn6xar08hgwdmhlcpmnsxjxaxx8x4dc2xm3csge0h686stxsxw9g4wwsk5u9c8wkkme3veyy4hw52t3x5c447uw56y5aw9afs6hg2sanfdsdwkhdt62swd7qecrj56ykps049hfqh37tqe3rhdv5navmakfm9anc6dsjc2hjyg8z8e9k9fc7u3ayre33gfvw7pfz3rw3fsw7c3mjvcj84qvzksjggt45pxz6kw6yrp9kmn4zvuv068jux2f03hnska62hf8xmy5w058wtmg2zae7rycv87vt2plmw4p36x6aga5l7kgu85gwm827a3xrwgfvjugf4y9spac5x40pxclwkutqhhh2jkl7epdt2r0c2fy5mgrjc707ekutt8yrj8mnq0ck3udq96ff35dvudxv6jkkr5pm8qcek9yuxru6m2g2ufgh2j0qcxl20dnlvlhnz5g3ug5slzn5phxpnxz343hm6lmgumgy8x9p5ac09l6d3jpsr5g06qak4ujjwtn7kzwqkm6dej4szf68z2p6pn39nha7q3nwsp97aj44m0mys5myj8wmn0xtw

Transparent + Sapling + Orchard

u1k7dczqy5un7u7xp24lw0dqg0rz35rs2czmmanml5rmwlec7vu5te95ynkpm8ezhtlchvs2gf3503g5cna8ljfrw0a7su54hrfryrfl45rf28mtn69quepc8l33pm69p9aetvv6feuudkryc6cl6rgxqkp2cdy5cex7q2wcu4lwjke4snf3egw04pzr3568zxudrdrlr8drq525scxp4

Size of addresses

Orchard + X-Wing with ML-KEM and Pallas:

​

Transparent + Sapling + Orchard:

What about other KEMs?

Dealing with large addresses

• There are two potential approaches to mitigate the cost of larger addresses / public keys.
• If notes are transferred over a point-to-point anonymous connection, that channel can carry a public or ephemeral key, and it will likely be higher bandwidth than some of the channels typically used for addresses. Sean mentioned this option in his talk yesterday.
• Onion routing doesn’t provide privacy against a global adversary, so we need a mix-net.
• I’m quite bullish about using NYM.
• This approach doesn’t support the “post a donation address on social media” use case.
• We can “register” addresses on the block chain and use shorter indices to refer to them.
• The registration transaction(s) still need to be sent anonymously.
• In Sapling / Orchard, diversified addresses don’t cost anything. If they were registered then you’d have to put a ~1248-byte address on chain for each counterparty. (More on diversified addresses later.)

What can we do in the short term?

• The Zerocash protocol, that we developed into Zcash, was intended ^⚠️ to have a property referred to as “everlasting anonymity” in the paper [BCGGMTV 2014].
• We have carefully maintained this property throughout the development of Sprout, Sapling, Orchard, and OrchardZSA.
• All symmetric cryptography in Zcash uses cryptovalues of size large enough to resist quantum attacks via Grover’s algorithm.
• It turns out that Grover’s algorithm is a lot more difficult to make practical than Shor’s algorithm, in any case. This is primarily due to the large number of steps.
• Grover’s algorithm is not the only possibility for quantum attacks on symmetric crypto.
• However, attacks in the quantum query model (such as [IHMSI 2018] against Feistel ciphers up to 6 rounds or [BLPS 2021] against MACs, or similar examples considered in [CLS 2022]) should be disregarded. An adversary has no power to force us to implement our primitives on a quantum computer and provide oracle access to them.

HNDL resistance in the short term

• To get “Harvest Now, Decrypt Later” resistance for Zcash now:
• Only send addresses via one of these apps, with disappearing messages enabled.
• Signal [PQXDH, RWC 2024]
• Apple iMessage [PQ3, RWC 2024]
• Tell your counterparties to keep addresses private.
• Pay attention to the security of your wallet backups and tell counterparties to do so.
• Don’t include “reply addresses” in memos (either manually or automatically).
• I explained this incorrectly in the talk; the problem isn’t that the recipient learns your address (which is intended), but that a quantum adversary that learns the recipient’s address will also learn yours.

Other messaging apps

• No other messaging apps (than Signal and iMessage) should be assumed to have any degree of HNDL resistance, whether or not they advertise “end-to-end encryption”.
• Most messaging apps don’t have even pre-quantum end-to-end encryption:
• Discord (text), Slack, Google Chat, Mattermost, Zulip, WeChat, Kik.
• ... or it’s not enabled by default, otherwise unreliable, not applied to all messages, a “premium” feature, etc.:
• Rocket.Chat, Telegram, Skype, Microsoft Teams, LINE, Instagram, imo, Kakaotalk, Troop.
• This is pretty terrible; in 2025 it should be a baseline requirement for a messaging app to have end-to-end encryption that is always-on and has forward secrecy, and active plans to introduce HNDL resistance or fully post-quantum cryptography.

Other messaging apps

• I’m not aware of any other apps that designed their own encryption / key exchange protocols having upgraded them to have HNDL resistance.
• Matrix (Element etc) uses Megolm protocol, which is not HNDL-resistant and has only partial forward secrecy.
• Threema rolled their own (Ibex) which is not HNDL-resistant.
• Viber rolled their own based on Signal Protocol, not HNDL-resistant.
• Wire rolled their own based on Axolotl (a predecessor of Signal), not HNDL-resistant.
• Keybase rolled their own which is not HNDL-resistant and has no forward secrecy.
• Briar rolled their own which is not HNDL-resistant and has no forward secrecy.
• Session previously used Signal Protocol, but ripped it out in 2021 in favour of a worse protocol which does not use ratcheting and has no forward secrecy.

Other apps using Signal Protocol

• Facebook (Messenger and web) uses a Java reimplementation of Signal Protocol [FB 2023] (their paper links to an archived GitHub repo so that’s not the version they’re using). No mention I can find of PQXDH deployment.
• WhatsApp also uses Signal Protocol, but cannot be recommended as a secure messaging app. It is controlled by Meta and reports copious amounts of sensitive user metadata to them and to law enforcement.
• According to a thorough 2021 Propublica article, the latter was instrumental in convicting Natalie Edwards, a FCEN official who had whistle-blown about Russian interference in US elections, after she used WhatsApp to communicate with a BuzzFeed reporter.
• Also, reportedly WhatsApp’s scanning for abusive images has many false positives.
• Dust uses Signal Protocol but I can’t find any further information on their implementation, and their docs don’t mention any upgrade to PQXDH.
• There might be others but nothing that has a significant user base, I think.

What’s Next?

What’s next?

• Sean and I will be trying to figure out whether his idea for scalable nullifiers can be made post-quantum.
• Does my half-baked idea for hybrid pre-quantum unlinkability and post-quantum key privacy work?
• Update: no. To get diversified addresses that are key-private against a discrete-log-breaking adversary, we probably need a lattice-based diversification scheme. That doesn’t seem impossible.
• How should we decide how to prioritize “post-quantum stuff” relative to other research and engineering?

Calls to Action

Calls To Action — Ecosystem

• Join the #cryptography channel on the R&D Discord.
• Document the cryptography you use.
• Consider integrations with HNDL-resistant messaging apps such as Signal and iMessage.
• Addresses are secrets. Don’t leak them.
• Consider removing “reply address” functionality.
• I know this will be controversial; let’s talk about it.
• Wallet files contain a huge amount of sensitive information. If viewing keys are leaked, it will compromise the user’s privacy for that account permanently.
• Never store cleartext data in locations subject to automatic backups. You don’t have control over the security of those backups. Even if claimed as “end-to-end encrypted” by the platform provider, that may be weakened at any time by regulatory attacks.
• Preferably encrypt wallets even locally. Then if they do get backed up, it’s not a disaster.

Calls To Action — Cryptographers

• Learn about constraints of real-world protocols. What’s stopping them from adopting PPQC?
• [Re-]read “The Moral Character of Cryptographic Work” [Rogaway 2015].
• We still haven’t solved the secure messaging problem yet.
• Read [BSI 2024] (the title is ‘Studie: Entwicklungsstand Quantencomputer’, but it’s in English).
• Take a course on quantum computation. It’s less hairy than you might imagine it to be.
• Try to find a breakthrough in PPQ proof, public key, or ciphertext sizes.
• Build and prove security of a hybrid encryption scheme with post-quantum unlinkability and key privacy.
• See you in Sofia for HACS and/or Real World Crypto!
• Not Real World PQC unfortunately (it clashes with HACS 😿).

Calls To Action — Users

• To get “Harvest Now, Decrypt Later” resistance for Zcash now, do all of this:
• Only send addresses via Signal or iMessage with disappearing messages enabled.
• Tell your counterparties to keep addresses private.
• Pay attention to the security of your wallet backups and tell counterparties to do so.
• Don’t include “reply addresses” in memos (which makes HNDL resistance of your own address dependent on that of the recipient’s address).
• Also:
• Pressure messaging app providers to take HNDL attacks seriously.
• Pressure Zcash wallet providers to take post-quantum security seriously.
• If we don’t fight fascism, all of this is going to be moot.

Learn more

• I’m in the process of reading the “Theoretical Minimum” series of books on classical mechanics, relativity, and quantum mechanics. They’re great, I recommend them if you’re good at math and regret not having learnt more physics.
• For more focussed study of quantum computation, try Scott Aaronson’s course at OpenCourseWare.
• The sources I used for Simon’s algorithm are:
• Simon’s paper, On the Power of Quantum Computation. It’s a good introduction!
• Shor’s paper, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
• The article “Exploring Simon’s Algorithm with Daniel Simon” was also invaluable.
• Chapter 5: Discrete Log and the Hidden Subgroup Problem in Childs’ textbook, Lecture Notes on Quantum Algorithms.

Thank you!

Questions?