Aggregating hash-based signatures using STARKs
This work presents an approach for compressing regular hash-based signatures using STARKs (Ben-Sasson et. al.'18).
The Lamport+ Signature Scheme
Let be a bitstring that represents the message to be signed, be two hash functions in the ROM, where are the output sizes of and , where Also be a key derivation function
The public parameters are , where is the public key for an accumulator.
The Lamport+ construction is defined as follows:
. Given the public parameters pp and randomness as inputs, KeyGen computes the private key as , "privkey" . For compute a list of tuples ,. Each corresponds to the sub-public-key for each the message-hash bit to be signed. Public key as ,
, priv). On inputs public parameters pp, message and private key priv, expand the private key to the list of tuples similarly to KeyGen . Hash the message and left-truncate it to bits (thus, remove the first bits Count the number of zeros on the remaining bits (this is the checksum) in and append this number representing it with bits. Denote the resulted -sized bitstream as . Compute the signature as follows: For if append to , else append . Output , which is a list of size of -sized elements.
, pub, sig). On input the public parameters pp, the signed message , the public key and the signature , compute similarly to Sign and execute the following logic: For if append to , else append . The verify algorithm outputs the bit
Aggregate Signatures
The scheme is noninteractive: any party can collect Lamport+ signatures over unrelated messages signed individually by different parties and compress them into a single aggregate signature.
The aggregate signature size is logarithmic in the number of individual signatures.
The signature is fast to verify, but the aggregation procedure may require significant time and/or processing power.
Given , a tuple of messages, , a tuple of Lamport+ public keys and , a tuple of Lamport+ signatures, let := a set of public parameters for .
We define :
For in : LP.Verify (LP.pp, Output
LP.pp, STARK.pp), where LP.pp and , are the public parameters for Lamport+ and STARK respectively.
: Given public parameters, LP.pp, integer , messages , public keys and signatures , let , LP.pp and and return ). : On inputs integer , messages , public keys , aggregated signature and public parameters LP.pp, STARK.pp), LP.pp). Output .