How to Prove Megabytes (Per Second)

Yaron Gvili

Paper 2017/846

How to Prove Megabytes (Per Second)

Yaron Gvili

Abstract

We propose the first provably secure zero-knowledge (ZK) argument of knowledge (AoK) protocol running at close to 1 megabyte per second (MBps) on commodity hardware -- about an order of magnitude faster than relevant current protocols. It is a post-quantum, (efficient-prover) honest-verifier (HV) statistical zero-knowledge (SZK) sigma protocol in the standard model under a hardness assumption on ideal lattices. We further propose an overhead-efficient low-latency amortization yielding a witness indistinguishable (WI) and witness hiding (WH) AoK protocol running at $> 100$ MBps. Both protocols have absolute soundness slack 1, or zero for small completeness error, and an argument size growing linearly, where amortization has slope 2 and latency 1 microsecond. Non-interactive (NI), non-HV, resettable ZK (rZK) and resettable WI (rWI) variations of the protocols are obtained using standard transforms. Choices of parameters with concrete security against known attacks are given along with experimental results showing practicality.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: zero-knowledge witness indistinguishable witness hiding argument of knowledge lattice-based hashing verifiable secret sharing large secrets
Contact author(s): cryptomniumllc @ gmail com
History: 2017-09-06: received
Short URL: https://ia.cr/2017/846
License: CC BY

BibTeX

@misc{cryptoeprint:2017/846,
      author = {Yaron Gvili},
      title = {How to Prove Megabytes (Per Second)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/846},
      year = {2017},
      url = {https://eprint.iacr.org/2017/846}
}