UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

BROADCAST INTERACTIVE PROOFS

BURMESTER, M; DESMEDT, Y; (1991) BROADCAST INTERACTIVE PROOFS. LECT NOTES COMPUT SC , 547 81 - 95.

Full text not available from this repository.

Abstract

In this paper we extend the notion of (single-verifier) interactive zero-knowledge proofs to (multi-verifier) broadcast proofs. In our scheme the prover broadcasts messages to many verifiers simultaneously. We consider two cases: one for which the number of rounds of messages exchanged is unbounded (as a function of the length of the common input x), and one for which it is constant. Compared to repeated single-verifier proofs (one proof for each verifier), the saving. in broadcast bits is of the order of the number of verifiers in the first case, provided there axe enough verifiers. More precisely, if the number of verifiers exceeds log Absolute value of x then there is ''practically'' no extra cost in broadcast bits by further increasing the number of verifiers. In the second case the saving in the number of rounds is ''practically'' Absolute value of x log Absolute value of x. An added feature of broadcast proofs of the second type is that they axe sabotage-free.Our scheme makes use of a network which directs the messages of the verifiers to the prover. The universality of the scheme derives from the way in which the network handles collisions.

Type:Article
Title:BROADCAST INTERACTIVE PROOFS
Keywords:KNOWLEDGE
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record