Local verifiability

Definition 7.27 (Local verifiability). Let a pair CorrFam, GoodFam) as in Definition 7.25 be given. It is called locally verifiable if there is... 

Remark 7.35. If the good prekeys are locally verifiable, and thus there is no error probability in the soundness of the zero-knowledge proof scheme, there is no real use for the family AllFam any more, and all jest can be omitted. ... 

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

If the prekey is locally verifiable, one can consider letting the entities of the risk bearers carry out the prekey generation without the signer s entity, because the signer s entity can verify the correctness of the prekey afterwards. This may be worth while if one wants to use the same prekey for all signers, as in Remark 7.36. However, one must take some care to fulfil effectiveness and correctness of initialization. 

A zero-knowledge proof scheme could be permitted instead of local verifiability, or, as with prekeys, two families of good and all acceptable groups. 

As mentioned before, the definitions could be relaxed by allowing more algorithms to be probabilistic and allowing more small error probabilities. In particular, one could restrict more properties to good keys (which are assumed to be verified with zero-knowledge proofs and thus with error probabilities), instead of all acceptable keys (which are assumed to be locally verifiable). 

In the scheme with local verifiability As GoodFam = AllFam in the given family BundFam, the good keys are locally verifiable, too, i.e., the zero-knowledge proof scheme is derived from alljtest with Lemma 7.28. (Of course, this algorithm only needs to be carried out once in A and res)... 

Functions tau and taui that determine the bundling degree in the schemes with local verifiability and with zero-knowledge proof, respectively, are defined as follows ... 

Scheme with local verifiability For A e Goodji T only a much weaker bound is shown ... 

Furthermore, the zero-knowledge proof scheme from [GrPe88] with the modifications sketched in Section 8.1.3 is used to prove that n is a generalized Blum integer, or it is locally verified that n g 4N + 1, respectively. 

The random choice of y (and similarly y ) in RQR works as follows In the scheme with zero-knowledge proof, y is chosen randomly in 2Z , and y = y or y = -y, whichever is smaller than nil, is used. In the scheme with local verifiability, a number y is chosen repeatedly, until it has the Jacobi symbol +1, and then negated if it is greater than nil. 

Remark 9.20. In the scheme with local verifiability, the random choice of jkj and sk2 is rather inefficient because of the computation of Jacobi symbols. One could avoid this if the bundling homomorphism were based on RQR% instead of RQR. However, no polynomial-time membership test in RQR" is known, and hence Definition 8.29 is not fulfilled. Nevertheless, it is now shown that the random choice in the main key generation of the signature scheme can be restricted to RQR, while maintaining the weaker membership tests for RQR in test and in verify simple. 

The schemes with zero-knowledge proof and with local verifiability can be treated together if one uses the abbreviation... 

In the scheme with local verifiability Generation of random numbers (six on average, because half of all numbers have the Jacobi symbol +1), the computation of Jacobi symbols (four on average) and 2t squarings modulo numbers of length 1. 

Discrete-logarithm scheme Factoring scheme with zero-knowledge proof Factoring scheme with local verifiability... 

In addition to a family of hash functions in the sense of Definition 8.35, one needs a method to verify that keys are acceptable before they are used. As no difference between good and all acceptable keys had to be made with hash fimctions, local verifiability is assumed. 

Remark 10.6 (Two variants of broken ). If a collision of the hash function occurs as a proof of forgery, it is sufficient to choose a new hash function, whereas one can retain the prekey prek from the underlying scheme and the values sk and mk. As the keys of the hash functions were assumed to be locally verifiable, only the risk bearer(s) have to publish a new key of a hash function after such a proof of forgery, whereas the signers need not send any new information. This may be helpful if one decides to use fast, but not provably collision-intractable hash functions. 

Finally both models can be combined together, with source parameters estimated by a regional network and ground motion locally verified at a specific site. 

---