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

Hami Satılmış, Sedat Akleylek and Cheng-Chi Lee
Additional contact information
Hami Satılmış: Department of Computer Engineering, Ondokuz Mayıs University, Samsun 55200, Turkey
Sedat Akleylek: Department of Computer Engineering, Ondokuz Mayıs University, Samsun 55200, Turkey
Cheng-Chi Lee: Department of Library and Information Science, Research and Development Center for Physical Education, Health, and Information Technology, Fu Jen Catholic University, New Taipei City 242, Taiwan

Mathematics, 2021, vol. 9, issue 14, 1-19

Abstract: 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.

Keywords: lattice-based cryptography; sieving algorithms; efficient software implementations; SVP (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/14/1618/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/14/1618/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:14:p:1618-:d:591055

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().