Open access

Author

Date

2023Type

- Doctoral Thesis

ETH Bibliography

yes
Altmetrics

Abstract

The origins of modern cryptography can be traced back to several milestones: Shannon's work on the perfect secrecy of symmetric encryption, the advent of public-key cryptography through the Diffie–Hellman key exchange, and the invention of the RSA public-key encryption scheme. Following these breakthroughs, the introduction of provable security laid out the methodological groundwork for arguing the security of cryptographic protocols, by relating their security to hard mathematical problems: if an attacker is able to invalidate the security of the scheme, then it must also be able to efficiently solve a problem for which no known efficient algorithm exists. The hardness of the problem with respect to specific parameters is formally framed as a cryptographic assumption. Over an expansive span of time, algorithmic research into these hard problems has the goal of investigating their properties and establishing various relations and hierarchies between them. In turn, this ever-changing complexity-theoretical landscape motivates the design of schemes that rely on either weaker assumptions or new assumptions altogether, offering alternatives in the eventuality of algorithmic breakthroughs that would invalidate previous solutions.
Several years after the first public-key encryption was proposed, modern cryptographic research has expanded well beyond the confines of symmetric and public-key encryption. One of these developments is zero-knowledge proof systems for NP, in which a prover convinces a verifier that a problem instance belongs to a language included in NP, while at the same time avoiding the leakage of any information about the witnesses of the instance (beyond the knowledge that at least one such witness exists).
In this thesis, we are mainly focused on building schemes that are round-efficient, with an interaction that is limited to only one or two messages:
1. we provide new constructions of non-interactive zero-knowledge proofs (NIZKs), where the entire interaction consists of one message from prover to verifier.
2. we build new ZAPs, which are a special case of two-message zero-knowledge proofs: the verifier initiates with the first message (which is a uniformly random string), and the second message must be the reply of the prover. Moreover, the verifier message should be securely reusable for potentially different statements for an arbitrary polynomial number of times. Since fully-fledged zero-knowledge is impossible in less than three rounds, only witness indistinguishability is required for ZAPs: honest proofs computed using different witnesses must be indistinguishable.
Over the past two decades, NIZKs and ZAPs emerged as a crucial tool in the design of more complex protocols, owing that to both their round efficiency and their usefulness in arguing about computation. Due to the high expressivity of NP languages, these protocols allow to prove for instance that an output corresponds to a faithful execution of some polynomial-time program. This property has been leveraged to build complex cryptographic primitives, such as ring signatures, group signatures or delegatable anonymous credentials.
We describe novel constructions whose security depends on assumptions for which no previous result existed, following the general cryptographic approach of being able to resort to alternatives should some of the previous assumptions be invalidated by algorithmic breakthroughs. One of our constructions relies on a standard cryptographic assumption that was not previously known to imply statistical ZAPs, while the other results are based on well-studied, but less standard assumptions. Relying on all these previously untackled assumptions requires devising new techniques along the way, therefore enlarging our knowledge about what properties are required from our assumptions in order to leverage them into constructions of ZAPs or NIZKs. Moreover, our results also lead to new relations between the cryptographic assumptions that we consider.
Our first result concerns the relationship of zero-knowledge with indistinguishability obfuscation (IO). Informally, IO is a powerful assumption which allows to obfuscate any program in such a way that its functionality is hidden, but the program can still be executed. NIZKs and IO both offer different security guarantees for computation, and our work establishes a connection between these distinct notions. Moreover, our result also helps link IO with a family of algebraic assumptions.
In more detail, we construct a NIZK with a dual-mode property, based on the subexponential security of indistinguishability obfuscation IO, and one-way functions, along with the polynomial security of an algebraic object with a lossy property (such as lossy encryption). The dual-mode property allows the common reference string to exist in two computationally-indistinguishable modes, requiring that one ensures statistical soundness and the other statistical zero-knowledge. Our construction has further implications, and in conjunction with previously known results, leads to new relations between IO and algebraic assumptions such as DDH, bilinear SDDH or multilinear k-MDDH. Our results are encompassed in a work published at Asiacrypt 2019.
In our second result, we build a NIZK in cyclic groups without requiring the use of pairings. Pairings are a specific type of bilinear map, and have been successfully used to build NIZKs. This comes however at the cost of assuming more algebraic structure, and NIZKs in pairing-free cyclic groups have remained an important open problem until recently.
More explicitly, we build a NIZK based on polynomially-hard Computational Diffie-Hellman (CDH), along with the 2^{-c\lambda}-OWKDM assumption, for constant c=3/4 (the constant is improved to 1/2 in a subsequent result). Defined over cyclic groups of size 2^\lambda, the 2^{-c\lambda}-OWKDM assumption is that efficient adversaries against the key-dependent message one-wayness of ElGamal are limited to an advantage of poly(\lambda)/2^{c\lambda}, where f is any efficient function f. The key-dependent message one-wayness of ElGamal means that given an ElGamal encryption of f(k), where k is the ElGamal key and f is an efficient function, the adversary cannot recover f(k). This result corresponds to our work published at Eurocrypt 2020.
Finally, we design statistical two-message public-coin witness-indistinguishable proof systems (statistical ZAPs) for NP. Until a recent breakthrough result, statistical ZAPs in cyclic groups have remained elusive, even in the presence of pairings. Our two constructions are based on:
1. An asymmetric pairing group (G_1,\G_2), for which the explicit hardness of DDH holds in G_1 and the kernel Diffie-Hellman problem is hard in G_2. Explicit hardness states that the advantage of any PPT adversary is upper-bounded by an explicit bound \mu, which in our case is the inverse of an arbitrarily small superpolynomial function. The Kernel Diffie-Hellman problem is implied by the DDH assumption in the same group.
2. A pairing-free group G, in which the \mu explicit hardness of the DDH assumption holds relative to the inverse of an arbitrarily small superpolynomial function, along with the 2^{-\lambda/2}-OWKDM security of ElGamal with respect to efficient functions.
Both ZAP constructions are encompassed in a paper published at TCC 2021. Show more

Permanent link

https://doi.org/10.3929/ethz-b-000635023Publication status

publishedExternal links

Search print copy at ETH Library
Publisher

ETH ZurichSubject

COMPUTER SCIENCE; CryptographyOrganisational unit

09693 - Hofheinz, Dennis / Hofheinz, Dennis
More

Show all metadata
ETH Bibliography

yes
Altmetrics