AuthorsP. Fauzi, H. Lipmaa and B. Zhang
EditorsD. Hutchison, T. Kanade, J. Kittler, J. M. Kleinberg, F. Mattern, J. C. Mitchell, M. Naor, O. Nierstrasz, P. C. Rangan, B. Steffen et al.
TitleEfficient Modular NIZK Arguments from Shift and Product
AfilliationCryptography
Project(s)No Simula project
StatusPublished
Publication TypeProceedings, refereed
Year of Publication2013
Conference NameCryptology and Network Security (CANS 2013)
Volume8257371918411522619174
Pagination92 - 121
PublisherSpringer International Publishing
Place PublishedCham
ISBN Number978-3-319-02936-8
ISSN Number0302-9743
Abstract

We propose a non-interactive product argument, that is more efficient than the one by Groth and Lipmaa, and a novel shift argument. We then use them to design several novel non-interactive zero-knowledge (NIZK) arguments. We obtain the first range proof with constant communication and subquadratic prover’s computation. We construct NIZK arguments for NP-complete languages, Set-Partition, Subset-Sum and Decision-Knapsack, with constant communication, subquadratic prover’s computation and linear verifier’s computation.

URLhttps://link.springer.com/chapter/10.1007/978-3-319-02937-5_6
DOI10.1007/978-3-319-02937-510.1007/978-3-319-02937-5_6
Citation Key26616