Towards Scalable Threshold Cryptosystems
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), v...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129845 |
| _version_ | 1826215913327689728 |
|---|---|
| author | Tomescu, Alin Chen, Robert Zheng, Yiming Abraham, Ittai Pinkas, Benny Gueta, Guy Golan Devadas, Srinivas |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Tomescu, Alin Chen, Robert Zheng, Yiming Abraham, Ittai Pinkas, Benny Gueta, Guy Golan Devadas, Srinivas |
| author_sort | Tomescu, Alin |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:39:00Z |
| format | Article |
| id | mit-1721.1/129845 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:39:00Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1298452022-10-03T07:26:45Z Towards Scalable Threshold Cryptosystems Tomescu, Alin Chen, Robert Zheng, Yiming Abraham, Ittai Pinkas, Benny Gueta, Guy Golan Devadas, Srinivas Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2021-02-19T20:16:13Z 2021-02-19T20:16:13Z 2020-07 2020-05 2020-12-10T17:44:30Z Article http://purl.org/eprint/type/ConferencePaper 9781728134970 https://hdl.handle.net/1721.1/129845 Tomescu, Alin et al. "Towards Scalable Threshold Cryptosystems." 2020 IEEE Symposium on Security and Privacy, May 2020, San Francisco, California, Institute of Electrical and Electronics Engineers, July 2020. © 2020 IEEE en http://dx.doi.org/10.1109/sp40000.2020.00059 2020 IEEE Symposium on Security and Privacy Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Tomescu, Alin Chen, Robert Zheng, Yiming Abraham, Ittai Pinkas, Benny Gueta, Guy Golan Devadas, Srinivas Towards Scalable Threshold Cryptosystems |
| title | Towards Scalable Threshold Cryptosystems |
| title_full | Towards Scalable Threshold Cryptosystems |
| title_fullStr | Towards Scalable Threshold Cryptosystems |
| title_full_unstemmed | Towards Scalable Threshold Cryptosystems |
| title_short | Towards Scalable Threshold Cryptosystems |
| title_sort | towards scalable threshold cryptosystems |
| url | https://hdl.handle.net/1721.1/129845 |
| work_keys_str_mv | AT tomescualin towardsscalablethresholdcryptosystems AT chenrobert towardsscalablethresholdcryptosystems AT zhengyiming towardsscalablethresholdcryptosystems AT abrahamittai towardsscalablethresholdcryptosystems AT pinkasbenny towardsscalablethresholdcryptosystems AT guetaguygolan towardsscalablethresholdcryptosystems AT devadassrinivas towardsscalablethresholdcryptosystems |