You are looking at a specific version 20131024:083457 of this paper. See the latest version.

Paper 2013/670

Switching Lemma for Bilinear Tests and Constant-size NIZK Proofs for Linear Subspaces

Charanjit Jutla and Arnab Roy

Abstract

We state a switching lemma for tests on adversarial inputs involving bilinear pairings in hard groups, where the tester can effectively switch the randomness used in the test from being given to the adversary to being chosen after the adversary commits its input. The switching lemma can be based on any $k$-linear hardness assumptions on one of the groups. In particular, this enables convenient information theoretic arguments in the construction of sequence of games proving security of cryptographic schemes, paralleling proofs and constructions in the random oracle model. As an immediate application, we show that the quasi-adaptive NIZK proofs of Jutla and Roy (ASIACRYPT 2013) for linear subspaces can be further shortened to \emph{constant}-size proofs, independent of the number of witnesses and equations. In particular, under the SXDH assumption, a length $n$ vector of group elements can be proven to belong to a subspace of rank $t$ with a quasi-adaptive NIZK proof of just a single group element. Similar quasi-adaptive aggregation of proofs is also shown for Groth-Sahai NIZK proofs of linear multi-scalar multiplication equations, as well as linear pairing-product equations (equations without any quadratic terms).

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
NIZKbilinear pairingsquasi-adaptiveGroth-SahaiRandom OracleIBECCA2
Contact author(s)
arnabr @ gmail com
History
2018-09-14: last of 6 revisions
2013-10-24: received
See all versions
Short URL
https://ia.cr/2013/670
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.