Czasopismo | PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE | Rocznik 2021 - zeszyt 1

SPRZĘTOWA AKCELERACJA ALGORYTMU PRZESIEWANIA KRATY

Hardware acceleration of Lattice Sieving Algorithms

10.15199/59.2021.1.3

nr katalogowy: 130335
10.15199/59.2021.1.3

Streszczenie

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.

Abstract

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

Keywords

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.

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE- e-publikacja (pdf) z zeszytu 2021-1 , nr katalogowy 130335 licencja: Osobista Produkt cyfrowy Nowość	10.00 zł

Zeszyt


PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE- e-zeszyt (pdf) 2021-1 licencja: Osobista Produkt cyfrowy Nowość	52.00 zł

Prenumerata

PRZEGLĄD TELEKOMUNIKACYJNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

300.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna	348.00 zł brutto 322.22 zł netto 25.78 zł VAT (stawka VAT 8%)
PRZEGLĄD TELEKOMUNIKACYJNY - pakowanie i wysyłka	21.00 zł brutto 17.07 zł netto 3.93 zł VAT (stawka VAT 23%)

369.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	450.00 zł brutto 416.67 zł netto 33.33 zł VAT (stawka VAT 8%)

450.00 zł

Zeszyt

2021-1

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma