EUROCRYPT 11 - Day 2

Tuesday was a short day with only two sessions; one on signatures, on which I will focus, and one on information-theoretic cryptography. The afternoon was then reserved for the social event, which was a walking tour in the historic centre of Tallinn.

The first talk of the day was by Sven Schäge from Bochum who talked about tight proofs for signatures schemes without random oracles. For many standard-model signatures schemes, the proof of unforgeability splits into two cases depending on whether or not the adversary recycles parts of a signature it obtained in a signing query for its forgery. For the recycle case, the simulator in the proof typically guesses which of the queries the forgery will relate to, which introduces a polynomial loss in the reduction. Having tighter security proofs now allows us to use smaller parameters for practical instantiations.

The rest of the session were Bristol papers: the first one by Dario Catalano and Fiore, and Bogdan. Dario II introduced the concept of adaptive pseudo-free groups. This is an abstraction of objects typically used in cryptography where certain operations are "hard". A pseudo-free group is a group with efficient group operations which behaves like a free group for computationally bounded adversaries, such as an RSA group. For cryptographic applications this concept might be too weak, as e.g. for signature schemes, the adversary is allowed to see solutions to non-trivial equations by making signing queries. Adaptive pseudo-free groups extend thus pseudo-free groups to adaptive adversaries.

The last talk of the session was by myself on a new primitive called commuting signatures. They extend the functionality of verifiably encrypted signatures, which enable encryption of signatures and/or messages while giving a publicly verifiable proof that the content is valid. Commuting signatures allow a signer, given an encryption of a message, to produce a verifiably encrypted signature on the plaintext. As an application I gave the currently most efficient instantiation of delegatable anonymous credentials, which can be non-interactively delegated.