Efficient Cryptographic Primitives for Non-Interactive Zero-Knowledge Proofs and Applications

Candidate: Kristiyan Haralambiev

Advisor: Victor Shoup

Non-interactive zero-knowledge (NIZK) proofs have enjoyed much
interest in cryptography since they were introduced more than twenty
years ago by Blum et al. [BFM88].
While quite useful when designing modular cryptographic schemes, until
recently NIZK could be realized efficiently only using certain
heuristics. However, such heuristic schemes
have been widely criticized. In this work we focus on designing
schemes which avoid them. In [GS08], Groth and Sahai presented the
first efficient (and currently the only) NIZK
proof system in the standard model. The construction is based on
bilinear maps and is limited to languages of certain satisfiable
system of equations. Given this expressibility limitation
of the system of equations, we are interested in cryptographic
primitives that are "compatible" with it. Equipped with such
primitives and Groth-Sahai proof system, we show how to
construct cryptographic schemes efficiently in a modular fashion.

In this work, we describe properties required by any cryptographic
scheme to mesh well with Groth-Sahai proofs. Towards this, we
introduce the notion of "structure-preserving"
cryptographic scheme. We present the first constant-size
structure-preserving signature scheme for messages consisting of
general bilinear group elements. This allows us (for the first time)
to instantiate efficiently a modular construction of round-optimal
blind signature based on the framework of Fischlin [Fis06].

Our structure-preserving homomorphic trapdoor commitment schemes
yield efficient leakage-resilient signatures (in the bounded leakage
model) which satisfy the standard security
requirements and additionally tolerates any amount of leakage; all
previous works satisfied at most two of those three properties.

Lastly, we build a structure-preserving encryption scheme which
satisfies the standard CCA security requirements. While somewhat
similar to the notion of verifiable encryption, it provides
better properties and yields the first efficient two-party protocol
for joint ciphertext computation. Note that the efficient realization
of such a protocol was not previously possible even using
the heuristics mentioned above.

Lastly, in this line of work, we revisit the notion of simulation
extractability and define "true-simulation extractable" NIZK proofs.
Although quite similar to the notion of simulation-sound
extractable NIZK proofs, there is a subtle but rather important
difference which makes it weaker and easier to instantiate
efficiently. As it turns out, in many scenarios, this new notion is
sufficient, and using it, we can construct efficient leakage resilient
signatures and CCA encryption scheme.