International Association
for Cryptologic Research

The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $\Sigma$-protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $(2\mu + 1)$-move protocol is, in general, approximately $Q^\mu$, where $Q$ is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $\mu$-fold sequential repetition of $\Sigma$-protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for $(k_1, \ldots, k_\mu)$-special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in $Q$, instead of $Q^\mu$. On the negative side, we show that for $t$-fold \emph{parallel repetitions} of typical $(k_1, \ldots, k_\mu)$-special-sound protocols with $t \geq \mu$ (and assuming for simplicity that $t$ and $Q$ are integer multiples of $\mu$), there is an attack that results in a security loss of approximately~$\frac12 Q^\mu /\mu^{\mu+t}$.

We introduce a new approach for constructing range proofs. Our approach is modular, and leads to highly competitive range proofs under standard assumption, using less communication and (much) less computation than the state of the art methods, and without relying on a trusted setup. Our range proofs can be used as a drop-in replacement in a variety of protocols such as distributed ledgers, anonymous transaction systems, and many more, leading to significant reductions in communication and computation for these applications. At the heart of our result is a new method to transform any commitment over a finite field into a commitment scheme which allows to commit to and efficiently prove relations about bounded integers. Combining these new commitments with a classical approach for range proofs based on square decomposition, we obtain several new instantiations of a paradigm which was previously limited to RSA-based range proofs (with high communication and computation, and trusted setup). More specifically, we get: - Under the discrete logarithm assumption, we obtain the most compact and efficient range proof among all existing candidates (with or without trusted setup). Our proofs are 12% to 20% shorter than the state of the art Bulletproof (Bootle et al., CRYPTO'18) for standard choices of range size and security parameter, and are more efficient (both for the prover and the verifier) by more than an order of magnitude. - Under the LWE assumption, we obtain range proofs that improve over the state of the art in a batch setting when at least a few dozen range proofs are required. The amortized communication of our range proofs improves by up to two orders of magnitudes over the state of the art when the number of required range proofs grows. - Eventually, under standard class group assumptions, we obtain the first concretely efficient standard integer commitment scheme (without bounds on the size of the committed integer) which does not assume trusted setup.

A common definition of black-box zero-knowledge considers strict polynomial time (PPT) adversaries but expected polynomial time (EPT) simulation. This is necessary for constant round black-box zero-knowledge in the plain model, and the asymmetry between simulator and adversary an accepted consequence. Consideration of EPT adversaries naturally leads to designated adversaries, i.e. adversaries which are only required to be efficient in the protocol they are designed to attack. They were first examined in Feige’s thesis [Fei90], where obstructions to proving security are shown. Prior work on (designated) EPT adversaries by Katz and Lindell (TCC’05) requires superpolynomial hardness assumptions, whereas the work of Goldreich (TCC’07) postulates “nice” behaviour under rewinding. In this work, we start from scratch and revisit the definition of efficient algorithms. We argue that the standard runtime classes, PPT and EPT, behave “unnatural” from a cryptographic perspective. Namely, algorithms can have indistinguishable runtime distributions, yet one is considered efficient while the other is not. Hence, classical runtime classes are not “closed under indistinguishability”, which causes problems. Relaxations of PPT which are “closed” are (well-)known and used. We propose computationally expected polynomial time (CEPT), the class of runtimes which are (computationally) indistinguishable from EPT, which is “closed”. We analyze CEPT in the setting of uniform complexity (following Goldreich (JC’93)) with designated adversaries, and provide easy-to-check criteria for zero-knowledge protocols with blackbox simulation in the plain model, which show that many (all known?) such protocols handle designated CEPT adversaries in CEPT.

An updatable encryption scheme allows a data host to update ciphertexts of a client from an old to a new key, given so-called update tokens from the client. Rotation of the encryption key is a common requirement in practice in order to mitigate the impact of key compromises over time. There are two incarnations of updatable encryption: One is ciphertext-dependent, i.e. the data owner has to (partially) download all of his data and derive a dedicated token per ciphertext. Everspaugh et al. (CRYPTO’17) proposed CCA and CTXT secure schemes in this setting. The other, more convenient variant is ciphertext-independent, i.e., it allows a single token to update all ciphertexts. However, so far, the broader functionality of tokens in this setting comes at the price of considerably weaker security: the existing schemes by Boneh et al. (CRYPTO’13) and Lehmann and Tackmann (EUROCRYPT’18) only achieve CPA security and provide no integrity protection. Arguably, when targeting the scenario of outsourcing data to an untrusted host, plaintext integrity should be a minimal security requirement. Otherwise, the data host may alter or inject ciphertexts arbitrarily. Indeed, the schemes from BLMR13 and LT18 suffer from this weakness, and even EPRS17 only provides integrity against adversaries which cannot arbitrarily inject ciphertexts. In this work, we provide the first ciphertext-independent updatable encryption schemes with security beyond CPA, in particular providing strong integrity protection. Our constructions and security proofs of updatable encryption schemes are surprisingly modular. We give a generic transformation that allows key-rotation and confidentiality/integrity of the scheme to be treated almost separately, i.e., security of the updatable scheme is derived from simple properties of its static building blocks. An interesting side effect of our generic approach is that it immediately implies the unlinkability of ciphertext updates that was introduced as an essential additional property of updatable encryption by EPRS17 and LT18.