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 {\phi(n)} Euler’s totient function, let {Z^*_n = \{x \in N : 1 \leq x \leq n - 1 \mbox{ and } x \mbox{ and } n \mbox{ are relatively prime} \}}, and let {m} be the message — i.e. let {m \in Z^*_n}. Of course, we are thinking of {Z^*_n} as the multiplicative group over {n}, which has size {|Z^*_n| = \phi(n)}. Recall that in RSA:

  • Initialization
    1. The sender {Alice} selects two large primes {p} and {q}, and multiplies them together to get {n = pq}.
    2. {Alice} selects {s} such that {\phi(n)} and {s} are relatively prime.
    3. Typically, {Alice} calculates a {d} such that {sd = 1 \pmod n}, using something like the extended Euclidean algorithm.
    4. {Alice} and releases {n} and {s} as public keys. The primes {p} and {q} and the inverse {d} are kept as the secret keys.
  • Encryption
    1. {Bob} computes {\mathbf{E}_A(m) = m^s \pmod{n} = c}
  • Decryption
    1. {Alice} computes {\mathbf{D}_A(c) = (m^s)^d \pmod{n} = m^{sd} \pmod{n} = m \pmod n}

    Rabin’s scheme modifies this simply by choosing {s = 2}, and so the encryption function is {\mathbf{E}_A(x) = x^2 \pmod n}. In the Goldwasser and Micali paper, the authors claim that means that {E_A} 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 {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.

    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 {x,y \in Z^*_n} such that {x^2 \equiv y^2 \pmod n} and {x \neq \pm y \pmod n}, there is a polynomial time algorithm to factor {n}.

  • Advertisements