Probabilistic encryption

Journal of Computer and System SciencesPublished 1 April 1984

Shafi Goldwasser, Silvio Micali

DOI10.1016/0022-0000(84)90070-9

Source URL

Citations2,554

SJR quartileQ1

SJR score1.03

SNIP1.08

TL;DR

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.

Abstract

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 interactability assumptin of deciding Quadratic Residuosity modulo composite numbers whose factorization is unknown.

Keywords

Computer Science

IEEE Transactions on Information TheoryNew directions in cryptography

14,441 Citations1976Whitfield Diffie, Martin E. Hellman

Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems

13,083 Citations1978Ronald L. Rivest, Adi Shamir +1 more

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key, soriers or other secure means are not needed to transmit keys.

View PDF

Bell System Technical JournalCommunication Theory of Secrecy Systems*

9,330 Citations1949Claude E. Shannon

A theory of secrecy systems is developed on a theoretical level and is intended to complement the treatment found in standard works on cryptography.

DSpace@MIT (Massachusetts Institute of Technology)DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION

1,024 Citations1979M. O. Rabin

It is proved that for any given n, if the authors can invert the function y = E (x1) for even a small percentage of the values y then they can factor n, which seems to be the first proved result of this kind.

View PDF

Riemann's Hypothesis and tests for primality

189 Citations1975Gary L. Miller

It is shown that primality is testable in time a polynomial in the length of the binary representation of a number, and a partial solution is given to the relationship between the complexity of computing the prime factorization of a numbers, computing the Euler phi function, and computing other related functions.

View PDF

On Computationally Secure Authentication Tags Requiring Short Secret Shared Keys

93 Citations1983Gilles Brassard

As an application of strongly universal-2 classes of hash functions, Wegman and Carter have proposed a provably secure authentication tag system that requires that the sender and the receiver share a rather long secret key if they wish to use the system more than once.

How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin

83 Citations1983Michael Luby, Silvio Micali +1 more

A cryptographic protocol allowing two mutually distrusting parties, A and B, each having a secret bit, to "simultaneously" exchange the values of those bits is presented, and a new tool to implement this protocol is developed: a slightly biased symmetric coin.