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)


Michael de Mare (#497)
Name Michael de Mare
Personal Homepage
Topic of his/her doctorate. Secure Set Membership Using 3SAT
Category foundations
Ph.D. Supervisor(s) Rebecca Wright
Year of completion 2010

In this thesis, we develop a cryptographic primitive: a solution to the secure set membership problem. The secure set membership problem is the problem of creating a set representation so that it is possible to verify that a string is a member of the set without being able to learn members of the set from the representation. The secure set membership primitive includes a distributed protocol for set establishment and a proof-of-possession protocol to show set membership without revealing the member of the set.

We use a subset of the instances of the \thSAT\ witness-finding problem in developing a new complexity assumption for the secure set membership primitive. It is risky to base cryptosystems on \NP-c omplete problems, as what is hard in the worst case may be easy in most cases. To mitig ate this risk, we limit the instances of \thSAT\ that we generate to try to select only hard instances; our complexity assumption is different than mere \NP-completeness.

We assume that \thSAT\ instances with certain parameters are difficult to find witnesses for. We back up this assumption with experiments using the MiniSAT \SAT\ solver as well as our own software. We use these experiments to determine which parameters are most likely to yield a secure system.

We suggest applications of secure set membership including anonymous digital credentials, accounts with multiple users, access control lists, and document timestamping. We include both centralized and distributed protocols for establishing the set, and both pseudonomynous and anonymous protocols for verifying that a user possesses a witness that is a member of the set.

Last Change 2011-04-22 14:57:06
To provide an update on this entry, please click .

Contact: phds (at)

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