Scribed by Cynthia Sturton
Today we continue to discuss number-theoretic constructions of CPA-secure encryption schemes.
First, we return to the Decision Diffie Hellman assumption (the one under which we proved the security of the El Gamal encryption scheme) and we show that it fails for , although it is conjectured to hold in the subgroup of quadratic residues of .
Then we introduce the notion of trapdoor permutation and show how to construct CPA-secure public-key encryption from any family of trapdoor permutations. Since RSA is conjectured to provide a family of trapdoor permutations, this gives a way to achieve CPA-secure encryption from RSA.
1. Decision Diffie Hellman and Quadratic Residues
Recall that if is a distribution over triples , in which is a cyclic group of elements and is a generator, then satisfies the Decision Diffie Hellman Assumption if for every algorithm of complexity we have
In Lecture 17, we gave the group , prime, as an example of cyclic group for which the discrete logarithm problem is conjectured to be hard. The Decision Diffie Hellman assumption, however, is always false for groups of the type .
To see why, we need to consider the notion of quadratic residue in . An integer is a quadratic residue if there exists such that . (In such a case, we say that is a square root of .)
As an example, let . The elements of are,
The squares of the elements,:
The quadratic residues of :
For every odd primes , exactly of the elements of are quadratic residues, and each has two square roots. Furthermore, there is an efficient algorithm (polynomial in the number of digits of ) to check whether is a quadratic residue. This fact immediately gives an algorithm that contradicts (1) if we take to be , when . To see why this is so, first consider , a generator in . Then is a quadratic residue if and only if is even:
Since is a generator, can be written as,
Squaring every element in gives the quadratic residues:
When is even, is the square of . All the quadratic residues can be written as so must be even.
In (1) is a random element in so it is a quadratic residue with probability . But is a quadratic residue with probability (if are even). Since there is an efficient algorithm to check if a value is a quadratic residue, the algorithm can easily distinguish between and with probability by outputting when it finds that the final input parameter (either or ) is a quadratic residue.
Note, however, that the set of quadratic residues of is itself a cyclic group, and that if is a generator of then is a generator of .
is a cyclic group:
- 1 is a quadratic residue
- if , are quadratic residues, then is a quadratic residue.
- if is a quadratic residue then is a quadratic residue
If is a generator of then is a generator of :
Which is exactly
It is believed that if is a prime of the form , where is again prime then taking and letting be any generator of satisfies (1), with and exponentially large in the number of digits of .
2. Trapdoor Permutations and Encryption
A family of trapdoor permutations is a triple of algorithms such that:
- is a randomized algorithm that takes no input and generates a pair , where is a public key and is a secret key;
- is a deterministic algorithm such that, for every fixed public key , the mapping is a bijection;
- is a deterministic algorithm such that for every possible pair of keys generated by and for every we have
That is, syntactically, a family of trapdoor permutations is like an encryption scheme except that the “encryption” algorithm is deterministic. A family of trapdoor permutations is secure if inverting for a random is hard for an adversary that knows the public key but not the secret key. Formally,
Definition 1 A family of trapdoor permutations is -secure if for every algorithm of complexity
It is believed that RSA defines a family of trapdoor permutations with security parameters and that grow exponentially with the number of digits of the key. Right now the fastest factoring algorithm is believed to run in time roughly , where is the number of digits, and so RSA with -bit key can also be broken in that much time. In 2005, an RSA key of 663 bits was factored, with a computation that used about elementary operations. RSA with keys of 2048 bits may plausibly be -secure as a family of trapdoor permutations.
In order to turn a family of trapdoor permutations into a public-key encryption scheme, we use the notion of a trapdoor predicate.
Definition 2 Let be a family of trapdoor permutations, where takes plaintexts of length . A boolean function is a -secure trapdoor predicate for if for every algorithm of complexity we have
Remark 1 The standard definition is a bit different. This simplified definition will suffice for the purpose of this section, which is to show how to turn RSA into a public-key encryption scheme.
Essentially, is a trapdoor predicate if it is a hard-core predicate for the bijection . If is a secure family of trapdoor permutations, then is one-way, and so we can use Goldreich-Levin to show that is a trapdoor predicate for the permutation .
Suppose now that we have a family of trapdoor permutations and a trapdoor predicate . We define the following encryption scheme which works with one-bit messages:
- : same as
- : pick random , output
Theorem 3 Suppose that is -secure trapdoor predicate for , then as defined above is -CPA secure public-key encryption scheme.
Proof: In Theorem 2 of Lecture 13 we proved that if is a permutation and is a hard-core predicate for , then for every algorithm of complexity we have
we can rewrite (2) as
And taking to be our trapdoor permutation,
showing that is CPA secure.
The encryption scheme described above is only able to encrypt a one-bit message. Longer messages can be encrypted by encrypting each bit separately. Doing so, however, has the undesirable property that an bit message becomes an bit ciphertext, if is the input length of and . A “cascading construction” similar to the one we saw for pseudorandom generators yields a secure encryption scheme in which an -bit message is encrypted as a cyphertext of length only .