## CryptoDB

### Moti Yung

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

"Bifurcated Cryptography" Folding Competing Cryptosystems into a Single Scheme: On Accountability vs. Anonymity in Private Signatures
Abstract

Over the development of modern cryptography, often, alternative cryptographic schemes are developed to achieve goals that in some important respect are orthogonal. Thus, we have to choose either a scheme which achieves the first goal and not the second, or vice versa.
This results in two types of schemes that compete with each other. In the basic area of user privacy, specifically in anonymous (multi-use credentials) signing, such an orthogonality exists between anonymity and accountability.
The conceptual contribution of this work is to reverse the above orthogonality by design, which essentially typifies the last 25 years or so, and to suggest an alternative methodology where the opposed properties are carefully folded into a single scheme. The schemes will support both opposing properties simultaneously in a bifurcated fashion, where:
- First, based on rich semantics expressed over the message's context and content, the user, etc., the relevant property is applied point-wise per message operation depending on a predicate; and
- Secondly, at the same time, the schemes provide what we call ``branch-hiding;'' namely, the resulting calculated value hides from outsiders which property has actually been locally applied.
Specifically, we precisely define and give the first construction and security proof of a ``Bifurcated Anonymous Signature'' (BiAS): A scheme which supports either absolute anonymity or anonymity with accountability, based on a specific contextual predicate, while being branch-hiding. This novel signing scheme has numerous applications not easily implementable or not considered before, especially because: (i) the conditional traceability does 'not' rely on a trusted authority as it is (non-interactively) encapsulated into signatures; and (ii) signers 'know' the predicate value and can make a conscious choice at each signing time.
Technically, we realize BiAS from homomorphic commitments for a general family of predicates that can be represented by bounded-depth circuits. Our construction is generic and can be instantiated in the standard model from lattices and, more efficiently, from bilinear maps. In particular, the signature length is independent of the circuit size when we use commitments with suitable efficiency properties.

2021

PKC

Non-Interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings
📺
Abstract

We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.

2021

CRYPTO

Receiver-Anonymity in Reradomizable RCCA-Secure Cryptosystems Resolved
📺
Abstract

In this work, we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing Rand-RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek’s scheme (which was the first construction of Rand-RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of Rand-RCCA-secure encryption.

2021

ASIACRYPT

Identity-Based Encryption for Fair Anonymity Applications: Defining, Implementing, and Applying Rerandomizable RCCA-secure IBE
Abstract

Our context is anonymous encryption schemes hiding their receiver, but in a setting which allows authorities to reveal the receiver when needed. While anonymous Identity-Based Encryption (IBE) is a natural candidate for such fair anonymity (it gives trusted authority access by design), the {\it de facto} security standard (a.k.a. IND-ID-CCA) is incompatible with the ciphertext rerandomizability which is crucial to anonymous communication. Thus, we seek to extend IND-ID-CCA security for IBE to a notion that can be meaningfully relaxed for rerandomizability while it still protects against active adversaries.
To the end, inspired by the notion of replayable adaptive chosen-ciphertext attack (RCCA) security (Canetti {\it et al.}, Crypto'03), we formalize a new security notion called Anonymous Identity-Based RCCA (ANON-ID-RCCA) security for rerandomizable IBE and propose the first construction with rigorous security analysis. The core of our scheme is a novel extension of the double-strand paradigm, which was originally proposed by Golle {\it et al.} (CT-RSA'04) and later extended by Prabhakaran and Rosulek (Crypto'07), to the well-known Gentry-IBE (Eurocrypt'06). Notably, our scheme is the first IBE that simultaneously satisfies adaptive security, rerandomizability, and recipient-anonymity to date. As the application of our new notion, we design a new universal mixnet in the identity-based setting that does not require public key distribution (with fair anonymity). More generally, our new notion is also applicable to most existing rerandomizable RCCA-secure applications to eliminate the need for public key distribution infrastructure while allowing fairness.

2020

CRYPTO

Two-Sided Malicious Security for Private Intersection-Sum with Cardinality
📺
Abstract

Private intersection-sum with cardinality allows two parties, where each party holds a private set and one of the parties additionally holds a private integer value associated with each element in her set, to jointly compute the cardinality of the intersection of the two sets as well as the sum of the associated integer values for all the elements in the intersection, and nothing beyond that.
We present a new construction for private intersection sum with cardinality that provides malicious security with abort and guarantees that both parties receive the output upon successful completion of the protocol. A central building block for our constructions is a primitive called shuffled distributed oblivious PRF (DOPRF), which is a PRF that offers oblivious evaluation using a secret key shared between two parties, and in addition to this allows obliviously permuting the PRF outputs of several parallel oblivious evaluations. We present the first construction for shuffled DOPRF with malicious security. We further present several new sigma proof protocols for relations across Pedersen commitments, ElGamal encryptions, and Camenisch-Shoup encryptions that we use in our main construction, for which we develop new batching techniques to reduce communication.
We implement and evaluate the efficiency of our protocol and show that we can achieve communication cost that is only 4-5x greater than the most efficient semi-honest protocol. When measuring monetary cost of executing the protocol in the cloud, our protocol is 25x more expensive than the semi-honest protocol. Our construction also allows for different parameter regimes that enable trade-offs between communication and computation.

2020

ASIACRYPT

Subvert KEM to Break DEM: Practical Algorithm-Substitution Attacks on Public-Key Encryption
📺
Abstract

Motivated by the widespread concern about mass surveillance of encrypted communications, Bellare \textit{et al.} introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare \textit{et al.}, CRYPTO'14 \& CCS'15; Ateniese \textit{et al.}, CCS'15; Berndt and Li\'{s}kiewicz, CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much current attention, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key and previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Li\'{s}kiewicz, CCS'17).
In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practical systems. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack.
Our attack relies on a novel identification and formalization of specific non-black-box yet general enough properties that yield practical ASAs on KEMs. More broadly, this may shed some light on exploring the structural weakness of other composed cryptographic primitives, which may make them susceptible to more dangerous ASAs that surpass the logarithmic upper bound of exfiltration rate on universal ASAs.

2020

JOFC

Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions
Abstract

In threshold cryptography, private keys are divided into n shares, each one of which is given to a different server in order to avoid single points of failure. In the case of threshold public-key encryption, at least $$t \le n$$ t ≤ n servers need to contribute to the decryption process. A threshold primitive is said robust if no coalition of t malicious servers can prevent remaining honest servers from successfully completing private key operations. Non-interactive schemes, considered the most practical ones, allow servers to contribute to decryption without interactions. So far, most non-interactive threshold cryptosystems were only proved secure against static corruptions. In the adaptive corruption scenario (where the adversary can corrupt servers at any time, based on its complete view), all existing robust threshold encryption schemes that also resist chosen-ciphertext attacks till recently require interaction in the decryption phase. A very specific method (in composite order groups) for getting rid of interaction was recently suggested, leaving the question of more generic frameworks and constructions with better security and, in particular, better flexibility (i.e., compatibility with distributed key generation). This paper advances the state of the art and describes a general construction of adaptively secure robust non-interactive threshold cryptosystems with chosen-ciphertext security. We define the novel notion of all-but-one perfectly sound threshold hash proof systems that can be seen as (threshold) hash proof systems with publicly verifiable and simulation-sound proofs. We show that this notion generically implies threshold cryptosystems combining the aforementioned properties. Then, we provide efficient instantiations under well-studied assumptions in bilinear groups (e.g., in such groups of prime order). These instantiations have a tighter security proof in the single-challenge setting and are indeed compatible with distributed key generation protocols.

2019

PKC

Let a Non-barking Watchdog Bite: Cliptographic Signatures with an Offline Watchdog
Abstract

We study how to construct secure digital signature schemes in the presence of kleptographic attacks. Our work utilizes an offline watchdog to clip the power of subversions via only one-time black-box testing of the implementation. Previous results essentially rely on an online watchdog which requires the collection of all communicating transcripts (or active re-randomization of messages).We first give a simple but generic construction, without random oracles, in the partial-subversion model in which key generation and signing algorithms can be subverted. Then, we give the first digital signature scheme in the complete-subversion model in which all cryptographic algorithms can be subverted. This construction is based on the full-domain hash. Along the way, we enhance the recent result of Russell et al. (CRYPTO 2018) about correcting a subverted random oracle.

2018

CRYPTO

Correcting Subverted Random Oracles
📺
Abstract

The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.

2015

EPRINT

2015

EPRINT

2015

CRYPTO

2015

ASIACRYPT

2014

EUROCRYPT

2014

ASIACRYPT

2013

PKC

2013

ASIACRYPT

2010

EPRINT

Adaptive Concurrent Non-Malleability with Bare Public-Keys
Abstract

Concurrent non-malleability (CNM) is central for cryptographic protocols running concurrently in environments such as the Internet. In this work, we formulate CNM in the bare public-key (BPK) model, and show that round-e±cient concurrent non-malleable cryptography with full adaptive input selection can be established, in general, with bare public-keys (where, in particular, no trusted assumption is made).

2010

EPRINT

A New Framework for RFID Privacy
Abstract

Formal RFID security and privacy frameworks are fundamental to the design and analysis of robust RFID systems. In this paper, we develop a new definitional framework for RFID privacy in a rigorous and precise manner. Our framework is based on a zero-knowledge (ZK) formulation [7, 5] and incorporates the notions of adaptive completeness and mutual authentication. We provide meticulous
justification of the new framework and contrast it with existing ones in the literature. In particular, we prove that our framework is stronger than the ind-privacy model of [14], which answers an open question posed in [14] for developing stronger RFID privacy models. Along the way we also try to clarify certain confusions and rectify several defects in the existing frameworks.
Based on the protocol of [16], we propose an efficient RFID mutual authentication protocol and analyze its security and privacy. The methodology used in our analysis is of independent interest and can be applied to analyze other RFID protocols within the new framework.

2010

EPRINT

Concurrent Knowledge Extraction in the Public-Key Model
Abstract

Knowledge extraction is a fundamental notion, modeling machine possession of values (witnesses) in a computational complexity sense and enabling one to argue about the internal state of a party in a protocol without probing its internal secret state. However, when
transactions are concurrent (e.g., over the Internet) with players possessing public-keys (as is common in cryptography), assuring that entities ``know" what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. Here, we investigate how to formally treat knowledge possession by parties (with registered public-keys) interacting over the Internet. Stated more technically, we look into the relative power of the notion of ``concurrent knowledge-extraction" (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model where statements being proven can be dynamically and adaptively chosen by the prover.
We show the potential vulnerability of man-in-the-middle (MIM) attacks turn out to be a real security threat to existing natural protocols running concurrently in the public-key model, which motivates us to introduce and formalize the notion of CKE, alone with clarification of various subtleties. Then, both generic (based on standard polynomial assumptions), and efficient (employing complexity leveraging in a novel way) implementations for NP are presented for constant-round (in particular, round-optimal) concurrently knowledge-extractable concurrent zero-knowledge (CZK-CKE) arguments in the BPK model. The efficient implementation can be further practically instantiated for specific number-theoretic language.

2009

EPRINT

On the Portability of Generalized Schnorr Proofs
Abstract

The notion of Zero Knowledge Proofs (of knowledge) [ZKP] is central to
cryptography; it provides a set of security properties that proved
indispensable in concrete protocol design. These properties are defined for any given input and also for any auxiliary verifier private state, as they are aimed at any use of the
protocol as a subroutine in a bigger application.
Many times, however, moving the theoretical notion to
practical designs has been quite problematic. This is due to the fact
that the most efficient protocols fail to provide the above ZKP
properties {\em for all} possible inputs and verifier states.
This situation has created various problems to protocol designers who
have often either introduced imperfect protocols with mistakes or with
lack of security arguments, or they have been forced to use much less
efficient protocols in order to achieve the required properties. In
this work we address this issue by introducing the notion of
``protocol portability,'' a property that identifies input and
verifier state distributions under which a protocol becomes a ZKP when
called as a subroutine in a sequential execution of a larger
application. We then concentrate on the very efficient and heavily employed
``Generalized Schnorr Proofs'' (GSP) and identify the portability of
such protocols. We also point to previous protocol weaknesses and
errors that have been made in numerous applications throughout the
years, due to employment of GSP instances while lacking the notion of
portability (primarily in the case of unknown order groups). This
demonstrates that cryptographic application designers who care about
efficiency need to consider our notion carefully.
We provide a compact specification language for GSP protocols that
protocol designers can employ. Our specification language is
consistent with the ad-hoc notation that is currently widely used and it
offers automatic derivation of the proof protocol while dictating
its portability (i.e., the proper initial state and inputs) and
its security guarantees. Thus, our language specifications can be used modularly in
designs and proofs. This assures that the protocol implementation can
indeed be used as a subroutine that is ZKP in its context.
Finally, as a second alternative to designers wishing to use GSPs, we
present a modification of GSP protocols that is unconditionally
portable (i.e., ZKP) and is still quite efficient. Our constructions
are the first such protocols proven secure in the standard model
(while the previously known efficient constructions relied on the
Random Oracle model).

2008

EPRINT

The CCA2-Security of Hybrid Damgård's ElGamal
Abstract

We consider a hybrid version of Damgård's ElGamal public-key
encryption scheme that incorporates the use of a symmetric cipher and a hash function for key-derivation. We prove that under appropriate choice of the hash function this scheme is IND-CCA secure
under the Decisional Diffie-Hellman assumption in the standard model.
Our results can be generalized to universal hash proof systems where our main technical contribution can be viewed as an efficient generic transformation from 1-universal to 2-universal hash proof systems.

2008

EPRINT

A New Randomness Extraction Paradigm for Hybrid Encryption
Abstract

We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as DDH, QR and Paillier. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991s Damgaards ElGamal public-key encryption
scheme under the DDH assumption.

2008

EPRINT

Constructing Variable-Length PRPs and SPRPs from Fixed-Length PRPs
Abstract

We create variable-length pseudorandom permutations (PRPs) and strong PRPs (SPRPs) accepting any input length chosen from the range of b to 2b bits from fixed-length, b-bit PRPs. We utilize the elastic network that underlies the recently introduced concrete design of elastic block ciphers, exploiting it as a network of PRPs. We prove that three and four-round elastic networks are variable-length PRPs and five-round elastic networks are variable-length SPRPs, accepting any input length that is fixed in the range of b to 2b bits, when the round functions are independently chosen fixed-length PRPs on b bits. We also prove that these are the minimum number of rounds required.

2008

EPRINT

Fair Traceable Multi-Group Signatures
Abstract

This paper presents fair traceable multi-group signatures (FTMGS), which have enhanced capabilities, compared to group and traceable signatures, that are important in real world scenarios combining accountability and anonymity. The main goal of the primitive is to allow multiple groups that are managed separately (managers are not even aware of the other ones), yet allowing users (in the spirit of the Identity 2.0 initiative) to manage what they reveal about their identity with respect to these groups by themselves. This new primitive incorporates the following additional features.
- While considering multiple groups it discourages users from sharing their private membership keys through two orthogonal and complementary approaches. In fact, it merges functionality similar to credential systems with anonymous type of signing with revocation.
- The group manager now mainly manages joining procedures, and new entities (called fairness authorities and consisting of various representatives, possibly) are involved in opening and revealing
procedures. In many systems scenario assuring fairness in anonymity revocation is required.
We specify the notion and implement it in the random oracle model.

2007

EPRINT

Group Encryption
Abstract

We present group encryption, a new cryptographic primitive which is
the encryption analogue of a group signature. It possesses similar
verifiability, security and privacy properties, but whereas a group
signature is useful whenever we need to conceal the source (signer)
within a group of legitimate users, a group encryption is useful
whenever we need to conceal a recipient (decryptor) within a group of
legitimate receivers.
We introduce and model the new primitive and present sufficient as
well as necessary conditions for its generic implementation.
We then develop an efficient novel number theoretic construction
for group encryption of discrete logarithms whose complexity is
independent of the group size. To achieve this we construct a
new public-key encryption for discrete logarithms that satisfies
CCA2-key-privacy and CCA2-security in the standard model.
Applications of group encryption include settings where a user wishes to
hide her preferred trusted third party or even
impose a hidden hierarchy of trusted parties, or
settings where verifiable well-formed ciphertexts are kept in a
untrusted storage server that must be prevented from both
learning the content of records as well as analyzing the
identities of their retrievers.

2007

EPRINT

Cryptographic Hardness based on the Decoding of Reed-Solomon Codes
Abstract

We investigate the decoding problem of Reed-Solomon (RS) Codes, also
known as the Polynomial Reconstruction Problem (PR), from a
cryptographic hardness perspective. Namely, we deal with PR instances
with parameter choices for which decoding is not known to be feasibly
solvable and where part of the solution polynomial is the hidden
input. We put forth a natural decisional intractability assumption that
relates to this decoding problem: distinguishing between a single randomly
chosen error-location and a single randomly chosen non-error location for a
given corrupted RS codeword with random noise.
We prove that under this assumption, PR-instances are entirely pseudorandom,
i.e., they are indistinguishable from random vectors over the
underlying finite field. Moreover, under the same assumption we show
that it is hard to extract any partial information related to the
hidden input encoded by the corrupted PR-instance, i.e., PR-instances
hide their message polynomial solution in the semantic security sense.
The above results lay a framework for the exploitation of PR as an
intractability assumption for provable security of cryptographic
primitives. Based on this framework, we present provably secure
cryptographic constructions for (i) a pseudorandom extender, (ii) a
semantically secure version of the Oblivious Polynomial Evaluation
Protocol, and (iii) a stateful cipher with a set of interesting
properties that include: semantic security, forward secrecy,
error-correcting decryption and an array of random self-reducibility
properties with respect to the plaintext choice, key choice and
partial domain choice.

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

ASIACRYPT

2006

EPRINT

Threshold and Proactive Pseudo-Random Permutations
Abstract

We construct a reasonably efficient threshold and proactive pseudo-random permutation (PRP). Our protocol needs only O(1) communication rounds. It tolerates up to (n-1)/2 of n dishonest servers in the semi-honest environment. Many protocols that use PRPs (e.g., a CBC block cipher mode) can now be translated into the distributed setting. Our main technique for constructing invertible threshold PRPs is a distributed Luby-Rackoff construction where both the secret keys *and* the input are shared among the servers. We also present protocols for obliviously computing pseudo-random functions by Naor-Reingold and Dodis-Yampolskiy with shared input and keys.

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.

2006

EPRINT

Copyrighting Public-key Functions and Applications to Black-box Traitor Tracing
Abstract

Copyrighting a function is the process of embedding hard-to-remove
marks in the function's implementation while retaining its original
functionality. Here we consider the above problem in the context of
public-key encryption and we parallel the process of copyrighting a function to the process of designing traitor tracing schemes.
We derive two copyrighted public-key encryption functions for the
$2$-key setting, solving an open question left by earlier work
with respect to copyrighting discrete-logarithm based functions. We then follow a modular design approach and show how to
elevate the $2$-key case to the multi-user setting, employing
collusion secure codes. Our methodology provides a general framework for constructing
public-key traitor tracing schemes that has the interesting property
that the transmission rate remains constant if the plaintext size can be
calibrated to reach an appropriate minimal length.
Achieving a constant rate, i.e., constant expansion in the
size of ciphertexts and keys, is an important open problem
in the area of traitor tracing schemes. Our design shows
how one can solve it for settings that accommodate the
required plaintext calibration (e.g., when a bulk of
symmetric cipher keys can be encrypted in one message).
Our constructions support ``black-box traitor
tracing'', the setting Â where the tracer only accesses
the decryption box in input/output queries/responses. For the first time here we provide a modeling of black-box traitor tracing that takes into account adversarially chosen plaintext distributions, a security notion we call {\em semantic black-box traceability}. In order to facilitate the design of schemes with semantic black-box traceability we introduce as part of our modular design approach a simpler notion called semantic user separability and we show that Â this notion implies semantic black-box traceability. In the multi-user setting our constructions also demonstrate how one can derive public-key traitor tracing by reducing the required ``marking assumption'' of collusion-secure codes to cryptographic hardness assumptions.

2006

EPRINT

Do We Need to Vary the Constants? (Methodological Investigation of Block-Cipher Based Hash Functions)
Abstract

The recent collision attacks on the MD hash function family do not depend
on the constants used in the function, but rather on its structure
(i.e., changing the constants will not affect the differential analysis
based attacks). Thus, is seems that the role of constants in maintaining
security and preventing these attacks is unclear, at best, for this case
and in particular fixing or varying the constants will not matter
for these analyses.
%
In this work we present a methodological investigation into the case
of block-cipher based PGV hash functions family, and investigate the
importance of constants in securing these designs.
%
To this end we consider the
twelve variants of the PGV family that yield secure
hash in the generic ideal cipher case (as was shown by
Black, Rogaway and Shrimpton), but consider them under concrete
instantiation.
%
%
To investigate the role of constant in the key derivation procedure we
just ignore the constants. In this more uniform setting we further
consider a very regular cipher, namely AES modified to have Mixcolumn
also in the last round (which should still be a strong cipher).
%
Analyzing this modified-AES based hashing, we show that with about 16\%
probability we can find collisions with complexity $2^{49}$ (much
smaller than the birthday attack complexity $2^{64}$).
While we do not claim to break the AES based version, this
nevertheless shows that constants in block cipher have an important
role in resisting collision attack (in particular there is a need to
vary the constant). It also shows that (in the symmetric modified
version) merely the concrete AES structure does not guarantee the security of
AES-based hash function (shown secure under the ideal cipher
model). This is undesirable and
non-robust, because this means that even though a
block cipher has complicated structures in its round function and its key
scheduling algorithm, we can not have a confidence about the security
of hash functions based solely on it (note that there are several
block ciphers such as IDEA, 3-key triple DES which do not use any
constants).
%
Given the above methodological findings, we suggest new AES-based hash
function constructions (essentially modified PGV) which can be
generalized to any block cipher. The functions inherit the security
under the ideal cipher model on the one hand, while, on the other
hand, concretely assure in their structure that the weakness exhibited
herein is dealt with.

2005

EPRINT

Group Signatures with Efficient Concurrent Join
Abstract

A group signature is a basic privacy mechanism. The group joining operation
is a critical component of such a scheme. To date all secure
group signature schemes either employed a trusted-party aided join operation
or a complex joining protocol requiring many interactions between the prospective user
and the Group Manager (GM).
In addition no efficient scheme employed a join protocol proven secure against
adversaries that have the capability
to dynamically initiate multiple concurrent join sessions during an attack.
This work presents the first efficient group signature scheme with a simple
Joining protocol that is based on a ``single message and signature response''
interaction between the prospective user and the GM. This single-message and
signature-response
registration paradigm where no other actions are taken, is
the most efficient possible join interaction and was originally alluded to
in 1997 by Camenisch and Stadler, but its efficient instantiation
remained open till now.
The fact that joining has two short communication flows and does not require secure
channels is highly advantageous:
for example, it allows users to easily join by a
proxy (i.e., a security officer of a company can send a file with all
registration requests in his company and get back their certificates
for distribution back to members of the company). It further allows
an easy and non-interactive global system re-keying operation as well
as straightforward treatment of multi-group signatures.
We present a strong security model for group signatures (the first
explicitly taking into account concurrent join attacks) and an efficient
scheme with a single-message and signature-response join protocol.
The present manuscript is a full version containing proofs, minor corrections as well
as a more flexible and efficient protocol construction compared to the proceedings
version.

2004

ASIACRYPT

2004

PKC

2004

EPRINT

Traceable Signatures
Abstract

We present, implement and apply a new privacy primitive that we call
``Traceable Signatures.'' To this end we develop the underlying
mathematical and protocol tools, present the concepts and the underlying
security model, and then realize the scheme and its security proof.
Traceable signatures support an extended set of fairness mechanisms
(mechanisms for anonymity management and revocation) when compared
with the traditional group signature mechanism.
We demonstrate that this extended function is needed for proper
operation and adequate level of privacy in various settings and
applications. For example, the new notion allows (distributed)
tracing of all signatures by a single (misbehaving) party without
opening signatures and revealing identities of any other user in the system.
In contrast, if such tracing is implemented by a state of the art
group signature system, such wide opening of all signatures of a
single user is a (centralized) operation that requires the opening
of {\em all} anonymous signatures and revealing the users associated
with them, an act that violates the privacy of all users.
Our work includes a novel modeling of security in privacy systems
that leads to simulation-based proofs. Security notions
in privacy systems are typically more complex than the traditional
security of cryptographic systems, thus our modeling methodology may
find future applications in other settings.
To allow efficient implementation of our scheme we develop a number of basic tools, zero-knowledge proofs, protocols, and primitives that we use extensively throughout. These novel mechanisms work directly over a group of unknown order, contributing to the efficiency and modularity of our design, and may be of independent interest. The interactive version of our signature scheme yields the notion of ``traceable (anonymous) identification.''

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.

2004

EPRINT

Group Signatures: Provable Security, Efficient Constructions and Anonymity from Trapdoor-Holders
Abstract

To date, a group signature construction which is efficient,
scalable, allows dynamic adversarial joins, and proven secure in a
formal model has not been suggested. In this work we give the first
such construction in the random oracle model.
The demonstration of an efficient construction proven secure in
a formal model that captures all intuitive security properties of a certain
primitive is a basic goal in cryptographic design.
To this end we adapt a formal model for group signatures
capturing all the basic requirements that have been identified as desirable
in the area and we construct an efficient scheme and prove its security.
Our construction is based on the Strong-RSA assumption
(as in the work of Ateniese et al.). In our system, due to
the requirements of provable security in a formal model, we
give novel constructions as well as innovative extensions of
the underlying mathematical requirements and properties.
Our task, in fact, requires the investigation of
some basic number-theoretic techniques for arguing
security over the group of quadratic residues modulo a composite
when its factorization is known. Along the way we
discover that in the basic construction, anonymity
does not depend on factoring-based assumptions, which, in turn, allows
the natural separation of user join management and anonymity
revocation authorities. Anonymity can, in turn, be shown even against
an adversary controlling the join manager.

2004

EPRINT

Elastic Block Ciphers
Abstract

We introduce the new concept of elastic block ciphers, symmetric-key encryption algorithms that (1) for a variable-size input do not expand the plaintext (i.e., do not require plaintext padding) and (2) adjust their computational load proportionally to the size increase. Contrary to stream ciphers, elastic block ciphers maintain the diffusion property and non-synchronicity of traditional block ciphers. Elastic block ciphers are ideal (when combined with encryption modes) for applications where length-preserving encryption is most beneficial, such as protecting variable-length database fields or network packets.
We present a general algorithm for converting a traditional block
cipher, such as AES, to its elastic version, and analyze the security
of the resulting cipher against key recovery attacks. Our approach
allows us to ``stretch'' the supported block size of a block cipher up
to twice the original length, while increasing the computational load
proportionally to the expanded block size. Our approach does not allow
us to use the original cipher as a ``black box'' (i.e., as an
ideal cipher or a pseudorandom permutation as is used in constructing
modes of encryption). Nevertheless, under some reasonable conditions
on the cipher's structure and its key schedule, we reduce certain key
recovery attacks of the elastic version to such attacks on the fixed-size block cipher. This schema and the security reduction enable us to capitalize on secure ciphers and their already established security properties in developing elastic designs. We note that we are not aware of previous ``reduction type'' proofs of security in the area of concrete (i.e., non ``black-box'') block cipher design. Our work puts forth the notion of elasticity in block cipher design.

2004

EPRINT

Elastic AES
Abstract

Recently an algorithmic schema was proposed for converting any existing block cipher into one which excepts variable length inputs with the computational workload increasing in proportion to the block size. The resulting cipher is referred to as an elastic block cipher. The initial work presented immunity to certain key recovery attacks, and left open further analysis of the method and its possible instantiations. In order to provide a concrete example of an elastic block cipher, we design and implement an elastic version of the Advanced Encryption Standard (AES) cipher which accepts all block sizes in the range 128 to 255 bits. To validate the design we perform differential cryptanalysis on elastic AES which confirms that the cipher does not introduce potential differential attacks as a result of a subset of bits being omitted from each round (which is at the heart of the elastic design). We also compare the performance of software implementations of elastic AES and regular AES on variable size inputs, as a step in determining the practicality of the elastic version.

2004

EPRINT

Scalable Public-Key Tracing and Revoking
Abstract

Traitor Tracing Schemes constitute a very useful tool against
piracy in the context of digital content broadcast. In such
multi-recipient encryption schemes, each decryption key is
fingerprinted and when a pirate decoder is discovered, the
authorities can trace the identities of the users that
contributed in its construction (called traitors).
Public-key traitor tracing schemes allow for a multitude of
non-trusted content providers using the same set of keys, which
makes the scheme ``server-side scalable.''
To make such schemes also ``client-side scalable,'' i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations.
Previous work on public-key traitor tracing did not address this
dynamic scenario thoroughly, and there is no efficient scalable public
key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.
To address these issues, we introduce the model of Scalable
Public-Key Traitor Tracing, and present the first construction of such
a scheme. Our model mandates for deterministic traitor tracing and an
unlimited number of efficient Add-user operations and Remove-user operations.
A scalable system achieves an unlimited number of revocations
while retaining high level of efficiency by dividing the run-time of
the system into periods. Each period has a saturation level for the
number of revocations. When a period becomes saturated, an _efficient_ New-period operation is issued by the system server that resets the saturation level.
We present a formal adversarial model for our system taking into
account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.

2004

EPRINT

Cryptanalyzing the Polynomial-Reconstruction based Public-Key System Under Optimal Parameter Choice
Abstract

Recently, Augot and Finiasz presented a coding theoretic public key
cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.

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.

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

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.

1997

EPRINT

Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function
Abstract

We fill a gap in the theory of zero-knowledge protocols by presenting
NP-arguments that achieve negligible error probability and computational
zero-knowledge in four rounds of interaction, assuming only the existence of a
one-way function. This result is optimal in the sense that four rounds and a
one-way function are each individually necessary to achieve a negligible error
zero-knowledge argument for NP.

1996

EPRINT

Proactive RSA
Abstract

We consider a "mobile adversary" which may corrupt all
participants throughout the lifetime of the system in a non-monotonic
fashion (i.e. recoveries are possible) but the adversary is unable to
corrupt too many participants during any short time period.
Schemes resiliant to such adverasry are called proactive.
We present a proactive RSA system in which a threshold of servers
applies the RSA signature (or decryption) function in a distributed manner.
Employing new combinatorial and elementary number theoretic
techniques, our protocol enables the dynamic updating
of the servers (which hold the RSA key distributively);
it is secure even when a linear number of
the servers are corrupted during any time period;
it efficiently "self-maintains" the
security of the function and its
messages (ciphertexts or signatures); and it enables continuous
availability, namely, correct function application using the shared
key is possible at any time.

1992

CRYPTO

1989

EUROCRYPT

#### Program Committees

- Eurocrypt 2018
- PKC 2016
- TCC 2012
- Crypto 2009
- PKC 2008
- Eurocrypt 2008
- PKC 2007
- FSE 2006
- PKC 2006
- Asiacrypt 2006
- FSE 2005
- PKC 2005
- Eurocrypt 2005
- Asiacrypt 2004
- PKC 2004
- Asiacrypt 2003
- PKC 2003
- Crypto 2002 (Program chair)
- PKC 2002
- Asiacrypt 2001
- PKC 2001
- PKC 2000
- Eurocrypt 2000
- Asiacrypt 2000
- Crypto 1999
- Eurocrypt 1998
- Crypto 1998
- Asiacrypt 1996
- Eurocrypt 1995
- Eurocrypt 1994
- Crypto 1994
- Crypto 1991

#### Coauthors

- Aydin Aysu (2)
- Mihir Bellare (4)
- Vicente Benjumea (1)
- Ray Bird (1)
- Carlo Blundo (1)
- Gilles Brassard (2)
- Ernest F. Brickell (1)
- Enrico Buonanno (1)
- Jan Camenisch (2)
- Julien Cathalo (1)
- Donghoon Chang (3)
- Rongmao Chen (3)
- Seung Geol Choi (4)
- Sherman S. M. Chow (1)
- Debra L. Cook (3)
- Ronald Cramer (1)
- Claude Crépeau (1)
- Giovanni Di Crescenzo (1)
- Yi Deng (1)
- Robert H. Deng (1)
- Yvo Desmedt (2)
- Julien Devevey (1)
- Yevgeniy Dodis (7)
- Ariel Elbaz (2)
- Nelly Fazio (1)
- Dengguo Feng (1)
- Yair Frankel (10)
- Matthew K. Franklin (2)
- Zvi Galil (3)
- Juan A. Garay (2)
- Ran Gelles (2)
- Peter Gemmell (2)
- Inder S. Gopal (1)
- Vipul Goyal (1)
- Ege Gulcan (2)
- Stuart Haber (3)
- Helena Handschuh (1)
- Amir Herzberg (3)
- Xinyi Huang (3)
- Russell Impagliazzo (1)
- Markus Jakobsson (5)
- Philippe A. Janson (1)
- Stanislaw Jarecki (1)
- David S. Johnson (2)
- Marc Joye (7)
- Ari Juels (1)
- Ali Juma (1)
- Jonathan Katz (13)
- Angelos D. Keromytis (3)
- Aggelos Kiayias (21)
- Eike Kiltz (3)
- Hugo Krawczyk (1)
- Shay Kutten (2)
- Dong Hoon Lee (2)
- Sangjin Lee (1)
- Kwangsu Lee (2)
- Yingjiu Li (1)
- Benoît Libert (18)
- Dongdai Lin (1)
- Javier Lopez (1)
- Philip D. MacKenzie (5)
- Tal Malkin (11)
- Luke McAven (1)
- Peihan Miao (1)
- Petros Mol (1)
- Refik Molva (1)
- Daisuke Moriyama (2)
- Mridul Nandi (2)
- Moni Naor (2)
- Khoa Nguyen (2)
- Jianting Ning (1)
- Satoshi Obana (2)
- Tatsuaki Okamoto (2)
- Rafail Ostrovsky (5)
- Jong Hwan Park (1)
- Sarvar Patel (1)
- Olivier Pereira (1)
- Thomas Peters (13)
- Christophe Petit (1)
- Krzysztof Pietrzak (3)
- David Pointcheval (1)
- Jean-Jacques Quisquater (1)
- Mariana Raykova (1)
- Alexander Russell (4)
- Reihaneh Safavi-Naini (1)
- Amit Sahai (1)
- Alfredo De Santis (3)
- Patrick Schaumont (2)
- Berry Schoenmakers (1)
- Karn Seth (1)
- Martijn Stam (3)
- François-Xavier Standaert (3)
- Julien P. Stern (1)
- Qiang Tang (4)
- Isamu Teranishi (3)
- Yiannis Tsiounis (8)
- Ugo Vaccaro (1)
- Yevgeniy Vahlis (2)
- Serge Vaudenay (1)
- Ramarathnam Venkatesan (3)
- Bin Wang (2)
- Ying Wang (2)
- Shouhuai Xu (3)
- Aleksandr Yampolskiy (2)
- Guomin Yang (1)
- Andrew Chi-Chih Yao (1)
- Andrew C. Yao (3)
- Adam Young (11)
- Yunlei Zhao (6)
- Yongjun Zhao (1)
- Hong-Sheng Zhou (4)