Crypto, day 4

My favourite session today was undoubtedly the first one, also because it was related to past work by myself. The first talk was given jointly by Dominique Schröder and Sanjam Garg, which reflected the merged nature of the paper, and was about round-optimal blind signatures. Blind signatures allow a user to obtain a signature on a message which remains hidden from the signer. However, the user cannot get signatures on more messages than he requested; signatures are thus unforgeable. We call such a scheme round optimal if the communication between the user and the signer consists of only one message each.

Applications of blind signatures include e-cash (which is becoming more and more practically relevant), anonymous credentials and e-voting. For example, FIFA used Votopia to determine the most valuable player (not sure whether FIFA is a good testimonial though)...

There is an abundance of literature on the topic of blind signatures and a few of the schemes are round optimal. However, each one has its restrictions: it is proven secure in the random-oracle model, under interactive assumptions, or it requires a trusted setup. The presented paper gives the first (though not practical) scheme that does not have any of these restrictions.

An interesting detail is that their scheme seemingly contradicts a result presented at EUROCRYPT last year which established the impossibility of even 3-move blind signatures. However, this statement only holds for a class of signatures satisfying some technical properties -- in which most schemes fall.

The second talk, given by Jens Groth, also achieved something optimal: the shortest possible structure-preserving signatures. I presented this concept at CRYPTO last year and we showed how it leads to efficient instantiations of numerous primitives when combined with non-interactive zero-knowledge proofs. Examples are group signatures and blind signatures, and consequently their applications as mentioned above.

Structure-preserving signatures are defined over bilinear groups (think elliptic curves); their messages, signatures and verification keys consist of group elements and verification is done by applying the bilinear map to these elements.

If one assumes that the signing algorithm can only perform generic group operations (which implies for example that it does not look at the bit representation of the elements) then due to their rich structure, one can show that it is actually impossible to have signatures consisting of fewer than three group elements, and that there must be at least two verification equations. Having shown this, the authors construct a scheme that achieves this minimal requirements and is thus optimal.