International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Moti Yung

Affiliation: Columbia University and Snap Inc., USA

Publications

Year
Venue
Title
2019
PKC
Let a Non-barking Watchdog Bite: Cliptographic Signatures with an Offline Watchdog
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 📺
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.
2016
ASIACRYPT
2016
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
PKC
2015
CRYPTO
2015
ASIACRYPT
2015
CHES
2014
EUROCRYPT
2014
PKC
2014
EPRINT
2014
ASIACRYPT
2014
ASIACRYPT
2013
PKC
2013
CRYPTO
2013
ASIACRYPT
2012
TCC
2012
EUROCRYPT
2012
CRYPTO
2012
PKC
2011
TCC
2011
FSE
2011
EUROCRYPT
2011
ASIACRYPT
2010
TCC
2010
EPRINT
Adaptive Concurrent Non-Malleability with Bare Public-Keys
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
EUROCRYPT
2010
EPRINT
A New Framework for RFID Privacy
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
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
ASIACRYPT
2009
ASIACRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2009
EPRINT
On the Portability of Generalized Schnorr Proofs
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
PKC
2008
EPRINT
The CCA2-Security of Hybrid Damgård's ElGamal
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
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 1991’s Damgaard’s ElGamal public-key encryption scheme under the DDH assumption.
2008
EPRINT
Constructing Variable-Length PRPs and SPRPs from Fixed-Length PRPs
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
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
ASIACRYPT
2007
ASIACRYPT
2007
EUROCRYPT
2007
PKC
2007
JOFC
2007
EPRINT
Group Encryption
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
Aggelos Kiayias Moti Yung
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
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
TCC
2006
TCC
2006
JOFC
2006
EPRINT
Threshold and Proactive Pseudo-Random Permutations
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
PKC
2006
EPRINT
A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks (extended version)
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
Aggelos Kiayias Moti Yung
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)
Donghoon Chang Moti Yung
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
EUROCRYPT
2005
EPRINT
Group Signatures with Efficient Concurrent Join
Aggelos Kiayias Moti Yung
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
EUROCRYPT
2004
EUROCRYPT
2004
PKC
2004
EPRINT
Traceable Signatures
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
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
Aggelos Kiayias Moti Yung
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
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
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
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
Aggelos Kiayias Moti Yung
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.
2004
PKC
2003
CRYPTO
2003
EUROCRYPT
2003
PKC
2003
EPRINT
Scalable Protocols for Authenticated Group Key Exchange
Jonathan Katz Moti Yung
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
ASIACRYPT
2002
ASIACRYPT
Crypto-integrity
Moti Yung
2002
EUROCRYPT
2002
EUROCRYPT
2002
PKC
2002
EPRINT
Key-Insulated Public-Key Cryptosystems
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
CHES
2001
CRYPTO
2001
EUROCRYPT
2001
FSE
2001
PKC
2001
PKC
2001
EPRINT
Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
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
Jonathan Katz Moti Yung
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.
2000
ASIACRYPT
2000
FSE
2000
PKC
2000
PKC
2000
PKC
1999
ASIACRYPT
1999
FSE
1999
PKC
1999
PKC
1998
ASIACRYPT
1998
EUROCRYPT
1998
FSE
1998
PKC
1998
PKC
1998
PKC
1998
JOFC
1997
CRYPTO
1997
CRYPTO
1997
CRYPTO
1997
EUROCRYPT
1997
EUROCRYPT
1997
EUROCRYPT
1997
FSE
1997
EPRINT
Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function
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
ASIACRYPT
1996
CRYPTO
1996
CRYPTO
1996
EUROCRYPT
1996
EPRINT
Proactive RSA
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.
1996
JOFC
1995
CRYPTO
1995
CRYPTO
1995
CRYPTO
1994
EUROCRYPT
1993
EUROCRYPT
1992
CRYPTO
1992
CRYPTO
1992
CRYPTO
1991
CRYPTO
1991
EUROCRYPT
1990
CRYPTO
1990
CRYPTO
1990
CRYPTO
1990
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1987
CRYPTO
1987
CRYPTO
1985
CRYPTO
1984
CRYPTO

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
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)
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)
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)
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 (15)
Dongdai Lin (1)
Javier Lopez (1)
Philip D. MacKenzie (5)
Tal Malkin (11)
Luke McAven (1)
Petros Mol (1)
Refik Molva (1)
Daisuke Moriyama (2)
Mridul Nandi (2)
Moni Naor (2)
Satoshi Obana (2)
Tatsuaki Okamoto (2)
Rafail Ostrovsky (5)
Jong Hwan Park (1)
Olivier Pereira (1)
Thomas Peters (11)
Christophe Petit (1)
Krzysztof Pietrzak (3)
David Pointcheval (1)
Jean-Jacques Quisquater (1)
Alexander Russell (4)
Reihaneh Safavi-Naini (1)
Amit Sahai (1)
Alfredo De Santis (3)
Patrick Schaumont (2)
Berry Schoenmakers (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)
Shouhuai Xu (3)
Aleksandr Yampolskiy (2)
Andrew Chi-Chih Yao (1)
Andrew C. Yao (3)
Adam Young (11)
Yunlei Zhao (6)
Yongjun Zhao (1)
Hong-Sheng Zhou (4)