Long term privacy

If all of the cryptography that ZCash uses (RSA, discrete log, etc.) is broken, can past shielded transactions be revealed (i.e., senders, recipients, amounts, etc.)? Or does the privacy persist even after the cryptography if broken?

It just came to my attention that is not true for Monero. If discrete log is broken, one can go back and retroactively deanonymize all of the transactions.

6 Likes

Hello, and welcome to the forums!

I assume your question is motivated by large-scale quantum computers who indeed could break discrete logarithm/RSA (and breaking discrete logarithm is enough to, say, find out the correct key image in Monero).

In Zcash, if recipient address is kept secret between the sender and recipient, the payments have forward-secrecy against quantum attackers (under plausible conjectures). See Post-quantum Zcash GitHub issue. There might be other ways how privacy can be compromised (e.g. if there is an efficient attack breaking the relevant hash functions) but these other assumptions are not known to be quantum-vulnerable.

14 Likes

in the Discord discussion where I found this forum thread (and which I hope you’ll copy here :slightly_smiling_face:), @str4d was unsure whether this is the case. (unless your plausible conjectures include that a quantum adversary can’t gain advantage in “singe-target many-base situations”.)

also note that in practice, addresses largely won’t remain secret. even if the parties take the effort to use end-to-end encrypted channels (Element, Signal, Threema, etc.) instead of regular channels (email, Twitter DM, etc.) to communicate the address, the encryption of the former is the same encryption a quantum adversary can break. right now all the adversary needs to do is capture internet traffic and store it until they gain quantum computational capabilities. once that happens, they can recover Zcash addresses from the traffic, and combine this knowledge with the contents of the Zcash blockchain to recover transaction information. according to str4d (see the above link), even with this they can only recover the output note value and memo field content of incoming transactions, which is insufficient for deanonymizing the transaction graph.

but if you want to make the work of a future quantum adversary harder, not publishing addresses is not enough. you have to communicate addresses either:

  • in person/offline, or
  • through an online channel that’s end-to-end encrypted with post-quantum encryption (almost non-existent for now).
2 Likes

@str4d answered this in Discord (copied with permission):

A good place to start is ZIP 310: Security Properties of Sapling Viewing Keys which documents the privacy properties of Sapling Full Viewing Keys.
But to short-cut the process: we rely on ECHD to derive the encryption key that is used by the recipient to decrypt an incoming note, so a discrete-log-breaking adversary can compromise it and recover ivk. Once they have that, the adversary can scan the chain and recover the same information that someone with the incoming viewing capability could.
For a known payment address, it’s trivial (a single DL break). For an unknown payment address, it would naively require 2^88 work to figure out which diversified base ( g_d ) is the one used by a specific note. IDK if there are any quantum algorithms that help speed up the singe-target many-base situation.
In any case, all the adversary learns is the recipient address, output note value, and the contents of the memo field. Given a single transaction, they do not learn the sender address or input note value.
Also, even after learning the received notes, they wouldn’t know when those notes became spent, because they’d need to obtain nk for that, and ivk is derived from nk via a commitment scheme. Sapling uses BLAKE2s (so would require a preimage attack), while Orchard uses SinsemillaCommit which is perfectly blinding.

1 Like

To be more clear, I currently think that 288 work is sufficiently high that it’s impractical for any kind of mass surveillance. If we very generously assume that each “core” / thread / whatever of a quantum adversary could break a single discrete log every 1ns, you’d be looking at around 232 core years to have a 50% chance of finding the ivk for a single address. While I said I don’t know if there are algorithms that could provide multi-base quantum speedups, I doubt they would reduce the runtime enough to make anything more than targeted breaks practical. I’d love to know more about the state of the art in this area though!

Senders and recipients can alternatively (or in addition) eliminate the data that the quantum adversary is decrypting, by transmitting the output notes out-of-band via a PQ-secure channel (which TBH could be as simple as e.g. just sending the transaction data directly between a phone and a merchant terminal), and filling the on-chain encrypted ciphertext with dummy data. The zero-knowledge proof does not enforce the correctness of the encrypted ciphertexts, partly for efficiency, and partly to enable this PQ use case. The downside is that you lose on-chain data recovery.

4 Likes