Non-interactive identity-based DNF signature scheme and its extensions

Kwangsu Lee, Jung Yeon Hwang, Dong Hoon Lee

Research output: Contribution to journalConference articlepeer-review


An ID-based DNF signature scheme is an ID-based signature scheme with an access structure which is expressed as a disjunctive normal form (DNF) with literals of signer identities. ID-based DNF signature schemes are useful to achieve not only signer-privacy but also a multi-user access control. In this paper, we formally define a notion of a (non-interactive) ID-based DNF signature and propose the first non- interactive ID-based DNF signature schemes that are secure under the computational Diffie-Hellman and subgroup decision assumptions. Our first scheme uses random oracles, and our second one is designed without random oracles. To construct the second one, we use a novel technique that converts a non-interactive witness indistinguishable proof system of encryption of one bit into a corresponding proof system of encryption of a bit-string. This technique may be of independent interest. The second scheme straightforwardly yields the first ID-based ring signature that achieves anonymity against full key exposure without random oracles. We finally present two extensions of the proposed ID-based DNF signature schemes to support multiple KGCs and different messages.

Original languageEnglish
Pages (from-to)166-183
Number of pages18
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 2009
Event11th International Conference on Information Security and Cryptology, ICISC 2008 - Seoul, Korea, Republic of
Duration: 2008 Dec 32008 Dec 5

Bibliographical note

Funding Information:
This work was supported by the Second Brain Korea 21 Project.


  • Access structure
  • Disjunctive normal form
  • Identity-based signature
  • Signer anonymity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-interactive identity-based DNF signature scheme and its extensions'. Together they form a unique fingerprint.

Cite this