Asynchronous Consensus Without Trusted Setup or Public-Key Cryptography

This sounds interesting but the description goes way over my head. Anyone care to explain in layman's terms the concept and the non-obvious benefits?

So the protocol seems to boil down to:

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.

I noticed that Victor Shoup is an author. I recognize the name from citations in papers by cryptographer D. J. Bernstein (known for creating ChaCha20, Ed25519, qmail, and more). Shoup is referenced in over 100 pages on Bernstein's cr.yp.to domain (https://www.google.com/search?q=shoup+site%3Acr.yp.to), so my first impression is to regard this paper as potentially legit and important.

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.

One of the original authors also published a follow up with some additional details and analysis that may be of interest (still reading through it myself) [0]

[0] https://eprint.iacr.org/2024/696

Haven’t had a chance to go through this but my instant #1 question is security against malicious nodes.

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?

I was expecting multivariate polynomials, as those used to be all the rage. Just an example: https://ieeexplore.ieee.org/document/9066840

I kind of wish Git had a feature where multiple people could sign a PR or commit.

Is there a multiple signature method that isn't "just" signing other people's signatures?

Please note the Cryptology ePrint Archive is not a peer-reviewed source. The description of the paper may indicate another (peer-reviewed) publication, but this is entirely optional and not required for a submission.

Edit: Adding this as a PSA in case folks start debating the veracity assuming this has undergone review by experts.

Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure. One reason why this is significant is because existing post-quantum public key algorithms such as SPHINCS+ use much larger keys than classic public key algorithms such as RSA or ECDH.

*Edit: As other have pointed out, for SPHINCS+ it's the signature size and not the key size that's significantly larger.