IACR News item: 24 October 2013
Charanjit Jutla, Arnab Roy
ePrint ReportThe 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).
Additional news items may be found on the IACR news page.