Part1Forward-Secure Signatures

1Definition

A forward-secure signature scheme for a message space consists of the following algorithms:

• Key generation: . The signer runs the key generation algorithm on input the maximum number of time periods to generate a public verification key and an initial secret signing key for time period .

• Key update: The signer updates its secret key for time period to for the next period using the key update algorithm.

• Signing: On input the current signing key and message , the signer uses this algorithm to compute a signature .

• Verification. Anyone can verify a signature for on message for time period under public key by running the verification algorithm, which returns 1 to indicate that the signature is valid and 0 otherwise.

Correctness

Correctness requires that for all messages and for all time periods it holds that with probability 1 if and for

Unforgeability under Chosen-message Attack

The experiment generates a fresh key pair and hands the public key to the adversary . The adversary is given access to the following oracles:

• Key update. If the current time period (initially set to ) is less than , then this oracle updates the key to and increases .

• Signing. On input a message , this oracle runs the signing oracle with the current secret key and message , and returns the resulting signature

• Break in. The experiment records the break-in time and hands the current signing key to the adversary. This oracle can only be queried once, and after it has been queried, the adversary can make no further queries to the key update or signing oracles.

At the end of the game, the adversary outputs its forgery . It wins the game if verifies correctly under for time period and message , if it never queried the signing oracle on during time period , and if it queried the corrupt oracle, then it did so in a time period . We define 's advantage as its probability in winning the above game.

2Construction

• Common parameters. Let be the message space of the scheme and let be a hash function that maps messages to bit strings of length such that Apart from the description of the groups, the common system parameters also contain the maximum number of time slots and random group elements . These parameters could, for example, be generated as the output of a hash function modeled as a random oracle.

• Key generation. Each signer chooses and computes It sets its public key to and computes its initial secret keys as .

• Key update. Imagine the time periods as being organized as the leaves of a binary tree of depth , sorted in increasing order from left to right. Then one can see that the path from the root of the tree to leaf node is simply the binary representation of , where means taking the left branch at level , and means taking the right branch. In the same way, each internal node in the tree can be identified by a bit string describing the path from the root, where is the level of the node in the tree. Let's associate to each node a key of the form

for Given the key of an internal node , one can derive a key for a descendant node for as

for Let the minimal cover of leaves be defined as the smallest subset of nodes so that the subset contains an ancestor of all leaves in , but doesn't contain any ancestor of any leaf in . The secret key at time period then contains keys corresponding to all nodes in the minimal cover of . To update to the secret key for time period , the signer determines the cover of , derives keys for all nodes in using the keys in , and securely deletes all re-randomization exponents as well as all keys in .

• Signing. To generate a signature on message in time period , the signer derives from the keys in a key for the leaf node It then chooses and outputs

• Verification. Anyone can verify a signature on message under public key in time period by checking whether

Part2Forward-Secure Multi-Signatures

3Definitions

A forward-secure multi-signature scheme adds the following algorithms.

• Key aggregation: . On input a list of individual public keys the key aggregation returns an aggregate public key , or to indicate that key aggregation failed.

• Signature aggregation. Anyone can aggregate a given list of individual signatures by different signers with public keys on the same message and for the same period into a single multi-signature .

• Aggregate verification. Given an aggregate public key , a message , a time period , and an aggregate signature , the verification algorithm returns 1 to indicate that all signers in signed in period , or 0 to indicate that verification failed.

Correctness

Correctness requires that for all messages , for all , and for all time periods , it holds that with probability 1 if and for and .

Unforgeability under Chosen-message Attack

The adversary is given the public key of an honest signer and access to the same key update, signing, and break-in oracles. However, at the end of the game, the adversary's forgery consists of a list of public keys , a message , a time period , and a multi-signature . The forgery is considered valid if

• is valid with respect to the aggregate public key of , message , and time period ,
• and never made a signing query for during time period .

4Construction

The multi-signature scheme reuses the key update and signature algorithms from the scheme from above section, but uses different key generation and verification algorithms, and adds signature and key aggregation.

• Key generation. Each signer chooses and computes and PoP, , where PoP is a fixed string used as a prefix for domain separation. It sets its public key to and computes its initial secret key as .

• Key aggregation. Given public keys , the key aggregation algorithm first validates the proofs of possession in the public keys by checking whether

for , or equivalently, whether

Of course, these verifications only need to be performed once for each key; after that, the key can be marked as valid and used in more key aggregation without verifying again. If these checks pass, then it computes and returns the aggregate public key . If not, it returns .

• Signature aggregation. Given signatures on the same message , the signature aggregation algorithm outputs

• Aggregate verification. Given an aggregate signature on message under aggregate public key in time period , the verifier accepts if and only if and