Efficient Implementations of Sieving and Enumeration Algorithms for Lattice-Based Cryptography

Creative Commons License

SATILMIŞ H., Akleylek S., Lee C.

MATHEMATICS, cilt.9, sa.14, 2021 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 9 Sayı: 14
  • Basım Tarihi: 2021
  • Doi Numarası: 10.3390/math9141618
  • Dergi Adı: MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Communication Abstracts, Metadex, zbMATH, Directory of Open Access Journals, Civil Engineering Abstracts
  • Anahtar Kelimeler: lattice-based cryptography, sieving algorithms, efficient software implementations, SVP, IMPROVED PRACTICAL ALGORITHMS, BASIS REDUCTION
  • Ondokuz Mayıs Üniversitesi Adresli: Evet

Özet

The security of lattice-based cryptosystems is based on solving hard lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). Various cryptanalysis algorithms such as (Pro)GaussSieve, HashSieve, ENUM, and BKZ have been proposed to solve these hard problems. Several implementations of these algorithms have been developed. On the other hand, the implementations of these algorithms are expected to be efficient in terms of run time and memory space. In this paper, a modular software package/library containing efficient implementations of GaussSieve, ProGaussSieve, HashSieve, and BKZ algorithms is developed. These implementations are considered efficient in terms of run time. While constructing this software library, some modifications to the algorithms are made to increase the performance. Then, the run times of these implementations are compared with the others. According to the experimental results, the proposed GaussSieve, ProGaussSieve, and HashSieve implementations are at least 70%, 75%, and 49% more efficient than previous ones, respectively.