International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Stephen Weis (#224)
Name Stephen Weis
Personal Homepage
Topic of his/her doctorate. New Foundations for Efficient Authentication, Commutative Cryptography, and Private Disjointness Testing
Category foundations
Keywords authentication, public-key cryptography
Ph.D. Supervisor(s) Ronald Linn Rivest
Year of completion 2006

This dissertation presents new constructions and security definitions related to three areas: authentication, cascadable and commutative cryptography, and private set operations. Existing works relevant to each of these areas fall into one of two categories: efficient solutions lacking formal proofs of security or provably-secure, but highly inefficient solutions. This work will bridge this gap by presenting new constructions and definitions that are both practical and provably-secure.

The first contribution in the area of efficient authentication is a provably-secure authentication protocol named HB+. The HB+ protocol is efficient enough to be implemented on extremely low-cost devices, or even by a patient human with a coin to flip. The security of HB+ is based on the hardness of a long-standing learning problem that is closely related to coding theory. HB+ is the first authentication protocol that is both practical for low-cost devices, like radio frequency identification (RFID) tags, and provably secure against active adversaries.

The second contribution of this work is a new framework for defining and proving the security of cascadable cryptosystems, specifically commutative cryptosystems. This new framework addresses a gap in existing security definitions that fail to handle cryptosystems where ciphertexts produced by cascadable encryption and decryption operations may contain some message-independent history. Several cryptosystems, including a new, practical commutative cryptosystem, are proven secure under this new framework.

Finally, a new and efficient private disjointness testing construction named HW is offered. Unlike previous constructions, HW is secure in the face of malicious parties, but without the need for random oracles or expensive zero-knowledge protocols. HW is as efficient as previous constructions and may be implemented using standard software libraries. The security of HW is based on a novel use of subgroup assumptions.

These assumptions may prove useful in solving many other private set operation problems.

E-Mail Address sw (at)
Last Change 2011-02-15 10:58:40
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR