Back to Search
Start Over
Towards Scalable Threshold Cryptosystems
- Source :
- IEEE Symposium on Security and Privacy, arXiv
- Publication Year :
- 2020
- Publisher :
- IEEE, 2020.
-
Abstract
- The resurging interest in Byzantine fault tolerant systems will demand more scalable threshold cryptosystems. Unfortunately, current systems scale poorly, requiring time quadratic in the number of participants. In this paper, we present techniques that help scale threshold signature schemes (TSS), verifiable secret sharing (VSS) and distributed key generation (DKG) protocols to hundreds of thousands of participants and beyond. First, we use efficient algorithms for evaluating polynomials at multiple points to speed up computing Lagrange coefficients when aggregating threshold signatures. As a result, we can aggregate a 130,000 out of 260,000 BLS threshold signature in just 6 seconds (down from 30 minutes). Second, we show how "authenticating" such multipoint evaluations can speed up proving polynomial evaluations, a key step in communication-efficient VSS and DKG protocols. As a result, we reduce the asymptotic (and concrete) computational complexity of VSS and DKG protocols from quadratic time to quasilinear time, at a small increase in communication complexity. For example, using our DKG protocol, we can securely generate a key for the BLS scheme above in 2.3 hours (down from 8 days). Our techniques improve performance for thresholds as small as 255 and generalize to any Lagrange-based threshold scheme, not just threshold signatures. Our work has certain limitations: we require a trusted setup, we focus on synchronous VSS and DKG protocols and we do not address the worst-case complaint overhead in DKGs. Nonetheless, we hope it will spark new interest in designing large-scale distributed systems.
- Subjects :
- Authentication
Computer science
business.industry
020206 networking & telecommunications
Cryptography
02 engineering and technology
Cryptographic protocol
Distributed key generation
Computer engineering
0202 electrical engineering, electronic engineering, information engineering
Key (cryptography)
Overhead (computing)
Cryptosystem
020201 artificial intelligence & image processing
Verifiable secret sharing
Communication complexity
business
Time complexity
Byzantine fault tolerance
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- 2020 IEEE Symposium on Security and Privacy (SP)
- Accession number :
- edsair.doi.dedup.....13e76892d831305bd9d4572905a381c6