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.

I found the advice on the following page to be pretty useful.

We seem to spend (an enjoyable) 2+ hours each time we meet, and yet it always feels as though we’ve just scratched the surface on the paper we are discussing.  New definitions take time to understand: you have to poke them, try them out on simple test cases, see how they fall apart if you remove assumptions, etc.  Likewise for constructions: you should look at each piece that is being used and ask “why is this here?”, “what happens if I replace this piece with something weaker?”, and so on.  Theorem statements, too, should be picked apart.  I don’t mean the proof, just the theorem statement: what does the security bound “say”?  What is the scope of the statement, e.g. what kinds of adversaries are allowed by it?

Anyway, it’s easy to spend two hours discussing a paper when you approach it like this.  (In fact, it’s easy to spend four hours.)  And I’m not even including time to discuss the motivation for the problem, related work, open questions.  On the other hand, it’s easy to read a paper naively and feel as though you “got it” in 30 minutes; don’t be fooled.

I think our meetings are useful and interesting, and I hope you agree.  But I think they could be even more so with a bit of organization and good use of available tools  Here are some thoughts.

1. This blog and our mailing list are great places to circulate questions and comments before the meeting.  We can help the discussion leader to focus the discussion.  Is there a definition that doesn’t make sense?  Does it feel like there’s a connection to a previous  paper that we’ve read?  Are you missing the motivation? Is there some bit of notation that is preventing you from making progress?  Say so!

2. For discussion leaders, think about how you want to spend your two hours.  In reality, you can hope to get though a definition or two, a couple of constructions, and one or two main results.  That’s if you yourself really feel like you understand things, and will be able to answer questions and guide the discussion smoothly.  If you aren’t so comfortable with the paper –the more likely case, given your busy schedules and still developing crypto “infrastructure”– then expect to cover even less.

A good (?) template for preparing might be something like this.  First, spend a few minutes setting the stage: what problem(s) are being addressed, and why are these problems interesting/important?  If the authors have written a nice paper, the answers should be in the introduction of the paper.  (But you might have to do some work to unpack the answers so they are accessible to the group.)  Second, briefly introduce the main contributions of the paper: a new definition? a new construction? a new cryptographic primitive or assumption?  a new area of cryptography?  Finally, say which of these you want to focus upon in the discussion — “There are lots of results in this paper, but I’d like to talk mainly about definitions X and Y, the ABC construction and its associated security statement.”  I think all of that should take a maximum of 20 minutes.  The remaining 1.5+ hours can be spent digging in to the parts you really want to explore.

By the way, don’t forget that this is a reading/discussion group, not a conference!  As leader, you should try to be in better command of the paper than the rest of us (otherwise, you can’t really lead a discussion), but no one expects a polished presentation and complete understanding.  The best parts of the meetings, the parts that “stick”, are invariably produced in the discussion anyway.

3. Relatedly, you can probably accomplish more during your two hours by “prepping” the group.  A quick email/blog post that tells everyone (even loosely) what results, theorems, sections you really want to pick apart.  Give a helpful nudge to come with certain things already in mind, e.g. “For the discussion it will be really useful if everyone recalls the IND-CCA notion and what is a tweakable blockcipher.  Also, I’m going to need that entropic security definition from the Dodis, Smith paper, so you might want to look at that quickly before the meeting.”  Of course, it’s the group’s job to make sure they take advantage of your nudging! 🙂

Admittedly, none of what I’m saying here is rocket science; it’s mostly common sense.  But implementing these simple things is not always a simple matter, and really you can never have enough practice at the tasks of reading and discussing what someone else has written.

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

  • The following questions occurred to me while I was reading the intro:

    1. What is the PRIV notion?  ([BBO, C’07])  How does it relate to the notion of entropic security of Dodis and Smith?

    2. Can we find attacks on DtR when the message-randomness entropy is badly split between the message and encryption randomness? (First, what’s “badly split”?)

    3. What is this notion of anonymity of encryptions? ([BBDP, AC’01])

    4. What is the “crooked LHL”?  ([BFO, C’08])

    5. Where are the proofs?! 🙂 (Perhaps we can sketch out the main ideas for some of them…)

    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.

    WordPress has a good introduction to LaTeX.  Terry Tao also has some good things to say about using LaTeX in WordPress.  Lastly, I use a very efficient LaTeX to WordPress’s LaTeX converter written (in python) by Luca Trevisan.

    An example from a well known text:

    Let F: \mathcal{K} \times D \rightarrow R be a family of functions, and let A be an algorithm that takes an oracle and returns a bit.  We consider two games as described in Fig. 3.1.  The prf-advantage of A is defined as

    \displaystyle   \textnormal{\textbf{Adv}}_F^\textnormal{prf}(A) = \textnormal{Pr}\left[\textnormal{Real}_F^A \Rightarrow 1\right] - \textnormal{Pr}\left[\textnormal{Rand}_R^A \Rightarrow 1\right].

    I made this post by first typing up everything into my LaTeX editor (TexShop) and then I used the python script to turn it into the appropriate WordPress code. WordPress doesn’t really have error checking, so I find this to be the fastest way to create posts.

    For more information about the particular ‘Roles’ you can have on a WordPress blog, check out here

    Blog Archives

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

    Join 3 other followers