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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The families of bijective transformations Gn of affine space Kn over general commutative ring K of increasing order with the property of stability will be constructed. Stability means that maximal degree of elements of cyclic subgroup generated by the transformation of degree d is bounded by d. In the case K-Fq these transformations of Kn can be of an exponential order. We introduce large groups formed by quadratic transformations and numerical encryption algorithm protected by secure protocol of Noncommutative Cryptography. The construction of transformations is presented in terms of walks on Double Schubert Graphs.
The article concise introduction to cryptography post-quantum. It explains the basic concepts related to the field. The reason for the development of cryptography is the threat posed by the possibility of building a quantum computer with high computing power. Defined the term "quantum computer". DiVincenzo criteria conditioning the possibility of constructing such a computer are discussed. Several groups of algorithms, which can be considered as resistant to attack by a quantum computer has been discussed.
PL
W artykule dokonano zwięzłego wprowadzenia do kryptografii postkwantowej. Wyjaśniono podstawowe pojęcia związane z tą dziedziną. Przyczyną rozwoju kryptografii postkwantowej jest zagrożenie wynikające z możliwości zbudowania komputera kwantowego dużej mocy. Zdefiniowano pojęcie komputera kwantowego i omówiono kryteria DiVincenzo konstrukcji takiego komputera. Przedstawiono cztery grupy algorytmów uważanych za odporne na ataki przy użyciu komputera kwantowego.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.