Paper 2016/476

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

Keita Xagawa


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Non-interactive proof systemsthe Groth-Sahai proof systemsymmetric bilinear groupsthe DLIN assumption
Contact author(s)
xagawa keita @ lab ntt co jp
2016-05-20: revised
2016-05-19: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.