Fully post-quantum Zcash

[daira]

There are three components necessary for a post-quantum Zcash:

• a post-quantum public key encryption scheme;
• reanalysis of symmetric crypto parameter choices against quantum attacks;
• a practical post-quantum zkSNARK.

(For spend authorization, there are two options: use a post-quantum public key signature scheme, or incorporate spend authorization fully into the SNARK circuit. So only the three components above are strictly necessary.)

The first of these is already available, for example using New Hope [edit: or CRYSTALS-Kyber as suggested below] key exchange in place of Curve25519 elliptic curve key exchange. A complication is that New Hope has larger public keys and larger ciphertexts (2048 bytes each; see section 7.1 of the New Hope paper). The public key size means that a New Hope key can't be encoded directly in an address, but that is not a fundamental obstacle: it might be possible to use an address registration protocol as described in #340, for example. The ciphertext size is quite large compared to the rest of a Pour description (and remember that we need two of them), but not totally impractical. Alternatively some other scheme may have shorter ciphertexts.

For the zkSNARK, in principle the existence of one-way functions is sufficient for the existence of ZK proof systems. The issue is practicality: practical zkSNARKs use pairing-based cryptography, and it is not clear whether or not that is available for PQ public key cryptosystems.

Note that even though lacking a PQ-zkSNARK means that arbitrary currency could be forged by a quantum attacker (if quantum computers are ever practical), there is still value in switching to a PQ encryption scheme and ensuring that the symmetric parameter choices are sufficient. This is because a quantum attacker could otherwise break the Curve25519-based encryption (for known addresses) and obtain past transaction metadata.

It is also useful to reanalyse the symmetric parameter choices in order to check whether Zcash already achieves post-quantum past privacy for payments to addresses that have been kept secret. If this were the case then it would allow Zcash to be used now by people who require that property.

[imichaelmiers]

Given the changes in the commitment scheme, we no longer provide post quantum privacy for zcash even if the ciphertext is null or done using post quantum secure crypto. Because the commitment scheme is only computationally hiding, it is breakable by a powerful attacker.

[daira]

@imichaelmiers Post-quantum security does not mean security against computationally unbounded attackers. The commitment scheme [in Sprout] is post-quantum secure if the SHA-256 compression function is a post-quantum collision-resistant PRF. (It may or may not be, but computationally unbounded attackers are not the issue.)

[defuse]

If you have a guess for a_pk and rho then some kind of a Grover search probably lets you find the 192-bit r in ~2^96 time on a quantum computer.

[Edit by Daira: the length of r was increased to 256 bits, mostly for this reason.]

[matthewdgreen]

Aside from using perfect/statistical commitments and ZK (and maybe symmetric primitives with very large key sizes), I don't think we know enough in 2016 to meaningfully guess at what will be post-quantum in 2040 or whenever real quantum machines arrive. The most we could do is take a stab and potentially put people at great risk by being wrong. *

To meaningfully enable PQ Zcash I would suggest that the following elements are most critical:

1. Replace the SHA256 commitments with Pedersen commitments in the appropriate bilinear group. See the Pinnochio-coin paper for estimates of the cost.
2. Keep all symmetric and public key encryption decisions independent of the core Zcash construction, so users have agility to choose alternate encryption algorithms -- including the "algorithm" that consists of writing your coin trapdoors on paper and handing them to your friend, who subsequently burns them.

I wouldn't worry too much about the zkSNARK. There will be plenty of warning before QCs reach the level of capability that makes currency forgery a concern.

• Note: here I mean risk that we are wrong about PQ-security, but /also/ risk that we are wrong about classical security. Let's not do this.

[daira]

Grover's algorithm (the multi-target version) is provably optimal for a black-box quantum preimage search. I think there is considerable value in choosing parameters to resist that if we can do so by making minor tweaks, like the length of r.

(Note that we're already arguably over the performance cost budget and will need significant optimizations to make Zcash really practical; making the protocol even more expensive by use of Pedersen commitments etc. is not really on the table.)

[Much later edit: Sapling uses statistically hiding Pedersen commitments, so that issue is resolved. I disagree about algorithm agility; it would greatly complicate the protocol. On the other hand we have been careful to not exclude out-of-band transmission of notes, even though the protocol spec does not describe how to do it.]

[defuse]

Grover can also be used to speed up collision-finding to the cube-root rather than the square-root, e.g. http://arxiv.org/pdf/quant-ph/9705002.pdf (Høyer was my quantum computing prof and this was on the final exam!). So a quantum attacker can find a SHA256 collision in ~2^85 time and space. This impacts everywhere we rely on collision resistance of 256-bit values: the binding of the commitment scheme, faerie gold defense, etc.

The cube root algorithm above is optimal for searching for collisions in black boxes.

Increasing the lengths of hash outputs to 384 bits requires a change of hash function which is definitely out of scope for the 1.0 launch. We just need to keep this fact in mind if we're answering questions about post-quantum security.

[matthewdgreen]

@daira I agree -- I don't think we have any runway or engineering budget to spend time on considerations about PQ security in v1.0. But if you think it's valuable enough to start a thread and have a discussion about it, I'm happy to include my recommendations. These are not near-term recommendations, but given the Pinnochio-coin results it seems obvious that they're not that far from practice (for a 2.0 or a 3.0 release). I would say these probably deserve a higher priority rank than experiments with new public-key cryptography, since statistically-hiding commitments provide tangible benefits we can actually deliver.

[daira]

@defuse wrote:

Grover can also be used to speed up collision-finding to the cube-root rather than the square-root, e.g. http://arxiv.org/pdf/quant-ph/9705002.pdf

Dan Bernstein disagrees:

A quantum algorithm by Brassard, Høyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3. This paper analyzes the Brassard–Høyer–Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot–Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.

[daira]

Note that Pedersen commitments are not post-quantum binding. Neither are the potentially more SNARK circuit-efficient commitments in section 4 of https://eprint.iacr.org/2014/719

Later edit: commitments based on circuit-efficient hashes such as MiMC, Rescue, or Poseidon would be post-quantum binding. (That doesn't address the proof system; you would need both the proof system and the commitments to be post-quantum secure in order to get post-quantum integrity.)

[daira]

BTW, let's agree to use "post-quantum" only for protocols that, as far as we know now, actually have some hope of being secure against quantum computers. Let's use "quantum forward-private" for protocols that, as far as we know now, avoid leading secret/private information to future quantum adversaries (under the assumption that no-one has a large quantum computer now), but may not meet their other security goals against a quantum adversary.

[burdges]

I'd just say "post-quantum anonymity" as opposed to "post-quantum financial soundness" because "forward-private" sounds too much like "forward-secure", which always denotes an improvement, not a weakening.

If folk want post-quantum anonymity now, then they could set up a modified Taler exchange to provide it. RSA blind signatures do offer post-quantum anonymity for customers. As is, Taler's refresh protocol is not post-quantum, but if you do not care about taxability then it can be made post-quantum trivially. And I can tell you how to make it post-quantum with taxability if anyone cares. RSA blind signatures do not provide anonymity for merchants, if the customer is compromised, but you always buy something from yourself and delete the records.

In any case, I'd think Tor needs a post-quantum key exchange before any of this makes any difference.

[daira]

I'd like to reiterate that Zcash as it stands, already is conjectured to be post-quantum forward private when addresses are kept secret.

[daira]

@elibensasson et al's work on post-quantum STARKs is relevant here: https://www.youtube.com/watch?v=HJ9K_o-RRSY

[daira]

See #570 (comment) for a note on post-quantum forward privacy.

[daira]

https://www.youtube.com/watch?v=kYmnXxs9kUM is a version of Eli's talk with more technical detail.

[str4d]

@imichaelmiers and I were discussing PQ-privacy of note ciphertexts in the Zcash block chain, and came up with the following proposal for a scheme that requires no modification to the current Zcash protocol. Assume that the existing symmetric encryption scheme is itself PQ-secure (which it should be) - the current lack of PQ privacy is due to the use of public-key crypto to derive the symmetric encryption key.

1. Alice and Bob use an out-of-band PQ-secure communication channel to negotiate a symmetric encryption key for Alice to use for sending payments to Bob, and an associated "key ID". The key ID could perhaps be derived from the symmetric key itself instead, or from some part of the PQ process (whatever can be done securely) - it just needs to be know to both Alice and Bob, but no one else.
2. Alice derives a 256-bit "key tag" from the key ID using a rachet-like system, e.g. key_tag = SHA256(1 || key_id). The exact scheme may end up being slightly different - the goal is for the key tag to be a plausible Curve25519 public key.
3. Alice creates her first JoinSplit to Bob, encrypts the output note for Bob using the negotiated symmetric encryption key, and sets e_pk to the key tag. She then increments her ratchet (so the next note she sends will use e.g. key_tag = SHA256(2 || key_id)).
4. When scanning the block chain, Bob first checks the e_pk to see if it is derived from one of his key IDs. If it is, he uses the corresponding symmetric key to decrypt and checks whether the resulting note is valid (by checking the commitment). If it is invalid, Bob assumes the e_pk just collided with his key tags, and proceeds as normal with trial decryption of the note ciphertext with all his z-addresses. If it is valid, Bob increments his ratchet.

Ratcheting is used to ensure that sequential JoinSplits encrypted to the same symmetric key remain indistinguishable (as using the key ID directly would make them trivially linkable). As an additional benefit, a non-PQ adversary cannot distinguish between a JoinSplit using this scheme, and one using the existing non-PQ-secure scheme. A PQ adversary can only determine that some out-of-band mechanism is being used, but not which one (ie. this scheme is indistinguishable from users simply sending the notes out-of-band and filling the ciphertext fields with random data).

For Bob finding and decrypting notes on the block chain, this scheme is effectively O(1) in the number of PQ keys (compared to O(N) for Bob having N z-addresses), because deriving ratchet values is significantly cheaper than trial decryption (and key tags can be pre-computed at various ratchet points, whereas trial decryption against a random e_pk is inherently un-cacheable).

[str4d]

The above scheme is insecure because it re-uses keys. The current Zcash note encryption scheme (libsodium's aead_chacha20poly1305_ietf) uses a zero nonce because keys are never re-used: the ephemeral nature of e_pk means a unique Curve25519 output per JoinSplit, and the symmetric key used is derived from that via a KDF that takes the note index within the JoinSplit as an input. The obvious solution is to extend the ratcheting system to the symmetric keys themselves:

1. Alice and Bob use an out-of-band PQ-secure communication channel to negotiate a seed for Alice to use when sending payments to Bob.
2. Alice derives a 256-bit symmetric key and a 256-bit "key tag" from the seed using a rachet-like system, e.g. symm_key = SHA256("SymmKey" || 1 || seed) and key_tag = SHA256("KeyTag" || 1 || seed). The exact scheme for the key tag may end up being slightly different - the goal is for the key tag to be a plausible Curve25519 public key.
3. Alice creates her first JoinSplit to Bob, encrypts the output note for Bob using the derived symmetric encryption key, and sets e_pk to the derived key tag. She then increments her ratchet (so the next note she sends will use e.g. symm_key = SHA256("SymmKey" || 2 || seed) and key_tag = SHA256("KeyTag" || 2 || seed)).
4. When scanning the block chain, Bob first checks the e_pk to see if it is a key tag derived from one of his seeds. If it is, he uses the corresponding symmetric key to decrypt and checks whether the resulting note is valid (by checking the commitment). If it is invalid, Bob assumes the e_pk just collided with his key tags, and proceeds as normal with trial decryption of the note ciphertext with all his z-addresses. If it is valid, Bob increments his ratchet.

[daira]

What's the advantage of this over PQ-securely negotiating a shared-secret address, and then using the current note encryption with it?

The shared-secret address approach has the advantage that it's still conventionally secure if the PQ-confidentiality of the secure channel fails, which given the current state of cryptanalysis (due to their being new crypto) of candidates for PQ-secure key exchange, might be a very good idea.

[str4d]

@daira could you elaborate on the shared-secret address you are thinking of? I can imagine two different strategies consistent with that name; one of them is the proposal I outlined above (where the shared secret is roughly equivalent to the output of Curve25519 in our current note encryption), and the other one is PQ-insecure because it still uses Curve25519 (where the shared secret is the z-key).

[daira]

Instead of negotiating a shared symmetric key on the PQ-secure channel, the payee generates a new (spending key, payment address) and sends the payment address to the payer on the PQ-secure channel. That's all there is to it; everything else is the same as the current usage of Zcash. This is PQ-secure as explained in #570 (comment) , but if the PQ channel confidentiality fails, it devolves to classical security (unlike the scheme in #805 (comment) which fails completely in that case).

(Note that PQ-authentication is easier than PQ-confidentiality because you can use a hash-based signature, of which there are candidates such as SPHINCS that are already practical and proven secure based on quite weak assumptions.)

[zookozcash]

https://z.cash/support/faq.html#quantum-computers

[daira]

A commitment based on a SNARK-friendly cipher such as MiMC could be post-quantum hiding and binding, and also practically efficient (even more so than Pedersen commitments).

However I think we're likely to go with Pedersen commitments for Sapling despite their failure to be post-quantum binding, because:

• we have more assurance of their classical security (than, say, MiMC);
• it wouldn't really affect post-quantum soundness because we've already lost on that until we have a post-quantum sound zk-SNARK;
• they are statistically (and therefore post-quantum) hiding, so we don't lose on privacy relative to Sprout, at least not for this reason.

[daira]

@defuse wrote, before the Zcash launch:

Grover can also be used to speed up collision-finding to the cube-root rather than the square-root, e.g. http://arxiv.org/pdf/quant-ph/9705002.pdf (Høyer was my quantum computing prof and this was on the final exam!). So a quantum attacker can find a SHA256 collision in ~2^85 time and space. This impacts everywhere we rely on collision resistance of 256-bit values: the binding of the commitment scheme, faerie gold defense, etc.

I previously pointed out Bernstein's paper disputing that Brassard–Høyer–Tapp provides any cost improvement over classical parallel-rho collision search. Recently another quantum collision-search algorithm was published by André Chailloux, Marı́a Naya-Plasencia, and André Schrottenloher, with title "An efficient quantum collision search algorithm and implications on symmetric cryptography". Bernstein disputes the implication of better-than-classical efficiency of this one as well, in a comprehensive blog post.

Note that we don't claim resistance to quantum attacks on soundness / balance preservation. (Indeed, a DLP-breaking adversary can easily break soundness of the zk-SNARK, and a quantum adversary can apply the discrete-log variant of Shor's algorithm to do that.) We claim it only for privacy of transactions for which destination addresses are kept secret, and that does not, as far as I'm aware, rely on collision-resistance of any hash function in Sprout. In particular, the hiding property of SHA256Compress does not depend on collision resistance. We need to make sure that is still the case in Sapling, which is the topic of #2527, but I don't see any obstacle.

[defuse]

Another consideration for post-quantum Zcash is the proof-of-work. A Grover search could speed up finding solutions to Bitcoin's PoW, but this paper suggests Bitcoin ASICs are so fast that it will be a while before quantum computers can compete. The same paper suggests that hash-collision-based PoWs (Momentum, Equihash) are more resistant to quantum attack.

[daira]

@defuse posted a potential attack on privacy in Sapling by DLP-breaking adversaries: #2527 (comment) but it doesn't work: #2527 (comment)

[daira]

SIDH/SIKE isogeny-based cryptosystems are starting to look quite promising for post-quantum key exchange. Here's a recent paper with benchmarks: https://eprint.iacr.org/2018/1215

[daira]

I posted a comment on the forum that reflects my current understanding of Zcash's post-quantum privacy. There will be more detail in my upcoming Zcon3 presentation.

[daira]

My presentation slides are at https://github.com/daira/zcash-security , and the video is at https://www.youtube.com/watch?v=f6UToqiIdeY .

[daira]

NIST have selected some of the algorithms to be standardized in their post-quantum cryptography project: the key encapsulation mechanism CRYSTALS-Kyber (which can be used for encryption), and the signature algorithms CRYSTALS-Dilithium, FALCON, and SPHINCS+.

This comment does not consider the signature algorithms because we don't need them: it would be better (smaller transactions, no stronger security assumptions, and simpler) IMHO to do the spend authorization entirely in the SNARK, especially if the SNARK has recursion so that the spend authorizations can be folded into a single proof. (There is some issue as to whether hardware wallets could create a proof, but I am optimistic that could be resolved.)

Suppose that we needed or wanted to make Zcash fully quantum-secure using only existing algorithms. An attractive option would be to use Plonky2 for the zk-SNARK and CRYSTALS-Kyber (I'll just call it Kyber below) for the note encryption.

Plonky2's proof sizes are larger than Halo 2's — about 45 KiB. This would be within the range of practicality if, by use of recursion, we only needed one proof per transaction (or one proof per aggregate, per #4946).

Kyber has several sets of security parameters, and we would need to decide which provides adequate security. That page says:

For users who are interested in using Kyber, we recommend the following:

• Use Kyber in a so-called hybrid mode in combination with established "pre-quantum" security; for example in combination with elliptic-curve Diffie-Hellman.
• We recommend using the Kyber-768 parameter set, which—according to a very conservative analysis—achieves more than 128 bits of security against all known classical and quantum attacks.

Kyber-768 has secret key size 2400 bytes, public key size 1184 bytes, and ciphertext overhead (for the Kyber-specific part) 1088 bytes.

The secret key size is not a significant problem. The public key size might be, since that would have to go into an address in the current design. The ciphertext overhead is much smaller than a Plonky2 proof, and is per-recipient (it need not be duplicated for more than one output to the same recipient, but this is at the expense of leaking the number of recipients).

The key generation and encryption performance of Kyber is more than adequate. The decryption performance is 53156 cycles on Haswell using AVX2; at 3.5 GHz this would be ~15 microseconds per potential transaction recipient, which is unlikely to be a bottleneck (actually the Diffie–Hellman part of the hybrid-mode encryption is likely to be more expensive).

[daira]

Note that a sensible stepping stone would be to switch to Kyber first, leaving a switch to a post-quantum SNARK for later. That would be sufficient for post-quantum privacy (because Halo 2 already has post-quantum zk, even though it does not have post-quantum knowledge soundness).

[daira]

I wrote in August 2019:

SIDH/SIKE isogeny-based cryptosystems are starting to look quite promising for post-quantum key exchange. Here's a recent paper with benchmarks: https://eprint.iacr.org/2018/1215

A recent, unexpectedly severe break of SIDH has cast significant doubt on isogeny-based systems.

[RorschachRev]

@daira Aside from the NIST selection, was there any reason to discredit NTRU Prime from PQ ZCash? Also this paper https://eprint.iacr.org/2019/1146 caused US MIL to switch to AES256 as a minimum, because of Grover attacks against AES. They included Q# source code and did some clever tricks, so I don't think symmetric is as safe as many people claim but I would trust DJB to evaluate.