JEDNOSTKA NAUKOWA KATEGORII A+

Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

Subfield algorithms for ideal- and module-SVP based on the decomposition group

Tom 126 / 2023

Christian Porter, Andrew Mendelsohn, Cong Ling Banach Center Publications 126 (2023), 161-186 MSC: Primary 11H06; Secondary 11H55 DOI: 10.4064/bc126-10

Streszczenie

Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Module-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversary’s benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor can be utilised to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an “easy” instance of SVP. It is important to note that the work on ideal SVP does not break Ring-LWE, since its security reduction is from worst case ideal SVP to average case Ring-LWE, and is one way.

Autorzy

  • Christian PorterDepartment of EEE
    Imperial College London
    London SW7 2AZ
    United Kingdom
    e-mail
  • Andrew MendelsohnDepartment of EEE
    Imperial College London
    London SW7 2AZ
    United Kingdom
    e-mail
  • Cong LingDepartment of EEE
    Imperial College London
    London SW7 2AZ
    United Kingdom
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek