Secure set membership using 3Sat

Michael de Mare, Rebecca N. Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


A wide variety of powerful cryptographic tools have been built using RSA, Diffie-Hellman, and other similar assumptions as their basis. Computational security has been achieved relative to complexity assumptions about the computational difficulty of a variety of number theoretic problems. However, these problems are closely related, and it is likely that if any one of them turns out to be efficiently solvable with new mathematical advances or new kinds of computational devices, then similar techniques could be applicable to all of them. To provide greater diversity of security assumptions so that a break of one of them is less likely to yield a break of many or all of them, it is important to expand the body of computational problems on which security systems are based. Specifically, we suggest the use of hardness assumptions based on the complexity of logic problems, and in particular, we consider the well known Boolean 3Sat problem. In this paper, we consider the use of the 3Sat problem to provide a cryptographic primitive, secure set membership. Secure set membership is a general problem for participants holding set elements to generate a representation of their set that can then be used to prove knowledge of set elements to others. Set membership protocols can be used, for example, for authentication problems such as digital credentials and some signature problems such as timestamping.

Original languageEnglish (US)
Title of host publicationInformation and Communications Security - 8th International Conference, ICICS 2006, Proceedings
EditorsPeng Ning, Sihan Qing, Ninghui Li
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783540494966
StatePublished - 2006
Externally publishedYes
Event8th International Conference on Information and Communications Security, ICICS 2006 - Raleigh, United States
Duration: Dec 4 2006Dec 7 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4307 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Conference on Information and Communications Security, ICICS 2006
CountryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Secure set membership using 3Sat'. Together they form a unique fingerprint.

Cite this