Part1Aggregating Bellare-Shoup OTS

Fix a message space and let be two hash functions. We construct an aggregate signature scheme as follows:

• pp: On input a security parameter , the parameter generation algorithm defines a group of prime order . It samples a group element and returns .
• : On input the public parameter pp, the key generation algorithm samples two exponents and computes It sets

• On input a signing key and a message , the signing algorithm computes the hash It sets and returns .
• On input a set of public keys , messages , and signatures , the aggregation algorithm computes the hash It then defines the aggregate signature to be

and returns .

• On input a set of public keys , messages , and a signature , the verification algorithm first parses the public keys as for . It then computes the hash values
• for
• and verifies the following relation:

If the relation holds, then the algorithm accepts the signature (outputs 1 and otherwise, it rejects (outputs 0).

Part2Aggregatable OTS from Lattices

Let and be positive integers and let be a ring. Fix a message and let be two hash functions. We construct an aggregate signature scheme as follows:

• pp: On input a security parameter , the parameter generation algorithm generates a uniformly random vector of ring elements and sets .
• : On input the public parameters pp, the key generation algorithm samples two vectors of ring elements It then defines and sets

• : On input a signing key and a message , the signing algorithm computes the hash . It sets and returns .

• : On input a set of public keys , messages , and signatures , the aggregation algorithm computes the hash in It then defines the aggregate signature as

and returns

• On input a set of public keys as , messages , and a signature , the verification algorithm first parses the public keys for It then computes the hash values
• for
• and then verifies the following conditions:
• If both of these conditions are true, then the algorithm accepts the signature (outputs 1 ) and otherwise, it rejects (outputs 0