Hofheinz and Kiltz’s paper *Practical Chosen Ciphertext Secure Encryption from Facoring* is based upon the scheme proposed by Rabin in his 1979 paper *Digital signatures and public key functions as intractable as factorization*. I could not find a digital copy of this paper, but I did find a paper by Goldwasser and Micali from 1983 entitled *Probabilistic Encryption* that discusses the results mentioned in the Rabin paper.

Rabin’s PKE scheme is a particularization of RSA. For the (brief) description of RSA below, let Euler’s totient function, let , and let be the message — i.e. let . Of course, we are thinking of as the multiplicative group over , which has size . Recall that in RSA:

Initialization
- The sender selects two large primes and , and multiplies them together to get .
- selects such that and are relatively prime.
- Typically, calculates a such that , using something like the extended Euclidean algorithm.
- and releases and as public keys. The primes and and the inverse are kept as the secret keys.

Encryption
- computes

Decryption
- computes

Rabin’s scheme modifies this simply by choosing , and so the encryption function is . In the Goldwasser and Micali paper, the authors claim that means that is a 4-1 function (does anyone see why this must be true?). From Rabin, we then have the following theorem and lemma.

**Theorem 1 (Rabin)** * If for a fraction of the quadratic residues one could find one square root of , then one could factor in random polynomial time. *

In other words, if we were to make an otherwise secure Rabin-based cryptosystem, breaking the scheme would require the attacker to factor integers, which of course we assume is difficult (at least for non-quantum computers). The Rabin’s theorem follows from Lemma 2 below (presented without proof).

**Lemma 2** * Given such that and , there is a polynomial time algorithm to factor . *

### Like this:

Like Loading...

## 1 comment

Comments feed for this article

May 22, 2010 at 9:56 am

TomIn fact, I regularly give the proof of lemma 2 as a homework problem in my crypto class.

The fact that squaring is 4-to-1 over follows from the fact that squaring is 2-to-1 over when is prime, and that there is an isomorphism between and . The elements of the later group that square to the identity are , so there are also four elements that square to in . (This isomorphism is the Chinese Remanider Theorem.)