## CryptoDB

### Jonathan Katz

#### Affiliation: University of Maryland

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Covert Security with Public Verifiability: Faster, Leaner, and Simpler
Abstract

The notion of covert security for secure two-party computation serves as a compromise between the traditional semi-honest and malicious security definitions. Roughly, covert security ensures that cheating behavior is detected by the honest party with reasonable probability (say, 1/2). It provides more realistic guarantees than semi-honest security with significantly less overhead than is required by malicious security.The rationale for covert security is that it dissuades cheating by parties that care about their reputation and do not want to risk being caught. But a much stronger disincentive is obtained if the honest party can generate a publicly verifiable certificate when cheating is detected. While the corresponding notion of publicly verifiable covert (PVC) security has been explored, existing PVC protocols are complex and less efficient than the best covert protocols, and have impractically large certificates.We propose a novel PVC protocol that significantly improves on prior work. Our protocol uses only “off-the-shelf” primitives (in particular, it avoids signed oblivious transfer) and, for deterrence factor 1/2, has only 20–40% overhead compared to state-of-the-art semi-honest protocols. Our protocol also has, for the first time, constant-size certificates of cheating (e.g., 354 bytes long at the 128-bit security level).As our protocol offers strong security guarantees with low overhead, we suggest that it is the best choice for many practical applications of secure two-party computation.

2019

JOFC

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens
Abstract

We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware tokens for universally composable secure computation. As our main result, we show an oblivious-transfer (OT) protocol in which two parties each create and transfer a single, stateless token and can then run an unbounded number of OTs. We also show a more efficient protocol, based only on standard symmetric-key primitives (block ciphers and collision-resistant hash functions), that can be used if a bounded number of OTs suffice. Motivated by this result, we investigate the number of stateless tokens needed for universally composable OT. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.

2019

TCC

Synchronous Consensus with Optimal Asynchronous Fallback Guarantees
Abstract

Typically, protocols for Byzantine agreement (BA) are designed to run in either a synchronous network (where all messages are guaranteed to be delivered within some known time $$\varDelta $$ from when they are sent) or an asynchronous network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start.Fix some number of parties n, and $$0< t_a< n/3 \le t_s < n/2$$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that is resilient to (1) $$t_s$$ corruptions when run in a synchronous network and (2) $$t_a$$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $$t_a + 2\cdot t_s < n$$.

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.

2018

CRYPTO

Optimizing Authenticated Garbling for Faster Secure Two-Party Computation
📺
Abstract

Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the-art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically:We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6$$\times $$× improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation.We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5$$\times $$× improvement in the communication and a 2$$\times $$× improvement in the computation for that step.

2018

CRYPTO

Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
📺
Abstract

Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a wn-bit block cipher from n-bit public permutations (often called S-boxes), which alternate keyless and “local” substitution steps utilizing such S-boxes, with keyed and “global” permutation steps which are non-cryptographic. Many widely deployed block ciphers are constructed based on the SPNs, but there are essentially no provable-security results about SPNs.In this work, we initiate a comprehensive study of the provable security of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying n-bit permutation is modeled as a public random permutation. When the permutation step is linear (which is the case for most existing designs), we show that 3 SPN rounds are necessary and sufficient for security. On the other hand, even 1-round SPNs can be secure when non-linearity is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-birthday” (up to
$$2^{2n/3}$$
22n/3 adversarial queries) security, and, as the number of non-linear rounds increases, our bounds are meaningful for the number of queries approaching
$$2^n$$
2n. Finally, our non-linear SPNs can be made tweakable by incorporating the tweak into the permutation layer, and provide good multi-user security.As an application, our construction can turn two public n-bit permutations (or fixed-key block ciphers) into a tweakable block cipher working on wn-bit inputs, 6n-bit key and an n-bit tweak (for any
$$w\ge 2$$
w≥2); the tweakable block cipher provides security up to
$$2^{2n/3}$$
22n/3 adversarial queries in the random permutation model, while only requiring w calls to each permutation, and 3w field multiplications for each wn-bit input.

2018

ASIACRYPT

Simple and Efficient Two-Server ORAM
Abstract

We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations.A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter $$\lambda $$, the servers each store 4N encrypted blocks, the client stores $$\lambda +2\log N$$ blocks, and the total communication per logical access is roughly $$10 \log N$$ encrypted blocks.

2018

ASIACRYPT

More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting
Abstract

The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case.In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.

2014

TCC

2013

JOFC

Round-Optimal Password-Based Authenticated Key Exchange
Abstract

We show a general framework for constructing password-based authenticated key-exchange protocols with optimal round complexity—one message per party, sent simultaneously—in the standard model, assuming the existence of a common reference string. When our framework is instantiated using bilinear-map-based cryptosystems, the resulting protocol is also (reasonably) efficient. Somewhat surprisingly, our framework can be adapted to give protocols in the standard model that are universally composable while still using only one (simultaneous) round.

2010

EPRINT

One-Round Password-Based Authenticated Key Exchange
Abstract

We show a general framework for constructing password-based authenticated key exchange protocols with optimal round complexity --- one message per party, sent simultaneously --- in the standard model, assuming the existence of a common reference string. When our framework is instantiated using bilinear-map cryptosystems, the resulting protocol is also (reasonably) efficient. Somewhat surprisingly, our framework can be adapted to give protocols (still in the standard model) that are universally composable, while still using only one (simultaneous) round.

2010

EPRINT

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation
Abstract

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest.
It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.

2010

EPRINT

A New Framework for Password-Based Authenticated Key Exchange
Abstract

Protocols for password-based authenticated key exchange (PAKE) allow
two users who share only a short, low-entropy password to agree on a cryptographically strong session key. The challenge in designing such protocols is that they must be immune to off-line dictionary attacks in which an eavesdropping adversary exhaustively enumerates the dictionary of likely passwords in an attempt to match a password to the set of observed transcripts.
To date, few general frameworks for constructing PAKE protocols in the standard model are known. Here, we abstract and generalize a protocol by Jiang and Gong to give a new methodology for realizing PAKE without random oracles, in the common reference string model. In addition to giving a new approach to the problem, the resulting construction offers several advantages over prior work. We also describe an extension of our protocol that is secure within the universal composability~(UC) framework and, when instantiated using El Gamal encryption, is more efficient than a previous protocol of Canetti et al.

2010

EPRINT

Cryptography Resilient to Continual Memory Leakage
Abstract

In recent years, there has been a major effort to design cryptographic schemes
that remain secure even if part of the secret key is leaked. This is due to a
recent proliferation of side channel attacks which, through various physical
means, can recover part of the secret key. We explore the possibility of
achieving security even with continual leakage, i.e., even if some information
is leaked each time the key is used.
We show how to securely update a secret key while information is leaked: We
construct schemes that remain secure even if an attacker, {\em at each time
period}, can probe the entire memory (containing a secret key) and ``leak'' up
to a $(1-o(1))$ fraction of the secret key. The attacker may also probe the
memory during the updates, and leak $O(\log k)$ bits, where $k$ is the security
parameter (relying on subexponential hardness allows $k^\epsilon$ bits of
leakage during each update process). All of the above is achieved without
restricting the model as is done in previous works (e.g. by assuming that
``only computation leaks information'' [Micali-Reyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which
allows for a leakage rate of $(1/2-o(1))$) or the symmetric external
Diffie-Hellman assumption (which allows for a leakage rate of $(1-o(1))$), we
achieve the above for public key encryption, identity-based encryption, and
signature schemes. Prior to this work, it was not known how to construct
public-key encryption schemes even in the more restricted model of [MR].
The main contributions of this work are (1) showing how to securely update a
secret key while information is leaked (in the more general model) and (2)
giving a public key encryption (and IBE) schemes that are resilient to
continual leakage.

2010

EPRINT

Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
Abstract

Consider two parties holding samples from correlated distributions W and W', respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {R_j} using multiple pairs {W_j, W'_j}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.
Our results improve upon previous work in several respects:
-- The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2n/3, where n is the bit-length of W. Our solution applies whenever min-entropy of W exceeds the minimal possible} threshold n/2, and yields a longer key.
-- Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model.
-- Previous solutions for the keyed case were stateful. We give the first stateless solution.

2009

ASIACRYPT

2009

EPRINT

Attacking Cryptographic Schemes Based on "Perturbation Polynomials"
Abstract

We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes.
Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).

2008

EUROCRYPT

2008

EPRINT

Efficient Rational Secret Sharing in the Standard Communication Model
Abstract

We propose a new methodology for rational secret sharing leading to various instantiations that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks.
Of additional interest, we propose new equilibrium notions for this setting (namely, computational versions of strict Nash equilibrium and stability with respect to trembles), show relations between them, and prove that our protocols satisfy them.

2008

EPRINT

Partial Fairness in Secure Two-Party Computation
Abstract

Complete fairness is impossible to achieve, in general, in secure two-party computation. In light of this, various techniques for obtaining \emph{partial} fairness in this setting have been suggested. We explore the possibility of achieving partial fairness with respect to a strong, simulation-based definition of security within the standard real/ideal world paradigm. We show feasibility with respect to this definition for randomized functionalities where each player may possibly receive a different output, as long as at least one of the domains or ranges of the functionality are polynomial in size. When one of the domains is polynomial size, our protocol is also secure-with-abort. In contrast to much of the earlier work on partial fairness, we rely on standard assumptions only (namely, enhanced trapdoor permutations).
We also provide evidence that our results are, in general, optimal. Specifically, we show a boolean function defined on a domain of super-polynomial size for which it is impossible to achieve both partial fairness and security with abort, and provide evidence that partial fairness is impossible altogether for functions whose domains and ranges all have super-polynomial size.

2008

EPRINT

Complete Fairness in Secure Two-Party Computation
Abstract

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved, in general, without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late '80s.
In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an ``embedded XOR''; this class of functions includes boolean AND/OR as
well as Yao's ``millionaires' problem''. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

2008

EPRINT

Compact Signatures for Network Coding
Abstract

Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. Since it does not require centralized control, network coding has been suggested for routing packets in ad-hoc networks, for content distribution in P2P file systems, and for improving the efficiency of large-scale data dissemination over the Internet.
In contrast to traditional routing schemes, however, network coding requires intermediate nodes to process and modify data packets en route. For this reason, standard signature schemes are inapplicable and it is therefore a challenge to provide resilience to tampering by malicious nodes in the network. Here, we propose a novel homomorphic signature scheme that can be used in conjunction with network coding to prevent malicious modification of data. The overhead of our scheme is small and independent of the file or packet size: both public keys and signatures in our scheme consist of only a single group element.

2008

EPRINT

Collusion-Free Multiparty Computation in the Mediated Model
Abstract

Collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. In the standard communication model (and assuming the existence of one-way functions), protocols satisfying any reasonable degree of privacy cannot be collusion-free. To circumvent this impossibility result, Alwen et al. recently suggested the mediated model where all communication passes through a mediator; the goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees continue to hold if the mediator is dishonest. In this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting.
We strengthen the definition of Alwen et al. in several ways, and resolve the key open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.

2008

EPRINT

Signing a Linear Subspace: Signature Schemes for Network Coding
Abstract

Network coding offers increased throughput and improved robustness
to random faults in completely decentralized networks.
In contrast to traditional routing schemes, however, network coding
requires intermediate nodes to modify data packets en route;
for this reason, standard signature schemes are inapplicable and it
is a challenge to provide resilience to tampering by malicious
nodes.
Here, we propose two signature schemes that can be used in
conjunction with network coding to prevent malicious modification of
data. In particular, our schemes can be viewed as signing linear
subspaces in the sense that a signature on V
authenticates exactly those vectors in V.
Our first scheme is homomorphic and has better performance,
with both public key size and per-packet overhead being constant.
Our second scheme does not rely on random oracles and uses weaker assumptions.
We also prove a lower bound on the length of signatures for
linear subspaces showing that both of our schemes are essentially optimal in
this regard.

2007

EPRINT

Which Languages Have 4-Round Zero-Knowledge Proofs?
Abstract

We show, unconditionally, that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box simulation).

2007

EPRINT

Improving the Round Complexity of 'Round-Optimal' VSS
Abstract

We revisit the following question: what is the optimal round complexity of verifiable secret sharing~(VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties $t$ satisfies $t < n/3$, with $n$ being the total number of parties. Work of Gennaro et al. (STOC~2001) and Fitzi et al. (TCC~2006) shows that, assuming a broadcast channel, 3~rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available ``for free'' and does not attempt to minimize its usage. As argued previously by the authors, this approach leads to poor round complexity when protocols are compiled for a point-to-point network.
We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain ``2-level sharing'' property that makes it useful for constructing protocols for general secure computation.

2007

EPRINT

Universally Composable Multi-Party Computation with an Unreliable Common Reference String
Abstract

Universally composable multi-party computation has been studied in two settings:
\begin{itemize}
\item When a majority of participants are honest, universally composable multi-party computation
is known to be possible without any assumptions.
\item When honest participants are \emph{not} in the majority, universally composable multi-party computation is known to be impossible (under any cryptographic assumption) in the bare model. On the other hand, feasibility results have been obtained (under standard cryptographic assumptions) in various augmented models, the most popular of which posits the existence of a \emph{common references string} (CRS) available to all parties who are executing the protocol.
\end{itemize}
In either of the above settings, some \emph{assumption} regarding the protocol execution is made (i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second), and if this assumption is incorrect then all security is lost.
A natural question is whether it is possible to design protocols giving \emph{some} assurance of security in case \emph{either one} of these assumptions holds, i.e., a single protocol (that uses a CRS) which is secure if \emph{either} at most $s$ players are dishonest \emph{or} if up to $t$ players are dishonest (with $t > s$) but the CRS is chosen in the proscribed manner. We show that such protocols exist if and only if $s+t < n$.

2007

EPRINT

Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products
Abstract

Predicate encryption is a new paradigm generalizing, among other
things, identity-based encryption. In a predicate encryption scheme,
secret keys correspond to predicates and ciphertexts are associated
with attributes; the secret key SK_f corresponding to the predicate
f can be used to decrypt a ciphertext associated with attribute I if and only if f(I)=1. Constructions of such schemes are currently known for relatively few classes of predicates.
We construct such a scheme for predicates corresponding to the evaluation of inner products over N (for some large integer N).
This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold predicates (among others). Besides serving as what we feel is a significant step forward in the theory of predicate encryption,
our results lead to a number of applications that are interesting in their own right.

2006

EPRINT

Analyzing the HB and HB+ Protocols in the ``Large Error'' Case
Abstract

HB and HB+ are two shared-key, unidirectional authentication protocols whose extremely low computational cost makes them potentially well-suited for severely resource-constrained devices. Security of these protocols is based on the conjectured hardness of learning parity with noise; that is, learning a secret $s$ given ``noisy'' dot products of $s$ that are incorrect with probability $\epsilon$.
Although the problem of learning parity with noise is meaningful for any constant $\epsilon < 1/2$, existing proofs of security for HB and HB+ only imply security when $\epsilon < 1/4$. In this note, we show how to extend these proofs to the case of arbitrary $\epsilon < 1/2$.

2006

EPRINT

On Expected Constant-Round Protocols for Byzantine Agreement
Abstract

In a seminal paper, Feldman and Micali (STOC '88) show an $n$-party Byzantine agreement protocol tolerating $t < n/3$ malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming
honest majority (i.e., $t < n/2$), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI).
Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool --- a new primitive we introduce called moderated VSS --- also yields a simpler proof of the Feldman-Micali result.
We also show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using $o(n)$ rounds) for the case of $t<n/2$.

2006

EPRINT

Rational Secret Sharing, Revisited
Abstract

We consider the problem of secret sharing among $n$ rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for $n=2$ but show a solution for the case $n\geq 3$. Contrary to their claim, we show a protocol for rational secret sharing among $n=2$ players; our protocol extends to the case $n\geq 3$, where it is simpler than the Halpern-Teague solution and also offers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague.
Our techniques extend to the case of rational players trying to securely compute an arbitrary function, under certain assumptions on the utilities of the players.

2006

EPRINT

On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation
Abstract

Two settings are typically considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide full security (and, in particular, guarantee output delivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security is completely compromised. On the other hand, protocols tolerating arbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the ''best of both worlds''; namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, and ruled out constant-round protocols of this type.
As our main result, we completely settle the question by ruling out
protocols using any (expected) polynomial number of rounds. Given this stark negative result, we ask what can be achieved if we are willing to assume simultaneous message transmission (or, equivalently, a non-rushing adversary). In this setting, we show that impossibility still holds for logarithmic-round protocols. We also show, for any polynomial $p$, a protocol (whose round complexity depends on $p$) that can be simulated to within closeness $O(1/p)$.

2005

EPRINT

Modeling Insider Attacks on Group Key-Exchange Protocols
Abstract

Protocols for authenticated key exchange (AKE) allow parties within an insecure network to establish a common session key which can then be used to secure their future communication. It is fair to say that group AKE is currently less well understood than the case of two-party AKE; in particular, attacks by malicious insiders --- a concern specific to the group setting --- have so far been considered only in a relatively ``ad-hoc'' fashion. The main contribution of this work is to address this deficiency by providing a formal, comprehensive model and definition of security for group AKE which automatically encompasses insider attacks. We do so by defining an appropriate ideal functionality for group AKE within the universal composability (UC) framework. As a side benefit, any protocol secure with respect to our definition is secure even when run concurrently with other protocols, and the key generated by any such protocol may be used securely in any subsequent application.
In addition to proposing this definition, we show that the resulting notion of security is strictly stronger than the one proposed by Bresson, et al. (termed ``AKE-security''), and that our definition implies all previously-suggested notions of security against insider attacks. We also show a simple technique for converting any AKE-secure protocol into one secure with respect to our definition.

2005

EPRINT

Universally Composable Password-Based Key Exchange
Abstract

We propose and realize a definition of security for password-based key exchange within the framework of universal composability (UC), thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, our definition does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show how to realize such channels given any password-based key exchange protocol.
The password-based key exchange protocol shown here is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the "plain" model (e.g., without a common reference string).

2005

EPRINT

Ring Signatures: Stronger Definitions, and Constructions without Random Oracles
Abstract

Ring signatures, first introduced by Rivest, Shamir, and Tauman, enable a user to sign a message so that a ring of possible signers (of which the user is a member) is identified, without revealing exactly which member of that ring actually generated the signature. In contrast to group signatures, ring signatures are completely ``ad-hoc'' and do not require any central authority or coordination among the various users (indeed, users do not even need to be aware of each other); furthermore, ring signature schemes grant users fine-grained control over the level of anonymity associated with any particular signature.
This paper has two main areas of focus. First, we examine previous definitions of security for ring signature schemes and suggest that most of these prior definitions are too weak, in the sense that they do not take into account certain realistic attacks. We propose new definitions of anonymity and unforgeability which address these threats, and give separation results proving that our new notions are strictly stronger than previous ones. Second, we show the first constructions of ring signature schemes in the standard model. One scheme is based on generic assumptions and satisfies our strongest definitions of security. Two additional schemes are more efficient, but achieve weaker security guarantees and more limited functionality.

2005

EPRINT

On Constructing Universal One-Way Hash Functions from Arbitrary One-Way Functions
Abstract

A fundamental result in cryptography is that a digital signature scheme can be constructed from an arbitrary one-way function. A proof of this somewhat surprising statement follows from two results: first, Naor and Yung defined the notion of universal one-way hash functions and showed that the existence of such hash functions implies the existence of secure digital signature schemes. Subsequently, Rompel showed that universal one-way hash functions could be constructed from arbitrary one-way functions. Unfortunately, despite the importance of the result, a complete proof of the latter claim has never been published. In fact, a careful reading of Rompel's original conference publication reveals a number of errors in many of his arguments which have (seemingly) never been addressed.
We provide here what is --- as far as we know --- the first complete write-up of Rompel's proof that universal one-way hash functions can be constructed from arbitrary one-way functions.

2005

EPRINT

Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs
Abstract

The standard class of adversaries considered in cryptography is that of {\em strict} polynomial-time probabilistic machines. However, {\em expected} polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is {\em essential} for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs.

2005

EPRINT

Parallel and Concurrent Security of the HB and HB+ Protocols
Abstract

At Crypto 2005, Juels and Weis (building on work of Hopper and Blum) proposed and analyzed two shared-key authentication protocols --- HB and HB+ --- whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the ``learning parity with noise'' (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB+ protocol is proven secure against active attacks.
Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB+ protocol to be parallelized, thereby reducing its round complexity from super-logarithmic (in the security parameter) to 3.
Using a recent result by Regev (STOC 2005) regarding the LPN problem, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. Applying Regev's result also yields what we find to be substantially simpler security proofs for these protocols which are also more complete in that they explicitly address the dependence of the soundness error on the number of iterations.

2004

EPRINT

Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption
Abstract

Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.

2004

EPRINT

Adaptively-Secure, Non-Interactive Public-Key Encryption
Abstract

Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure.
Impossibility holds even if secure data erasure is possible.
We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about
the frequency of communication between parties. Using this approach,
we construct adaptively-secure, completely non-interactive encryption
schemes supporting secure encryption of arbitrarily-many messages from
arbitrarily-many senders. Our schemes additionally provide
forward security and security against chosen-ciphertext attacks.

2004

EPRINT

Reducing Complexity Assumptions for Statistically-Hiding Commitment
Abstract

Determining the minimal assumptions needed to construct various
cryptographic building blocks has been a focal point of research in
theoretical cryptography. For most --- but not all! --- cryptographic
primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation.
In this work, we show that regular one-way functions suffice.
We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem.
Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.

2003

EPRINT

A Forward-Secure Public-Key Encryption Scheme
Abstract

Cryptographic computations are often carried out on insecure devices
for which the threat of key exposure represents a serious and
realistic concern. In an effort to mitigate the damage caused by
exposure of secret keys stored on such devices, the paradigm of
\emph{forward security} was introduced. In a forward-secure scheme,
secret keys are updated at regular periods of time; exposure of the
secret key corresponding to a given time period does not enable an
adversary to ``break'' the scheme (in the appropriate sense) for
any \emph{prior} time period. A number of constructions of
forward-secure digital signature schemes, key-exchange protocols,
and symmetric-key schemes are known.
We present the first non-trivial constructions of (non-interactive)
forward-secure public-key encryption schemes. Our main construction
achieves security against chosen-plaintext attacks under the decisional
bilinear Diffie-Hellman assumption in the standard model. This
scheme is practical, and all parameters grow at most logarithmically
with the total number of time periods. We also give a slightly more
efficient scheme in the random oracle model. Both our schemes can be
extended to achieve security against chosen-ciphertext attacks and to
support an unbounded number of time periods.
Toward our goal, we introduce the notion of \emph{binary tree
encryption} and show how to construct a binary tree encryption scheme
in the standard model. This new primitive may be of independent
interest. In particular, we use it to construct the first known example
of a (hierarchical) identity-based encryption scheme that is secure
in the standard model. (Here, however, the notion of security we
achieve is slightly weaker than what is achieved in some previous constructions
in the random oracle model.)

2003

EPRINT

Scalable Protocols for Authenticated Group Key Exchange
Abstract

We consider the fundamental problem of authenticated group key
exchange among $n$ parties within a larger and insecure public
network. A number of solutions to this problem have been proposed;
however, all provably-secure solutions thus far are not scalable and,
in particular, require $O(n)$ rounds. Our main contribution is the
first {\em scalable} protocol for this problem along with a rigorous
proof of security in the standard model under the DDH assumption;
our protocol uses a constant number of rounds and requires only $O(1)$
``full'' modular exponentiations per user. Toward this goal and of
independent interest, we first present a scalable compiler that
transforms any group key-exchange protocol secure against a passive
eavesdropper to an \emph{authenticated} protocol which is secure
against an active adversary who controls all communication in the
network. This compiler adds only one round and $O(1)$ communication
(per user) to the original scheme. We then prove secure --- against a
passive adversary --- a variant of the two-round group key-exchange
protocol of Burmester and Desmedt. Applying our compiler to this
protocol results in a provably-secure three-round protocol for
\emph{authenticated} group key exchange which also achieves
forward secrecy.

2003

EPRINT

Chosen-Ciphertext Security from Identity-Based Encryption
Abstract

We show how to construct a CCA-secure public-key encryption scheme
from any CPA-secure identity-based encryption (IBE) scheme. Our
conversion from IBE to a CCA-secure scheme is simple,
efficient, and provably secure in the standard model (i.e., security
of the resulting scheme does not rely on the random oracle model).
In addition, the resulting scheme achieves CCA security even if the
underlying IBE scheme satisfies only a ``weak'' notion of security
which is known to be achievable in the standard model based on the
bilinear Diffie-Hellman assumption. Thus, our results yield a new
construction of CCA-secure public-key encryption in the
standard model. Interestingly, the resulting scheme avoids any
non-interactive proofs of ``well-formedness'' which were shown to
underlie all previously-known constructions.
We also extend our technique to obtain a simple and reasonably efficient
method for securing any BTE scheme against adaptive chosen-ciphertext
attacks. This, in turn, yields more efficient constructions of CCA-secure
(hierarchical) identity-based and forward-secure encryption schemes in the
standard model.
Our results --- building on previous black-box separations ---
rule out black-box constructions of IBE from CPA-secure public-key encryption.

2002

EPRINT

Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications
Abstract

We describe very efficient protocols for non-malleable (interactive)
proofs of plaintext knowledge for the RSA, Rabin, Paillier, and
El-Gamal encryption schemes whose security can be proven in the
standard model. We also highlight some important applications of
these protocols, where we take care to ensure that our protocols
remain secure when run in an asynchronous, concurrent environment:
--- Chosen-ciphertext-secure, interactive encryption: In some settings
where both parties are on-line (e.g., SSL), an interactive encryption
protocol may be used. We construct chosen-ciphertext-secure interactive
encryption schemes based on any of the schemes above. In each case,
the improved scheme requires only a small overhead beyond the original,
semantically-secure scheme.
--- Password-based authenticated key exchange: We provide efficient
protocols for password-based authenticated key exchange in the public-
key model \cite{HK98,B99}. Security of our protocols may be based on
any of the cryptosystems mentioned above.
--- Deniable authentication: We demonstrate deniable authentication
protocols satisfying the strongest notion of security. These are the
first efficient constructions based on, e.g., the RSA or computational Diffie-Hellman assumptions.
Our techniques provide a general methodology for constructing efficient
\emph{non-malleable} (zero-knowledge) proofs of knowledge when shared
parameters are available (for our intended applications, these
parameters can simply be included as part of users' public keys). Thus,
non-malleable proofs of knowledge are easy to achieve ``in practice''.

2002

EPRINT

A Forward-Secure Public-Key Encryption Scheme
Abstract

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern.
In an effort to mitigate the damage caused by exposure of secret data stored on such devices, the paradigm of \emph{forward security} was introduced.
In this model, secret keys are updated at regular intervals throughout the lifetime of the system; furthermore, exposure of a secret key corresponding to a given interval does not enable an adversary to ``break'' the system (in the appropriate sense) for any \emph{prior} time period.
A number of constructions of forward-secure digital signature schemes and symmetric-key schemes are known.
We present the first construction of a forward-secure public-key encryption scheme whose security is based on the bilinear Diffie-Hellman assumption in the random oracle model.
Our scheme can be extended to achieve chosen-ciphertext security at minimal additional cost.
The construction we give is quite efficient: all parameters of the scheme grow (at most) poly-logarithmically with the total number of time periods.

2002

EPRINT

Key-Insulated Public-Key Cryptosystems
Abstract

Cryptographic computations (decryption, signature generation, etc.)
are often performed on a relatively insecure device (e.g., a mobile
device or an Internet-connected host) which cannot be trusted to
maintain secrecy of the private key. We propose and investigate the
notion of \emph{key-insulated security} whose goal is to minimize the damage
caused by secret-key exposures. In our model, the secret key(s)
stored on the insecure device are refreshed at discrete time periods
via interaction with a physically-secure --- but
computationally-limited --- device which stores a ``master key''. All
cryptographic computations are still done on the insecure device, and
the public key remains unchanged. In a (t, N)-key-insulated scheme, an
adversary who compromises the insecure device and obtains secret keys
for up to t periods of his choice is unable to violate the security
of the cryptosystem for \emph{any} of the remaining N-t periods.
Furthermore, the scheme remains secure (for \emph{all} time periods)
against an adversary who compromises \emph{only} the physically-secure
device.
We notice that key-insulated schemes significantly improve the security
guarantee of forward-secure schemes [A97,BM99], in which exposure
of the secret key at even a single time period (necessarily)
compromises the security of the system for all future time
periods. This improvement is achieved with minimal cost: infrequent
key updates with a (possibly untrusted) secure device.
We focus primarily on key-insulated public-key encryption. We construct a
(t,N)-key-insulated encryption scheme based on any (standard) public-key
encryption scheme, and give a more efficient construction based on the
DDH assumption. The latter construction is then extended to achieve
chosen-ciphertext security.

2001

EPRINT

Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
Abstract

We present an efficient password-authenticated key exchange protocol
which is secure against off-line dictionary attacks even when users
choose passwords from a very small space (say, a dictionary of English
words). We prove security in the standard model under the decisional
Diffie-Hellman assumption, assuming public parameters generated by a
trusted party. Compared to the recent work of Goldreich and Lindell
(which was the first to give a secure construction, under general
assumptions, in the standard model), our protocol requires only 3
rounds and is efficient enough to be used in practice.

2001

EPRINT

Efficient and Non-Interactive Non-Malleable Commitment
Abstract

We present new constructions of non-malleable commitment schemes, in
the public parameter model (where a trusted party makes parameters
available to all parties), based on the discrete logarithm or RSA
assumptions. The main features of our schemes are: they achieve
near-optimal communication for arbitrarily-large messages and are
non-interactive. Previous schemes either required (several rounds of)
interaction or focused on achieving non-malleable commitment based on
general assumptions and were thus efficient only when committing to a
single bit. Although our main constructions are for the case of
perfectly-hiding commitment, we also present a communication-efficient,
non-interactive commitment scheme (based on general assumptions) that
is perfectly binding.

2001

EPRINT

Threshold Cryptosystems Based on Factoring
Abstract

We consider threshold cryptosystems over a composite
modulus $N$ where the \emph{factors} of $N$ are shared among the
participants as the secret key.
This is a new paradigm for threshold cryptosystems based on a
composite modulus, differing from the
typical treatment of RSA-based systems where a ``decryption
exponent'' is shared among the participants. Our approach yields
solutions to some open problems in threshold cryptography; in particular, we obtain the following:
1. \emph{Threshold homomorphic encryption}. A number of applications (e.g., electronic voting or efficient multi-party computation) require threshold homomorphic encryption schemes.
We present a protocol for threshold decryption of the homomorphic Goldwasser-Micali encryption scheme \cite{GM84}, answering an open question of \cite{FPS00}.
2. \emph{Threshold cryptosystems as secure as factoring}. We describe a threshold version of a variant of the signature standards ISO 9796-2 and PKCS\#1 v1.5 (cf.\ \cite[Section 11.3.4]{MvOV}), thus giving the first threshold signature scheme
whose security (in the random oracle model) is equivalent to the hardness of factoring \cite{C02}.
Our techniques may be adapted to distribute the Rabin encryption
scheme \cite{R79} whose semantic security may be reduced to the hardness of factoring.
3. \emph{Efficient threshold schemes without a trusted dealer.}
Because our schemes only require sharing of $N$ --- which furthermore need not be a product of strong primes --- our schemes are very efficient (compared to previous schemes) when a trusted dealer is not assumed and key generation is done in a distributed manner.
Extensions to achieve robustness and proactivation are also possible with our schemes.

#### Program Committees

- Crypto 2020
- Crypto 2017
- TCC 2016
- Crypto 2016
- PKC 2015
- Eurocrypt 2013
- Crypto 2013
- TCC 2012
- Asiacrypt 2012
- Eurocrypt 2011
- Asiacrypt 2010
- PKC 2010
- Eurocrypt 2009
- Crypto 2009
- Eurocrypt 2008
- Asiacrypt 2008
- Asiacrypt 2007
- TCC 2007
- PKC 2007
- Crypto 2006
- TCC 2006
- Eurocrypt 2006
- Crypto 2005
- Asiacrypt 2004
- Crypto 2003

#### Coauthors

- Martin R. Albrecht (1)
- Joël Alwen (2)
- Daniel Apon (3)
- Giuseppe Ateniese (1)
- Adam Bender (3)
- Erica Blum (1)
- Dan Boneh (3)
- Xavier Boyen (1)
- Zvika Brakerski (2)
- Enrico Buonanno (1)
- Ran Canetti (9)
- T.-H. Hubert Chan (1)
- Jung Hee Cheon (1)
- Seung Geol Choi (8)
- Kai-Min Chung (2)
- Carlos Cid (2)
- Benoît Cogliati (1)
- Giovanni Di Crescenzo (2)
- Dana Dachman-Soled (6)
- Yevgeniy Dodis (10)
- David Evans (1)
- Xiong Fan (1)
- Serge Fehr (2)
- Nils Fleischhacker (3)
- David Freeman (2)
- Georg Fuchsbauer (2)
- Juan A. Garay (1)
- Rosario Gennaro (1)
- Craig Gentry (1)
- Shafi Goldwasser (1)
- S. Dov Gordon (11)
- Vipul Goyal (3)
- Adam Groce (3)
- Siyao Guo (1)
- Iftach Haitner (2)
- Shai Halevi (10)
- Carmit Hazay (2)
- Viet Tung Hoang (2)
- Cheng Hong (1)
- Omer Horvitz (4)
- Yan Huang (3)
- Yuval Ishai (1)
- Abhishek Jain (1)
- Yael Tauman Kalai (1)
- Seny Kamara (2)
- Vladimir Kolesnikov (3)
- Chiu-Yuen Koo (9)
- Hugo Krawczyk (1)
- Ranjit Kumaresan (6)
- Eyal Kushilevitz (1)
- Jooyoung Lee (1)
- Éric Levieil (1)
- Yehuda Lindell (10)
- Feng-Hao Liu (4)
- Julian Loss (1)
- Wen-jie Lu (1)
- Anna Lysyanskaya (3)
- Philip D. MacKenzie (2)
- Lior Malka (1)
- Alex J. Malozemoff (6)
- Ueli Maurer (2)
- Allen McIntosh (1)
- Ruggero Morselli (6)
- Steven Myers (1)
- David Naccache (2)
- Kartik Nayak (1)
- Adam O'Neill (1)
- Rafail Ostrovsky (8)
- Giuseppe Persiano (1)
- Erez Petrank (1)
- Antigoni Polychroniadou (1)
- Tal Rabin (1)
- Samuel Ranellucci (1)
- Vanishree Rao (1)
- Leonid Reyzin (2)
- Mike Rosulek (1)
- Amit Sahai (3)
- Dominique Schröder (6)
- Gil Segev (1)
- Jae Hong Seo (1)
- Ronen Shaltiel (2)
- Abhi Shelat (1)
- Elaine Shi (7)
- Ji Sun Shin (4)
- Adam Smith (9)
- Fang Song (2)
- John P. Steinberger (1)
- Björn Tackmann (2)
- Aishwarya Thiruvengadam (7)
- Vinod Vaikuntanathan (7)
- Ivan Visconti (1)
- Shabsi Walfish (1)
- Xiao Shaun Wang (1)
- Xiao Wang (4)
- Brent Waters (5)
- Hoeteck Wee (1)
- Shouhuai Xu (3)
- Arkady Yerukhimovich (6)
- Moti Yung (13)
- Mohammad Zaheri (1)
- Zhe Zhang (1)
- Hong-Sheng Zhou (13)
- Hong Sheng Zhou (1)
- Vassilis Zikas (7)