Interactive Aggregate Signatures from Lattices

原创 Kurt Pan XPTY

2021年07月22日 17:47

Let , and be positive integers and be a Gaussian parameter. Let be a message space and let be hash functions that are modeled as random oracles. We construct an interactive aggregate signature scheme as follows:

On input a security parameter , the parameter generation algorithm samples a random vector and sets
On input the public parameters , the key generation algorithm samples a short vector and defines It sets

Each signer has access to a list of public keys , its own signing key , and a message that it seeks to sign. It proceeds in each round of the protocol as follows:

Round 1: Signer samples a vector and computes It computes a hash commitment and sends to each cosigners.
Round 2: Signer receives the hash commitments from the cosigners. It sends the committed value to each cosigners.
Round 3: Signer receives from the cosigners. It proceeds as follows:

It verifies that for all It aborts the protocol and returns if any of these checks fail.
It computes and computes the hash
It sets It sends to each cosigners with probability . Otherwise, it sends to the signers to signal that it aborted. If there exists at least one signer that aborted during the protocol, each signer returns . Otherwise, at the end of the protocol, each signer holds the element as well as the set of vectors Each signer sets and returns

On input a set of public keys , messages , and a signature , the verification algorithm computes for , and defines It accepts the signature if both of the following conditions hold:

Theorem (Compactness). Let be a positive integer, or , and suppose that the parameters are set as polynomial functions over Then, the aggregate signature scheme above is compact .

Theorem (Correctness). Suppose that the parameters of Construction above are set such that the ring is instantiated as either or for a positive integer , and that the inequality holds. Then, Construction above is correct .

Theorem (Security). Suppose that the parameters of Construction above are instantiated such that the ring is instantiated with either or for a positive integer , and that the parameters satisfy the conditions of the leftover hash lemma . With these parameter settings, assume that the SIS problem for is hard. Then, the interactive aggregate signature scheme in Construction above satisfies unforgeability.