Efficient Nyberg-Rueppel type of NTRU digital signature algorithm

Elverdİ F., Akleylek S., KIRLAR B. B.

Turkish Journal of Mathematics, vol.46, no.1, pp.59-70, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 46 Issue: 1
  • Publication Date: 2022
  • Doi Number: 10.3906/mat-2102-116
  • Journal Name: Turkish Journal of Mathematics
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, MathSciNet, zbMATH, TR DİZİN (ULAKBİM)
  • Page Numbers: pp.59-70
  • Keywords: Digital signature, Message recovery, Ntru, Post-quantum cryptography
  • Süleyman Demirel University Affiliated: Yes


© TÜBİTAKMessage recovery is an important property in Nyberg-Rueppel type digital signature algorithms. However, the security of Nyberg-Rueppel type digital signature algorithms depends on the hard problems which might be vulnerable to quantum attacks. Therefore, quantum resistant Nyberg-Rueppel type digital signature algorithms with message recovery property are needed. Since NTRU-based cryptosystems are one of the best studied quantum-resistant schemes, using traditional NTRU encryption scheme has several advantages on the message recovery property. In this paper, we define Nyberg-Rueppel type of NTRU digital signature algorithm. It is carried out by combining NTRU-based encryption and signature algorithms. In the proposed scheme, efficient message recovery property is achieved with the help of NTRU. Then, we compare the computational cost of our Nyberg-Rueppel type signature scheme with the others in terms of the arithmetic complexity. According to the asymptotic complexity results, the proposed scheme has better arithmetic complexity than Nyberg-Rueppel type schemes. We also discuss the security properties of the proposed scheme by modifying attacks on Nyberg-Rueppel type algorithms and lattice-based algorithms