Sprzętowa akceleracja algorytmu przesiewania kraty

• Autorzy: Andrzejczak Michał , Paszkiewicz Andrzej

Identyfikatory

DOI

10.15199/59.2021.1.3

Warianty tytułu

EN

Hardware acceleration of Lattice Sieving Algorithms

• Języki publikacji: PL

Abstrakty

PL

W artykule podjęto próby akceleracji sprzętowej algorytmu przesiewania kraty – algorytmu Gaussa, wykorzystywanego do rozwiązania problemu najkrótszego wektora w kracie algebraicznej. Użyty algorytm cechuje wykładnicza złożoność pamięciowa. Jest to główna przeszkoda na drodze do efektywnej akceleracji sprzętowej ze względu na ograniczoną dostępność pamięci w układach programowalnych oraz kosztowny czasowo transfer danych pomiędzy układami FPGA a magazynem danych. Rozwiązano problem ograniczonej pamięci oraz spowalniającej transmisji danych przez odpowiednie zmiany w konstrukcji algorytmu, wyspecjalizowaną architekturę akceleratora sprzętowego oraz zastosowanie technik buforowania danych, co zapewniło uzyskanie znacznego przyspieszenia dla wykorzystanego algorytmu.

EN

In this paper we try to accelerate lattice sieving with FPGAs to solve Shortest Vector Problem. Used algorithm has exponential memory requirements and this is the main bottleneck in efficient hardware implementation, due to memory size limitations and communication bandwidth between FPGA and storage. We solve these problems with appropriate changes in algorithm and specialized hardware architecture adopting caching techniques, which lead to achieve significant speed-up for chosen algorithm.

Słowa kluczowe

PL

kryptografia postkwantowa; kryptografia oparta na kratach; najkrótszy wektor w kracie; algorytmy przesiewania kraty; FPGA

EN

post quantum cryptography; lattice based cryptography; shortest vector problem; lattice sieving algorithms; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2021
• Tom: nr 1
• Strony: 20--26
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Andrzejczak Michał

• Wojskowa Akademia Techniczna, Wydział Cybernetyki

autor

Paszkiewicz Andrzej

• Wojskowa Akademia Techniczna, Wydział Cybernetyki

Bibliografia

• [1] Shor P.W. „Algorithms for quantum computation: discrete logarithms and factoring”, Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124-134, 1994.
• [2] Ajtai M., R. Kumar i D. Sivakumar. „A Sieve Algorithm for the Shortest LatticeVector Problem”, Proceedings of the Thirty-Third Annual ACM Symposium on Theory ofComputing - STOC ’01, pp. 601-610, 2001.
• [3] Vidick T., P. Q. Nguyen, „Sieve algorithms for the shortest vector problem are practical”, Journal of Mathematical Cryptology Vol.2: Issue 2, 2008.
• [4] Ishiguro T., S. Kiyomoto, Y. Miyake i T. Takagi, „Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice”, Proceedings of the 17th International Conference on Public-Key Cryptography - PKC 2014 - Volume 8383, pp. 411-428, 2014.
• [5] Yang S.-Y., P.-C. Kuo, B.-Y. Yang i C.-M. Cheng, „Gauss Sieve Algorithm on GPUs”, Topics in Cryptology – CT-RSA 2017, 2017.
• [6] „SVP Challenge,” [Online]. Available: https://www.latticechallenge. org/svp-challenge/.
• [7] „g6k,” [Online]. Available: https://github.com/fplll/g6k.
• [8] Albrecht M., L. Ducas, E. Kirshanovai M.Stevens, The General Sieve Kernel and New Records in Lattice Reduction, Cryptology ePrint Archive, 2019.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).