## CryptoDB

### Nils Fleischhacker

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Robust Property-Preserving Hash Functions for Hamming Distance and More
📺
Abstract

Robust property-preserving hash (PPH) functions, recently introduced by Boyle, Lavigne, and Vaikuntanathan [ITCS 2019], compress large inputs $x$ and $y$ into short digests $h(x)$ and $h(y)$ in a manner that allows for computing a predicate $P$ on $x$ and $y$ while only having access to the corresponding hash values. In contrast to locality-sensitive hash functions, a robust PPH function guarantees to correctly evaluate a predicate on $h(x)$ and $h(y)$ even if $x$ and $y$ are chosen adversarially \emph{after} seeing $h$.
Our main result is a robust PPH function for the exact hamming distance predicate
\[
\mathsf{HAM}^t(x, y) =
\begin{cases}
1 &\text{if } d( x, y) \geq t \\
0 & \text{Otherwise}\\
\end{cases}
\]
where $d(x, y)$ is the hamming-distance between $x$ and $y$.
Our PPH function compresses $n$-bit strings into $\mathcal{O}(t \lambda)$-bit digests, where $\lambda$ is the security parameter.
The construction is based on the q-strong bilinear discrete logarithm assumption.
Along the way, we construct a robust PPH function for the set intersection predicate
\[
\mathsf{INT}^t(X, Y) =
\begin{cases}
1 &\text{if } \vert X \cap Y\vert > n - t \\
0 & \text{Otherwise}\\
\end{cases}
\]
which compresses sets $X$ and $Y$ of size $n$ with elements from some arbitrary universe $U$ into $\mathcal{O}(t\lambda)$-bit long digests.
This PPH function may be of independent interest.
We present an almost matching lower bound of $\Omega(t \log t)$ on the digest size of any PPH function for the intersection predicate, which indicates that our compression rate is close to optimal.
Finally, we also show how to extend our PPH function for the intersection predicate to more than two inputs.

2021

PKC

On Publicly-Accountable Zero-Knowledge and Small Shuffle Arguments
📺
Abstract

Constructing interactive zero-knowledge arguments from simple assumptions with small communication complexity and good computational efficiency is an important, but difficult problem.
In this work, we study interactive arguments with noticeable soundness error in their full generality and for the specific purpose of constructing concretely efficient shuffle arguments.
To counterbalance the effects of a larger soundness error, we show how to transform such three-move arguments into publicly-accountable ones which allow the verifier to convince third parties of detected misbehavior by a cheating prover.
This may be particularly interesting for applications where a malicious prover has to balance the profits it can make from cheating successfully and the losses it suffers from being caught.
We construct interactive, public-coin, zero-knowledge arguments with noticeable soundness error for proving that a target vector of commitments is a pseudorandom permutation of a source vector.
Our arguments do not rely on any trusted setup and only require the existence of collision-resistant hash functions.
The communication complexity of our arguments is \emph{independent} of the length of the shuffled vector.
For a soundness error of $2^{-5}=1/32$, the communication cost is $153$ bytes without and $992$ bytes with public accountability, meaning that our arguments are shorter than shuffle arguments realized using Bulletproofs (IEEE S\&P 2018) and even competitive in size with SNARKs, despite only relying on simple assumptions.

2019

TCC

Interactive Non-malleable Codes
Abstract

Non-malleable codes (NMC) introduced by Dziembowski et al. [ICS’10] allow one to encode “passive” data in such a manner that when a codeword is tampered, the original data either remains completely intact or is essentially destroyed.In this work, we initiate the study of interactive non-malleable codes (INMCs) that allow for encoding “active communication” rather than passive data. An INMC allows two parties to engage in an interactive protocol such that an adversary who is able to tamper with the protocol messages either leaves the original transcript intact (i.e., the parties are able to reconstruct the original transcript) or the transcript is completely destroyed and replaced with an unrelated one.We formalize a tampering model for interactive protocols and put forward the notion of INMCs. Since constructing INMCs for general adversaries is impossible (as in the case of non-malleable codes), we construct INMCs for several specific classes of tampering functions. These include bounded state, split state, and fragmented sliding window tampering functions. We also obtain lower bounds for threshold tampering functions via a connection to interactive coding. All of our results are unconditional.

2019

JOFC

Feasibility and Infeasibility of Secure Computation with Malicious PUFs
Abstract

A recent line of work has explored the use of physically unclonable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without additional setup and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions). Initial work assumed that all PUFs, even those created by an attacker, are honestly generated. Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful , as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless . We settle the main open questions regarding secure computation in the malicious-PUF model: We prove that unconditionally secure oblivious transfer is impossible, even in the stand-alone setting, if the adversary can construct (malicious) stateful PUFs. We show that if the attacker is limited to creating (malicious) stateless PUFs, then universally composable two-party computation is possible, unconditionally.

2019

JOFC

On Tight Security Proofs for Schnorr Signatures
Abstract

The Schnorr signature scheme is the most efficient signature scheme based on the discrete logarithm problem and a long line of research investigates the existence of a tight security reduction for this scheme in the random oracle model. Almost all recent works present lower tightness bounds and most recently Seurin EUROCRYPT 2012 showed that under certain assumptions the non -tight security proof for Schnorr signatures in the random oracle by Pointcheval and Stern EUROCRYPT’96 is essentially optimal. All previous works in this direction rule out tight reductions from the (one-more) discrete logarithm problem. In this paper, we introduce a new meta-reduction technique, which shows lower bounds for the large and very natural class of generic reductions. A generic reduction is independent of a particular representation of group elements. Most reductions in state-of-the-art security proofs have this property. It is desirable, because then the reduction applies generically to any concrete instantiation of the group. Our approach shows unconditionally that there is no tight generic reduction from any natural non-interactive computational problem $$\Pi $$ Π defined over algebraic groups to breaking Schnorr signatures, unless solving $$\Pi $$ Π is easy. In an additional application of the new meta-reduction technique, we also unconditionally rule out any (even non-tight) generic reduction from natural non-interactive computational problems defined over algebraic groups to breaking Schnorr signatures in the non-programmable random oracle model.

#### Program Committees

- Asiacrypt 2019

#### Coauthors

- Zvika Brakerski (1)
- Chris Brzuska (1)
- Dana Dachman-Soled (2)
- Nico Döttling (1)
- Marc Fischlin (1)
- Vipul Goyal (2)
- Tibor Jager (2)
- Abhishek Jain (2)
- Jonathan Katz (2)
- Johannes Krupp (2)
- Anna Lysyanskaya (2)
- Giulio Malavolta (1)
- Anat Paskin-Cherniavsky (1)
- Slava Radune (1)
- Jonas Schneider (1)
- Dominique Schröder (6)
- Mark Simkin (3)