Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization

Keita Xagawa

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2016/476

Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization

Keita Xagawa

Abstract

The Groth-Sahai proof system (EUROCRYPT 2008, SIAM Journal of Computing 41(5)) provides efficient non-interactive witness-indistinguishable (NIWI) and zero-knowledge (NIZK) proof systems for languages over bilinear groups and is a widely-used versatile tool to design efficient cryptographic schemes and protocols. We revisit randomization of the prover in the GS proof system. We find an unnoticed bug in the ``optimized'' randomization in the symmetric bilinear setting with several assumptions, say, the DLIN assumption or the matrix-DH assumption. This bug leads to security issues of the GS NIWI proof system with ``optimized'' randomization for multi-scalar multiplication equations and the GS NIZK proof system with ``optimized'' randomization for certain cases of pairing product equations and multi-scalar multiplication equations.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Non-interactive proof systems the Groth-Sahai proof system symmetric bilinear groups the DLIN assumption
Contact author(s): xagawa keita @ lab ntt co jp
History: 2016-05-20: revised; 2016-05-19: received; See all versions
Short URL: https://ia.cr/2016/476
License: CC BY

BibTeX

@misc{cryptoeprint:2016/476,
      author = {Keita Xagawa},
      title = {Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization},
      howpublished = {Cryptology ePrint Archive, Paper 2016/476},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/476}},
      url = {https://eprint.iacr.org/2016/476}
}