article

Joint encryption and message-efficient secure computation

Authors:

Matthew Franklin,

Stuart HaberAuthors Info & Claims

Journal of Cryptology, Volume 9, Issue 4

Pages 217 - 232

https://doi.org/10.1007/BF00189261

Published: 01 September 1996 Publication History

Abstract

This paper addresses the message complexity of secure computation in the (passive adversary) privacy setting. We show that O(nC) encrypted bits of communication suffice for n parties to evaluate any boolean circuit of size C privately, under a specific cryptographic assumption. This work establishes a connection between secure distributed computation and group-oriented cryptography, i.e., cryptographic methods in which subsets of individuals can act jointly as single agents. Our secure computation protocol relies on a new group-oriented probablistic public-key encryption scheme with useful algebraic properties.

References

[1]

D. Chaum, I. Damgard, and J. van de Graaf, Multiparty computations ensuring privacy of each party's input and correctness of the result, Advances in Cryptology--CRYPTO '87 Proceedings (Lecture Notes in Computer Science, Vol. 293), ed. C. Pomerance, pp. 87-119, Springer-Vedag, Berlin, 1988.

Crossref

Google Scholar

[2]

Y. Desmedt, Society and group oriented cryptography: a new concept Advances in Cryptology--CRYPTO '87 Proceedings (Lecture Notes in Computer Science, Vol. 293), ed. C. Pomerance, pp. 120-127, Springer-Verlag, Berlin, 1988.

Crossref

Google Scholar

[3]

Y. Desmedt and Y. Frankel, Threshold cryptosystems, Advances in Cryptology--CRYPTO '89 Proceedings (Lecture Notes in Computer Science, Vol. 435), ed. G. Brassard, pp. 307-315, Springer-Verlag, Berlin, 1990.

Crossref

Google Scholar

[4]

W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22(6):644-654, 1976.

Digital Library

Google Scholar

[5]

T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 31:469-472, 1985.

Digital Library

Google Scholar

[6]

Z. Galil, S. Haber, and M. Yung, Cryptographic computation: secure fault-tolerant protocols and the public-key model, Advances in Cryptography--CRYPTO '87 Proceedings (Lecture Notes in Computer Science, Vol. 293), ed. C. Pomerance, pp. 135-155, Springer-Verlag, Berlin, 1988.

Crossref

Google Scholar

[7]

O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, Proceedings of the 19th Annual Symposium on Theory of Computing, 1987, pp. 218-229.

Digital Library

Google Scholar

[8]

O. Goldreich and R. Vainish, How to solve any protocol problem--an efficiency improvement, Advances in Cryptology--CRYPTO '87 Proceedings (Lecture Notes in Computer Science, Vol. 293), ed. C. Pomerance, pp. 73-86, Springer-Verlag, Berlin, 1988.

Crossref

Google Scholar

[9]

S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, 28:270- 299, 1984.

Crossref

Google Scholar

[10]

K. McCurley, A key distribution system equivalent to factoring, Journal of Cryptology, 1:95-105, 1988.

Digital Library

Google Scholar

[11]

S. Micali, Fair public-key cryptosystems, Advances in Cryptology--CRYPTO '92 Proceedings (Lecture Notes in Computer Science, Vol. 740), ed. E. Brickell, pp. 114-139, Springer-Verlag, Berlin, 1993.

Crossref

Google Scholar

[12]

Z. Shmuely, Composite Diffie-Hellman public-key generating systems are hard to break, Technical Report #356, Technion--Israel Institute of Technology, February 1985.

Google Scholar

[13]

A. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 160-164.

Digital Library

Google Scholar

[14]

A. Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 162-167.

Digital Library

Google Scholar

Cited By

View all

Rotaru DSmart NTanguy TVercauteren FWood T(2022)Actively Secure Setup for SPDZJournal of Cryptology10.1007/s00145-021-09416-w35:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s00145-021-09416-w
Wang QChen SXiang Y(2021)Anonymous Blockchain-based System for ConsortiumACM Transactions on Management Information Systems10.1145/345908712:3(1-25)Online publication date: 3-Jun-2021
https://dl.acm.org/doi/10.1145/3459087
Badrinarayanan SMiao PRaghuraman SRindal P(2021)Multi-party Threshold Private Set Intersection with Sublinear CommunicationPublic-Key Cryptography – PKC 202110.1007/978-3-030-75248-4_13(349-379)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75248-4_13
Show More Cited By

Index Terms

Joint encryption and message-efficient secure computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Dynamic and efficient joint encryption scheme in the plain public key model

In this paper, we propose a joint encryption scheme (JES) based on discrete logarithms in the plain public key model, in which a sender can easily encrypt messages under the public keys of a group of recipients, so that only by collaborating together ...
Joint Encryption and Message-Efficient Secure Computation
CRYPTO '93: Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology

This paper connects two areas of recent cryptographic research: secure distributed computation, and group-oriented cryptography. We construct a probabilistic public-key encryption scheme with the following properties: - It is easy to encrypt using the ...
Public‐key encryption indistinguishable under plaintext‐checkable attacks

Indistinguishability under chosen‐ciphertext attack (IND‐CCA) is now considered the de facto security notion for public‐key encryption. However, this sometimes offers a stronger security guarantee than what is needed. In this study, the authors consider a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Cryptology Volume 9, Issue 4

September 1996

63 pages

ISSN:0933-2790

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 1996

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rotaru DSmart NTanguy TVercauteren FWood T(2022)Actively Secure Setup for SPDZJournal of Cryptology10.1007/s00145-021-09416-w35:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s00145-021-09416-w
Wang QChen SXiang Y(2021)Anonymous Blockchain-based System for ConsortiumACM Transactions on Management Information Systems10.1145/345908712:3(1-25)Online publication date: 3-Jun-2021
https://dl.acm.org/doi/10.1145/3459087
Badrinarayanan SMiao PRaghuraman SRindal P(2021)Multi-party Threshold Private Set Intersection with Sublinear CommunicationPublic-Key Cryptography – PKC 202110.1007/978-3-030-75248-4_13(349-379)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75248-4_13
Boyle ECouteau GGilboa NIshai YKohl LScholl P(2019)Efficient Pseudorandom Correlation Generators: Silent OT Extension and MoreAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26954-8_16(489-518)Online publication date: 18-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-26954-8_16
Mukherjee PWichs D(2016)Two Round Multiparty Computation via Multi-key FHEProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081764(735-763)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081764
Beerliová-Trubíniová ZHirt MNielsen JRicha AGuerraoui R(2010)On the theoretical gap between synchronous and asynchronous MPC protocolsProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835746(211-218)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835746
Dolev SGilboa NKopeetsky MShin SOssowski SSchumacher MPalakal MHung C(2010)Computing multi-party trust privatelyProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774401(1460-1465)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774401
Kursawe KNeven GTuyls P(2006)Private policy negotiationProceedings of the 10th international conference on Financial Cryptography and Data Security10.1007/11889663_6(81-95)Online publication date: 27-Feb-2006
https://dl.acm.org/doi/10.1007/11889663_6
Damgård IIshai Y(2006)Scalable secure multiparty computationProceedings of the 26th annual international conference on Advances in Cryptology10.1007/11818175_30(501-520)Online publication date: 20-Aug-2006
https://dl.acm.org/doi/10.1007/11818175_30
Hirt MNielsen J(2006)Robust multiparty computation with linear communication complexityProceedings of the 26th annual international conference on Advances in Cryptology10.1007/11818175_28(463-482)Online publication date: 20-Aug-2006
https://dl.acm.org/doi/10.1007/11818175_28
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Dynamic and efficient joint encryption scheme in the plain public key model