The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Simplified VSS and fast-track multiparty computations with applications to threshold cryptography
Open accessAbstract
The goal of this paper is to introduce a simple verifiable secret sharing scheme, to improve the efficiency of known secure multiparty protocols and, by employing these techniques, to improve the efficiency of applications which use these protocols.First we present a very simple Verifiable Secret Sharing protocol which is based on fast cryptographic primitives and avoids altogether the need for expensive zero-knowledge proofs.This is followed by a highly simplified protocol to compute multiplications over shared secrets.This is a major component in secure multiparty computation protocols and accounts for much of the complexity of proposed solutions.Using our protocol as a plug-in unit in known protocols reduces their complexity.We show how to achieve efficient multiparty computations in the computational model, through the application of homomorphic commitments.Finally, we present fast-track multiparty computation protocols.In a model in which malicious faults are rare we show that it is possible to carry out a simpler and more efficient protocol which does not perform all the expensive checks needed to combat a malicious adversary from foiling the computation.Yet, the protocol still enables detection of faults and recovers the computation when faults occur without giving any information advantage to the adversary.This results in protocols which are much more efficient under normal operation of the system i.e. when there are no faults.As an example of the practical impact of our work we show how our techniques can be used to greatly improve the speed and the fault-tolerance of existing threshold cryptography protocols.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Safeguarding cryptographic keys
BLAKLEY, G. R. (1979) · 1979 International Workshop on Managing Requirements Knowledge (MARK) · doi:10.1109/mark.1979.8817296 · Cited by 3,499
Protocols for secure computations
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.38 · Cited by 3,306
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Efficient signature generation by smart cards
Schnorr, C. P. (1991) · Journal of Cryptology · doi:10.1007/bf00196725 · Cited by 2,787
Protocols for secure computations
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,661
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62213 · Cited by 2,524
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing
Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_9 · Cited by 2,448
A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms
ElGamal, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39568-7_2 · Cited by 1,604
Multiparty unconditionally secure protocols
Chaum, D., Crépeau, C., & Damgard, I. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62214 · Cited by 1,544
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
Desmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_28 · Cited by 1,131
A practical scheme for non-interactive verifiable secret sharing
Feldman, P. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.4 · Cited by 1,125
Verifiable secret sharing and multiparty protocols with honest majority
Rabin, T., & Ben-Or, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73014 · Cited by 930
Self-citationA Threshold Cryptosystem without a Trusted Party
Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46416-6_47 · Cited by 777
Verifiable secret sharing and achieving simultaneity in the presence of faults
Chor, B., Goldwasser, S., Micali, S., & Awerbuch, B. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.64 · Cited by 771
On sharing secrets and Reed-Solomon codes
McEliece, R. J., & Sarwate, D. V. (1981) · Communications of the ACM · doi:10.1145/358746.358762 · Cited by 625
Adaptively secure multi-party computation
Canetti, R., Feige, U., Goldreich, O., & Naor, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.238015 · Cited by 548
Society and Group Oriented Cryptography: a New Concept
Desmedt, Y. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_8 · Cited by 433
Robust Threshold DSS Signatures
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_31 · Cited by 427
Self-citationShared generation of authenticators and signatures
Desmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_37 · Cited by 394
How to share a secret with cheaters
Tompa, M., & Woll, H. (1989) · Journal of Cryptology · doi:10.1007/bf02252871 · Cited by 388
How to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Foundations of Secure Interactive Computing
Beaver, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_31 · Cited by 277
Communication complexity of secure computation (extended abstract)
Franklin, M., & Yung, M. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129780 · Cited by 268
Non-cryptographic fault-tolerant computing in constant number of rounds of interaction
Bar-Ilan, J., & Beaver, D. (1989) · Proceedings of the eighth annual ACM Symposium on Principles of distributed computing - PODC '89 · doi:10.1145/72981.72995 · Cited by 266
Optimal algorithms for Byzantine agreement
Feldman, P., & Micali, S. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62225 · Cited by 255
Robust and Efficient Sharing of RSA Functions
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_13 · Cited by 189
Self-citationMicali, S. M., & Rogaway, P. (1991) · International Cryptology Conference · Cited by 164
Desmedt, Y. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57220-1_47 · Cited by 164
Shared Generation of Authenticators and Signatures (Extended Abstract)
Desmedt, Y., & Frankel, Y. (1991) · UCL Discovery (University College London) · Cited by 159
Robust Threshold DSS Signatures
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (2001) · Information and Computation · doi:10.1006/inco.2000.2881 · Cited by 144
Self-citationOn the Existence of Statistically Hiding Bit Commitment Schemes and Fail-Stop Signatures
Damgård, I., Pedersen, T. P., & Pfitzmann, B. (2007) · Springer eBooks · doi:10.1007/3-540-48329-2_22 · Cited by 100
Robust sharing of secrets when the dealer is honest or cheating
Rabin, T. (1994) · Journal of the ACM · doi:10.1145/195613.195621 · Cited by 98
Self-citationMultiparty Protocols Tolerating Half Faulty Processors
Beaver, D. (2007) · Springer eBooks · doi:10.1007/0-387-34805-0_49 · Cited by 86
Threshold DSS Signatures without a Trusted Party
Langford, S. K. (1995) · Lecture notes in computer science · doi:10.1007/3-540-44750-4_32 · Cited by 72
Robust and Efficient Sharing of RSA Functions
Gennaro, R., Rabin, T., Jarecki, S., & Krawczyk, H. (2000) · Journal of Cryptology · doi:10.1007/s001459910011 · Cited by 69
Self-citationWitness-based cryptographic program checking and robust function sharing
Frankel, Y., Gemmell, P. S., & Yung, M. M. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237998 · Cited by 63
Cited by
Universally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
Private Circuits: Securing Hardware against Probing Attacks
Ishai, Y., Sahai, A., & Wagner, D. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_27 · Cited by 1,073
Secret-Sharing Schemes: A Survey
Beimel, A. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20901-7_2 · Cited by 652
Constant-Size Commitments to Polynomials and Their Applications
Kate, A., Zaverucha, G. M., & Goldberg, I. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_11 · Cited by 624
Multiparty Computation from Threshold Homomorphic Encryption
Cramer, R., Damgård, I., & Nielsen, J. B. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_18 · Cited by 578
Metadata
- Authors
- Gennaro, R., Rabin, M. O., & Rabin, T.
- Venue
- Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98
- Publisher
- ACM Press
- Published
- 1998
- Pages
- 101-111
- OpenAlex
- W2036133214
- Cited by
- 464
- References
- 44
- FWCI
- 11.44
- Type
- conference paper
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.