Main public key test

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. 

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. 

The main public key test verifies that mk is a possible hash value, i.e., that its length is 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.)... 

Main public key test Each value mk,- is tested as in Lemma 9.12. 

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. 

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. 

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). ... 

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.)... 

Testing On input a message nij and a supposed signature s = (mk,. j, j,), the new one-time main public key is tested with mkjtest and then the new one-time signature with test(mki, mi, mfc,+i), s,), where the current one-time main public key rnkf is taken from locaJ memory. If the result is TRUE, the overall result is TRUE, too, and mki is replaced by as the current one-time main public key. 

---