Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Non-interactive proof systems, the Groth-Sahai proof system, symmetric bilinear groups, the DLIN assumption

Date: received 18 May 2016, last revised 19 May 2016

Contact author: xagawa keita at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20160520:022345 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]