Is Zcash actually quantum private?

[str4d]

@Zchurn

Based on some brief Internet searching of “google’s quantum computer”, 2^88 (ops per second?) seems not much work at all for an attacker - very quantum vulnerable given the progress being made in QC. Maybe I’m wrong about how many physical qubits are actually needed, but Google’s existing quantum computer has 72 physical qubits - I see that 72 qubit QC means 2^72 values at once. (Per second?) So this means Goog’s QC can already crack any shielded ZEC tx’s recipient address, output value, or memo, in just 18 hours (2^88/2^72/60/60)? Hardly the future, this is today.

Side-note: what I meant by 2^{88} work is 2^{88} discrete-log-breaking quantum operations, not 2^{88} classical operations. The qubits in that scenario are already “in use” finding s given P and B such that P = [s] B. As I estimated further down in the thread you reference:

@str4d

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 2^{32} core years to have a 50% chance of finding the ivk for a single address.

That being said:

@Zchurn

All the above is contradicted by this very specific comment from @str4d (my emphasis added):

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

@daira and I went back and stared at my comment, and I cannot reproduce my thought process I think when writing my comment I believed that the adversary could figure out ivk from the on-chain data in 2^{88} work, but I now cannot see any pathway via which they could achieve this.

The adversary can take epk from each output and guess esk, landing on the correct one with 2^{88} work. However, they can’t do anything with this information, because without knowledge of pk_d they can’t derive the shared secret in order to confirm their guess against the note ciphertext.

So what can a quantum adversary obtain? Here’s what @daira and I sketched out (these are rough notes, and the “better than” section is my own):

Scenario

Let’s assume we have:

• An efficient discrete-log-breaking adversary (quantum or otherwise).
• Full history of the Zcash block chain (the block data).
• No knowledge of any shielded addresses (other than those generated by the attacker).

This means the following information is available:

• Spends:
  • nf
  • The anchor, which limits the set of candidate outputs.
  • rk
  • spendAuthSig (I’m not sure what this could be used for)
• Outputs:
  • epk
  • cm*
  • encCiphertext, which can be used to test a candidate sharedSecret.
  • outCiphertext, which can be used to test a candidate ock.

The following information is available but useless:

• cv (these are Pedersen commitments, which are perfectly hiding).
• Proofs (we use proving systems with either perfect or statistical zero knowledge).

Quantum brute-force decryption

Given a target shielded output, we can guess ivk and then trial-decrypt with it, using the AEAD ciphertext as a confirmation. With Grover’s algorithm this requires around 2^{127} work.

Similarly, we can use Grover’s algorithm on ock. This requires 2^{128} work (because ock is a 256-bit binary value), but it might be more concretely efficient because trial decryption does not require performing a scalar mul (for KA.Agree). The actual confirmation would likely be:

• Perform a single ChaCha20 block to decrypt outCiphertext.
• Test if the candidate plaintext contains esk as a valid scalar and pk_d as a valid curve point.
• Check the Poly1305 MAC, which requires processing 4 16-byte Poly1305 blocks.

Neither of these is a “break”, because our claimed security level is 2^{125}.

Better than brute-force decryption

This is the scenario I was mistaken about in my earlier comment.

The adversary needs to obtain either ivk or ock more efficiently than brute force.

• ock can’t be improved upon, because it is derived from the 256-bit binary value ovk via a hash function, so our DL-breaking adversary has nothing to work with (and to my knowledge there are no known algorithms that give any quantum adversary an advantage for breaking symmetric primitives).
• ivk is used in the scalar multiplication pk_d = [ivk] g_d, where d, pk_d is the recipient’s address, and g_d is derived from d via a common public algorithm. The DL-breaking adversary doesn’t have the recipient address, and thus can’t recover ivk that way.
• ivk is derived from the full viewing key components (ak, nk) (and rivk in Orchard), so if the adversary could extract these components from the transaction, then they’ve learned the full viewing key and can trivially decrypt outputs. However:
  • ak is linked to rk via rk = [\alpha] ak = [\alpha \cdot ask] G, where G is the spending key base. The adversary knows rk and G, and so can learn rsk = \alpha \cdot ask. But \alpha is uniformly random, and acts as a blinding factor on ask; a specific rsk could correspond to any ask.
  • ak, nk, rivk, and \alpha are private inputs to the circuit, so cannot be extracted from the proof.

Linking outputs without decrypting

What if we weaken the adversary’s goal: now instead of being able to decrypt a shielded output, they only want to know if two shielded outputs were sent to the same address. The rough outline of the attack strategy is:

1. Take two epk values from on-chain outputs (epk_1 and epk_2).
2. Determine that they correspond to the same g_d (even if the precise base g_d is not learned).
3. As long as there are fewer than 2^{44} outputs on-chain, then with high probability, two outputs that correspond to the same g_d were sent to the same address.
   • This will always be the case for the current shielded protocols, as the note commitment trees limit each protocol to at most 2^{32}.

The question is whether we can build a successful gadget for step 2. I don’t know if this is possible, but it would maybe looks something like:

Pick an arbitary base g' (not necessarily a valid g_d) and use the DL-breaking adversary to find the discrete logs of epk_1 and epk_2 with respect to g' (say, a and b).

If the outputs were indeed sent to the same address, then g' = [k] g_d for some scalar k, and:

\begin{aligned} epk_1 = [a] g' = [a \cdot k] g_d = [esk_1] g_d \\ epk_2 = [b] g' = [b \cdot k] g_d = [esk_2] g_d \end{aligned}

The adversary can therefore cancel out k to get:

a \cdot b^{-1} = esk_1 \cdot esk_2^{-1}

If the outputs were not sent to the same address, then g' = [k_1] g_{d,1} = [k_2] g_{d,2} for some independent scalars (k_1, k_2), and:

\begin{aligned} epk_1 = [a] g' = [a \cdot k_1] g_{d,1} = [esk_1] g_{d,1} \\ epk_2 = [b] g' = [b \cdot k_2] g_{d,2} = [esk_2] g_{d,2} \end{aligned}

and the adversary would instead obtain:

a \cdot b^{-1} = esk_1 \cdot esk_2^{-1} \cdot k_1 \cdot k_2^{-1}

The problem now is figuring out what to do with this; esk values are uniformly random, as will be k_1 \cdot k_2^{-1}.

---

Anyway, that’s just some rough thoughts, but I hope it’s helpful!