## CryptoDB

### Tal Rabin

#### Affiliation: IBM Research

#### Publications

**Year**

**Venue**

**Title**

2020

TCC

Can a Blockchain Keep a Secret?
📺
Abstract

Blockchains are gaining traction and acceptance, not just for cryptocurrencies, but increasingly as an architecture for distributed computing.
In this work we seek solutions that allow a \emph{public} blockchain to act as a trusted long-term repository of secret information:
Our goal is to deposit a secret with the blockchain, specify how it is to be used (e.g., the conditions under which it is released), and have the blockchain keep the secret and use it only in the specified manner (e.g., release only it once the conditions are met).
This simple functionality enables many powerful applications, including signing statements on behalf of the blockchain, using it as the control plane for a storage system, performing decentralized program-obfuscation-as-a-service, and many more.
Using proactive secret sharing techniques, we present a scalable solution for implementing this functionality on a public blockchain, in the presence of a mobile adversary controlling a small minority of the participants.
The main challenge is that, on the one hand, scalability requires that we use small committees to represent the entire system, but, on the other hand, a mobile adversary may be able to corrupt the entire committee if it is small.
For this reason, existing proactive secret sharing solutions are either non-scalable or insecure in our setting.
We approach this challenge via "player replaceability", which ensures the committee is anonymous until after it performs its actions.
Our main technical contribution is a system that allows sharing and re-sharing of secrets among the members of small dynamic committees, without knowing who they are until after they perform their actions and erase their secrets. Our solution handles a fully mobile adversary corrupting roughly 1/4 of the participants at any time, and is scalable in terms of both the number of parties and the number of time intervals.

2019

JOFC

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting
Abstract

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.

2019

TCC

On Fully Secure MPC with Solitary Output
Abstract

We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities?We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way.On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

2018

CRYPTO

On the Local Leakage Resilience of Linear Secret Sharing Schemes
📺
Abstract

We consider the following basic question: to what extent are standard secret sharing schemes and protocols for secure multiparty computation that build on them resilient to leakage? We focus on a simple local leakage model, where the adversary can apply an arbitrary function of a bounded output length to the secret state of each party, but cannot otherwise learn joint information about the states.We show that additive secret sharing schemes and high-threshold instances of Shamir’s secret sharing scheme are secure under local leakage attacks when the underlying field is of a large prime order and the number of parties is sufficiently large. This should be contrasted with the fact that any linear secret sharing scheme over a small characteristic field is clearly insecure under local leakage attacks, regardless of the number of parties. Our results are obtained via tools from Fourier analysis and additive combinatorics.We present two types of applications of the above results and techniques. As a positive application, we show that the “GMW protocol” for honest-but-curious parties, when implemented using shared products of random field elements (so-called “Beaver Triples”), is resilient in the local leakage model for sufficiently many parties and over certain fields. This holds even when the adversary has full access to a constant fraction of the views. As a negative application, we rule out multi-party variants of the share conversion scheme used in the 2-party homomorphic secret sharing scheme of Boyle et al. (Crypto 2016).

2018

TCC

Best Possible Information-Theoretic MPC
Abstract

We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be “best possible.” This notion still requires full security against dishonest minority in the usual sense, and adds a meaningful notion of information-theoretic security even against dishonest majority.We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

2013

TCC

2010

EPRINT

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
Abstract

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
The Diffie-Hellman protocol (DHP) is one of the most studied protocols in cryptography. Much work has been dedicated to armor the original protocol against active attacks while incurring a minimal performance overhead relative to the basic (unauthenticated) DHP. This line of work has resulted in some remarkable protocols, e.g., MQV, where the protocol's communication cost is identical to that of the basic DHP and the computation overhead is small. Unfortunately, MQV and similar 2-message ``implicitly authenticated" protocols do not achieve full security against active attacks since they cannot provide forward secrecy (PFS), a major security goal of DHP, against active attackers.
In this paper we investigate the question of whether one can push the limits of authenticated DHPs even further, namely, to achieve communication complexity as in the original DHP (two messages with a single group element per message), maintain low computational overhead, and yet achieve full PFS against active attackers in a provable way. We answer this question in the affirmative by resorting to an old and elegant key agreement protocol: the Okamoto-Tanaka protocol \cite{okta}. We present a variant of the protocol (denoted mOT) which achieves the above minimal communication, incurs a computational overhead relative to the basic DHP that is practically negligible, and yet achieves full provable key agreement security, including PFS, against active attackers. Moreover, due to the identity-based properties of mOT, even the sending of certificates (typical for authenticated DHPs) can be avoided in the protocol.
As additional contributions, we apply our analysis to prove the security of a recent multi-domain extension of the Okamoto-Tanaka protocol by Schridde et al. and show how to adapt mOT to the (non id-based) certificate-based setting.

2008

EPRINT

Threshold RSA for Dynamic and Ad-Hoc Groups
Abstract

We consider the use of threshold signatures in ad-hoc and dynamic groups such as MANETs ("mobile ad-hoc networks"). While the known threshold RSA signature schemes have several properties that make them good candidates for deployment in these scenarios, we show that none of these schemes is practical enough for realistic use in these highly-constrained environments. In particular, this is the case of the most efficient of these threshold RSA schemes, namely, the one due to Shoup. Our contribution is in presenting variants of Shoup's protocol that overcome the limitations that make the original protocol unsuitable for dynamic groups. The resultant schemes provide the efficiency and flexibility needed in ad-hoc groups, and add the capability of incorporating new members (share-holders) to the group of potential signers without relying on central authorities. Namely, any threshold of existing members can cooperate to add a new member. The schemes are efficient, fully non-interactive and do not assume broadcast.

2008

EPRINT

Degradation and Amplification of Computational Hardness
Abstract

What happens when you use a partially defective bit-commitment protocol to commit to the same bit many times? For example, suppose that the protocol allows the receiver to guess the committed bit with advantage $\eps$, and that you used that protocol to commit to the same bit more than $1/\eps$ times. Or suppose that you encrypted some message many times (to many people), only to discover later that the encryption scheme that you were using is partially defective, and an eavesdropper has some noticeable advantage in guessing the encrypted message from the ciphertext. Can we at least show that even after many such encryptions, the eavesdropper could not have learned the message with certainty?
In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for $n$ times, the receiver's advantage in guessing the encrypted bit is negligibly close to $1-(1-\eps)^n$.
Our results for hardness amplification follow just by observing that some of the known proofs for Yao's lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch.

2008

EPRINT

Strongly-Resilient and Non-Interactive Hierarchical Key-Agreement in MANETs
Abstract

Key agreement is a fundamental security functionality by which pairs of nodes agree on shared keys to be used for protecting their pairwise communications. In this work we study key-agreement schemes that are well-suited for the mobile network environment.
Specifically, we describe schemes with the following haracteristics:
-- Non-interactive: any two nodes can compute a unique shared secret
key without interaction;
-- Identity-based: to compute the shared secret key, each node only
needs its own secret key and the identity of its peer;
-- Hierarchical: the scheme is decentralized through a
hierarchy where intermediate nodes in the hierarchy can derive the secret keys for each of its children without any limitations or prior knowledge on the number of such children or their identities;
-- Resilient: the scheme is fully resilient against compromise of
{\em any number of leaves} in the hierarchy, and of a threshold number of nodes in each of the upper levels of the hierarchy.
Several schemes in the literature have three of these four properties, but the schemes in this work are the first to possess all four. This makes them well-suited for environments such as MANETs and tactical networks which are very dynamic, have significant bandwidth and energy constraints, and where many nodes are vulnerable to compromise. We provide rigorous analysis of the proposed schemes and discuss implementations aspects.

2007

EPRINT

Secure Computation Without Authentication
Abstract

Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where all
messages sent by the parties may be tampered with and modified by the
adversary without the honest parties being able to detect this
fact. In this model, it is not possible to achieve the same level
of security as in the authenticated-channel setting. Nevertheless,
we show that meaningful security guarantees can be provided:
Essentially, all the adversary can do is to partition the network into
disjoint sets, where in each set the computation is secure in itself,
and also independent of the computation in the other sets. In the basic setting our construction provides, for the first time,
non-trivial security guarantees in a model with no set-up assumptions whatsoever. We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems
that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. As an application of our results, we study the question of constructing secure protocols in partially-authenticated networks, where some of the links are authenticated and some are not (as is the case in most networks today).

2004

EPRINT

Protocol Initialization for the Framework of Universal Composability
Abstract

Universally composable protocols (Canetti, FOCS 2000) are cryptographic protocols that remain secure even when run concurrently with arbitrary other protocols. Thus, universally composable protocols can be run in modern networks, like the Internet, and their security is guaranteed. However, the definition of universal composition actually assumes that each execution of the protocol is assigned a unique session identifier, and furthermore, that this identifier is known to all the participating parties. In addition, all universally composable protocols assume that the set of participating parties and the specification of the protocol to be run are a-priori agreed upon and known to all parties. In a decentralized network like the Internet, this setup information must be securely generated by the parties themselves. In this note we formalize the setup problem and show how to securely realize it with a simple and highly efficient protocol.

2004

EPRINT

Secure Hashed Diffie-Hellman over Non-DDH Groups
Abstract

We show that in applications that use the Diffie-Hellman (DH) transform but
take care of hashing the DH output (as required, for example, for secure
DH-based encryption and key exchange) the usual requirement to work over a
DDH group (i.e., a group in which the Decisional Diffie-Hellman assumption
holds) can be relaxed to only requiring that the DH group contains a large
enough DDH subgroup. In particular, this implies the security of (hashed)
Diffie-Hellman over non-prime order groups such as $Z_p^*$. Moreover, our
results show that one can work directly over $Z_p^*$ without requiring any
knowledge of the prime factorization of $p-1$ and without even having to
find a generator of $Z_p^*$.
These results are obtained via a general characterization of DDH groups in
terms of their DDH subgroups, and a relaxation (called $t$-DDH)
of the DDH assumption via computational entropy.
We also show that, under the short-exponent
discrete-log assumption, the security of the hashed Diffie-Hellman transform
is preserved when replacing full exponents with short exponents.

2004

EPRINT

On the Composition of Authenticated Byzantine Agreement
Abstract

A fundamental problem of distributed computing is that of
simulating a secure broadcast channel, within the setting of a
point-to-point network. This problem is known as Byzantine
Agreement (or Generals) and has been the focus of much research.
Lamport et al. showed that in order to achieve Byzantine Agreement
in the standard model, more than 2/3 of the participating
parties must be honest. They further showed that by augmenting the
network with a public-key infrastructure for digital signatures,
it is possible to obtain protocols that are secure for any number
of corrupted parties. The problem in this augmented model is
called "authenticated Byzantine Agreement".
In this paper we consider the question of concurrent, parallel and
sequential composition of authenticated Byzantine Agreement
protocols. We present surprising impossibility results showing
that:
* If an authenticated Byzantine Agreement protocol remains
secure under parallel or concurrent composition (even for just two
executions), then more than 2/3 of the participating parties
must be honest.
* Deterministic authenticated Byzantine Agreement protocols that
run for $r$ rounds and tolerate 1/3 or more corrupted parties,
can remain secure for at most $2r-1$ sequential executions.
In contrast, we present randomized protocols for authenticated
Byzantine Agreement that remain secure under sequential
composition, for {\em any}\/ polynomial number of executions. We
exhibit two such protocols. In the first protocol, the number of
corrupted parties may be any number less than 1/2 (i.e., an
honest majority is required). In the second protocol, any number
of parties may be corrupted; however, the overall number of
parties must be limited to $O(\log k/\log\log k)$, where $k$ is
the security parameter (and so all parties run in time that is
polynomial in $k$). Finally, we show that when the model is
further augmented so that unique and common session identifiers
are assigned to each concurrent session, then any polynomial
number of authenticated Byzantine agreement protocols can be
concurrently executed, while tolerating any number of corrupted
parties.

2002

EPRINT

On the Security of Joint Signature and Encryption
Abstract

We formally study the notion of a joint signature and encryption in
the public-key setting. We refer to this primitive as {\em
signcryption}, adapting the terminology of Zheng [Zhe97]. We present
wo definitions for the security of signcryption depending on whether
the adversary is an outsider or a legal user of the system. We then
examine generic sequential composition methods of building
signcryption from a signature and encryption scheme. Contrary to
what recent results in the symmetric setting [BN00,Kra01] might
lead one to expect, we show that classical ``encrypt-then-sign''
(EtS) and ``sign-then-encrypt'' (StE) methods are both {\em secure}
composition methods in the public-key setting.
We also present a new composition method which we call
``commit-then-encrypt-and-sign'' (CtE&S). Unlike the generic
sequential composition methods, CtE&S applies the expensive
signature and encryption operations {\em in parallel}, which could
imply a gain in efficiency over the StE and EtS schemes. We
also show that the new CtE&S method elegantly combines with the
recent ``hash-sign-switch'' technique of Shamir and Tauman [ST01],
leading to efficient {\em on-line/off-line} signcryption.
Finally and of independent interest, we discuss the {\em definitional}
inadequacy of the standard notion of chosen ciphertext (CAA)
security. Motivated by our applications to signcryption, we show
that the notion of CAA-security is syntactically ill-defined, and
leads to artificial examples of ``secure'' encryption schemes which
do not meet the formal definition of CCA-security. We suggest a
natural and very slight relaxation of CAA-security, which we call
generalized CCA-security (gCCA). We show that gCCA-security suffices
for all known uses of CCA-secure encryption, while no longer
suffering from the definitional shortcomings of the latter.

2002

EPRINT

Universal Composition with Joint State
Abstract

Cryptographic systems often involve running multiple concurrent instances of some protocol, where the instances have some amount of joint state and randomness. (Examples include systems where multiple protocol instances use the same public-key infrastructure, or the same common reference string.) Rather than attempting to analyze the entire system as a single unit, we would like to be able to analyze each such protocol instance as stand-alone, and then use a general composition theorem to deduce the security of the entire system. However, no known composition theorem applies in this setting, since they all assume that the composed protocol instances have disjoint internal states, and that the internal random choices in the various instances are independent.
We propose a new composition operation that can handle the case where
different components have some amount of joint state and randomness,
and demonstrate sufficient conditions for when the new operation preserves security. The new operation, which is called {\em universal composition with joint state} (and is based on the recently proposed universal composition operation), turns out to be very useful in a number of quite different scenarios such as those mentioned above.

1999

EPRINT

Secure Hash-and-Sign Signatures without the Random Oracle
Abstract

We present a new signature scheme which is existentially unforgeable
under chosen message attacks, assuming some variant of the RSA conjecture.
This scheme is not based on "signature trees", and instead it uses
the so called "hash-and-sign" paradigm. It is unique in that the
assumptions made on the cryptographic hash function in use are well
defined and reasonable (although non-standard). In particular, we
do not model this function as a random oracle.
We construct our proof of security in steps. First we describe and
prove a construction which operates in the random oracle model. Then
we show that the random oracle in this construction can be replaced
by a hash function which satisfies some strong (but well defined!)
computational assumptions. Finally, we demonstrate that these assumptions
are reasonable, by proving that a function satisfying them exists under
standard intractability assumptions.

1998

EPRINT

Fast Batch Verification for Modular Exponentiation and Digital Signatures
Abstract

Many tasks in cryptography (e.g., digital signature
verification) call for verification of a basic operation like modular
exponentiation in some group: given (g,x,y) check that g<sup>x</sup>=y.
This is typically done by re-computing g<sup>x</sup> and checking we get y.
We would like to do it differently, and faster.
The approach we use is batching. Focusing first on the basic modular
exponentiation operation, we provide some probabilistic batch verifiers, or
tests, that verify a sequence of modular exponentiations significantly faster
than the naive re-computation method. This yields speedups for several
verification tasks that involve modular exponentiations.
Focusing specifically on digital signatures, we then suggest a weaker notion of
(batch) verification which we call ``screening.'' It seems useful for many
usages of signatures, and has the advantage that it can be done very fast;
in particular, we show how to screen a sequence of RSA signatures at the
cost of one RSA verification plus hashing.

1998

EPRINT

An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products
Abstract

We present efficient zero-knowledge proof systems for quasi-safe
prime products and other related languages. Quasi-safe primes are a
relaxation of safe primes, a class of prime numbers useful in many
cryptographic applications.
Our proof systems achieve higher security and better
efficiency than all previously known ones.
In particular, all our proof systems are perfect or statistical
zero-knowledge, meaning that even a computationally
unbounded adversary cannot extract any information
from the proofs.
Moreover, our proof systems are extremely efficient because they do
not use general reductions to NP-complete problems, can be easily
parallelized preserving zero-knowledge, and are non-interactive for
computationally unbounded provers. The prover can also be efficiently
implemented given some trapdoor information and using very little
interaction.
We demonstrate the applicability of quasi-safe primes
by showing how they can be effectively used in the
context of RSA based undeniable signatures to enforce
the use of ``good'' public keys, i.e.,
keys such that if a signer can convince a recipient
of the validity of a signature, then he won't be able to
subsequently deny the same signature in case of a dispute.

1998

EPRINT

Chameleon Hashing and Signatures
Abstract

We introduce CHAMELEON SIGNATURES that provide with an undeniable
commitment of the signer to the contents of the signed document (as regular
digital signatures do) but, at the same time, do not allow the recipient
of the signature to disclose the contents of the signed information to any
third party without the signer's consent. These signatures are closely
related to Chaum's "undeniable signatures", but chameleon signatures allow
for simpler and more efficient realizations than the latter.
In particular, they are essentially non-interactive and do not involve the
design and complexity of zero-knowledge proofs on which traditional undeniable
signatures are based. Instead, chameleon signatures are generated
under the standard method of hash-then-sign. Yet, the hash functions
which are used are CHAMELEON HASH FUNCTIONS. These hash functions are
characterized by the non-standard property of being collision-resistant
for the signer but collision tractable for the recipient.
We present simple and efficient constructions of chameleon hashing and
chameleon signatures. The former can be constructed based on standard
cryptographic assumptions (such as the hardness of factoring or discrete
logarithms) and have efficient realizations based on these assumptions.
For the signature part we can use any digital signature (such as RSA or DSS)
and prove the unforgeability property of the resultant chameleon signatures
solely based on the unforgeability of the underlying digital signature
in use.

1998

EPRINT

Secure Distributed Storage and Retrieval
Abstract

In his well-known Information Dispersal Algorithm paper, Rabin showed
a way to distribute information in n pieces among n servers in such a
way that recovery of the information is possible in the presence of up
to t inactive servers. An enhanced mechanism to enable construction
in the presence of malicious faults, which can intentionally modify
their pieces of the information, was later presented by Krawczyk.
Yet, these methods assume that the malicious faults occur only at
reconstruction time. <P>
In this paper we address the more general problem of secure storage
and retrieval of information (SSRI), and guarantee that also the
process of storing the information is correct even when some of the
servers fail. Our protocols achieve this while maintaining the
(asymptotical) space optimality of the above methods. <P>
We also consider SSRI with the added requirement of confidentiality,
by which no party except for the rightful owner of the information is
able to learn anything about it. This is achieved through novel
applications of cryptographic techniques, such as the distributed
generation of receipts, distributed key management via threshold
cryptography, and ``blinding.'' <P>
An interesting byproduct of our scheme is the construction of a secret
sharing scheme with shorter shares size in the amortized sense. An
immediate practical application of our work is a system for the secure
deposit of sensitive data. We also extend SSRI to a ``proactive''
setting, where an adversary may corrupt all the servers during the
lifetime of the system, but only a fraction during any given time
interval.

#### Program Committees

- Crypto 2013
- TCC 2013
- Crypto 2010
- TCC 2006
- TCC 2005
- Crypto 2003
- PKC 2003
- Eurocrypt 2001
- Crypto 1998

#### Coauthors

- Jee Hea An (2)
- Gilad Asharov (2)
- Boaz Barak (4)
- Mihir Bellare (2)
- Fabrice Benhamouda (3)
- Ran Canetti (6)
- Ashish Choudhary (1)
- Ronald Cramer (1)
- Ivan Damgård (1)
- Akshay Degwekar (1)
- Yevgeniy Dodis (4)
- Stefan Dziembowski (1)
- Sebastian Faust (1)
- Juan A. Garay (3)
- Rosario Gennaro (24)
- Craig Gentry (1)
- Sergey Gorbunov (1)
- Shai Halevi (12)
- Johan Håstad (1)
- Carmit Hazay (1)
- Martin Hirt (1)
- Yuval Ishai (4)
- Stanislaw Jarecki (7)
- Charanjit S. Jutla (1)
- Jonathan Katz (1)
- Hugo Krawczyk (21)
- Eyal Kushilevitz (3)
- Chengyu Lin (1)
- Yehuda Lindell (8)
- Anna Lysyanskaya (2)
- Nikolaos Makriyannis (1)
- Tal Malkin (1)
- Silvio Micali (2)
- Daniele Micciancio (1)
- Gert Læssøe Mikkelsen (1)
- Angelo Agatino Nicolosi (1)
- Rafael Pass (3)
- Arpita Patra (1)
- C. Pandu Rangan (1)
- Steffen Reidt (1)
- Leonid Reyzin (2)
- Tomas Toft (1)
- Eran Tromer (1)
- Vinod Vaikuntanathan (1)
- Stephen D. Wolthusen (1)