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 $\ge 2^{100}$ 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-knowledgewitness indistinguishablewitness hidingargument of knowledgelattice-based hashingverifiable secret sharinglarge secrets
Contact author(s)
cryptomniumllc @ gmail com
History
2017-09-06: received
Short URL
https://ia.cr/2017/846
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.