Comments on a signature scheme based on the third order LFSR proposed at ACISP2001

Seongan Lim, Seungjoo Kim, Ikkwon Yie, Jaemoon Kim

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


In this paper we will compare two signature schemes proposed by different sets of authors. One is the XTR-Nyberg-Rueppel signature proposed by A.K. Lenstra and E.R. Verheul in [3] and the other is the signature scheme proposed by C.H. Tan, X. Yi and C.K. Siew (We will call it TYS signature.) in [9]. XTR-NR signature uses the third degree trace projection Tr: GF(p6) → GF(p2) and has been generalized in [8] by Lim et. al. as a scheme in GF(p6m) using Tr: GF(p6m) → GF(p2m). On the other hand, TYS signature is based on a third order LFSR. Tan et. al. claimed that TYS signature is as secure as Schnorr signature scheme. We will explain why these two schemes are essentially the same. In addition, we will point out that TYS signature as it is has some flaws in their arguments. We will show that in order to cure the flaws of TYS signature, one should bring in exactly the same security and efficiency consideration of XTR scheme as in [8].

Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings
EditorsC. Pandu Rangan, Cunsheng Ding
PublisherSpringer Verlag
Number of pages8
ISBN (Print)9783540453116
Publication statusPublished - 2001
Externally publishedYes
Event2nd International Conference on Cryptology in India, INDOCRYPT 2001 - Chennai, India
Duration: 2001 Dec 162001 Dec 20

Publication series

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


Other2nd International Conference on Cryptology in India, INDOCRYPT 2001


  • Digital signature scheme
  • LFSR
  • Trace projection
  • XTR

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Comments on a signature scheme based on the third order LFSR proposed at ACISP2001'. Together they form a unique fingerprint.

Cite this