abstract.tex

\begin{abstract}

Non-Interactive Zero-Knowledge (NIZK) proofs, are proofs that yield nothing beyond their validity. As opposed to the interactive variant, NIZK proofs consist of only one message and are more suited for building inherently non-interactive schemes, like signatures or encryption, and for high-latency scenarios. While there exist very efficient (constant-size, with a  prover quasi-linear in the circuit size) for proving circuit satisfiability, they rely on very strong assumptions, namely knowledge-of-exponent type of assumptions. These assumptions are very controversial because they are non-falsifiable (according to a classification by Naor), meaning they can't be proven to be false. 


In addition to the use of non-falsifiable assumptions, the generality of NIZK proofs for NP-complete languages hides a subtle: the use of (expensive) reductions from the statement to the satisfiability of a circuit, while in cryptographic applications statements are more naturally expressed by other means. In fact, with the advent of Pairing-Based Cryptography many cryptosystems have been built using bilinear groups, that is, three abelian groups $\GG_1$, $\GG_2$, $\GG_T$ of order $q$ together with a bilinear function $e : \GG_1 \times \GG_2 \to \GG_T$. Statements related to pairing-based cryptographic schemes are more naturally expressed as the satisfiability of equations over these groups and $\Z_q$.

The Groth-Sahai proof system, introduced by Groth and Sahai at Eurocrypt 2008 allows to prove the satisfiability of equations over bilinear groups and over the integers modulo a prime $q$. Its security relies on standard and falsifiable assumptions such as the Decisional Diffie-Hellmann assumption. Although Groth-Sahai proofs are quite efficient, they easily get expensive unless the statement is very simple. Specifically, proving satisfiability of $m$ equations in $n$ variables requires 
sending as commitments to the solutions $\Theta(n)$ elements of a bilinear group, and a proof that they satisfy the equations, which we simply call the proof, requiring additional $\Theta(m)$ group elements. 

Jutla and Roy at Crypto 2013 constructed constant size proofs for very specific statements: proofs of membership on linear subspaces of $\GG^n_1$ (or $\GG_2^n$). They rely only on standard assumptions and, interestingly, they showed that the same techniques allow to construct Groth-Sahai proofs of size $\Theta(n)+\Theta(1)$ for some linear equations -- i.e.~$\Theta(n)$ group elements for the solutions plus a constant-size proof for the satisfiability of the equations.

In this thesis we study how to construct more efficient proofs for all types of equations and how to use them to build more efficient cryptographic schemes. We show that \textbf{all linear equations} over the integers admit proofs of size $\Theta(1)$ and then we show how to extend these results for linear equations over bilinear groups with some limitations. We use these results to build constant-size proofs that two sets of commitments open to the same values. We then study the case of quadratic integer equations, more concretely the equation $b(b-1)=0$ which is the most useful type of quadratic integer equation. We construct a proof of size $\Theta(1)$ for the satisfiability of $b_1(b_1-0)=0, \ldots, b_n(b_n-1)=0$. We use these results to build more efficient \emph{Threshold Groth-Sahai} proofs and more efficient \emph{Ring Signatures}.

We then study a natural generalization of quadratic equations which we call set-membership proofs -- i.e.~to show that a variable belongs to some set -- which in the case of integer sets captures high-degree equations -- i.e.~$p(x)=0$ for a polynomial $p$. We first show that many set-membership proofs for any subset of $\GG_1$ or $\GG_2$ admits aggregated proofs of size $\Theta(t)$, where $t$ is the set size, and when the set is of the form $[0,t-1]\subset\Z_q$ admit an aggregated proof of size $\Theta(\log t)$. We note that some cryptographic schemes can be naturally constructed as set-membership proofs, specifically we study the case of \emph{Proofs of Correctness of a Shuffle} and \emph{Range Proofs}. Starting from set-membership proofs as a common building block, we build the shortest proofs for both proof systems.
 We then further improve the size of our set-membership proofs and show that 
 \textbf{all set-membership proofs over the integers} admit aggregated proofs of size $\Theta(\log t)$, where $t$ is the set size. We also show that these results can be extended to set-membership proofs over bilinear groups meeting some restrictions.
 
\end{abstract}