*09:17*[Pub][ePrint] Fully Secure and Fast Signing from Obfuscation, by Kim Ramchen and Brent Waters

In this work we explore new techniques for building short signatures

from obfuscation. Our goals are twofold. First, we would like to

achieve short signatures with adaptive security proofs. Second, we

would like to build signatures with fast signing, ideally

significantly faster than comparable signatures that are not based on

obfuscation. The goal here is to create an \"imbalanced\" scheme where

signing is fast at the expense of slower verification.

We develop new methods for achieving short and fully secure

obfuscation-derived signatures. Our base signature scheme is built

from punctured programming and makes a novel use of the \"prefix

technique\" to guess a signature. We find that our initial scheme has

slower performance than comparable algorithms (e.g. EC-DSA). We find

that the underlying reason is that the underlying PRG is called

l^2 times for security parameter l.

To address this issue we construct a more efficient scheme by adapting the Goldreich-Goldwasser-Micali [GGM86] construction to form the basis for a new puncturable PRF. This puncturable PRF accepts

variable-length inputs and has the property that evaluations on all

prefixes of a message can be efficiently pipelined. Calls to the

puncturable PRF by the signing algorithm therefore make fewer

invocations of the underlying PRG, resulting in reduced signing

costs.

We evaluate our puncturable PRF based signature schemes using a

variety of cryptographic candidates for the underlying PRG. We show

that the resulting performance on message signing is competitive with

that of widely deployed signature schemes.