Transitive signature schemes for undirected graphs from lattices

Geontae Noh, Ik Rae Jeong

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


In a transitive signature scheme, a signer wants to authenticate edges in a dynamically growing and transitively closed graph. Using transitive signature schemes it is possible to authenticate an edge (,)ik, if the signer has already authenticated two edges (,)ij and (,)jk. That is, it is possible to make a signature on (,)ik using two signatures on (,)ij and (,)jk. We propose the first transitive signature schemes for undirected graphs from lattices. Our first scheme is provably secure in the random oracle model and our second scheme is provably secure in the standard model.

Original languageEnglish
Pages (from-to)3316-3332
Number of pages17
JournalKSII Transactions on Internet and Information Systems
Issue number6
Publication statusPublished - 2019 Jun 30

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No. 2017R1C1B5076610).

Publisher Copyright:
© 2019 KSII.


  • Lattice-based cryptography
  • Transitive signature
  • Undirected graphs

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this