## CryptoDB

### Tal Malkin

#### Affiliation: Columbia University

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Non-Malleable Codes Against Bounded Polynomial Time Tampering
📺
Abstract

We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) $$\mathbf {E}$$E is hard for $$\mathbf {NP}$$NP circuits of some exponential $$2^{\beta n}$$2βn ($$\beta >0$$β>0) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) $$\mathbf {P}$$P-certificates with sub-exponential soundness exist.While it is impossible to construct NMC secure against arbitrary polynomial-time tampering (Dziembowski, Pietrzak, Wichs, ICS ’10), the existence of NMC secure against $$O(n^c)$$O(nc)-time tampering functions (for any fixedc), was shown (Cheraghchi and Guruswami, ITCS ’14) via a probabilistic construction. An explicit construction was given (Faust, Mukherjee, Venturi, Wichs, Eurocrypt ’14) assuming an untamperable CRS with length longer than the runtime of the tampering function. In this work, we show that under computational assumptions, we can bypass these limitations. Specifically, under the assumptions listed above, we obtain non-malleable codes in the plain model against $$O(n^c)$$O(nc)-time tampering functions (for any fixed c), with codeword length independent of the tampering time bound.Our new construction of NMC draws a connection with non-interactive non-malleable commitments. In fact, we show that in the NMC setting, it suffices to have a much weaker notion called quasi non-malleable commitments—these are non-interactive, non-malleable commitments in the plain model, in which the adversary runs in $$O(n^c)$$O(nc)-time, whereas the honest parties may run in longer (polynomial) time. We then construct a 4-tag quasi non-malleable commitment from any sub-exponential OWF and the assumption that $$\mathbf {E}$$E is hard for some exponential size $$\mathbf {NP}$$NP-circuits, and use tag amplification techniques to support an exponential number of tags.

2019

TCC

Is Information-Theoretic Topology-Hiding Computation Possible?
Abstract

Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. Existing THC protocols consider an adversary that may corrupt an arbitrary number of parties, and rely on cryptographic assumptions such as DDH.In this paper we address the question of whether information-theoretic THC can be achieved by taking advantage of an honest majority. In contrast to the standard MPC setting, this problem has remained open in the topology-hiding realm, even for simple “privacy-free” functions like broadcast, and even when considering only semi-honest corruptions.We uncover a rich landscape of both positive and negative answers to the above question, showing that what types of graphs are used and how they are selected is an important factor in determining the feasibility of hiding topology information-theoretically. In particular, our results include the following.
We show that topology-hiding broadcast (THB) on a line with four nodes, secure against a single semi-honest corruption, implies key agreement. This result extends to broader classes of graphs, e.g., THB on a cycle with two semi-honest corruptions.On the other hand, we provide the first feasibility result for information-theoretic THC: for the class of cycle graphs, with a single semi-honest corruption.
Given the strong impossibilities, we put forth a weaker definition of distributional-THC, where the graph is selected from some distribution (as opposed to worst-case).
We present a formal separation between the definitions, by showing a distribution for which information theoretic distributional-THC is possible, but even topology-hiding broadcast is not possible information-theoretically with the standard definition.We demonstrate the power of our new definition via a new connection to adaptively secure low-locality MPC, where distributional-THC enables parties to “reuse” a secret low-degree communication graph even in the face of adaptive corruptions.

2019

ASIACRYPT

Public-Key Function-Private Hidden Vector Encryption (and More)
Abstract

We construct public-key function-private predicate encryption for the “small superset functionality,” recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).d-CNFs and read-once conjunctions of d-disjunctions for constant-size d.
Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key
$$\mathsf {sk} _f$$
reveals nothing about f as long as f is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

2018

EUROCRYPT

2018

CRYPTO

A Simple Obfuscation Scheme for Pattern-Matching with Wildcards
📺
Abstract

We give a simple and efficient method for obfuscating pattern matching with wildcards. In other words, we construct a way to check an input against a secret pattern, which is described in terms of prescribed values interspersed with unconstrained “wildcard” slots. As long as the support of the pattern is sufficiently sparse and the pattern itself is chosen from an appropriate distribution, we prove that a polynomial-time adversary cannot find a matching input, except with negligible probability. We rely upon the generic group heuristic (in a regular group, with no multilinearity). Previous work [9, 10, 32] provided less efficient constructions based on multilinear maps or LWE.

2018

CRYPTO

Hardness of Non-interactive Differential Privacy from One-Way Functions
📺
Abstract

A central challenge in differential privacy is to design computationally efficient non-interactive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset $$D \in X^n$$D∈Xn consisting of some small number of elements n from some large data universe X, and efficiently outputs a summary that allows a user to efficiently obtain an answer to any query in some large family Q.Ignoring computational constraints, this problem can be solved even when X and Q are exponentially large and n is just a small polynomial; however, all algorithms with remotely similar guarantees run in exponential time. There have been several results showing that, under the strong assumption of indistinguishability obfuscation, no efficient differentially private algorithm exists when X and Q can be exponentially large. However, there are no strong separations between information-theoretic and computationally efficient differentially private algorithms under any standard complexity assumption.In this work we show that, if one-way functions exist, there is no general purpose differentially private algorithm that works when X and Q are exponentially large, and n is an arbitrary polynomial. In fact, we show that this result holds even if X is just subexponentially large (assuming only polynomially-hard one-way functions). This result solves an open problem posed by Vadhan in his recent survey [52].

2013

ASIACRYPT

2013

EUROCRYPT

2008

TCC

2007

EPRINT

ProSiBIR: Proactive Signer-Base Intrusion Resilient Signatures
Abstract

The notion of Signer-Base Intrusion-Resilient (SiBIR) signatures was introduced in [IR02] as a scheme that can withstand an arbitrary number of key-exposures, as long as both of its modules are not compromised simultaneously. This was achieved by dividing time into predefined time periods, each corresponding to a different time-evolving secret key, while maintaining a constant public key. The two modules of this scheme consist of a signer that can generate signatures on its own, and a base that is used to update the signer's key as it evolves through time. The purpose of this paper is to provide a model for multi-signer, multi-base intrusion-resilient signatures. This proactive SiBIR scheme essentially breaks the preexisting notions of signer and base, to an arbitrary number of signer and base modules. This tends to implementations where multiple parties need to agree for a document to be signed. An attacker needs to break into all the signers at the same time in order to forge a signature for that period. Moreover, he needs to break into all the bases as well, at that same time period, in order to "break" the scheme and generate future signatures. Thereby, by assuming a large number of bases, the risk of our scheme being compromised becomes arbitrarily small. We provide an implementation that's provably secure in the random oracle model, based on the strong RSA assumption. We also yield a modest improvement in the upperbound of our scheme's insecurity function, as opposed to the one presented in [IR02].

2007

EPRINT

A Block Cipher based PRNG Secure Against Side-Channel Key Recovery
Abstract

We study the security of a block cipher-based pseudorandom number generator (PRNG), both in the black box world and in the physical world, separately. We first show that the construction is a secure PRNG in the black box world, relying on standard computational assumptions. Then, we demonstrate its security against a Bayesian side-channel key recovery adversary. As a main result, we show that our construction guarantees that the success rate of the adversary does not increase with the number of physical bservations, but in a limited and controlled way. Besides, we observe that, under common assumptions on side-channel attack strategies, increasing the security parameter (typically the block cipher key size) by a polynomial factor involves an increase of a side-channel attack complexity by an exponential factor, as usually expected for secure cryptographic primitives. Therefore, we believe this work provides a first interesting example of the way the algorithmic design of a cryptographic scheme influences its side-channel resistance.

2006

EPRINT

Towards a Separation of Semantic and CCA Security for Public Key Encryption
Abstract

We address the question of whether or not semantically secure public-key encryption primitives imply the existence of chosen ciphertext attack (CCA) secure primitives. We show a black-box separation, using the methodology introduced by Impagliazzo and Rudich, for a large non-trivial class of constructions. In particular, we show that if the proposed CCA construction's decryption algorithm does not query the semantically secure primitive's encryption algorithm, then the proposed construction cannot be CCA secure

2006

EPRINT

A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks (extended version)
Abstract

The fair evaluation and comparison of side-channel attacks and countermeasures has been a long standing open question, limiting further developments in the field. Motivated by this challenge, this work makes a step in this direction and proposes a framework for the analysis of cryptographic implementations that includes a theoretical model and an application methodology. The model is based on commonly accepted hypotheses about side-channels that computations give rise to. It allows quantifying the effect of practically relevant leakage functions with a combination of information theoretic and security metrics, measuring the quality of an implementation and the strength of an adversary, respectively. From a theoretical point of view, we demonstrate formal connections between these metrics and discuss their intuitive meaning. From a practical point of view, the model implies a unified methodology for the analysis of side-channel key recovery attacks. The proposed solution allows getting rid of most of the subjective parameters that were limiting previous specialized and often ad hoc approaches in the evaluation of physically observable devices. It typically determines the extent to which basic (but practically essential) questions such as "How to compare two implementations?" or "How to compare two side-channel adversaries?" can be answered in a sound fashion.

2004

JOFC

2004

EPRINT

The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures
Abstract

For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of signers within organizations and among entities). On the other hand, various notions of the key-evolving signature paradigms (forward-secure, key-insulated, and intrusion-resilient signatures) have been suggested in the last few years for protecting the security of signature schemes, localizing the damage of secret key exposure.
In this work we relate the various notions via direct and concrete security reductions that are tight. We start by developing the first formal model for fully hierarchical proxy signatures, which, as we point out, also addresses vulnerabilities of previous schemes when self-delegation is used. Next, we prove that proxy signatures are, in fact, equivalent to key-insulated signatures. We then use this fact and other results to establish a tight hierarchy among the key-evolving notions, showing that intrusion-resilient signatures and key-insulated signatures are equivalent, and imply forward-secure signatures. We also introduce other relations among extended notions.
Besides the importance of understanding the relationships among the various notions that were originally designed with different goals or with different system configuration in mind, our findings imply new designs of schemes. For example, many proxy signatures have been presented without formal model and proofs, whereas using our results we can employ the work on key-insulated schemes to suggest new provably secure designs of proxy signatures schemes.

2001

EPRINT

On adaptive vs. non-adaptive security of multiparty protocols
Abstract

Security analysis of multiparty cryptographic protocols distinguishes
between two types of adversarial settings: In the non-adaptive
setting, the set of corrupted parties is chosen in advance, before the
interaction begins. In the adaptive setting, the adversary chooses
who to corrupt during the course of the computation. We study the
relations between adaptive security (i.e., security in the adaptive
setting) and non-adaptive security, according to two definitions and
in several models of computation. While affirming some prevailing
beliefs, we also obtain some unexpected results. Some highlights of
our results are:
o According to the definition of Dodis-Micali-Rogaway (which is set in
the information-theoretic model), adaptive and non-adaptive security
are equivalent. This holds for both honest-but-curious and Byzantine
adversaries, and for any number of parties.
o According to the definition of Canetti, for honest-but-curious
adversaries, adaptive security is equivalent to non-adaptive
security when the number of parties is logarithmic, and is strictly
stronger than non-adaptive security when the number of parties is
super-logarithmic. For Byzantine adversaries, adaptive security is
strictly stronger than non-adaptive security, for any number of
parties.

2001

EPRINT

Secure Multiparty Computation of Approximations
Abstract

Approximation algorithms can sometimes be used to obtain efficient
solutions where no efficient exact computation is known. In
particular, approximations are often useful in a distributed setting
where the inputs are held by different parties and are extremely
large. Furthermore, for some applications, the parties want to
cooperate to compute a function of their inputs without revealing more
information than they have to.
Suppose the function $\fhat$ is an approximation to the function $f$.
Secure multiparty computation of $f$ allows the parties to compute $f$
without revealing more than they have to, but it requires some
additional overhead in computation and communication. Hence, if
computation of $f$ is inefficient or just efficient enough to be
practical, then secure computation of $f$ may be impractically
expensive. Furthermore, a secure computation of $\fhat$ is not
necessarily as private as a secure computation of $f$, because the
output of $\fhat$ may reveal more information than the output of $f$.
In this paper, we present definitions and protocols of secure
multiparty approximate computation that show how to realize most of
the cost savings available by using $\fhat$ instead of $f$ without
losing the privacy of a secure computation of $f$.
We make three contributions. First, we give formal definitions of
secure multiparty approximate computations. Second, we present an
efficient, sublinear-communication, private approximate computation
for the Hamming distance; we also give an efficient,
polylogarithmic-communication solution for the $L^{2}$ distance
in a relaxed model. Finally, we give an efficient private
approximation of the permanent and other related \#P-hard problems.

2001

EPRINT

Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures
Abstract

Forward-secure digital signatures, initially proposed by Anderson in
CCS 97 and formalized by Bellare and Miner in Crypto 99, are signature
schemes which enjoy the additional guarantee that a compromise of the
secret key at some point in time does not help forge signatures
allegedly signed in an earlier time period. Consequently, if the
secret key is lost, then the key can be safely revoked without
invalidating previously-issued signatures. Since the introduction of
the concept, several forward-secure signature schemes have been
proposed, with varying performance both in terms of space and time.
Which scheme is most useful in practice typically depends on the
requirements of the specific application.
In this paper we propose and study some general composition operations
that can be used to combine existing signature schemes (whether
forward-secure or not) into new forward-secure signature schemes. Our
schemes offer interesting trade-offs between the various efficiency
parameters, achieving a greater flexibility in accommodating the
requirements of different applications. As an extension of our
techniques, we also construct the first efficient forward-secure
signature scheme where the total number of time periods for which the
public key is used does not have to be fixed in advance. The scheme
can be used for practically unbounded time, and the performance
depends (minimally) only on the time elapsed so far.
Our scheme achieves excellent performance overall, is very competitive
with previous schemes with respect to all parameters, and outperforms
each of the previous schemes in at least one parameter. Moreover, the
scheme can be based on any underlying digital signature scheme, and
does not rely on specific assumptions. Its forward security is proven
in the standard model, without using a random oracle.

2000

CRYPTO

1998

EPRINT

A Random Server Model for Private Information Retrieval (or How to Achieve Information Theoretic PIR Avoiding Data Replication)
Abstract

Private information retrieval (PIR) schemes enable users to obtain
information from databases while keeping their queries secret from the
database managers. We propose a new model for PIR, utilizing
auxiliary random servers to provide privacy services for database
access. In this model, prior to any on-line communication where users
request queries, the database engages in an initial preprocessing
setup stage with the random servers. Using this model we achieve the
first PIR information theoretic solution in which the database does
not need to give away its data to be replicated, and with minimal
on-line computation cost for the database. This solves privacy and
efficiency problems inherent to all previous solutions.
In particular, all previous information theoretic PIR schemes required
multiple replications of the database into separate entities which are
not allowed to communicate with each other; and in all previous
schemes (including ones which do not achieve information theoretic
security), the amount of computation performed by the database on-line
for every query is at least linear in the size of the database.
In contrast, in our solutions the database does not give away its
contents to any other entity; and after the initial setup stage, which
costs at most O(n log n) in computation, the database needs to
perform only O(1) amount of computation to answer questions of users
on-line. All the extra on-line computation is done by the auxiliary
random servers.

#### Program Committees

- Eurocrypt 2020
- TCC 2018
- Eurocrypt 2017
- TCC 2016
- Crypto 2012
- TCC 2012
- Crypto 2008
- Crypto 2006
- TCC 2006
- Crypto 2005
- TCC 2005
- Crypto 2004
- PKC 2003

#### Coauthors

- Philip Atzemoglou (1)
- Marshall Ball (5)
- James Bartusek (1)
- Amos Beimel (6)
- Allison Bishop (1)
- Elette Boyle (2)
- Ran Canetti (4)
- Brent Carmer (1)
- Melissa Chase (1)
- Seung Geol Choi (7)
- Ran Cohen (1)
- Giovanni Di Crescenzo (1)
- Dana Dachman-Soled (11)
- Ivan Damgård (3)
- Yevgeniy Dodis (1)
- Stefan Dziembowski (3)
- Ariel Elbaz (2)
- Joan Feigenbaum (1)
- Rosario Gennaro (2)
- Yael Gertner (3)
- Shafi Goldwasser (1)
- S. Dov Gordon (1)
- Siyao Guo (1)
- Alexander Healy (1)
- Yuval Ishai (6)
- Abhishek Jain (1)
- Zhengzhong Jin (1)
- Ari Juels (1)
- Aggelos Kiayias (2)
- Lucas Kowalczyk (3)
- Hugo Krawczyk (1)
- Mukul Kulkarni (3)
- Tancrède Lepoint (1)
- Huijia Lin (1)
- Yehuda Lindell (1)
- Anna Lysyanskaya (2)
- Fermi Ma (1)
- Mohammad Mahmoody (2)
- Alex J. Malozemoff (1)
- Silvio Micali (2)
- Daniele Micciancio (2)
- Sara K. Miner (2)
- Tal Moran (2)
- Ryan Moriarty (1)
- Steven Myers (2)
- Kobbi Nissim (4)
- Satoshi Obana (2)
- Igor Carboni Oliveira (1)
- Rafail Ostrovsky (1)
- Valerio Pastro (1)
- Olivier Pereira (1)
- Christophe Petit (1)
- Tal Rabin (1)
- Mariana Raykova (3)
- Leonid Reyzin (1)
- Alon Rosen (1)
- Mike Rosulek (1)
- Kevin Shi (1)
- François-Xavier Standaert (3)
- Martin Strauss (1)
- Isamu Teranishi (3)
- Jonathan Ullman (2)
- Yevgeniy Vahlis (1)
- Muthuramakrishnan Venkitasubramaniam (1)
- Hoeteck Wee (5)
- Enav Weinreb (2)
- Daniel Wichs (1)
- Rebecca N. Wright (1)
- Nikolai Yakovenko (1)
- Moti Yung (11)
- Mark Zhandry (1)