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 ), but I will still be talking about it a high level.

- Quadratic residues are essential to this paper. A number is called a quadratic residue if there exists an such that . If we know , it is easy to find , but it is hard in general to find the . 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 given the factorization of a composite . I’m not sure if I will touch upon the Chinese remainder theorem or not.
- 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? - Take a look at the key encapsulation method and try to figure out how it works. Also, try and figure out how the 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 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:

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

- computes

- 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 2Given such that and , there is a polynomial time algorithm to factor .

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.