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
Project(s)No Simula project
Publication TypeProceedings, refereed
Year of Publication2013
Conference NameCryptology and Network Security (CANS 2013)
Pagination92 - 121
PublisherSpringer International Publishing
Place PublishedCham
ISBN Number978-3-319-02936-8
ISSN Number0302-9743

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.

Citation Key26616