You are currently browsing Josh Hoak’s articles.

There was an interesting paper just uploaded to the cryptology e-print archive entitled: Near Collisions for the Compress Function of Hamsi-256 Found by Genetic Algorithm. The function — Hamsi 256 — is one of the candidates for the NIST hash competition. I am not sure how damaging this is for the Hamsi hash function, but this paper piqued my interest since I am in general somewhat cynical about the effectiveness of genetic algorithms and so it was cool to see them in action.

Tomorrow, we will be discussing Practical Chosen Ciphertext Secure Encryption from Factoring. I feel like I can guide us through the main proof of this paper, but it would be helpful to review a couple of the following preliminaries. By the way, I will probably be skimming some of the gross math (ex. the correctness of the {\textnormal{\textsf{KEM}}}), but I will still be talking about it a high level.

  1. Quadratic residues are essential to this paper. A number {q} is called a quadratic residue if there exists an {x} such that {x^2 \equiv q \pmod n}. If we know {x}, it is easy to find {q}, but it is hard in general to find the {x}. There are all sorts of really deep mathematics having to do with quadratic residues (and quadratic reciprocity), but the most important for our discussion will be that we can use the Chinese remainder theorem to calculate {x} given the factorization of a composite {n}. I’m not sure if I will touch upon the Chinese remainder theorem or not.
  2. This paper is about a public key cryptoscheme that is CCA secure. The authors of this paper provide their own definition of CCA-security for the key encapsulation method (pp 5, def 2). Does it seem reasonable to use this definition for CCA-security?
  3. Take a look at the key encapsulation method and try to figure out how it works. Also, try and figure out how the {\textnormal{\textsf{BBS}}} random generator (section 3.1) works. I’ll go over these, but it will helpful to have seen them.

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}.

  • Over the next several weeks I (Josh) will be working to understand Practical Chosen Ciphertext Secure Encryption from Factoring by Dennis Hofheinz and Eike Kiltz so I can present on it for our Crypto reading group. It won the Best Paper award at last year’s Eurocrypt. I honestly haven’t looked through it much, but it looks pretty dense which is exciting.

    Blog Archives

    Enter your email address to subscribe to this blog and receive notifications of new posts by email.

    Join 3 other followers