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
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.