## CryptoDB

### Philip D. MacKenzie

#### Publications

**Year**

**Venue**

**Title**

2005

EPRINT

Universally Composable Password-Based Key Exchange
Abstract

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

2005

EPRINT

Resource Fairness and Composability of Cryptographic Protocols
Abstract

We introduce the notion of {\em resource-fair} protocols.
Informally, this property states that if one party learns the
output of the protocol, then so can all other parties, as long as
they expend roughly the same amount of resources. As opposed to
similar previously proposed definitions, our definition follows
the standard simulation paradigm and enjoys strong composability
properties. In particular, our definition is similar to the
security definition in the universal composability (UC) framework,
but works in a model that allows any party to request additional
resources from the environment to deal with dishonest parties that
may prematurely abort.
In this model we specify the ideally fair functionality as
allowing parties to ``invest resources'' in return for outputs,
but in such an event offering all other parties a fair deal. (The
formulation of fair dealings is kept independent of any particular
functionality, by defining it using a ``wrapper.'') Thus, by
relaxing the notion of fairness, we avoid a well-known
impossibility result for fair multi-party computation with
corrupted majority; in particular, our definition admits
constructions that tolerate arbitrary number of corruptions. We
also show that, as in the UC framework, protocols in our framework
may be arbitrarily and concurrently composed.
Turning to constructions, we define a ``commit-prove-fair-open''
functionality and design an efficient resource-fair protocol that
securely realizes it, using a new variant of a cryptographic
primitive known as ``time-lines.'' With (the fairly wrapped
version of) this functionality we show that some of the existing
secure multi-party computation protocols can be easily transformed
into resource-fair protocols while preserving their security.

2004

TCC

2004

EPRINT

Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness
Abstract

We study the problem of constructing secure multi-party computation
(MPC) protocols that are {\em completely fair} --- meaning that either
all the parties learn the output of the function, or nobody does ---
even when a majority of the parties are corrupted. We first propose a
framework for fair multi-party computation, within which we formulate
a definition of secure and fair protocols. The definition follows the
standard simulation paradigm, but is modified to allow the protocol to
depend on the runing time of the adversary. In this way, we avoid a
well-known impossibility result for fair MPC with corrupted majority;
in particular, our definition admits constructions that tolerate up to
$(n-1)$ corruptions, where $n$ is the total number of parties. Next,
we define a ``commit-prove-fair-open'' functionality and construct an
efficient protocol that realizes it, using a new variant of a
cryptographic primitive known as ``time-lines.'' With this
functionality, we show that some of the existing secure MPC protocols
can be easily transformed into fair protocols while preserving their
security.
Putting these results together, we construct efficient, secure MPC
protocols that are completely fair even in the presence of corrupted
majorities. Furthermore, these protocols remain secure when
arbitrarily composed with any protocols, which means, in particular,
that they are concurrently-composable and non-malleable. Finally, as
an example of our results, we show a very efficient protocol that
fairly and securely solves the socialist millionaires' problem.

2004

EPRINT

Efficient and Universally Composable Committed Oblivious Transfer and Applications
Abstract

Committed Oblivious Transfer (COT) is a useful cryptographic primitive
that combines the functionalities of bit commitment and oblivious
transfer. In this paper, we introduce an extended version of COT
(ECOT) which additionally allows proofs of relations among committed
bits, and we construct an efficient protocol that securely realizes an
ECOT functionality in the universal-composability (UC) framework in
the common reference string (CRS) model. Our construction is more
efficient than previous (non-UC) constructions of COT, involving only
a constant number of exponentiations and communication rounds. Using the ECOT functionality as a building block, we construct efficient UC protocols for general two-party and multi-party functionalities (in the CRS model), each gate requiring a constant number of ECOT's.

2003

PKC

2003

EPRINT

Strengthening Zero-Knowledge Protocols using Signatures
Abstract

Recently there has been an interest in zero-knowledge protocols
with stronger properties, such as concurrency, unbounded simulation
soundness, non-malleability, and universal composability.
In this paper, we show a novel technique to convert a large class of
existing honest-verifier zero-knowledge protocols into ones with these
stronger properties in the common reference string model.
More precisely, our technique utilizes a signature scheme
existentially unforgeable against adaptive chosen-message attacks, and
transforms any $\Sigma$-protocol (which is honest-verifier
zero-knowledge) into an unbounded simulation sound concurrent
zero-knowledge protocol. We also introduce $\Omega$-protocols,
a variant of $\Sigma$-protocols for which our technique further
achieves the properties of non-malleability and/or universal
composability.
In addition to its conceptual simplicity, a main advantage of
this new technique over previous ones is that
it avoids the Cook-Levin theorem, which tends to be rather
inefficient. Indeed, our technique allows for very efficient
instantiation based on the security of some efficient
signature schemes and standard number-theoretic assumptions.
For instance, one instantiation of our technique yields a
universally composable zero-knowledge protocol under the
Strong RSA assumption, incurring an overhead of a small
constant number of exponentiations, plus the generation of two
signatures.

2003

EPRINT

On Simulation-Sound Trapdoor Commitments
Abstract

We study the recently introduced notion of a simulation-sound trapdoor
commitment (SSTC) scheme. In this paper, we present a new, simpler
definition for an SSTC scheme that admits more efficient constructions
and can be used in a larger set of applications. Specifically, we
show how to construct SSTC schemes from any one-way functions, and how
to construct very efficient SSTC schemes based on specific
number-theoretic assumptions. We also show how to construct
simulation-sound, non-malleable, and universally-composable
zero-knowledge protocols using SSTC schemes, yielding, for instance,
the most efficient universally-composable zero-knowledge protocols
known. Finally, we explore the relation between SSTC schemes and
non-malleable commitment schemes by presenting a sequence of
implication and separation results, which in particular imply that
SSTC schemes are non-malleable.

2001

EPRINT

On the Security of the SPEKE Password-Authenticated Key Exchange Protocol
Abstract

In the most strict formal definition of security for
password-authenticated key exchange, an adversary can test at most one
password per impersonation attempt. We propose a slightly relaxed
definition which restricts an adversary to testing at most a constant
number of passwords per impersonation attempt. This definition seems
useful, since there is currently a popular password-authenticated key
exchange protocol called SRP that seems resistant to off-line
dictionary attack, yet does allow an adversary to test two passwords
per impersonation attempt. In this paper we prove (in the random
oracle model) that a certain instantiation of the SPEKE protocol that
uses hashed passwords instead of non-hashed passwords is a secure
password-authenticated key exchange protocol (using our relaxed
definition) based on a new assumption, the Decision
Inverted-Additive Diffie-Hellman assumption. Since this is a new
security assumption, we investigate its security and relation to other
assumptions; specifically we prove a lower bound for breaking this new
assumption in the generic model, and we show that the computational
version of this new assumption is equivalent to the Computational
Diffie-Hellman assumption.

2000

EPRINT

Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman
Abstract

When designing password-authenticated key exchange protocols (as
opposed to key exchange protocols authenticated using
cryptographically secure keys), one must not allow any information
to be leaked that would allow verification of the password (a weak
shared key), since an attacker who obtains this information may be
able to run an off-line dictionary attack to determine the
correct password. Of course, it may be extremely difficult to hide
all password information, especially if the attacker may pose as one
of the parties in the key exchange. Nevertheless, we present a new
protocol called PAK which is the first Diffie-Hellman-based
password-authenticated key exchange protocol to provide a formal
proof of security (in the random oracle model) against both passive
and active adversaries. In
addition to the PAK protocol that provides mutual explicit
authentication, we also show a more efficient protocol called PPK that
is provably secure in the implicit-authentication model. We then
extend PAK to a protocol called PAK-X, in which one side (the
client) stores a plaintext version of the password, while the other
side (the server) only stores a verifier for the password. We
formally prove security of PAK-X, even when the server is
compromised. Our formal model for password-authenticated key
exchange is new, and may be of independent interest.

2000

EPRINT

Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions
Abstract

We initiate the investigation of the class of relations
that admit extremely efficient perfect zero knowledge
proofs of knowledge: constant number of rounds, communication
linear in the length of the statement and the witness, and
negligible knowledge error. In its most general incarnation,
our result says that for relations that have a particular
three-move honest-verifier zero-knowledge (HVZK) proof of knowledge,
and which admit a particular three-move HVZK proof of knowledge for
an associated commitment relation, perfect zero knowledge
(against a general verifier) can be achieved essentially for free,
even when proving statements on several instances combined
under under monotone function composition. In addition,
perfect zero-knowledge is achieved with an optimal 4-moves.
Instantiations of our main protocol lead to efficient perfect
ZK proofs of knowledge of discrete logarithms and RSA-roots,
or more generally, $q$-one-way group homomorphisms.
None of our results rely on intractability assumptions.

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.

#### Program Committees

- Eurocrypt 2006
- Crypto 2004
- TCC 2004
- Crypto 2003
- Asiacrypt 2002

#### Coauthors

- Victor Boyko (2)
- Ran Canetti (2)
- Agnes Hui Chan (1)
- Ronald Cramer (2)
- Ivan Damgård (2)
- Yair Frankel (6)
- Juan A. Garay (9)
- Irene Gassko (1)
- Peter Gemmell (3)
- Craig Gentry (1)
- Shai Halevi (2)
- Markus Jakobsson (3)
- Jonathan Katz (2)
- Yehuda Lindell (2)
- Sarvar Patel (3)
- Manoj Prabhakaran (3)
- Zulfikar Ramzan (1)
- Michael K. Reiter (2)
- Thomas Shrimpton (2)
- Ram Swaminathan (1)
- Yiannis Tsiounis (1)
- Ke Yang (11)
- Moti Yung (5)