Asynchronous Consensus Without Trusted Setup or Public-Key Cryptography
eprint.iacr.org
eprint.iacr.org
Consensus algorithms are important for all kinds of distributed computing problems. A simple example would be failover. If you have a leader database that replicates to 4 others, and you want another node to take over if the leader DB fails, then you need a consensus algorithm to prevent a situation where 2 different machines both think they're the new leader in a netsplit.
There are many other equivalent problems in distributed computing, from atomic transactions to "exactly once" messaging systems.
Asynchronous consensus is a model where you cannot make assumptions about the bounded nature of call timings, whereas in a synchronous model, you can assume everything is bounded.
Byzantine fault tolerance is important for security under byzantine faults, that is to say malicious actors acting deliberately against what the protocol specifies they should do.
1) Already have a leader "Dealer"
2) The leader builds a K-of-N set of shared secret keys.
3) They publish a mapping of each participant (participant_i->hash(secret_i))
4) The leader transmits each key to each participant
5) Participants exchange secrets pairwise, armed with the upfront mapping of participants->secrets
6) Select K and a k-of-N secret scheme such that a majority of participants now have a shared key
lots of the claims aren't meaningful:
- "post quantum" for example isn't a special value in this situation.
- "minimal use of cryptography" isn't relevant to practicality
- The "experimental" component doesn't meaningful contribute to the conclusion.
- No public-key-encryption really means "outsource sender identification to the network layer"
- They pretend using a system of equations to solve for a shared key isn't"cryptography".
In general the contribution of the paper reads as "offusicated". The lack of "public key cryptography" sets them up for a novel problem to solve, but it is an arbitrary handicap that doesn't provide utility.
This is academic "make up a novel and nontrivial problem and then solve it", its of utility to the process of producing grad students and publication count but not something we need to get excited about. Read it like a survey paper of the space, which it does well as.
These statements presuppose an overly expansive definition of PKI, i.e., distribution of keys for public-key encryption. A more conservative definition is PKI = availability of trustworthy publicly verifiable signatures (i.e., public-key certificates). Post-quantum signatures can be based on target collision-resistant hash functions, like XMSS.
The paper assumes pairwise private and authenticated channels. While in practice this is not necessarily a good substitute for PKI, in theory it is a strictly weaker setting.
The proofs for the security security of most of the methods of public/private key systems are weaker than "you can't reverse this hash function".
They are still robust in the face of computers that may physically exist in foreseeable futures. Elliptic Curve Encryption was adopted for being post-quantum twenty years ago and more work since then I haven't followed.
The person I am arguing with is imagining a future pessimistic beyond what most would consider reasonable.
Yeah I didn't read the full paper but from the abstract my intuition was telling me they just assumed away a bunch of things that are fairly necessary when actually implementing a BFT consensus as part of the environment.
First, an important missing point is that the protocol does not require trusted setup. In contrast, most prior works require that parties hold threshold secret keys (necessitating a trusted third-party or expensive setup procedure).
Second, a lot of effort is currently being poured into the transition to post-quantum. So having a post-quantum secure protocol is evidently valuable to a lot of people.
Third, Byzantine agreement protocols usually always assume pairwise private and authenticated communication channels. It makes sense that protocols should not need to concern themselves with the communication layer and such channels can be realized from standard cryptographic building blocks anyways. Here the paper not using any PK-cryptography is especially nice because the protocol can be layered on top without a lot of fuss—no matter what the channels are based on.
Last, this problem is far from "made up". It was an obvious (and also seemingly hard to solve) to people working in this area. Also, Byzantine agreement is a practically important problem and this is an elegant solution.
That said, my very uneducated guess is that the problem being solved here is not important for many users of distributed consensus algorithms. If you have a bunch of nodes that need to agree on something, you generally don't mind sharing a cryptographic secret among them as part of the set-up.
All such protocols, even Bitcoin and friends, break under a sufficiently costly Sybil attack. The trick with cryptocurrency is to make the attack so expensive that it requires a highly economically irrational actor.
What are the thresholds here?
Doesn't that mean that an adversary using multiple identities would be able to do so? And therefore, some means of limiting the number of identities (through public key or prior trust) would still be desirable?
What am I missing? Is this mitigated through staking?
Sybil prevention is something that I wasn't taught at school and it concerns itself with creating the pre-requisites for consensus algorithm. Given the world population, how do we establish participant set for consensus while minimizing their chance to attack. Well, maybe by requiring them to waste record-breaking amounts of stupid compute.
Is there a multiple signature method that isn't "just" signing other people's signatures?
Just adding an additional signature on top of an existing commit wouldn't carry too much info. What are you actually signing off on? Is it approval? Is it acknowledgement? And then it can be hard to sign off on something negative, like a code review that rejects.
Threshold cryptography.
Each participant generates one part of a key, and can only create one part of the signature.
You can do stuff like requiring 3 of 5 signatures parts to be valid, etc.
Edit: Adding this as a PSA in case folks start debating the veracity assuming this has undergone review by experts.
If they actually wrote their contribution in clear terms they couldn't get it published because it sounds too simple. I think they should be able able to get it published without inflating it's complexity like this. They are just reacting to a broken system.
In general, I am also not fond of this writing style. However, if one reads more papers published in this community/area, then one notices that many of them are written similarly. Since the primary audience of these papers are other researchers in the same area, they are presumably able to read past the cruft efficiently.
I also agree that academia incentivizes overselling results. In this case, however, this is a nice result and not oversold by the authors (being somewhat knowledgeable in this field).
They were never what most people thought they were. At their best, they amounted to "a few relevant experts in the same field read the paper and didn't find any blatantly obvious methodological errors."
*Edit: As other have pointed out, for SPHINCS+ it's the signature size and not the key size that's significantly larger.
SPHINCS is essentially Lamport Signatures and SPHINCS+ is essentially removing the need to store “state” by using chains of hashes and a random oracle
https://crypto.stackexchange.com/questions/54304/difference-...
I prefer tham to lattice-based methods because it seems to me that cryptographic hashes (and other trapdoor functions) are more likely to be quantum-resistant than lattices (for which an algorithm like Shor’s algorithm merely hasn’t been found yet).
> Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.
NIST Post-Quantum Cryptography Standardization > Round 3 > Selected Algorithms 2022 > Hash based > SPHINCS+: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...
SPHINCS+ is a hash based PQ Post Quantum (quantum resistant) cryptographic signature algorithm.
SPHINCS+: https://github.com/sphincs/sphincsplus
Can you elaborate on this?
(Roughly because of Grover’s algorithm, but there are algorithms that perform similarly or better on classical machines. Which is why modern hash functions have relatively large margins anyways.)