eprintid: 1398517
rev_number: 40
eprint_status: archive
userid: 608
dir: disk0/01/39/85/17
datestamp: 2013-07-08 13:29:17
lastmod: 2021-11-04 00:12:52
status_changed: 2013-07-08 13:29:17
type: proceedings_section
metadata_visibility: show
item_issues_count: 0
creators_name: Bayer, S
creators_name: Groth, J
title: Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists
ispublished: pub
divisions: UCL
divisions: B04
divisions: C05
divisions: F48
note: © IACR 2013. This article is the final version submitted by the author(s) to the IACR and to Springer-Verlag. The version published by Springer-Verlag is available at 10.1007/978-3-642-38348-9_38
abstract: Verification of a polynomial’s evaluation in a secret committed value plays a role in cryptographic applications such as non-membership or membership proofs. We construct a novel special honest verifier zero-knowledge argument for correct polynomial evaluation. The argument has logarithmic communication cost in the degree of the polynomial, which is a significant improvement over the state of the art with cubic root complexity at best. The argument is relatively efficient to generate and very fast to verify compared to previous work. The argument has a simple public-coin 3-move structure and only relies on the discrete logarithm assumption.

The polynomial evaluation argument can be used as a building block to construct zero-knowledge membership and non-membership arguments with communication that is logarithmic in the size of the blacklist. Non-membership proofs can be used to design anonymous blacklisting schemes allowing online services to block misbehaving users without learning the identity of the user. They also allow the blocking of single users of anonymization networks without blocking the whole network.
date: 2013
publisher: Springer Verlag
official_url: http://dx.doi.org/10.1007/978-3-642-38348-9_38
vfaculties: VENG
oa_status: green
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_source: Manually entered
elements_id: 883327
doi: 10.1007/978-3-642-38348-9_38
lyricists_name: Groth, Jens
lyricists_id: JGROT52
full_text_status: public
series: Lecture Notes in Computer Science
volume: 7881
place_of_pub: Berlin/ Heidelberg, Germany
pagerange: 646 - 663
event_title: Advances in Cryptology - EUROCRYPT
isbn: 978-3-642-38347-2
book_title: Advances in Cryptology – EUROCRYPT 2013: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013
citation:        Bayer, S;    Groth, J;      (2013)    Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists.                     In:  Advances in Cryptology – EUROCRYPT 2013: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013.  (pp. 646 - 663).  Springer Verlag: Berlin/ Heidelberg, Germany.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/1398517/2/PolynomialZK30.pdf