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

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.
• 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.
• 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: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 13: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 14: Shamir, Rivest, and Adleman, Mental Poker, MIT Technical Report, 1978.
• 15: Daniel Shanks, Solved and unsolved problems in number theory, Chelsea Publishing Co., Inc., New York, 1985