More Web Proxy on the site http://driver.im/

Article

Introduction to Secure Computation

Author:

Ronald CramerAuthors Info & Claims

Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer School, Aarhus, Denmark, July 1998

Pages 16 - 62

Published: 17 November 2019 Publication History

Abstract

The objective of this paper is to give an elementary introduction to fundamental concepts, techniques and results of Secure Computation.

Topics covered include classical results for general secure computation by Yao, Goldreich & Micali & Wigderson, Kilian, Ben-Or & Goldwasser & Wigderson, and Chaum & CrÉpeau & Damgaard.

We also introduce such concepts as oblivious transfer, security against malicious attacks and verifiable secret sharing, and for some of these important primitives we discuss realization.

This paper is organized as follows. Part I deals with oblivious transfer and secure (general) two-party computation. Part II discusses secure general multi-party computation and verifiable secret sharing. Part III addresses information theoretic security and presents detailed but elementary explanations of some recent results in Verifiable Secret Sharing and Multi-Party Computation.

The importance of theory and general techniques often lies in the fact that the true nature of security is uncovered and that this henceforth enables to explore what is "possible at all". This then motivates the search for concrete and often specialized realizations that are more efficient. Nevertheless, many principles developed as part of the general theory are fundamental to the design of practical solutions as well.

References

[1]

W. Alexi, B. Chor, O. Goldreich and C.P. Schnorr: RSA and Rabin functions: Certain parts are as hard as the whole, SIAM Journal on Computing, 17(2):194- 209, April 1988.

Digital Library

[2]

J. Bar-Ilan and D. Beaver: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pages 201-209, Edmonton, Alberta, Canada, 14-16 August 1989.

Digital Library

[3]

D. Beaver and S. Goldwasser: Multiparty computation with faulty majority (extended announcement), In 30th Annual Symposium on Foundations of Computer Science, pages 468-473, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

Digital Library

[4]

D. Beaver: Foundations of Secure Interactive Computing, Proceedings of Crypto 91, Springer Verlag LNCS, vol. 576, pp. 420-432, Springer-Verlag, 1992.

Digital Library

[5]

D. Beaver: Secure Multiparty Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority, J. Cryptology 4:2 (1991), 75-122.

Digital Library

[6]

D. Beaver: Efficient Multiparty Protocols Using Circuit Randomization, Proceedings of Crypto '91, Springer-Verlag LNCS, 1992, 420-432.

Digital Library

[7]

D. Beaver: How to break a "secure" oblivious transfer protocol., Eurocrypt '92, volume 658 of Lecture Notes in Computer Science, pages 285-296. Springer-Verlag, 24-28 May 1992.

Digital Library

[8]

D. Beaver and S. Haber: Cryptographic protocols provably secure against dynamic adversaries, volume 658 of Lecture Notes in Computer Science, pages 307-323, Springer-Verlag, 24-28 May 1992.

Digital Library

[9]

D. Beaver: Equivocable Oblivious Transfer, Proceedings of Eurocrypt '96, Springer-Verlag LNCS 1070, 1996, 119-130.

Digital Library

[10]

D. Beaver: Adaptively Secure Oblivious Transfer, to appear in the Proceedings of Asiacrypt '98.

Digital Library

[11]

J. Benaloh, J. Leichter: Generalized Secret Sharing and Monotone Functions, Proc. of Crypto '88, Springer Verlag LNCS series, pp. 25-35.

Digital Library

[12]

M. Ben-Or, R. Canetti, O. Goldreich: Asynchronous Secure Computations, Proc. ACM STOC '93, pp. 52-61.

Digital Library

[13]

M. Ben-Or, S. Goldwasser, A. Wigderson: Completeness theorems for Non-Cryptographic Fault-Tolerant Distributed Computation, Proc. ACM STOC '88, pp. 1-10.

Digital Library

[14]

M. Bertilsson, I. Ingemarsson: A Construction of Practical Secret Sharing Schemes using Linear Block Codes, Proc. AUSCRYPT '92, LNCS 718 (1993), 67-79.

Digital Library

[15]

G. R. Blakley: Safeguarding Cryptographic Keys, Proceedings of AFIPS 1979 National Computer Conference, vol. 48, N.Y., 1979, pp. 313-317.

[16]

M. Blum: Three Applications of the Oblivious Transfer, Technical report, Dept. EECS, University of California, Berkeley, CA, 1981.

[17]

G. Brassard, C. CrÉpeau and M. Sántha: Oblivious Transfers and Intersecting Codes, IEEE Transaction on Information Theory, special issue on coding and complexity, Volume 42, Number 6, pp. 1769-1780, November 1996.

Digital Library

[18]

E. F. Brickell: Some Ideal Secret Sharing Schemes, J. Combin. Maths. & Combin. Comp. 9 (1989), pp. 105-113.

[19]

R. Canetti: Studies in Secure Multiparty Computation and Applications, Ph. D. thesis, Weizmann Institute of Science, 1995.

[20]

R. Canetti, U. Feige, O. Goldreich, M. Naor: Adaptively Secure Multi-Party Computation, Proc. ACM STOC '96, pp. 639-648.

Digital Library

[21]

R. Canetti: Security and Composition of Multiparty Cryptographic Protocols, draft, presented at the 1998 Weizmann Workshop on Cryptography, Weizmann Institute of Science, Rehovot, Israel, June 1998.

[22]

D. Chaum: Achieving Electronic Privacy, Scientific American, August 1992.

[23]

D. Chaum, I. Damgård and J. vd Graaf: Multi-Party Computations Ensuring Secrecy of Each Party's Input and Correctness of the Output, Proceedings of Crypto'87 volume 293 of Lecture Notes in Computer Science, pages 87-119, 16-20, Springer-Verlag, 1988.

Digital Library

[24]

D. Chaum, C. CrÉpeau, I. Damgård: Multi-Party Unconditionally Secure Protocols, Proc. of ACM STOC '88, pp. 11-19.

Digital Library

[25]

D. Chaum: Transaction Systems to make Big Brother Obsolete, Communications of the ACM, vol. 28, no. 10, October 1985, pp. 1030-1044.

Digital Library

[26]

D. Chaum: Untraceable Electroic Mail, Return Addresses, and Digital Pseudonyms, Communications of the ACM, vol. 24, no. 2, 1985, pp. 84-88.

Digital Library

[27]

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch: Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, Proc. IEEE FOCS '85, pp. 383-395.

Digital Library

[28]

R. Cramer, I. Damgård and U. Maurer: Span Programs and Secure Multi-Party Computation, draft, presented at the 1998 Weizmann Workshop on Cryptography, Weizmann Institute of Science, Rehovot, Israel, June 1998. Completely revised version available from http://www.inf.ethz.ch/personal/cramer.

[29]

R. Cramer, I. Damgård: Zero Knowledge for Finite Field Arithmetic or: Can Zero Knowledge be for Free?, Proc. of CRYPTO'98, Springer Verlag LNCS series.

Digital Library

[30]

R. Cramer, I. Damgård, S. Dziembowski, M. Hirt and T. Rabin: Efficient Multi-Party Computations with Dishonest Minority, Proceedings of Eurocrypt '99, Springer Verlag LNCS. To appear.

[31]

R. Cramer, R. Gennaro and B. Schoenmakers : A Secure and Optimally Efficient Multi-Authority Election Scheme, Proceedings of EUROCRYPT '97, Konstanz, Germany, Springer Verlag LNCS, vol. 1233, pp. 103-118, May 1997. Journal version: Eur. Trans. Telecom, Vol. 8, No. 5, Sept./Oct. 1997.

Digital Library

[32]

R. Cramer, M. Franklin, B. Schoenmakers, M. Yung: Secure Secret Ballot Election Schemes with Linear Work, Proceedings of EUROCRYPT '96, Zaragoza, Spain, Springer Verlag LNCS, vol. 1070, pp. 72-83, May 1996.

Digital Library

[33]

C. CrÉpeau: Equivalence between two flavours of oblivious transfers (abstract), Proceedings of Crypto '87, volume 293 of Lecture Notes in Computer Science, pages 350-354. Springer-Verlag, 1988.

Digital Library

[34]

C. CrÉpeau: Correct and Private Reductions among Oblivious Transfers PhD thesis, Department of Elec. Eng. and Computer Science, Massachusetts Institute of Technology, 1990.

[35]

C. CrÉpeau, J.vd. Graaf and A. Tapp: Committed Oblivious Transfer and Private Multiparty Computation, proc. of Crypto 95, Springer Verlag LNCS series.

Digital Library

[36]

C. CrÉpeau and J. Kilian: Achieving oblivious transfer using weakened security assumptions, In 29th Symp. on Found. of Computer Sci., pages 42-52. IEEE, 1988.

Digital Library

[37]

C. CrÉpeau and L. Salvail: Oblivious Verification of Common String, CWI Quarterly (Special Issue on Cryptography), 8 (2), June 1995.

[38]

A. De Santis, Y. Frankel, Y. Desmedt and M. Yung: How to Share a Function Securely, Proceedings of 26th Annual ACM STOC, pp. 522-522, 1994.

Digital Library

[39]

Y. Desmedt: Threshold Cryptography, European Transactions in Telecommunication, 5 (1994), 449-457.

[40]

S. Even, O. Goldreich and A. Lempel: A Randomized Protocol for Signing Contracts, Communications of the ACM, vol. 28, 1985, pp. 637-647.

Digital Library

[41]

R. Fagin, M. Naor and P. Winkler: Comparing Common Secret Information without Leaking it, Communications of the ACM, vol 39, May 1996, pp. 77-85.

Digital Library

[42]

P. Feldman: A practical scheme for non-interactive verifiable secret sharing, Proceedings of 28th Annual Symposium on Foundations of Computer Science, pages 427-437, Los Angeles, California, 12-14 October 1987. IEEE.

Digital Library

[43]

P. Feldman, S. Micali: An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM J. Comp. Vol. 26, No. 4, pp. 873-933, August 1997.

Digital Library

[44]

M. Fischer, S. Micali and C. Rackoff: A Secure Protocol for Oblivious Transfer (extended abstract), presented at Eurocrypt '84. First published in Journal of Cryptology, 9(3):191-195, Summer 1996.

Digital Library

[45]

M. Fitzi and U. Maurer: Efficient Byzantine Agreement Secure Against General Adversaries, Proceedings of 12th International Symposium on Distributed Computing (DISC '98).

Digital Library

[46]

Y. Frankel, P. Gemmell, P. MacKenzie, M. Yung: Optimal-resilience proactive public-key cryptosystems, Proceedings of 38th Annual Symposium IEEE FOCS pages 384-393, 1997.

Digital Library

[47]

M. Franklin: Complexity and Security of Distributed Protocols, Ph.D. thesis, Columbia University, New York, 1992.

Digital Library

[48]

Z. Galil, S. Haber and M. Yung: Cryptographic computation: Secure fault-tolerant protocols and the public-key model, Proceedings of Crypto '87, volume 293 of Lecture Notes in Computer Science, pages 135-155, 16-20 August 1987. Springer-Verlag, 1988.

Digital Library

[49]

J.A. Garay and Y. Moses: Fully polynomial Byzantine agreement for n ¿ 3t processors in t + 1 rounds, SIAM Journal on Computing, 27(1):247-290, February 1998.

Digital Library

[50]

R. Gennaro: Theory and Practice of Verifiable Secret Sharing, Ph.D.-thesis, MIT, 1995.

Digital Library

[51]

R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin: Robust and efficient sharing of RSA functions, Proceedings of CRYPTO '96, volume 1109 of Lecture Notes in Computer Science, pages 157-172, 18-22, 1996.

Digital Library

[52]

R. Gennaro, M. Rabin, T. Rabin, Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography, Proceedings of ACM PODC'98.

Digital Library

[53]

O. Goldreich, S. Micali and A. Wigderson: Proofs that Yield Nothing but the Validity of the Assertion, and a Methodology of Cryptographic Protocol Design, Proceedings IEEE FOCS'86, pp. 174-187.

Digital Library

[54]

O. Goldreich, S. Micali and A. Wigderson: How to Play Any Mental Game or a Completeness Theorem for Protocols with Honest Majority, Proc. of ACM STOC '87, pp. 218-229.

Digital Library

[55]

O. Goldreich and R. Vainish: How to Solve any Protocol Problem: An Efficiency Improvement, Proceedings of Crypto'87, volume 293 of Lecture Notes in Computer Science, pages 73-86, 16-20 August 1987.

Digital Library

[56]

O. Goldreich: Modern Cryptography, Probabilistic Proofs and Pseudorandomness, ISBN 3-540-64766-x, Springer-Verlag, Algorithms and Combinatorics, Vol. 17, 1998.

Digital Library

[57]

O. Goldreich: Secure Multi-Party Computation (working draft), Weizman Institute of Science, Rehovot, Israel, June 1998. Avaliable through the author's homepage http://theory.lcs.mit.edu/ oded/.

[58]

S. Goldwasser, S. Micali and C. Rackoff: The Knowledge Complexity of Interactive Proof Systems, Proceedings of ACM STOC'85, pp. 291-304.

Digital Library

[59]

M. Hirt, U. Maurer: Complete Characterization of Adversaries Tolerable in General Multiparty Computations, Proc. ACM PODC'97, pp. 25-34.

Digital Library

[60]

M. Ito, A. Saito and T. Nishizeki: Secret Sharing Scheme Realizing General Access Structures, Proceedings IEEE Globecom '87, pp. 99-102, 1987.

[61]

M. Karchmer, A. Wigderson: On Span Programs, Proc. of Structure in Complexity, 1993.

[62]

J. Kilian: Founding Cryptography on Oblivious Transfer, ACM STOC '88, pp. 20-31.

Digital Library

[63]

J. Kilian, S. Micali and R. Ostrovsky: Minimum resource zero-knowledge proofs (extended abstract), Proceedings of 30th Annual IEEE Symposium on Foundations of Computer Science, pages 474-479, November 1989, IEEE.

Digital Library

[64]

L. Lamport, R.E. Shostak and M.C. Pease: The Byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.

Digital Library

[65]

S. Micali and P. Rogaway: Secure Computation, Manuscript, Preliminary version in Proceedings of Crypto 91.

[66]

R. Ostrovsky and M. Yung: How to withstand mobile virus attacks, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 51-59, 1991.

Digital Library

[67]

T. P. Pedersen: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proc. CRYPTO '91, Springer Verlag LNCS, vol. 576, pp. 129-140.

Digital Library

[68]

T. Rabin: A Simplified Approach to Threshold and Proactive RSA, Proceedings of Crypto '98, Springer Verlag LNCS, vol. 1462, pp. 89-104, 1998.

Digital Library

[69]

T. Rabin: Robust Sharing of Secrets when the Dealer is Honest or Cheating, J. ACM, 41(6):1089-1109, November 1994.

Digital Library

[70]

T. Rabin, M. Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest majority, Proc. ACM STOC '89, pp. 73-85.

Digital Library

[71]

M. Rabin: How to Exchange Secrets by Oblivious Transfer, Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.

[72]

R. Rivest, A. Shamir and L. Adleman: A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of ACM, 21 (1978), pp. 120-126.

Digital Library

[73]

A. Shamir: How to Share a Secret, Communications of the ACM 22 (1979) 612-613.

Digital Library

[74]

S. Wiesner: Conjugate Coding, SIGACT News, vol. 15, no. 1, 1983, pp. 78-88; Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

Digital Library

[75]

A. Yao: Protocols for Secure Computation, Proc. IEEE FOCS '82, pp. 160-164.

Digital Library

Cited By

Dziembowski SFaust SStandaert FWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)Private Circuits IIIProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978419(142-153)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978419
D'Arco PGonzález Vasco MPérez del Pozo ASoriente C(2012)Size-hiding in private set intersectionProceedings of the 5th international conference on Cryptology in Africa10.1007/978-3-642-31410-0_23(378-394)Online publication date: 10-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31410-0_23
Dziembowski S(2010)How to pair with a humanProceedings of the 7th international conference on Security and cryptography for networks10.5555/1885535.1885556(200-218)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1885535.1885556
Show More Cited By

Introduction to Secure Computation

Recommendations

Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
Optimistic Fair Secure Computation
CRYPTO '00: Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology

We present an efficient and fair protocol for secure two-party computation in the optimistic model, where a partially trusted third party T is available, but not involved in normal protocol executions. T is needed only if communication is disrupted or ...
Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer School, Aarhus, Denmark, July 1998

January 1999

250 pages

ISBN:3540657576

Editor:
Ivan Damgård

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 November 2019

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dziembowski SFaust SStandaert FWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)Private Circuits IIIProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978419(142-153)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978419
D'Arco PGonzález Vasco MPérez del Pozo ASoriente C(2012)Size-hiding in private set intersectionProceedings of the 5th international conference on Cryptology in Africa10.1007/978-3-642-31410-0_23(378-394)Online publication date: 10-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31410-0_23
Dziembowski S(2010)How to pair with a humanProceedings of the 7th international conference on Security and cryptography for networks10.5555/1885535.1885556(200-218)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1885535.1885556
Failla PSutcu YBarni MCampisi PDittmann JCraver S(2010)eSketchProceedings of the 12th ACM workshop on Multimedia and security10.1145/1854229.1854271(241-246)Online publication date: 9-Sep-2010
https://dl.acm.org/doi/10.1145/1854229.1854271
Tu MXia ZLi PTadayon N(2009)Allocation of partitioned data by using a neural network based approachNeurocomputing10.1016/j.neucom.2008.04.01172:4-6(1000-1011)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1016/j.neucom.2008.04.011
Ma QDeng P(2008)Secure Multi-party Protocols for Privacy Preserving Data MiningProceedings of the Third International Conference on Wireless Algorithms, Systems, and Applications10.1007/978-3-540-88582-5_49(526-537)Online publication date: 26-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-88582-5_49
Claessens JPreneel BVandewalle J(2003)(How) can mobile agents do secure electronic transactions on untrusted hosts? A survey of the security issues and the current solutionsACM Transactions on Internet Technology10.1145/643477.6434793:1(28-48)Online publication date: 1-Feb-2003
https://dl.acm.org/doi/10.1145/643477.643479
Herlea TClaessens JPreneel BNeven GPiessens FDe Decker B(2001)On securely scheduling a meetingProceedings of the 16th international conference on Information security: Trusted information: the new decade challenge10.5555/512350.510775(183-198)Online publication date: 11-Jun-2001
https://dl.acm.org/doi/10.5555/512350.510775

View Options

View options

Media

Figures

Other

Tables

View Table of Contents