Secret, safe and succinct

Krzysztof Pietrzak, Assistant Professor at IST Austria, together with Eike Kitz and Mario Szegedy presents a new scheme for the design of provably secure digital signatures that are shorter and therefore more compact than previously possible. The team of scientists presents their results next week at the annual CRYPTO conference in Santa Barbara (US), one of the two most important academic conferences in the field of cryptography. Their results are the outcome of a collaboration between the cryptologists Kitz and Pietrzak and the combinatorics expert Szegedy, who worked as Visiting Professor in the group of Herbert Edelsbrunner at IST Austria.

A digital signature scheme is used for the authentication of messages:  with a secret key, a digital signature can be created for every message. With the corresponding public key, the recipient of the message can verify that the signature matches the messages, i.e. that the message does indeed come from the stated sender.

The two most important parameters of a signature scheme are the signature length L and the security N, which is measured in bits. N-bits security mean that at least 2^N calculation steps are required to crack the scheme, so to find a valid signature without knowing the secret key. With 100-bit security, one would need the gigantic amount of 2^100 calculation steps for a successful attack. As one can find a signature by simply trying out all possibilities, the signature has to be at least as long as the desired security N. So to achieve N-bit security, the signature has to be as long, or even longer than, the desired security N (L≥N). The shortest signatures known up to now are twice as long as the desired security (L=2N), and therefore far away from the lower limit. In their publication, the scientists show a new signature scheme, in which the signature length reaches the optimal lower limit, as the signature only has to be as long as the desired security (L=N). Therefore, the signatures achieved with the newly developed scheme are significantly shorter than the shortest signatures that were possible with previous schemes.

Short signatures are interesting especially in the context of networks, such as the internet, where some protocols require all packets sent over the network to be authenticated. Here, more compact signatures can save a lot of additional communication required for authentication. Therefore, digitally signed documents can be sent fast, but are still safe.