Im all for building in crypto-agality. Cyber-orchard is a cool concept and I think its a good balance of forward / post privacy. The restriction on outputs recipients is interesting. Given the recent discussion around pay per output in the forum, any tx over the threshold would be potentially cheaper as a smaller transaction. The would result in more single recipient tx I think.
I agree its still too early to pick a winner though(kyber vs dillithium vs …) for full post Quantum privacy. At the very least, this requires the NIST process of vetting and selecting to complete.
Ethereum jumped the gun and selected keccak 256 as their hash algo before the sha3 competition ended and it has been an annoying tech debt.
I don’t think end users care about address lengths. An end user applications abstract this away, most wallets use qr codes or copy paste. Is the concern around length from a technical pov?
I didn’t say that; actually I think it would be fine to pick Kyber now, at least if it weren’t for the address length obstacle. I absolutely do think end-users care about address length; personally I check every character of the address shown on my Trezor for every transaction. Unified addresses help with this somewhat, because we designed them so that it should be secure to check the first 20 characters regardless of overall length.
Note that Kyber is the only encryption algorithm that NIST have said they will standardize so far. (CRYSTALS-Dilithium, Falcon, and SPHINCS+ are signature algorithms.) Kyber is a refinement of New Hope, and is as well-understood at this point as post-quantum encryption algorithms get.
I don’t propose to build in arbitrary algorithm agility. The current ECDL-based scheme and hybrid Kyber would be the only alternatives.
CRYSTALS-Dilithium, LMS, or XMSS for signatures, to be more precise. I don’t know why they’re not also allowing SPHINCS+ in CNSA 2.0; SPHINCS+ is the algorithm I’d recommend for applications that can handle its signature size. (Declaration of interest: I’m a co-designer of SPHINCS.)
Would it make sense to have a ZOMG RFP for a team to look more deeply into a Quantum-secure Orchard protocol? I would assume that the Arborist team at the ECC has their hands full and I get the impression that they do want this kind of work to be done.
Do you know anyone who would like to apply for such a grant, @Mikerah? I think it’ll be good to have professionals look into this more deeply and recommend the course of actions that the Zcash community could take to improve Zcash. I don’t think the questions posed here is urgent but I can sympathize with those who think otherwise.
I don’t have anyone off the top of my head hence the suggestion to have an RFP. That way, with an RFP, you can solicit newcomers to Zcash and give them a chance to contribute to the community. I would expect a wide range of potential teams ranging from academic teams to industrial teams.
With a fully-shielded Zcash transaction, the sender, recipient and amount are fully encrypted and completely private . Please note that fully transparent Zcash transactions are similar to BTC in that the sender, receiver and amount are visible on a public blockchain.
While I wouldn’t object to external help, I’d like to point out that:
Between me, Ying Tong, Deirdre Connolly, and Zooko (apologies to anyone else I missed), we already have more post-quantum cryptographic engineering expertise “in house” at ECC and ZF than almost any likely external team;
The obstacles to a post-quantum private Zcash aren’t really in the post-quantum crypto itself. They’re in things like how to do address registration without losing privacy, in order to mitigate the large address size. That’s squarely a core protocol responsibility.
Realistically, I think ECC Core Team’s capacity is going to be the main bottleneck to making Zcash post-quantum-private (or post-quantum secure in other ways) whether an external team helps or not.
Not really, because I think that the most likely path to improving quantum security is that we take into account address registration when making other protocol changes, in order to make it a feasible upgrade.
That SecurityWeek article is terrible; just awful reporting. It looks like they’ve uncritically let some scam-artist company (Incrypteon) pick a random legitimate paper on side-channel analysis of a PQ encryption algorithm, and use it to hawk some bullshit so-called “one-time pad” snake oil.
Okay, so first the potentially headline-grabbing stuff about “AI breaking post-quantum encryption”. It has not, for Kyber or otherwise. We shouldn’t be surprised by the existence of side-channel attacks on PQC, because:
Any implementation of an encryption algorithm, whether it is plausibly post-quantum or not and whether it is public key or not, is potentially subject to side-channel analysis. The post-quantum aspect is purely about whether a quantum computer could break the encryption given the public key (if any), the ciphertext, and potentially partial known plaintext; not about whether you can break it given side-channel information collected from the encryption. We should expect to see the same kind of evolution of side-channel attacks and mitigations for PQC implementations as we do for any other crypto.
The paper’s introduction cites 17 relevant papers on side-channel analysis and mitigation just for Kyber and the similar algorithm Saber. The attention to this for ring LWE/LWR-based algorithms has been partly due to their potential for standardisation and widespread use, and partly because they have a structural rotation property that has been used in the attacks.
Using deep learning AI for this is a standard technique used in many recent papers. It works well when you want to find the patterns in the output of the side channel without doing a lot of manual work analysing the specific encryption implementation. It’s not that AI is doing anything magically different from a non-AI-based approach; it’s just that it’s less cryptanalysis effort to do it this way (at greater computational cost, so it’s suited to attacks that are limited by available data rather than by computation).
That said, it is impressive to be able to do a practical message recovery attack on a 5th-order masked implementation. I’ve always been quite skeptical about masking as a side-channel mitigation, and this suggests a rethink is in order about how much it can help, in general rather than just for Kyber.
Note that if the sender is anonymous, that significantly reduces the applicability of any side-channel attack. You can’t break encryption by observing side channels if you don’t know who to observe, unless you are able to closely observe a large proportion of potential senders simultaneously, or you already have a guess that you are trying to confirm.
Quantum signatures must be added or modified immediately, and the development team must immediately discuss and choose to change the signature!
Starting in 2024, the Department of Commerce and the Department of Homeland Security may begin to publish approved algorithms that are easily cracked by quantum computers and are ready to be phased out on an annual basis.
The latest “Quantum Computer Development Status” report from the German BSI in August 2023 has this picture on page 61. This picture and the description on page 61 make it very clear:
ECC256 is the easiest to crack. When ECC256 is cracked, even RSA1024 is temporarily safe.
Elliptic Curve Signature ECC,
It is the easiest algorithm to be cracked by quantum computers!
If the pqc signature is replaced, what if the length of the signature is 40 times (dilithium), 200 times (hash), or 2000 times? How much is the efficiency reduced? Should we increase the block capacity? How much increase?
This is not a matter to be discussed, but something to be done immediately.
I’m from China. The Chinese government is constantly copying encrypted data and waiting for the quantum computer to reach a certain qubit to crack the data!
I think the zcash community is humble enough to listen and I would appreciate it if someone could relay to the founders and development team that I do not hold any zcash.
Here are some things cloudflare does
As far as the open cryptographic community is aware, there are no established cryptographic algorithms —in particular not the ones used by Zcash— for which we have any evidence that they are currently “easily cracked by quantum computers” or in imminent danger of being so. I don’t think that NIST has any such evidence either, despite their links to the NSA.
The first link you gave is to a project that intends to promote the use of algorithms that plausibly resist attacks using quantum computers. Such attacks are all currently theoretical. (Incidentally, one of those algorithms, SPHINCS+, is based in part on my work.) Obviously, quantum attacks against those algorithms are relevant in that there would be no point in promoting an algorithm that claims to resist them but doesn’t.
The second link, the Whitehouse memorandum, does not mention plausibly post-quantum cryptography [*] or quantum attacks at all. It refers to NIST’s poorly named “Zero-Trust Architecture” (pdf); that document also has no reference to anything quantum.
The third document by the German Federal Office for Information Security is very thorough. However, I take issue with your summary of its conclusions. For a start, RSA1024 is feasibly crackable now using classical attacks. Remember that a quantum attack can make use of any classical algorithm; it makes no sense to require that it use a quantum computer (either for the whole attack or any part of it) just for the sake of using one.
For ECC256, the document points out Ekerå’s approach, and is correct in saying that “Compared to Shor’s original algorithm, optimistically, we may hope that Ekerå’s approach approximately halves the number of gates and the circuit depth.” This constant-factor improvement comes nowhere close to making ECC256 practically breakable as far as we know, and neither do any of the other algorithms mentioned.
How could we possibly do that without discussing it? In any case, I’ll try to answer these questions.
In order to make Zcash secure for quantum attacks against balance preservation, we primarily need a plausibly post-quantum [PPQ] zk-SNARK. Signatures are a secondary consideration: we don’t strictly need signatures at all to make Zcash work. (The functionality of a signature is a special case of that of a zk proof. Zcash Sapling and Orchard use signatures only for efficiency. In a post-quantum setting, the use of a specialized plausibly post-quantum signature scheme could at best only improve efficiency by a small constant factor.)
The currently available PPQ-zk-SNARK with the smallest proofs and best efficiency for this usage is, I believe, Plonky2. (The field is progressing very quickly and that statement is likely to be outdated in less than a year, if it is not already, which is why “just do it now” is not really a practical approach.) I do not know what the size of an Orchard-like circuit would be in Plonky2, but its proofs are likely to be at least 10 times larger than Orchard proofs, which would make block sizes large if proofs were per-transaction. I suspect that the most practical approach would be to use recursive proofs to aggregate transactions, but estimating the cost of that would require much more time than I have to write this comment. (I see that I partially addressed it here: Fully post-quantum Zcash · Issue #805 · zcash/zcash · GitHub )
[*] I always use the “plausibly” modifier and I recommend that others do too. It is not a good idea to use terminology that assumes the conclusion.
ZKSNARk is based on elliptic curve signatures. Elliptic curve signatures may be officially announced by the United States in 2024 and will end in a specific number of years in the future and will no longer be used.
Zero-knowledge proofs are very important! It is a privacy-protecting protocol, but quantum-resistant digital signature cracking is the core security.
My main discussion is that zero-knowledge proofs need to be built on a digital signature that is quantum-resistant.
By 2025—within 12 months—the US government’s encryption standards will mandate that all companies selling solutions that use encryption of any kind to the U.S. government must transition to post-quantum encryption per Commercial National Security Algorithm Suite 2.0 (CNSA 2.0.)
I hope the zcash team will pay attention to the development of quantum signatures. This is the main reason why I come to the community. I am not a cryptographer. I am very grateful to the team for answering some questions. I won’t worry about some issues anymore.
That’s not how it really works. The US government is free to say that specific algorithms can’t obtain certification to be used in new government contracts, and have to be phased out for government use. They can’t control the private sector or open protocols. In practice, some new protocols will use PPQ crypto, some won’t, and the vast majority of existing systems will continue to do whatever they did before, unless and until there is some more alarming development in quantum algorithms or hardware.
It would certainly be possible to work on a post-quantum Zcash-like protocol. But with my R&D Engineering manager hat on, it isn’t one of the candidate R&D topics to focus on for Electric Coin Company, and in the absence of any pressing security concern, other things that have been suggested have a lot more “bang for the buck”.
With my ZIP Editor hat on I have no opinion, and personally I think it would be better to wait until PPQ-zk-SNARKs are a bit more mature and efficient (which will happen relatively soon).