The lattice isomorphism problem and applications to cryptography

Abstract

Como demonstrado por Shor em 1994, computadores quânticos ameaçam a segurança de criptossistemas clássicos, que majoritariamente possuem sua segurança baseada na dificuldade de fatorar inteiros grandes ou computar logaritmos discretos. Tal ameaça incentivou a busca por algoritmos que se mantêm resistentes, mesmo contra ataques realizados por estes computadores quânticos. Um pedaço desta área que se preocupa com estes algoritmos resistentes é nomeado criptografia pós-quântica. Entre todos algoritmos, os baseados em reticulados se destacam por serem particularmente flexíveis e eficientes, dado o reticulado escolhido. O problema LWE é uma ferramenta comum para construção de criptossistemas modernos e se trata da correção de pequenos erros em reticulados ?-ários. Contudo, devido a abordagens heurísticas e algoritmos de redução de base, é previsto que estes reticulados ?-ários implicam em esquemas com grandes reduções em suas expectativas de segurança. Por este motivo, Ducas e van Woerden propõe um novo método onde criptossistemas são construídos em cima do problema de encontrar um isomorfismo entre reticulados, e permite uma maior liberdade na escolha dos reticulados relacionados. Assim, os autores predizem a possibilidade de usar reticulados com propriedades excepcionais e obter criptossistemas com maiores expectativas de segurança do que os demais criptossistemas modernos baseados no problema LWE. Até onde sabemos, não houve qualquer proposta de concretizar um mecanismo de encapsulamento de chaves baseado neste problema de isomorfismo entre reticulados. Este trabalho revisa o estado-da-arte em criptografia baseado em reticulados e os avanços em construir criptossistemas baseados nestes problemas de equivalência. Além disso, o trabalho propõe a primeira instância de um mecanismo de encapsulamento de chaves, seguindo o modelo de Ducas e van Woerden, usando o reticulado de Barnes-Wall. Desta forma, (i) o trabalho propõe uma função derivada de funções de hash universais baseadas no problema SIS para extrair sequências que parecem aleatórias e independentes da entrada; (ii) modifica a representação das chaves para computar seus tamanhos; e (iii) provê uma avaliação rigorosa de segurança, estimando a dificuldade de um atacantes desencapsular a chave compartilhada a partir de reduções para problemas difíceis de reticulados. Finalmente, o mecanismo de encapsulamento proposto é comparado com demais mecanismos modernos baseados em reticulados e submetidos ao processo de padronização do NIST. As estimativas de segurança realizadas partem do princípio que nenhum adversário consegue resolver eficientemente o problema de encontrar o isomorfismo entre reticulados devido a falta de criptoanálise em cima deste problema. Por último, o trabalho resume a presença deste problema na criptografia, e discute ideias futuras para aprimorar tais criptossistemas.

Abstract: As demonstrated by Shor in 1994, quantum computers threaten the security of classical public key cryptosystems, which are based on the hardness of factoring large integers or computing discrete logarithms. Such a threat has fueled the research for algorithms that can withstand attacks by quantum devices; the subset of this research concerned with resistant algorithms is labeled post-quantum cryptography. These algorithms compose post-quantum cryptosystems, each possessing distinct characteristics, such as ciphertext and key sizes, operation timings, and security assumptions. Among those, lattices stand out as being particularly flexible and efficient, depending on the chosen lattice. The LWE problem is commonly used when building modern lattice-based cryptosystems and relates to correcting small errors in ?-ary lattices. However, due to lattice heuristics and the BKZ basis reduction algorithm, it is expected that using these ?-ary lattices may imply in schemes with heavily reduced security strength. Therefore, Ducas and van Woerden propose a new approach where cryptosystems are built based on the lattice isomorphism problem, which allows greater freedom when choosing the underlying lattice. The authors allude to the possibility of using remarkable lattices to obtain schemes with higher security properties than modern LWE cryptosystems. To the best of our knowledge, no attempts have been made to concretely instantiate a key encapsulation mechanism based on the lattice isomorphism problem. We review the state-of-the-art lattice-based cryptography and the advancements in building cryptosystems based on equivalence problems. Furthermore, we propose the first instance of such a mechanism, in accordance with the framework of Ducas and van Woerden, using the Barness-Wall lattice. Additionally, we present a randomness extractor derived from a universal hash function based on the short integer solution problem, modify the representation of the key pairs to properly compute their sizes, and provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems. Finally, we compare our key-encapsulation mechanism with lattice-based cryptosystems submitted to the NIST PQC standardization process. We estimate the resulting security under the assumption that an adversary cannot efficiently solve related instances of the lattice isomorphism problem, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices. Lastly, we summarize the presence of lattice isomorphism in construction secure cryptosystens, and discuss a further idea for improving cryptosystems based on the hardness of finding isomorphism between lattices.