Probabilistic Encryption

1 Introduction

This paper proposes an encryption scheme that possesses the following property:

Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext.

The security of our encryption scheme is based on complexity theory. Thus, when we say that it is "impossible" for an adversary to compute any information about the cleartext from the cyphertext we mean that it is not computationally feasible.

The relatively young field of complexity theory has not yet been able to prove a nonlinear lower bound for even one natural NP-complete problem. At the same time, despite the enormous mathematical effort, some problems in number theory have for centuries refused any "domestication." Thus, for concretely implementing our scheme, we assume the intractability of some problems in number theory such as factoring or deciding quadratic residuosity with respect to composite moduli. In this context, proving that a problem is hard means to prove it equivalent to one of the above mentioned problems. In other words, any threat to the security of the concrete implementation of our encryption scheme will result in an efficient algorithm for deciding quadratic residuosity modulo composite integers.

• This research was done when both authors were students at the University of California at Berkeley and supported in part by NSF Grant MCS 82-04506. The preparation of this manuscript was done when the first author was at the Laboratory of Computer Science at MIT and supported by a Bantrell fellowship and an IBM faculty development award, and the second author was at the Computer Science Department at the University of Toronto.

1.1. Deterministic Encryption: The Trapdoor Function Model

Our encryption scheme benefits from the ideas of Diffie and Hellman [9], Rivest, Shamir, and Adleman [21], and Rabin [20].

Diffie and Hellman [9] introduced the idea of a public key cryptosystem, which is based on the intractability of some underlying computational problem. Intuitively, the idea is to find an encryption function $E$ which is easy to compute but difficult to invert unless some secret information, the trapdoor, is known. Such a function is called a trapdoor function. To encrypt a message $m$, anyone simply evaluates $E(m)$, but only those who know the trapdoor information can compute $m$ from $E(m)$.

The two implementations of a trapdoor function most relevant and inspiring for this paper are the RSA function [21], due to Rivest, Shamir, and Adleman, and its particularization suggested by Rabin [20].

1.2. Basic Objections to the Trapdoor Function Model

We point out two basic weaknesses of this approach:

(1) The fact that $f$ is a trapdoor function does not rule out the possibility of computing $x$ from $f(x)$ when $x$ is of a special form. Usually messages do not consist of numbers chosen at random but possess more structure. Such structural information may help in decoding. For example, a function $f$, which is hard to invert on a generic input, could conceivably be easy to invert on the ASCII representations of English sentences.

(2) The fact that $f$ is a trapdoor function does not rule out the possibility of easily computing some partial information about $x$ (even every other bit of $x$) from $f(x)$. Encrypting messages in a way that ensures the secrecy of all partial information is an important goal in cryptography. Assume we want to use encryption to play card games over the telephone. If the suit or color of a card could be compromised the whole game should be invalid. Indeed Lipton [17] has pointed out that one bit of information about cards to remain hidden can be easily computed in the SRA implementation of Mental Poker [22].

Though no one knows how to break the RSA or the Rabin scheme, in none of these schemes is it proved that decoding is hard without any assumptions made on the message space. Rabin shows that, in this scheme, decoding is hard for an adversary if the set of possible messages has some density property. We discuss this further in Section 2.

1.3. Probabilistic Encryption: The New Model

In this paper we switch from a deterministic framework to a probabilistic framework. This enables us to deal with the problems that arose with the trapdoor function model, without imposing any probability structure on the messages we would like to send.

We replace the notion of a trapdoor function with the notion of an unapproximable trapdoor predicate. Briefly, the predicate $B$ is trapdoor and unapproximable if anyone can select an $x$ such that $B(x) = 0$ or $y$ such that $B(y) = 1$, but only those who know the trapdoor information can, given $z$, compute the value of $B(z)$. When the trapdoor information is unknown, an adversary with polynomially bounded computational resources can not decide the value of $B(z)$ better than guessing at random (see Section 3 for formal definition).

We replace deterministic block encryption by probabilistic encryption of single bits, where there are many different encodings of a “1” and many different encodings of a “0.” To encrypt each message we make use of a fair coin. Thus the encoding of each message will depend on the message plus the result of a sequence of coin tosses. More specifically, a binary message will be encrypted bit-by-bit as follows: a “0” is encoded by randomly selecting an $x$ such that $B(x) = 0$ and a “1” is encoded by randomly selecting an $x$ such that $B(x) = 1$. Consequently, there are many possible encodings for each message. However, messages are always uniquely decodable.

Two properties of the new model are:

(1) Decoding is easy for the legal receiver of a message, who knows the trapdoor information, but provably hard for an adversary. Therefore the spirit of a trapdoor function is maintained. In addition, in our scheme, we do not impose any restrictions on the message space. The security of the scheme is proved for messages belonging to any message space with any probability distribution.

(2) No information about an encrypted message can be obtained by an adversary.

Let $g : M \to V$ be a nonconstant function $m$. Assume that the message space $M$ has some probability distribution. Accordingly, let $p_v = \operatorname{prob}(g(m) = v \mid m \in M)$ for each $v \in V$, and let $\bar{v} \in V$ be such that $p_{\bar{v}} = \max_{v \in V} p_v$. Then, without any special ability, an adversary given the cyphertext, can always guess the value of $g$ over the cleartext and be correct with probability $p_{\bar{v}}$. We prove that for a probabilistic encryption scheme, an adversary, given the cyphertext, cannot guess the value of $g$ over the cleartext with probability better than $p_{\bar{v}}$. Note that $g$ needs not be polynomially computable, or even recursive. Thus, our encryption model passes a polynomially bounded version of Shannon’s perfect secrecy definition; see Subsection 7.3.

This property enabled Goldwasser and Micali [11] to device a scheme for Mental Poker for which, under the Quadratic Residuosity Assumption, no partial information about cards that should remain hidden can be easily computed.

1.4. Concrete Implementation of the New Model

We introduce Quadratic Residuosity modulo composite integers whose factorization is unknown (see Section 6 for precise definition), as the first example of an unapproximable trapdoor predicate. Thus we introduce a new probabilistic public key cryptosystem that is secure in a very strong probabilistic sense if and only if deciding quadratic residuosity with composite moduli is hard (see Section 4). The security offered by this Public Key Cryptosystems extends to all partial information about encrypted messages, to all possible message spaces and to all possible probability distributions for the message space (see Section 5 for formal definition of security).

Another example of such predicates, has appeared in a Goldwasser, Micali, and Tong [12] and in Goldwasser [13]. The predicate they propose is unapproximable if and only if factoring composite numbers is hard. Using the construction of Section 4, we can build a public key cryptosystem based on the predicate they propose. Again, any threat to the security of this last cryptosystem, will result in an efficient factoring algorithm.

In [26], Yao shows that unapproximable trapdoor predicates exist if one-to-one trapdoor functions exist.

1.5. Related Work

Blum and Micali in [5] showed the first example of an unapproximable predicate which is not trapdoor. Their predicate is unapproximable if and only if the discrete logarithm problem is hard.

The quadratic residuosity predicate is not only an example of an unapproximable trapdoor predicate, but possesses other properties which make it particularly attractive for protocol design. It has been widely used since we first proposed it in [10]. The first protocol that uses this predicate was suggested by Goldwasser and Micali in [11]. They design a protocol for two players to play mental poker over the telephone, so that no player can obtain any partial information about cards not in his hand. Other works in which this predicate has proved useful are: Blum, Blum, and Shub’s implementation [4] of a cryptographically strong pseudo random bit generator [5], Brassard’s [7] implementation of authentication tags, Luby, Micali, and Rackoff’s [19] method for simultaneously exchanging a secret bit, and Vazirani and Vazirani’s [25] implementation of one bit disclosures.

2 *Survey of Public Key Cryptosystems Based on Trapdoor Functions*

All the number theoretic notation used in this section will be defined in Section 3.

2.1. What Is a Public Key Cryptosystem?

The concept of a Public Key Cryptosystem was introduced by Diffie and Hellman in their ingenious paper [9]. Let $M$ be a finite message space, let $\{A, B, ...\}$ be users, and let $m \in M$ denote a message. Let $E_A : M \to M$ be $A$'s encryption function, which is ideally bijective, and $D_A$ be $A$'s decryption function such that $D_A(E_A(m)) = m$ for all $m \in M$. In a Public Key Cryptosystem $E_A$ is placed in a public file, and user $A$ keeps $D_A$ private. $D_A$ should be difficult to compute knowing only $E_A$. To send message $m$ to $A, B$ takes $E_A$ from the public file, computes $E_A(m)$ and sends this message to $A$. $A$ easily computes $D_A(E_A(m))$ to obtain $m$.

2.2. The RSA Scheme and the Rabin Scheme

Two implementations of such encryption functions $E_A$ are the RSA function [21] of Rivest et al. and the Rabin function [20].

The key idea in both the RSA scheme and the Rabin scheme$^1$ consists in the selection of an appropriate number theoretic trapdoor function. In the RSA scheme, user $A$ selects $n$, the product of two large distinct primes $p_1$ and $p_2$, and a number $s$ such that $s$ and $\varphi(n)$ are relatively prime, where $\varphi$ is the Euler totient function. $A$ puts $n$ and $s$ in a public file and keeps the factorization of $n$ private. Let $Z_n^* = \{ x \in N : 1 \leq x \leq n-1 \text{ and } x \text{ and } n \text{ are relatively prime} \}$. For every message $m \in Z_n^*$, $E_A(m) = m^s \mod n$. Clearly, the ability to take $s$th roots mod $n$ implies the ability to decode. $A$, who knows the factorization of $n$, can easily take $s$th roots mod $n$. No efficient way to take $s$th roots mod $n$ is known when the factorization of $n$ is unknown.

Rabin suggested to modify the RSA scheme by choosing $s = 2$. Thus, for all users $A$, $E_A(x) = x^2 \mod n$. Notice that $E_A$ is a 4–1 function because our $n$ is the product of two primes. In fact, every quadratic residue mod $n$, i.e., every $q$ such that $q \equiv x^2 \mod n$ for some $x \in Z_n^*$, has four square roots mod $n$: $\pm x \mod n$ and $\pm y \mod n$. As $A$ knows the factorization of $n$, upon receiving the encrypted message $m^2 \mod n$, she could easily compute its four square roots and get the message $m$. ($A$ may compute square roots mod $n$ by first computing square roots mod $p_1$ and $p_2$, and then by combining them via the Chinese Remainder Theorem.) The following heuristics may be suggested for eliminating ambiguity in decoding: for sending a message $m$, send $m^2 \mod n$ together with the last 20 bits of $m$. Such extra information cannot effectively help in decoding: one could always guess the last 20 digits of $m$. (To avoid publicizing the last 20 digits of $m$, just select a 20-bit random integer $r$ and send $(m2^{20} + r)^2 \mod n$ together with $r$.)

The following theorem shows how hard it is to invert Rabin’s function $x^2 \mod n$.

THEOREM (Rabin). If for a $1/\log n$ fraction of the quadratic residues $q \mod n$ one could find one square root of $q$, then one could factor $n$ in random polynomial time.

The theorem follows from Lemma 1 which we state without proof.

LEMMA 1. Given $x, y \in Z_n^*$ such that $x^2 \equiv y^2 \mod n$ and $x \neq \pm y \mod n$, there is a polynomial time algorithm to factor $n$. (In fact the greatest common divisor of $n$ and $x \pm y$ is a factor of $n$.)

Informal Proof of Rabin’s Theorem. Assume that we have a magic box MB such

$^1$ We will state a simplified version of his method.

that given $q$, a quadratic residue mod $n$, for a fraction $1/\log n$ of the $q$'s it outputs one square root of $q \mod n$. Then we could factor $n$ by iterating the following step:

Pick $i$ at random in $Z_n^*$ and compute $q = i^2 \mod n$. Feed the magic box MB with $q$. If $M$ outputs a square root of $q$ different from $i$ or $-i \mod n$, then (by Lemma 1) factor $n$.

The expected number of iterations is low, as at each step, we have a $1/2 \log n$ chance of factoring $n$.

2.3. Objections to Cryptosystems Based on Trapdoor Functions

The following problems may arise in the RSA and Rabin schemes and, more generally, in any other Public Key Cryptosystem based on trapdoor functions:

(1) The fact that $f$ is a trapdoor function does not rule out the possibility of computing $x$ from $f(x)$ when $x$ is of special form.

(2) The fact that $f$ is trapdoor function does not rule out the possibility of easily computing some partial information about $x$ from $f(x)$.

2.3.1. Discussion of Objection 1

One may argue that Rabin's Public Key Cryptosystem is as hard to break as factoring in the following way: whoever can get messages $m$ from their encryptions $m^2 \mod n$ for a fraction $1/\log n$ of the time, is actually realizing the magic box of Rabin's theorem and thus could efficiently factor $n$.

We would like to point out the following fact.

Claim. If $M$, the space of messages, is "sparse" in $Z_n^*$, the ability to decode for a fraction $1/\log n$ of all messages does not yield a random polynomial time algorithm for factoring.

By "sparse" we mean that for a randomly chosen $x \in Z_n^*$, the probability that $x$ is a message is virtually 0.

Let $f(x) = x^2 \mod n$. Assume that we are able to invert the function $f$ only on $f(M)$. Then, we would have a magic box MB which, on input $m^2 \mod n$, where $m \in M$, outputs $m$; and on input $q \notin \{ m^2 \mod n \mid m \in M \}$, outputs a correct answer, for a negligible portion of the $q$'s. Using such a magic box we could decode, but not factor $n$ efficiently. Let us look at the above informal proof of Rabin's theorem, using this MB. If we pick $m \in M$ and input $m^2 \mod n$ to MB, then we get $m$ back and cannot factor. If we pick $i \notin M$ and input $i^2 \mod n$ to MB, then the probability that any of the square roots of $i^2 \mod n$, which are different from $i$, belong to $M$ is practically 0 and we get no answer.

We conclude that for Rabin's function one can decode if and only if one can factor, provided the legal messages are dense in $Z_n^*$ (e.g., $M = Z_n^*$ and all messages are equally probable).

2.3.2. Discussion of Objection 2

One desirable property for an encryption algorithm is that an adversary should not be able to obtain any partial information about the cleartext from the cyphertext.

For example, let $f$ be a hashing function or a nonconstant predicate defined on the message space $M$. Let $m \in M$. If, given the encryption of $m$, an adversary can efficiently compute $f(m)$, then we say that information about $m$ can be obtained from the encryption of $m$.

Note that if the encryption algorithm, $E$, is a trapdoor function, then partial information about the cleartext cannot be hidden. In fact, the following predicate $B$, defined on the cleartext, is easy to evaluate from the cyphertext: $B(x) =$ true if and only if $E(x)$ is even. We can avoid such problems using probabilistic encryption.

Let us now discuss a crucial question, raised by Brassard [6], closely related to the security of partial information: how to send a single bit securely in a Public Key Cryptosystem.

2.3.3. Attempts to Send a Single Bit Securely in Public Key Cryptosystems Based on Trapdoor Functions

Suppose that user $B$ wants to send a single bit message to user $A$ in great secrecy. The bit is equally likely to be a 0 or a 1. $B$ wants no adversary to be able to guess correctly his message 51% of the time. $B$ knows that user's $A$'s public encryption function $E_A$ is hard to invert and tries to make use of this fact in the following way.

IDEA 1. All users in the system agree on an integer $i$. User $B$ selects $r \in M$ at random, except for the $i$th bit of $r$, which will be his message. $B$ sends $E_A(r)$ to $A$. $A$ can decode and thus get the desired bit. But what can an adversary do?

Danger. Let $y = E_A(x)$, where $E_A$ is a one way function. Then, given $y$, it could be difficult to compute $x$ but not a specific bit of $x$.

EXAMPLE. Let $p$ be a large prime such that $p - 1$ has at least one large prime factor. Let $g$ be a generator for $Z_p^*$. Then $y \equiv g^x \mod p$ is considered to be a one-way function. But, even though it is difficult to compute $x$ from $g^x \mod p$ (the index finding problem), it is easy to get the last bit of $x$. In fact, $x$ ends in 0 if and only if $y$ is a quadratic residue mod $p$, and there are probabilistic polynomial time algorithms for testing whether numbers are quadratic residues modulo primes $p$ (see Subsection 3.1).

The following idea was suggested by Donald Johnson.

IDEA 2. $B$ constructs a 100-bit integer $x$ as follows: he selects $8 \leq i \leq 100$ at random, and sets the $i$th bit of $x$ to the bit he wants to communicate. The remaining 92 bits of $x$ are chosen at random, except for the first 7 bits of $x$, which specify location $i$. $B$ sends $E_A(x)$ to $A$.

Danger. $E_A$ can be a trapdoor function and yet one could, given $E_A(x)$, easily compute the first 7 bits of $x$ and one of the last 93 bits of $x$. If this is the case, one could correctly compute $B$'s message $x$ with probability $\frac{1}{92} + \frac{1}{2} \cdot \frac{91}{92}$.

Summarizing, there are many ways in which a single bit could be "embedded" in a binary number $x$. Taking the "exclusive or" of all the digits of $x$ is just one more example. However, given $y = E_A(x)$, being able to discover single bits embedded in $x$ does not contradict the fact that it is hard to compute $x$. Then, what is a secure way to send a single bit? Unapproximable trapdoor predicates will provide a solution to this problem.

3 UNAPPROXIMABLE TRAPDOOR PREDICATES

In Section 4 we introduce the model of a probabilistic public key cryptosystem. We show that this model is highly secure. Our model switches from block encryption to bit-by-bit encryption. For this purpose we must abandon the notion of trapdoor functions for the new notion of unapproximable trapdoor predicates.

Definition ($\varepsilon$-approximates). A circuit $C[\cdot]$ $\varepsilon$-approximates the predicate $B : \Omega \to \{0, 1\}$ if $C[x] = B[x]$ for at least a fraction $\frac{1}{2} + \varepsilon$ of the $x \in \Omega$.

We proceed to formally define unapproximable trapdoor predicates.

Let $N$ denote the set of natural numbers and $N'$ be an infinite subset of $N$. For every $k \in N'$ let $S_k$ denote a subset of the $k$-bit integers and for every $i \in S_k$ let $\Omega_i$ be a subset of the integers with at most $k$ bits. Let

be a collection of predicates indexed by an integer of size $k$ and

We say that $B$ is an unapproximable trapdoor predicate (UTP) if:

(1) ($B$ is unapproximable): Fix polynomials $P_1$ and $P_2$. Let $k \in N'$. Let $c_k$ denote the size of the minimum size circuit $C[\ , ]$ such that $C\ , i)$-approximates $B_i$ for at least a fraction $1/P_2(k)$ of the $i \in S_k$. We say that $B$ is unapproximable if $c_k$ grows faster than any polynomial in $k$.

(2) ($B$ is trapdoor): For $v \in \{0, 1\}$ set $\Omega_i^v = \{ x \in \{ \Omega_i \} \mid B_i(x) = v \}$. We say that $B$ is trapdoor if:

(a) There exists a probabilistic polynomial in $k$ time Turing machine $T_1$ that on input $(i, v)$, where $i \in S_k$ and $v \in \{0, 1\}$, selects $x \in \Omega_i^v$ with uniform probability.

(b) There exists a function $\sigma: \bigcup_{k \in V'} S_k \to N$ such that for some polynomial $Q$, for all $x, |\sigma(x)| < Q(|x|)$, and a polynomial time Turing machine $T_2$ such that $T_2[i, \sigma(i), x] = B_i(x)$ for all $i \in S_k$, and for all $x \in \Omega_i$. We call $\sigma(i)$ the secret of $i$.

(c) (constructibility condition): for all $k \in N'$ it is possible in probabilistic polynomial in $k$ time to select any pair $(i \in S_k, \sigma(i))$, with probability $1/|S_k|$.

Condition (2c), the constructibility condition, guarantees that if someone picks a pair $(i, \sigma(i))$, where $i \in S_k$ and publicizes $i$, it will be hard to compute $B_i(x)$. Otherwise, suppose the pairs $(i, \sigma(i)), i \in S_k$, that could be efficiently selected constituted a very small fraction of all possible pairs. Then, an adversary could, from the public $i$, find out $\sigma(i)$ just by repeatedly selecting pairs $(j, \sigma(j))$ until $j = i$.

Remark 3.1. Note that if $B$ is an unapproximable predicate and $P_1, P_2$ are polynomials, then for all sufficiently large $k$, for a fraction $1 - (1/P_1(k))$ of the $i \in S_k$, $|\Omega_i^0|/|\Omega_i|$ and $|\Omega_i^1|/|\Omega_i|$ are both greater than $\frac{1}{2} - (1/P_2(k))$. Otherwise either the trivial circuit $C_k$ that always outputs 0 or the trivial circuit that always outputs 1 would $(1/P_2(k))-$ approximate $B_i$ for a fraction at least $1/P_1(k)$ of the $i \in S_k$.

3.1. Quadratic Residuosity as a UTP

We demonstrate an example of an unapproximable trapdoor set of predicates, under the intractability assumption of the Quadratic Residuosity Problem (QRP). If needed the number theoretic definitions can be found in Section 7.

Let $k \in N$. Let $p_1$ and $p_2$ denote primes. Set,

And let $Z_n^1$ denote the subset of $Z_n^*$ containing the elements with Jacobi symbol +1. For all $x \in Z_n^1$, $Q_n$ is defined as

Let $k \in N$. Let $x$ and $y$ be binary strings. We denote by $x \# y$ the concatenation of $x$ and $y$. Define $S_{4k} = \{ n \# y \mid n \in H_k \text{ and } y \in Z_n^1 \text{ is a quadratic nonresidue mod } n \}$. Define $\Omega_{n \# y} = Z_n^1$ and set $Q_{n \# y}(x) = Q_n(x)$ for each $x \in Z_n^1$. Then $Q^* = \{ Q_{n \# y} \mid n \# y \in S_{4k} \}$ is a set of predicates. The presence of the quadratic nonresidue $y$ will be needed to show the trapdoorness of $Q^*$.

(1) $Q^*$ is unapproximable: This is shown in Theorem 2 (Section 7), under the Quadratic Residuosity Assumption.

(2) $Q^*$ is trapdoor: Letting $\sigma_{4k}(n \# y)$ be the factorization of $n$, $Q^*$ is a trapdoor set of predicates. In fact, if the factorization of $n$ is known, $Q_n(\cdot)$ can be computed in $O(k^3)$ time. Moreover, given $y$, a quadratic nonresidue mod $n$, we can generate quadratic nonresidues mod $n$ with uniform probability in probabilistic polynomial in $k$ time by randomly selecting $x \in Z_n^*$ and computing $r = yx^2 \mod n$.

(3) $Q^*$ is constructible: Consider the following algorithm that selects one element $n \# y \in S_{4k}$, where $n \in H_k$ and $y \in Z_n^{+1}$ is a quadratic nonresidue mod $n$.

Step 1. Flip $4k$ fair coins.

Step 2. Check whether the first $k$ outcomes and the second $k$ outcomes constitute, respectively, the binary representation of a prime $p_1$ and a prime $p_2$ each of size $k$. If so, let $n = p_1 p_2$ and check if the last $2k$ bits constitute a quadratic nonresidue $y \mod n$. If so then halt: $p_1 \cdot p_2 \# y$ has been selected. Else go to Step 1.

As each element in $S_{4k}$ can be generated by exactly one $4k$-long sequence of coin tosses, the above algorithm selects elements in $S_{4k}$ with uniform probability. Due to the Prime Number Theorem and the existence of random polynomial time algorithms for primality checking, the above algorithm runs in random poly$(k)$ time.

We conclude that, under the QRA, $Q^*$ is an unapproximable trapdoor predicate.

4 Public Key Cryptosystems and Probabilistic Public Key Cryptosystems

In the last section we defined UTPs. We are now ready to introduce our probabilistic model of encryption. In Subsection 4.2 we formally define the notion of a public key cryptosystem (PKC) which is parameterized by a security parameter. In Subsection 4.3 we define our model of a probabilistic public key cryptosystem (PPKC). In Subsection 4.4 we present a concrete implementations of this model based on the QRA, the intractability assumption for the Quadratic Residuosity Problem.

4.1. Preliminary Notation

The following notation is used throughout the rest of this paper: Let $\Gamma$ be a probabilistic Turing machine. We write $\Gamma[\beta]$ to denote the set of possible outputs of $\Gamma$ on input $\beta$. We give $\Gamma[\beta]$ the following probability distribution: if $\alpha \in \Gamma[\beta]$ then the probability of $\alpha$ is the probability that $\Gamma$ outputs $\alpha$ on input $\beta$.

Let $T_1$ and $T_2$ be Turing machines. By saying that $T_1$ is input to (output by) $T_2$ we mean that a standard encoding of $T_1$ is input to (output by) $T_2$.

4.2. Public Key Cryptosystems

Informally, we think of a PKC as a server. Each user in the system comes to the PKC with a description of his message space and a common security parameter k. On such inputs, the PKC produces a pair of algorithms: an encryption algorithm (which is possibly probabilistic) and a decryption algorithm. The description of both the encryption algorithm and the decryption algorithm should be short (polynomial in k). Moreover, both algorithms should halt in polynomial time. The user stores the (description of the) encryption algorithm in the public file, and keeps secret the (description of the) decryption algorithm.

We proceed to formally define what a PKC is.

We let k denote a parameter that will be presented in unary to all the algorithms in this paper. Let $U = \{A, B, ...\}$ be a finite set of users.

A message generator is a probabilistic polynomial time Turing machine MG that on input k outputs a string referred to as a message.

Definition. A Public Key Cryptosystem is a probabilistic polynomial time Turing machine $\Pi$ that on inputs k and MG outputs the description of two algorithms, E and D such that

(1) for some constants constants c, on inputs of size n, both E and D halt within $n^c$ steps, and

(2) for all $m \in \mathrm{MG}[k]$, $D(E(m)) = m$.

We call E an encryption algorithm generated by $\Pi$, and D a decryption algorithm generated by $\Pi$. The encryption algorithms generated by $\Pi$ may be probabilistic.

Remark. Let us stress again that $\Pi$ is a probabilistic Turing machine, and thus on the same input pair (k, MG) it may output many different (encryption algorithm, decryption algorithm) pairs. When we are only interested in an encryption algorithm E generated by $\Pi$ on inputs k and MG, we will write $E \in \Pi(k, \mathrm{MG})$.

4.3. Probabilistic Public Key Cryptosystems

Let $\mathbf{B} = \bigcup_{k \in N'} \mathbf{B}_k$, where $\mathbf{B}_k = \{ B_i : \Omega_i \to \{0, 1\} \mid i \in S_k \}$, be an unapproximable trapdoor predicate. A Probabilistic Public Key Cryptosystem (PPKC) with UTP B is a PKC $\Pi$ that takes as input the security parameter k and the message generator MG and outputs a pair $(i, \sigma(i))$, where $i \in S_k$ and $\sigma(i)$ is the secret of i. This can be done by the constructibility property of B.

The output $i \in S_k$ of $\Pi$ specifies an encryption algorithm E as follows: E takes as input an l-bit binary message $m = m_1 m_2 \cdots m_l$. For each $m_j$ in the binary representation of m, E randomly selects an element $x_j \in \Omega_j$ such that $B_i(x_j) = m_j$ and outputs the l-tuple $(x_1, ..., x_l)$. In virtue of the trapdoor property of B this can be done in probabilistic time polynomial in k and l. The output of E is bounded by $O(kl)$.

In general, consider the binary string $b = b_1 \cdots b_l$, where $b_j \in \{0, 1\}$. We call any l-tuple $(x_1, ..., x_l)$ such that $x_j \in \Omega_i$ and $B_i(x_j) = b_j$ for all $1 \leq j \leq l$ a probabilistic encryption of $b$ using predicate $B_i$. Thus, note that in contrast with PKCs based on a trapdoor function such as the RSA, in a probabilistic public key cryptosystem every message $m$ has many possible probabilistic encryptions.

The output $\sigma(i)$ of $\Pi$ specifies a decryption algorithm $D$ as follows: Let $T$ be a probabilistic polynomial time Turing machine that on inputs $i \in S_k, x \in \Omega_i$, and $\sigma(i)$ computes $B_i(x)$. Such a $T$ exists by the trapdoor property of $B$. Then $D$ uses $T$ as a subroutine as follows: Let $D$'s input consist of the $l$-tuple $(x_1, ..., x_l)$, where $x_j \in \Omega_i$ for every $1 \leq j \leq l$. Then for every $1 \leq j \leq l$, $D$ calls $T$ with inputs $i, \sigma(i), x_j$ to compute $B_i(x_j)$, and writes every one of $T$'s $l$ answers on its output tape. As $T$ runs in polynomial time, so does $D$.

4.4. The Quadratic Residuosity Implementation of a PPKCS

Let us explicitly describe the implementation of a PPKC based on the Quadratic Residuosity Problem.

Example 1. Let $Q^*$ be the unapproximable trapdoor predicate defined in the previous section. Recall, $Q^* = \{ Q_{n\#y} | n \# y \in S_{4k} \}$, where $n \in H_k$ and $y \in Z_n^1$ is a quadratic nonresidue mod $n$.

Let $\Pi$ be a probabilistic public key cryptosystem based on the unapproximable trapdoor predicate $Q^*$. Let user input the security parameter $k$ to $\Pi$. On inputs $k$ and message generator MG, $\Pi$ works as follows:

(1) it randomly selects two $k$-bit primes $p_1$ and $p_2$, (2) sets $n = p_1 p_2$, (3) picks $y \in Z_n^1$ such that $y$ is a quadratic nonresidue modulo $n$, (4) outputs as an encryption algorithm some standard encoding of the pair $(n, y)$ and as a decryption algorithm some standard encoding of the pair $(p_1, p_2)$.

User $C$ publicizes the pair $(n, y)$ keeps secret the pair $(p_1, p_2)$.

How to Encrypt

Suppose user $B$ want to send a binary string $b = b_1 \cdots b_l$ to user $C$. Then, for each $b_i \in b$, $B$ picks $x \in Z_n^*$ at random if $b_i = 1$ $B$ sets $e_i = y x^2 \mod n$ else $B$ sets $e_i = x^2 \mod n$ $B$ sends $C$ the $l$-tuple $(e_1, ..., e_l) = E_n(b)$.

Encoding an $l$-bit message $b$ takes $O(l k^2)$ time. In general, one bit of cleartext is expanded into $k$ bits of cyphertext.

How to Decrypt

Suppose user C receives $(e_1, ..., e_l)$, the encryption of a message $b$. Then, for each $e_i \in e$, C sets $b_i = Q_n(e_i)$. (Note: As C knows the factorization of $n$, he can compute $Q_n(x)$) C sets $b = b_1 \cdots b_l$.

Computing $b, |b| = l$, from its encryption requires $O(lk^3)$ time.

5 THE SECURITY OF A PUBLIC KEY CRYPTOSYSTEM

We proceed to discuss the notion of security of a public key cryptosystem. Clearly, the notion of security in a public key cryptosystem depends on the model of possible behavior of an adversary. In this paper the adversary is a passive line-tapper. This adversary knows the message space and its probability distribution, knows the encryption algorithm, is given the cyphertext, and tries, by computing, to retrieve the cleartext.

5.1. Polynomial Security

Informal Setting

Let the message-finder $F$ and the line-tapper $T$ be your favorite computational model with polynomially bounded computational resources. Such $F$ and $T$ may be polynomial time Turing machines, probabilistic polynomial time Turing machine, "small" circuits etc. Intuitively, we say that a public key cryptosystem is polynomially secure if for all message spaces $M$ with any probability distribution, the encryption algorithms produced by the server will be such that: the polynomially bounded message finder $F$ cannot find two messages $m_1$ and $m_2$ in $M$ whose encryptions are distinguishable by the polynomially bounded line-tapper $T$. That is, given $\alpha$ (an encryption of either $m_1$ or $m_2$) $T$ should not have any advantage in understanding which of the two messages is being encoded by $\alpha$. Notice that there might very well be a pair of messages whose encryptions are distinguishable by $T$, but it will be impossible for the polynomially bounded $F$ to find such a pair. Note that PKCs generating deterministic encryption algorithms (e.g., RSA) cannot be polynomially secure.

In this paper, the message-finder and the line-tapper are chosen to be circuits.

Formal Setting

Let $\Pi$ be a PKC. Let MG be a message generator. We write $M_k$ for MG$k$. Without loss of generality, we assume that all $m \in M_k$ have the same length $l_k = Q(k)$ for some polynomial $Q$.

A k-line tapper is a circuit C with one Boolean output and enough Boolean inputs to receive (the description of an encryption algorithm) $E \in \Pi(k, MG)$ and $\alpha \in E(m)$, where $m \in M_k$ (see Fig. 1). Let $m_1, m_2 \in M_k$. Let $p_1^E$ be the probability with which C outputs 1 on inputs $E \in \Pi(k, MG)$ and $\alpha \in E(m_1)$ and $p_2^E$ be the probability with which C outputs 1 on inputs $E \in \Pi(k, MG)$ and $\alpha \in E(m_2)$. We say that C P-distinguishes $m_1$ from $m_2$ with respect to $E$ if $|p_1^E - p_2^E| > 1/P(k)$.

A k-message-finder is a circuit C with $2l_k$ Boolean outputs and enough Boolean inputs to describe an $E \in \Pi[k, MG]$. On input $E$, C outputs two messages $m_1, m_2 \in M_k$ (see Fig. 2).

Notice that $F_k$ may have a built-in description of MG.

Definition (Polynomially secure public key cryptosystems). Let $Q, P_1, P_2$ be polynomials. Let $\Pi$ be a public key cryptosystem and MG a message generator. Let $T = \{T_k\}$, where $T_k$ is a k-line-tapper with less than $Q(k)$ gates. Let $s_k^T$ be the size of a minimum size message-finder $F$ that with probability greater than $1/P_1(k)$ on input $E \in \Pi(k, MG)$ and MG outputs two messages $m_1$ and $m_2$ in $M_k$ such that $T_k$ $P_2$-distinguishes $m_1$ from $m_2$. We say that $\Pi$ is a polynomially secure with respect to MG if for any sequence of line-tappers $T$, $s_k^T$ grows faster than any polynomial in $k$. We say that $\Pi$ is a polynomially secure if for any message generator MG, $\Pi$ is polynomially secure with respect to MG.

Remark. Notice that in the definition of a polynomially secure public key cryptosystem we are not putting any constraints on the probability of $m_1$ and $m_2$. Thus, not even two messages that are very unlikely to occur and are distinguishable by $T_k$ can be easily found.

It is intuitive, and will be formally proved that polynomial security implies more traditional notions of security. Informally, if a public key cryptosystem is polynomially secure then no polynomially bounded line-tapper $T$ can, given the cyphertext, retrieve the cleartext or any partial information about it.

We first show that the newly introduced probabilistic PKCs are indeed polynomially secure.

Remarks about Theorem 5.1. The underlying idea of the proof of Theorem 5.1 is a sampling walk. Assume that every vertex $v$ in a $d$-dimensional hypercube $C$ is labeled with a real number $\lambda(v)$ in between 0 and 1 and that it is easy to find two vertices $u$ and $v$ such that $|\lambda(u) - \lambda(v)| > \varepsilon$. Then it is easy to find two adjacent vertices $s$ and $t$ such that $|\lambda(s) - \lambda(t)| > \varepsilon / d$: just find vertices $u$ and $v$ in $C$ such that $|\lambda(u) - \lambda(v)| > \varepsilon$; then consider $(\omega_0, ..., \omega_k)$, a minimum length vertex-walk from $u$ to $v$ and look at the pairs $(\omega_l, \omega_{l+1})$.

In our case, every vertex $v$ of the hypercube is a $d$-bit word. The label $\lambda(v)$ is the frequency with which the line-tapper outputs 1 on the probabilistic encryptions of $v$. We quickly approximate these frequencies by sampling. Then we find two adjacent words $s$ and $t$ with a jump in their associated frequency, and use $s$ and $t$ to approximate the UTP on which the system is based.

Theorem 5.1. Each probabilistic public key cryptosystem is polynomially secure.

Proof of Theorem 5.1. Let

be an unapproximable trapdoor predicate. Let $\Pi$ be a PPKC that on inputs $k$ and MG outputs $i \in S_k$ and $\sigma(i)$ with probability $1/|S_k|$. This specifies a probabilistic encryption algorithm $E$, as specified in Subsection 4.3. Recall, that $T_k$, the line-tapper, is a poly($k$) size circuit which upon receiving as input $i$ and a probabilistic encoding of $m$ in $M_k$ encoded using $B_i$, outputs either a 0 or a 1.

Let $f_{i,m}$ be the frequency with which $T_k$ outputs a 1 when given as input all the probabilistic encodings of $m$ using $B_i$.

Let $P_1$ and $P_2$ be polynomials. For $k \in N$ set

and let $F_k$ be a message-finder. Let $N''$ be an infinite subset of $N'$. Assume that for a fraction $\eta_k$ of the $i \in S_k$ $F_k$ outputs two messages $m_1^i$ and $m_2^i$ such that

Then we will show that for all $k \in N''$, there is a probabilistic poly$(k, \delta^{-1})$ time Turing machine $G$ with oracles $F_k$ and $T_k$ that with probability $1 - \delta$, $(\varepsilon_k/5l_k)$-approximates $B_i$ for a fraction $\eta_k/2$ of the $i \in S_k$.

Consequently, as the size of $T_k$ is bounded by a polynomial in $k$, if also the size of $F_k$ were bounded by a polynomial in $k$, $G$ could easily be converted, for each $k \in N''$, into a poly$(k)$ size circuit $C_k$ that $(\varepsilon_k/5l_k)$-approximates $B_i$ for at least a fraction $\eta_k/2$ of the $i \in S_k$. This would contradict the unapproximability of $B$. Thus, the size of $F_k$ must grow faster than any polynomial in $k$ and $\Pi$ is polynomially secure.

The Hamming distance between $a$ and $b \in \{0, 1\}^{l_k}$ is the number of bits in which $a$ and $b$ differ, and we say that $a$ and $b$ are adjacent if the distance between them is 1.

We proceed to construct the Turing machine $G$. Let $\Omega_i^{l_k}$ denote the set of all $l_k$-long sequences of elements of $\Omega_i$. On input $i \in S_k$ and $y \in \Omega_i$, $G$ guesses $B_i(y)$ as follows:

Part 1. It calls the oracle $F_k$ with input $i$ to find $m_1^i$ and $m_2^i$ in $M_k$ such that

Let $\Delta$ be the distance between $m_1^i$ and $m_2^i$. Let $a_0, a_1, ..., a_\Delta$ be a sequence of $l_k$-bit strings such that $a_0 = m_1$, $a_\Delta = m_2$ and $a_j$ is adjacent to $a_{j+1}$ for $0 \leq j < \Delta$. As $|f_{i,m_1^i} - f_{i,m_2^i}| > \varepsilon_k$ there must exist $x, 0 \leq x \leq \Delta - 1$, such that $|f_{i,a_x} - f_{i,a_{x+1}}| > \varepsilon_k/l_k$.

Assign $\Omega_i$ and $\Omega_i^{l_k}$ the uniform probability distribution. By the trapdoor property of $B$, in probabilistic poly$(k, \delta^{-1})$ time, such $a_x$ and $a_{x+1}$ can be correctly found with probability greater than $1 - \delta$ by means of a Monte Carlo experiment. For notational convenience, let $s = a_x$ and $t = a_{x+1}$. Compute $f_{i,s}$ and $f_{i,t}$.

As $s = (s_1, ..., s_{l_k})$ and $t = (t_1, ..., t_{l_k})$ are adjacent, they differ in exactly one location. Call this location $d$.

Part 2. Assume, without loss of generality, that $f_{i,s} > f_{i,t}$.

Case 1. $s_d = 1, t_d = 0$.

Then, pick $x = (x_1, x_2, ..., x_{l_k}) \in \Omega_i^{l_k}$ at random among all the elements $e = (e_1, ..., e_{l_k})$ in $\Omega_i^{l_k}$ such that $B_i(e_j) = s_j = t_j$ for $j \neq d$ and $e_d = y$.

(Recall that $y$ is the input of $G$.)

if $T_k(x) = 1$ then $G[y] = 1$ else if $T_k(x) = 0$ then $G[y] = 0$.

Case 2. $s_d = 0$ and $t_d = 1$.

Proceed as in Case 1, but set $G[y] = 1 - T_k[x]$. This completes the description of $G$.

Let us prove that, if $s$ and $t$ have been correctly found, for a fraction $\eta_k/2$ of the $i$'s in $S_k$, for $y \in \Omega_i$,