caa a22 4500 475827163 CHVBK 20180406123831.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1007/s001450010011 doi (NATIONALLICENCE)springer-10.1007/s001450010011 Short Non-Interactive Cryptographic Proofs [Elektronische Daten] [Joan Boyar, Ivan Damgård, René Peralta] Abstract. : We show how to produce short proofs of theorems such that a distrusting Verifier can be convinced that the theorem is true yet obtains no information about the proof itself. We assume the theorem is represented by a boolean circuit, of size m gates, which is satisfiable if and only if the theorem holds. We use bit commitments of size k and bound the probability of false proofs going undetected by 2 -r . We obtain non-interactive zero-knowledge proofs of size O(mk( log m +r)) bits. In the random oracle model, we obtain non-interactive proofs of size O(m( log m+r) + rk) bits. By simulating a random oracle, we obtain non-interactive proofs which are short enough to be used in practice. We call the latter proofs 's'sdiscreet.'' International Association for Criptologic Rese, 2000 Key words. Cryptographic proofs, Non-interactive proofs, Discreet proofs, Circuit complexity, Multiplicative complexity nationallicence Boyar Joan Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark joan@imada.sdu.dk, DK aut Damgård Ivan Department of Computer Science, BRICS, Aarhus University, DC-8000 Aarhus C, Denmark ivan@daimi.au.dk, DK aut Peralta René Department of Computer Science, Yale University, New Haven, CT 06520-8285, U.S.A. peralta-rene@cs.yale.edu, UK aut Journal of Cryptology Springer Berlin Heidelberg 13/4(2000-09-01), 449-472 0933-2790 13:4<449 2000 13 145 https://doi.org/10.1007/s001450010011 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s001450010011 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Boyar Joan Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark joan@imada.sdu.dk, DK aut NATIONALLICENCE 700 1- Damgård Ivan Department of Computer Science, BRICS, Aarhus University, DC-8000 Aarhus C, Denmark ivan@daimi.au.dk, DK aut NATIONALLICENCE 700 1- Peralta René Department of Computer Science, Yale University, New Haven, CT 06520-8285, U.S.A. peralta-rene@cs.yale.edu, UK aut NATIONALLICENCE 773 0- Journal of Cryptology Springer Berlin Heidelberg 13/4(2000-09-01), 449-472 0933-2790 13:4<449 2000 13 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer