Probabilistic encryption. (English) Zbl 0563.94013

A new probabilistic model of data encryption is introduced. For this model, under suitable complexity assumptions, it is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources. The proof holds for any message space with any probability distribution. The first implementation of this model is presented. The security of this implementation is proved under the intractability assumption of deciding Quadratic Residuosity modulo composite numbers whose factorization is unknown.


94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Adleman, L.; Manders, K.; Miller, G., On taking roots in finite fields, (), 175-177
[2] Adleman, L., On distinguishing prime numbers from composite numbers, (), 387-408
[3] Blum, M., Coin flipping by telephone, (), 133-137
[4] Blum, L.; Blum, M.; Shub, M., A simple secure pseudo-random number generator, (1982), CRYPTO · Zbl 0602.65002
[5] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo random bits, () · Zbl 0547.68046
[6] Brassard, G., Relativized cryptography, (), 383-391, San Juan, Puerto Rico · Zbl 0571.94011
[7] Brassard, G., On computationally secure authentication tags requiring short secret shared keys, (1982), CRYPTO
[8] Gauss, C.F., Disquisitiones arithmeticae, (1966), Yale Univ. Press New Haven, 1801, translated by A. Arthur and S. J. Clark · Zbl 0136.32301
[9] Diffie, W.; Hellman, M.E., New direction in cryptography, IEEE trans. inform. theory, IT-22, 6, 644-654, (1976) · Zbl 0435.94018
[10] Goldwasser, S.; Micali, S., A bit by bit secure public key cryptosystem, ()
[11] Goldwasser, S.; Micali, S., Probabilistic encryption & how to play mental poker, keeping secret all partial information, ()
[12] Goldwasser, S.; Micali, S.; Tong, P., Why and how to establish a private code in a public network, ()
[13] Goldwasser, S., Probabilistic encryption: theory and applications, ()
[14] Goldwasser, S.; Micali, S.; Yao, A., Strong signature schemes and authentication, () · Zbl 0556.94007
[15] Guy, K.R., How to factor a number, (), 49-89
[16] Knuth, D., ()
[17] Lipton, R., How to cheat at mental poker, ()
[18] Miller, G., Riemann’s hypothesis and tests for primality, () · Zbl 0365.68052
[19] Luby, M.; Micali, S.; Rackoff, C., How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin, (1983), FOCS
[20] Rabin, M., Digitalized signatures and public-key functions as intractable as factorization, MIT/ LCS/TR-212, technical memo MIT, (1979)
[21] Rivest, R.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM, (February 1978)
[22] Shamir, A.; Rivest, R.; Adleman, L., Mental poker, MIT technical report, (1978)
[23] Shannon, C.E., Communication theory of secrecy systems, Bell system tech. J., 28, 656-715, (1949) · Zbl 1200.94005
[24] Shanks, D., Solved and unsolved problems in number theory, (1978), Chelsea New York · Zbl 0397.10001
[25] Vazirani, V.; Vazirani, U., Secure one-bit disclosures using a pseudo random number generator, () · Zbl 0643.94002
[26] Yao, A., On the theory and application of trapdoor functions, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.