## CryptoDB

### Hugo Krawczyk

#### Publications

**Year**

**Venue**

**Title**

2021

PKC

On the (In)Security of the Diffie-Hellman Oblivious PRF with Multiplicative Blinding
📺
Abstract

Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns F_k(x) and nothing else while the server learns nothing. OPRF's have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is F_k(x)=H2(x,(H1(x))^k) computed using so-called exponential blinding, i.e., the client sends a=(H1(x))^r for random r, the server responds b=a^k, which the client ublinds as v=b^{1/r} to compute F_k(x)=H2(x,v).
However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation.
We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work.
On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.

2021

CRYPTO

KHAPE: Asymmetric PAKE from Key-Hiding Key Exchange
📺
Abstract

OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the integrity of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is immediately exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise.
In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an unauthenticated Diffie-Hellman exchange. KHAPE uses three messages with explicit client authentication and four with explicit server authentication (one more than OPAQUE in the latter case).
All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of "key-hiding AKE" which KHAPE uses as a main component, and our UC proofs of AKE security for protocols 3DH (a basis of Signal) and HMQV that we use as efficient instantiations of KHAPE.

2021

CRYPTO

You Only Speak Once: Secure MPC with Stateless Ephemeral Roles
📺
Abstract

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages.
We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect.
We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

2020

TCC

Can a Blockchain Keep a Secret?
📺
Abstract

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

2018

PKC

Two-Factor Authentication with End-to-End Password Security
Abstract

We present a secure two-factor authentication (TFA) scheme based on the possession by the user of a password and a crypto-capable device. Security is “end-to-end” in the sense that the attacker can attack all parts of the system, including all communication links and any subset of parties (servers, devices, client terminals), can learn users’ passwords, and perform active and passive attacks, online and offline. In all cases the scheme provides the highest attainable security bounds given the set of compromised components. Our solution builds a TFA scheme using any Device-Enhanced PAKE, defined by Jarecki et al., and any Short Authenticated String (SAS) Message Authentication, defined by Vaudenay. We show an efficient instantiation the modular, generic construction we give is not PAKE-agnostic because it doesn’t even use PAKE, but the instantiation of this scheme which instantiates DE-PAKE with PTR+PAKE is PAKE-agnostic as you say of this modular construction which utilizes any password-based client-server authentication method, with or without reliance on public-key infrastructure. The security of the proposed scheme is proven in a formal model that we formulate as an extension of the traditional PAKE model.We also report on a prototype implementation of our schemes, including TLS-based and PKI-free variants, as well as several instantiations of the SAS mechanism, all demonstrating the practicality of our approach.

2014

ASIACRYPT

2010

EPRINT

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

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

2010

EPRINT

Cryptographic Extraction and Key Derivation: The HKDF Scheme
Abstract

In spite of the central role of key derivation functions (KDF) in applied cryptography, there has been little formal work addressing the design and analysis of general multi-purpose KDFs. In practice, most KDFs (including those widely standardized) follow ad-hoc approaches that treat cryptographic hash functions as perfectly random functions. In this paper we close some gaps between theory and practice by contributing to the study and engineering of KDFs in several ways. We provide detailed rationale for the design of KDFs based on the extract-then-expand approach; we present the first general and rigorous definition of KDFs and their security which we base on the notion of computational extractors; we specify a concrete fully practical KDF based on the HMAC construction; and we provide an analysis of this construction based on the extraction and pseudorandom properties of HMAC. The resultant KDF design can support a large variety of KDF applications under suitable assumptions on the underlying hash function; particular attention and effort is devoted to minimizing these assumptions as much as possible for each usage scenario.
Beyond the theoretical interest in modeling KDFs, this work is intended to address two important and timely needs of cryptographic applications: (i) providing a single hash-based KDF design that can be standardized for use in multiple and diverse applications, and (ii) providing a conservative, yet efficient, design that exercises much care in the way it utilizes a cryptographic hash function.
(The HMAC-based scheme presented here, named HKDF, is being standardized by the IETF.)

2008

EPRINT

Threshold RSA for Dynamic and Ad-Hoc Groups
Abstract

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

2008

EPRINT

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

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

2007

EPRINT

Security under Key-Dependent Inputs
Abstract

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption schemes and in the random oracle model. We extend the investigation to deterministic symmetric schemes (such as PRFs and block ciphers) and to the standard model. We term this notion "security against key-dependent-input attack", or KDI-security for short. Our motivation for studying KDI security is the existence of significant real-world implementations of deterministic encryption (in the context of storage encryption) that actually rely on their building blocks to be KDI secure.
We consider many natural constructions for PRFs, ciphers, tweakable ciphers and randomized encryption, and examine them with respect to their KDI security. We exhibit inherent limitations of this notion and show many natural constructions that fail to be KDI secure in the standard model, including some schemes that have been proven in the random oracle model. On the positive side, we demonstrate examples where some measure of KDI security can be provably achieved (in particular, we show such examples in the standard model).

2006

EPRINT

Deniable Authentication and Key Exchange
Abstract

We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis.
SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first ``natural'' application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model.
SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, ``partial deniability" property: a party may not be able to deny that it was ``alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors.
We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

2005

EPRINT

HMQV: A High-Performance Secure Diffie-Hellman Protocol
Abstract

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying ``the next generation cryptography to protect US government information."
One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV's security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption.
We base the design and proof of HMQV on a new form of ``challenge-response signatures", derived from the Schnorr identification scheme, that have the property that both the challenger and signer can compute the {\em same} signature; the former by having chosen the challenge and the latter by knowing the private signature key.
REVISION: In http://eprint.iacr.org/2005/205, Menezes [32] describes some shortcomings in our analysis that lead to the need for a prime-order verification of public DH values in the protocol. Some of Menezes's claims are correct and some other are not. We keep the originally posted paper here but add a {\em Preface} section (preceding the introduction) that briefly explains these findings and their implications to our results. In essence, the provability of HMQV and its security superiority relative to MQV remain valid; even computation-wise, after adding the verification steps where needed, HMQV is as efficient as (and in some cases even more efficient than) MQV

2004

EPRINT

Secure Hashed Diffie-Hellman over Non-DDH Groups
Abstract

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

2003

CRYPTO

2003

EPRINT

Relaxing Chosen-Ciphertext Security
Abstract

Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security
notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat {\em too strong:} there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure ``for most practical purposes.''
We propose a relaxed variant of CCA security, called {\sf Replayable CCA (RCCA)} security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security.
We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches,
respectively. We show that the three formulations are equivalent in most interesting cases.

2002

EPRINT

Security Analysis of IKE's Signature-based Key-Exchange Protocol
Abstract

We present a security analysis of the Diffie-Hellman
key-exchange protocols authenticated with digital signatures
used by the Internet Key Exchange (IKE) standard, and of the more
comprehensive SIGMA family of key exchange protocols.
The analysis is based on an adaptation of the key-exchange security
model from [Canetti and Krawczyk, Eurocrypt'01] to the setting
where peer identities are not necessarily known or disclosed
from the start of the protocol. This is a common practical setting,
which includes the case of IKE and other protocols that provide
confidentiality of identities over the network. The rigorous study
of this ``post-specified peer" model is a further contribution of
this paper.

2002

EPRINT

Universally Composable Notions of Key Exchange and Secure Channels
Abstract

Recently, Canetti and Krawczyk (Eurocrypt 2001) formulated a notion of
security for key-exchange (KE) protocols, called SK-security, and
showed that this notion suffices for constructing secure channels.
Their model and proofs, however, do not suffice for proving more general
composability properties of SK-secure KE protocols.
We show that while the notion of SK-security is strictly
weaker than a fully-idealized notion of key exchange security, it
is sufficiently robust for providing secure composition with
arbitrary protocols. In particular, SK-security guarantees the security
of the key for any application that desires to set-up secret keys
between pairs of parties. We also provide new definitions of
secure-channels protocols with similarly strong composability properties,
and show that SK-security suffices for obtaining these definitions.
To obtain these results we use the recently proposed framework of
"universally composable (UC) security."
We also use a new tool, called "non-information
oracles," which will probably find applications beyond the present case.
These tools allow us to bridge between seemingly limited
indistinguishability-based definitions such as SK-security and
more powerful, simulation-based definitions, such as UC-security,
where general composition theorems can be proven.
Furthermore, based on such composition theorems we reduce the
analysis of a full-fledged multi-session key-exchange protocol to the
(simpler) analysis of individual, stand-alone,
key-exchange sessions.

2001

CRYPTO

2001

EPRINT

Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels
Abstract

We present a formalism for the analysis of key-exchange protocols
that combines previous definitional approaches and results in a definition
of security that enjoys some important analytical benefits:
(i) any key-exchange protocol that satisfies the security definition
can be composed with symmetric encryption and authentication functions
to provide provably secure communication channels;
and
(ii) the definition allows for simple modular proofs of security:
one can design and prove security of key-exchange protocols in an
idealized model where the communication links are perfectly authenticated,
and then translate them using general tools to obtain security in
the realistic setting of adversary-controlled links.
We exemplify the usability of our results by applying them to obtain the
proof of two main classes of key-exchange protocols, Diffie-Hellman and
key-transport, authenticated via symmetric or asymmetric techniques.
Further contributions of the paper include the formalization of
``secure channels'' in the context of key-exchange protocols, and
establishing sufficient conditions on the symmetric encryption and
authentication functions to realize these channels.

2001

EPRINT

Simple Forward-Secure Signatures From Any Signature Scheme
Abstract

In Crypto'99, Bellare and Miner introduced {\em forward-secure signatures}
as digital signature schemes with the attractive property that exposure
of the signing key at certain time period does not allow for the forgery
of signatures from previous time periods.
That paper presented the first full design of an efficient forward-secure
signatures scheme, but left open the question of building efficient
and practical schemes based on standard signatures such as RSA or DSS.
In particular, they called for the development of schemes where the
main size-parameters (namely, the size of the private key, public key,
and signature) do not grow with the total number of periods for which
the public key is to be in use.
We present an efficient and extremely simple construction of forward-secure
signatures based on {\em any} regular signature scheme (e.g., RSA and DSS);
the resultant signatures enjoy size-parameters that are independent of the
number of periods (except for the inclusion of an index to the period
in which a signature is issued). The only parameter that grows (linearly)
with the number of periods is the total size of local non-secret
memory of the signer. The forward-security of our schemes is directly
implied by the unforgeability property of the underlying signature
scheme and it requires no extra assumptions.
Our approach can also be applied to some signature schemes with special
properties, such as undeniable signatures, to obtain forward-secure
signatures that still enjoy the added special property.

2001

EPRINT

The order of encryption and authentication for protecting communications (Or: how secure is SSL?)
Abstract

We study the question of how to generically compose {\em symmetric}
encryption and authentication when building ``secure channels'' for
the protection of communications over insecure networks.
We show that any secure channels protocol designed to work with any combination
of secure encryption (against chosen plaintext attacks) and secure MAC
must use the encrypt-then-authenticate method.
We demonstrate this by showing that the other common methods
of composing encryption and authentication, including the
authenticate-then-encrypt method used in SSL, are not generically secure.
We show an example of an encryption function
that provides (Shannon's) perfect secrecy but when combined with
any MAC function under the authenticate-then-encrypt method
yields a totally insecure protocol (for example, finding passwords
or credit card numbers transmitted under the protection of such protocol
becomes an easy task for an active attacker).
The same applies to the encrypt-and-authenticate method used in SSH.
On the positive side we show that the authenticate-then-encrypt method
is secure if the encryption method in use is either CBC mode (with
an underlying secure block cipher) or a stream cipher (that xor the
data with a random or pseudorandom pad).
Thus, while we show the generic security of SSL to be broken,
the current standard implementations of the protocol that use
the above modes of encryption are safe.

1999

EPRINT

Public-key cryptography and password protocols
Abstract

We study protocols for strong authentication and key exchange in asymmetric
scenarios where the authentication server possesses a pair of private and
public keys while the client has only a weak human-memorizable password
as its authentication key. We present and analyze several simple password
protocols in this scenario, and show that the security of these protocols
can be formally proven based on standard cryptographic assumptions.
Remarkably, our analysis shows optimal resistance to off-line password
guessing attacks under the choice of suitable public key encryption
functions. In addition to user authentication, we enhance our protocols
to provide two-way authentication, authenticated key exchange, defense
against server's compromise, and user anonymity. We complement these
results with a proof that public key techniques are unavoidable for
password protocols that resist off-line guessing attacks.
As a further contribution, we introduce the notion of public passwords
that enables the use of the above protocols in situations where the
client's machine does not have the means to validate the server's
public key. Public passwords serve as "hand-held certificates" that
the user can carry without the need for special computing devices.

1998

EPRINT

A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols
Abstract

We present a general framework for constructing and analyzing authentication
protocols in realistic models of communication networks. This framework
provides a sound formalization for the authentication problem and suggests
simple and attractive design principles for general authentication and key
exchange protocols. The key element in our approach is a modular treatment of
the authentication problem in cryptographic protocols; this applies to the
definition of security, to the design of the protocols, and to their analysis.
In particular, following this modular approach, we show how to systematically
transform solutions that work in a model of idealized authenticated
communications into solutions that are secure in the realistic setting of
communication channels controlled by an active adversary.
Using these principles we construct and prove the security of simple and
practical authentication and key-exchange protocols. In particular, we provide
a security analysis of some well-known key exchange protocols (e.g.
authenticated Diffie-Hellman key exchange), and of some of the techniques
underlying the design of several authentication protocols that are currently
being deployed on a large scale for the Internet Protocol and other
applications.

1998

EPRINT

Chameleon Hashing and Signatures
Abstract

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

#### Program Committees

- TCC 2016
- PKC 2014 (Program chair)
- Crypto 2012
- TCC 2011
- Asiacrypt 2007
- PKC 2007
- Crypto 2004
- Eurocrypt 2001
- Crypto 1998 (Program chair)
- Crypto 1995

#### Coauthors

- Boaz Barak (1)
- Mihir Bellare (3)
- Fabrice Benhamouda (2)
- John Black (1)
- Ran Canetti (11)
- David Cash (1)
- Don Coppersmith (1)
- Dana Dachman-Soled (1)
- Yevgeniy Dodis (2)
- Sky Faber (1)
- Rosario Gennaro (20)
- Craig Gentry (2)
- Oded Goldreich (3)
- Sergey Gorbunov (1)
- Yanqi Gu (1)
- Shai Halevi (11)
- Johan Håstad (1)
- Amir Herzberg (1)
- Stanislaw Jarecki (15)
- Charanjit S. Jutla (1)
- Jonathan Katz (1)
- Aggelos Kiayias (1)
- Ted Krovetz (1)
- Chengyu Lin (1)
- Michael Luby (1)
- Bernardo Magri (1)
- Tal Malkin (1)
- Yishay Mansour (1)
- Quan Nguyen (1)
- Jesper Buus Nielsen (3)
- Kenneth G. Paterson (1)
- Olivier Pereira (1)
- Krzysztof Pietrzak (1)
- Tal Rabin (22)
- Mario Di Raimondo (1)
- Steffen Reidt (1)
- Leonid Reyzin (1)
- Phillip Rogaway (1)
- Marcel-Catalin Rosu (2)
- Nitesh Saxena (1)
- Maliheh Shirvanian (1)
- François-Xavier Standaert (1)
- Michael Steiner (2)
- Hoeteck Wee (2)
- Stephen D. Wolthusen (1)
- Jiayu Xu (2)
- Sophia Yakoubov (1)
- Yu Yu (1)
- Moti Yung (1)