Main public key

If the signer s entity is convinced, it generates a secret key and a corresponding public value mk, called the main public key, based on prek. The complete public key consists of prek and mk. ... 

For example, the prekey may be a number n=p q, and the risk bearer s entity may have to convince the signer s entity that n really has exactly two prime factors, but without showing it these factors, before the signer s entity generates the secret key and the main public key as certain numbers modulo n. 

A first expects to receive a value prek from the risk bearer s entity on the broadcast channel and tests it with all test par, prek). If the result is FALSE, it stops. Otherwise, it carries out the verifier s part, V, of the zero-knowledge proof scheme on input (par, prek), using the broadcast channel for all messages. This gives a result acc. If acc = FALSE, it stops. Otherwise, it executes gen (par, prek) to obtain values sk temp and mk. It broadcasts mk, the main public key, and outputs sk temp. 

If the prekey is locally verifiable, key distribution is identical to ordinary digital signature schemes after the initial publication of the prekey Every new signer simply publishes her main public key (except that, if the local verification of the prekey yielded FALSE, the signer would have to call on recipients and courts to punish the risk bearer). ... 

Main public key test mkjest (on input ( 1 , V, prek, mk) with prek = (q, p, g, g ) and mk = (mki, mk2)) Instead of testing that mki elements of Hgp, it is usually sufficient to test that they are in Zp The length restrictions are still fulfilled, and the only other property that could be violated by enlarging the set of acceptable main public keys is that test works in polynomial time for all public keys.that can possibly occur, and any usual multiplication algorithm works on the entire Zp. 

The corresponding main public key is the pair (mfci, mk2) of images under the bundling homomorphism, i.e.,... 

Main public key test mk test Instead of testing that mk and mk2 are elements of RQR, one can simply test that they are in Z , sirnilar to Lemma 9.12. 

As a conclusion, it will usually be optimal to sign each hash value as one message block and to use primes q°, p°, q, and p of approximately equal size, because signing is so much more efficient than testing that its exact complexity does not seem to matter in most applications, whereas longer main public keys are a disadvantage in the following constructions with tree authentication. 

Main key generation On input the parameters and a new prekey prek, N one-time key pairs (sk tempj, mkp based on prek are generated. The values mkj are used as the leaves of a binary tree. The value of each inner node is the hash value of its two children (regarded as one message). The new temporary secret key sk temp consists of the whole tree and a counter for the messages already signed, initialized with zero. But only the final hash value, i.e., the root of the tree, is published as the main public key mk of the new scheme. 

The main public key test verifies that mk is a possible hash value, i.e., that its length is len°(k). 

Thin black arrows denote the relation between a one-time secret key and the corresponding one-time main public key, broad grey arrows denote one-time signatures, and the tree is constructed by repeatedly hashing pairs of values. Values skjemp are abbreviated as sk. 

Test To test a new signature s of the form described above, one first tests the one-time signature sj with respect to the claimed value mkj. Then one reconstructs the values on the path to the root and tests if this path ends at the correct main public key mk. (That is, one starts by hashing mkj and its claimed neighbour, and iteratively hashes each intermediate result with its claimed neighbour until one obtains a value mk that should be the root value this is compared with mk. )... 

To make the components polynomial-time in the interface inputs alone, each value mkj that is received in a signature is first tested with mk test, and it is verified that each value that should be an inner node of the tree, and thus a hash value, is of length len° k). Similarly, a collision in a valid proof of forgery must either consist of acceptable one-time main public keys or values of length len°(k). ... 

Main key generation is almost identical to that of the one-time scheme A one-time key pair (sk temp, mk) based on prek is chosen, mk is the main public key, and the main public key test is identical. The temporary secret key in the new scheme is sk temp = (sk temp, par, prek,j), where par are the parameters, as usual, and j is a string initialized with d zeros, where N = 2 . It serves as a counter of the number of messages already signed. (The message number i in the previous sense is j + 1, if j is interpreted as a binary number.)... 

Test (test ) Given a signature of the form described above, all the one-time main public keys in it are tested with mk test and then the one-time signatures with test, where the top one-time signature is tested with respect to the correct main public key mk. (The form of the path is known from j.)... 

In the long run, only the one-time temporary secret key skjempi is stored at a Node I, but neither the one-time main public key mki nor the one-time signature sp More precisely, mki / t>e deleted when they are no longer needed in the path of any future signature. Hence, when the coimter j is updated toy + 1, and ify denotes the common prefix ofy andy + 1 (as strings), the values at the nodes below Node y 0 and Sj Q are deleted (but mkj Q not yet). 

If the one-time secret key sk tempi = (ski i, sk/2) has been used up by signing a message m/ (which may be a real message or a pair of one-time main public keys), it is processed as follows ... 

---