You are currently browsing the category archive for the ‘Uncategorized’ category.

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.

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

http://www.cs.jhu.edu/~jason/advice/how-to-read-a-paper.html

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.

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…)

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