## CryptoDB

### Thomas Holenstein

#### Publications

**Year**

**Venue**

**Title**

2019

JOFC

The Communication Complexity of Private Simultaneous Messages, Revisited
Abstract

Private simultaneous message (PSM) protocols were introduced by Feige, Kilian, and Naor (STOC ’94) as a minimal non-interactive model for information theoretic three-party secure computation. While it is known that every function $$f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$$ f : { 0 , 1 } k × { 0 , 1 } k → { 0 , 1 } admits a PSM protocol with exponential communication of $$2^{k/2}$$ 2 k / 2 (Beimel et al., TCC ’14), the best known (non-explicit) lower-bound is $$3k-O(1)$$ 3 k - O ( 1 ) bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the $$3k-O(1)$$ 3 k - O ( 1 ) lower-bound, and proved that a random function is likely to satisfy the requirements. We revisit the FKN lower-bound and prove the following results: (Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of $$2k+O(1)$$ 2 k + O ( 1 ) bits, revealing a gap in the FKN proof. (PSM lower-bounds) We show that by imposing additional requirements, the FKN argument can be fixed leading to a $$3k-O(\log k)$$ 3 k - O ( log k ) lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran, and Prabhakaran (Crypto ’14, IEEE Information Theory ’16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error. (CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear $$\varOmega (k)$$ Ω ( k ) -bit CDS lower-bounds. As a corollary, we settle the complexity of the inner-product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto ’15).

2010

EPRINT

Universal One-Way Hash Functions via Inaccessible Entropy
Abstract

This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction exploits a strong connection to the recently introduced notion of *inaccessible entropy* (Haitner et al. STOC 2009). With this perspective, we observe that a small tweak of any one-way function f is already a weak form of a UOWHF: Consider F(x, i) that outputs the i-bit long prefix of f(x). If F were a UOWHF then given a random x and i it would be hard to come up with x' \neq x such that F(x, i) = F(x', i). While this may not be the case, we show (rather easily) that it is hard to sample x' with almost full entropy among all the possible such values of x'. The rest of our
construction simply amplifies and exploits this basic property.
With this and other recent works we have that the constructions of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of one-way functions are to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the well-established notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy.

2008

EPRINT

On the (Im)Possibility of Key Dependent Encryption
Abstract

We study the possibility of constructing encryption schemes secure
under messages that are chosen depending on the key k of the
encryption scheme itself. We give the following separation results:
1. Let H be the family of poly(n)-wise independent hash-functions. There exists no fully-black-box reduction from an encryption scheme secure against key-dependent inputs to one-way permutations (and also to families of trapdoor permutations) if the adversary can obtain encryptions of h(k) for h \in H.
2. Let G be the family of polynomial sized circuits. There exists no reduction from an encryption scheme secure against key-dependent inputs to, seemingly, any cryptographic assumption, if the adversary can obtain an encryption of g(k) for g \in G, as long as the reduction's proof of security treats both the adversary and the function g as black box.

2002

EPRINT

Extended Validity and Consistency in Byzantine Agreement
Abstract

A broadcast protocol allows a sender to distribute a value among a set of
players such that it is guaranteed that all players receive the same
value (consistency), and if the sender is honest, then all players
receive the sender's value (validity). Classical broadcast protocols for
$n$ players provide security with respect to a fixed threshold $t<n/3$,
where both consistency and validity are guaranteed as long as at most $t$
players are corrupted, and no security at all is guaranteed as soon as
$t+1$ players are corrupted. Depending on the environment, validity or
consistency may be the more important property.
We generalize the notion of broadcast by introducing an additional
threshold $t^+\ge t$. In a {\em broadcast protocol with extended
validity}, both consistency and validity are achieved when no more than
$t$ players are corrupted, and validity is achieved even when up to $t^+$
players are corrupted. Similarly, we define {\em broadcast with extended
consistency}. We prove that broadcast with extended validity as well as
broadcast with extended consistency is achievable if and only if
$t+2t^+<n$ (or $t=0$).
For example, six players can achieve broadcast when at most one player is
corrupted (this result was known to be optimal), but they can even
achieve consistency (or validity) when two players are corrupted.
Furthermore, our protocols achieve {\em detection} in case of failure,
i.e., if at most $t$ players are corrupted then broadcast is achieved,
and if at most $t^+$ players are corrupted then broadcast is achieved or
every player learns that the protocol failed. This protocol can be
employed in the precomputation of a secure multi-party computation
protocol, resulting in {\em detectable multi-party computation}, where up
to $t$ corruptions can be tolerated and up to $t^+$ corruptions can
either be tolerated or detected in the precomputation, for any $t,t^+$
with $t+2t^+<n$.

#### Program Committees

- TCC 2015
- Crypto 2014
- TCC 2013
- Crypto 2010
- TCC 2009

#### Coauthors

- Benny Applebaum (2)
- Kfir Barhum (1)
- Jean-Sébastien Coron (1)
- Matthias Fitzi (3)
- Iftach Haitner (4)
- Martin Hirt (2)
- Robin Künzler (1)
- Ueli Maurer (1)
- Manoj Mishra (2)
- Jacques Patarin (1)
- Omer Reingold (2)
- Renato Renner (1)
- Grant Schoenebeck (1)
- Yannick Seurin (1)
- Ofer Shayevitz (2)
- Johan Sjödin (1)
- Stefano Tessaro (1)
- Salil P. Vadhan (2)
- Hoeteck Wee (2)
- Jürg Wullschleger (3)