Article

Free access

Probabilistic encryption & how to play mental poker keeping secret all partial information

Authors:

Shafi Goldwasser,

Silvio MicaliAuthors Info & Claims

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

Pages 365 - 377

https://doi.org/10.1145/800070.802212

Published: 05 May 1982 Publication History

Abstract

This paper proposes an Encryption Scheme that possess the following property : An adversary, who knows the encryption algorithm and is given the cyphertext, cannot obtain any information about the clear-text.

Any implementation of a Public Key Cryptosystem, as proposed by Diffie and Hellman in [8], should possess this property.

Our Encryption Scheme follows the ideas in the number theoretic implementations of a Public Key Cryptosystem due to Rivest, Shamir and Adleman [13], and Rabin [12].

References

[1]

Adleman, L., Private Communication, 1981.

[2]

Adleman, L., Manders K. and Miller G., On Taking Roots In Finite Fields, Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1977, 175-177.

Digital Library

[3]

Adleman, L., On Distinguishing Prime Numbers from Composite Numbers, Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science (FOCS), Syracuse, N.Y., 1980, 387-408.

[4]

Blum, M., Three Applications of The Oblivious Transfer, to appear, 1981.

[5]

Blum, M., and Micali, S., How to Flip A Coin Through the Telephone, to appear, 1982.

[6]

Blum, M., Mental Poker, to appear, 1982.

[7]

Brassard, G., Relativized Cryptography, Proceedings of the 20st IEEE Symposium on the Foundations of Computer Science (FOCS), San Juan, Puerto Rico, 1979, 383-391.

[8]

Diffie, W., and M. E. Hellman, New Direction in Cryptography, IEEE Trans. on Inform. Th. IT-22, 6 (1976), 644-654.

Digital Library

[9]

Goldwasser S., and Micali S., A Bit by Bit Secure Public Key Cryptosystem, Memorandum NO. UCB/ERL M81/88, University of California, Berkeley, December 1981.

[10]

Lipton, R., How to Cheat at Mental Poker, Proceeding of the AMS short course on Cryptology, January 1981.

[11]

Miller, G., Riemann's Hypothesis and Tests for Primality, Ph.D. Thesis, U.C. Berkeley, 1975.

[12]

Rabin, M., Digitalized Signatures and Public-Key Functions As Intractable As Factorization, MIT/LCS/TR-212, Technical Memo MIT, 1979.

Digital Library

[13]

Rivest, R., Shamir, A., Adleman, L., A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, February 1978.

Digital Library

[14]

Shamir, Rivest, and Adleman, Mental Poker, MIT Technical Report, 1978.

[15]

Shanks, D., Solved and Unsolved Problems in Number Theory, Chelsea Publishing Co. (1978).

Digital Library

Cited By

Menandas J. JChristo M(2024)Effective Implementation of the Database Primitive Functions Through Homomorphic Encryption Over CloudMachine Learning and Cryptographic Solutions for Data Protection and Network Security10.4018/979-8-3693-4159-9.ch020(332-353)Online publication date: 22-Mar-2024
https://doi.org/10.4018/979-8-3693-4159-9.ch020
Frattolillo F(2024)Blockchain and Smart Contracts for Digital Copyright ProtectionFuture Internet10.3390/fi1605016916:5(169)Online publication date: 14-May-2024
https://doi.org/10.3390/fi16050169
Deng JWu B(2024)A Practical Data Trading Protocol for Sudoku SolutionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.341970219(6935-6948)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3419702
Show More Cited By

Probabilistic encryption & how to play mental poker keeping secret all partial information

Recommendations

Achieving short ciphertexts or short secret-keys for adaptively secure general inner-product encryption

In this paper, we present two non-zero inner-product encryption (NIPE) schemes that are adaptively secure under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. One of the proposed NIPE schemes features constant-...
Adaptive CCA broadcast encryption with constant-size secret keys and ciphertexts

We consider designing public-key broadcast encryption schemes with constant-size secret keys and ciphertexts, achieving chosen-ciphertext security. We first argue that known CPA-to-CCA transforms currently do not yield such schemes. We then propose a ...
Achieving short ciphertexts or short secret-keys for adaptively secure general inner-product encryption
CANS'11: Proceedings of the 10th international conference on Cryptology and Network Security

In this paper, we present two <em>non-zero inner-product</em> encryption (NIPE) schemes that are <em>adaptively secure</em> under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. One of the proposed NIPE schemes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

May 1982

408 pages

ISBN:0897910702

DOI:10.1145/800070

Copyright © 1982 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 May 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

481
Total Citations
View Citations
2,298
Total Downloads

Downloads (Last 12 months)754
Downloads (Last 6 weeks)95

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Menandas J. JChristo M(2024)Effective Implementation of the Database Primitive Functions Through Homomorphic Encryption Over CloudMachine Learning and Cryptographic Solutions for Data Protection and Network Security10.4018/979-8-3693-4159-9.ch020(332-353)Online publication date: 22-Mar-2024
https://doi.org/10.4018/979-8-3693-4159-9.ch020
Frattolillo F(2024)Blockchain and Smart Contracts for Digital Copyright ProtectionFuture Internet10.3390/fi1605016916:5(169)Online publication date: 14-May-2024
https://doi.org/10.3390/fi16050169
Deng JWu B(2024)A Practical Data Trading Protocol for Sudoku SolutionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.341970219(6935-6948)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3419702
Nita SMihailescu MNita SMihailescu M(2024)Advanced Encryption SchemesCryptography and Cryptanalysis in Java10.1007/979-8-8688-0441-0_12(205-217)Online publication date: 14-Jul-2024
https://doi.org/10.1007/979-8-8688-0441-0_12
Couteau GKumar N(2024)10-Party Sublinear Secure Computation from Standard AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68400-5_2(39-73)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68400-5_2
Bell ZGoldwasser SKim MWatson J(2024)Certifying Private Probabilistic MechanismsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_11(348-386)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_11
Beyne TChen Y(2024)Information-Theoretic Security with AsymmetriesAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68385-5_15(463-494)Online publication date: 17-Aug-2024
https://doi.org/10.1007/978-3-031-68385-5_15
Lou PManohar NSahai A(2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58740-5_6
Brunetta CHeum HStam M(2024)SoK: Public Key Encryption with OpeningsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57728-4_2(35-68)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57728-4_2
Gay RUrsu B(2024)On Instantiating Unleveled Fully-Homomorphic Signatures from Falsifiable AssumptionsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57718-5_3(74-104)Online publication date: 13-Apr-2024
https://doi.org/10.1007/978-3-031-57718-5_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents