Criptografia baseada em code VS Lattice com correção de erros
Não sou um especialista em criptografia PQ, mas como entendo o código de correção de erros e a criptografia baseada em treliça, as suposições criptográficas são muito semelhantes. A principal diferença para mim é a natureza do ruído. Em um caso, o ruído é inspirado no "ruído físico", no outro, é mais matemático e considera uma distância mais complexa (distância euclidiana ao invés de distância de Hamming).
Intuitivamente, esse motivo faz sentido porque todos os aplicativos que conheço envolvendo criptografia baseada em rede são mais eficientes do que aqueles baseados em criptografia de correção de erros.
Minha intuição parece correta para você?
Em caso afirmativo, existe um teorema que certifique que todo protocolo criptográfico baseado em uma suposição de código de correção de erros pode ser transformado em um protocolo baseado em rede mais eficiente (ou seja, com o mesmo nível de segurança e baseado em uma suposição de rede mais fraca) ?
Se não, há uma reivindicação mais informal da pesquisa disponível que considera esta questão? Ou simplesmente não faz sentido comparar essas duas famílias de suposições?
Respostas
Em relação ao seu primeiro parágrafo, eu não diria que a principal diferença é o tipo de ruído, porque a criptografia baseada em rede (LBC) usa muitos ruídos diferentes: gaussiano, binário, ternário etc. vs amostragem Gaussiana discreta em Ring learning com erros ). Porém, algo extremamente útil no LBC é que você pode brincar com o módulo$q$do anel$\mathbb{Z}_q$você está trabalhando. Muitos problemas em LBC podem ser resolvidos simplesmente aumentando$q$, o que naturalmente influencia a solidez da suposição subjacente, mas em muitos casos o impacto é administrável.
Por outro lado, na criptografia baseada em código (CBC), na maioria das vezes o módulo é fixado em 2 (ex. BIKE). Quando isso acontece, o módulo é uma ferramenta a menos que o CBC pode aproveitar. Em conjunto com o módulo, a métrica certamente tem influência. Por exemplo, suponha que você adicione$n$vetores$x_i$de dimensão$n$com a mesma norma euclidiana (resp. Peso de Hamming):
- Com a norma euclidiana, você tem$\|\sum_i x_i \| \leq \sum_i \|x_i\|$. Então, se você definir o módulo$q$para ser grande o suficiente, você ainda pode argumentar que a soma é curta, o que é útil tanto para segurança quanto para correção.
- Da mesma forma, com o peso de Hamming w, você tem$w(\sum_i x_i) \leq \sum_i w(x_i)$. Então, se você adicionar$n$vetores de peso de Hamming$1$cada, você não pode dizer nada significativo sobre o peso de Hamming da soma.
Com relação às questões 1, 2, 3, é verdade que os esquemas LBC de última geração são mais eficientes do que seus equivalentes CBC no momento . Mas não há garantia de que isso sempre será verdade porque o CBC existe há mais de 40 anos, então os criptoanalistas tiveram muito tempo para encontrar ataques otimizados. A LBC é muito mais recente (20~ anos). Observe que, quando parametrizadas corretamente, ambas as famílias parecem fornecer dureza exponencial em seus parâmetros:
- Para hemograma completo:$O(2^{0.0885 \cdot n})$onde n é um parâmetro do sistema, consulte este artigo .
- Para LBC:$\tilde{O}(2^{0.295 \cdot B})$onde B é uma bagunça para calcular, mas parece crescer mais ou menos linearmente com os parâmetros do sistema, veja este artigo .
Como você mencionou, as suposições de ambas as famílias são semelhantes (por exemplo, esquemas baseados em QC-MDPC usam suposições que parecem extremamente semelhantes a NTRU e Ring-LWE, consulte o slide 4 desta apresentação ), e a maioria dos esquemas LBC simples tem equivalentes CBC e reciprocamente . Até certo ponto, pode-se até fazer analogias em um nível mais profundo , o que considero conceitualmente satisfatório.
De um modo geral, é verdade que a principal diferença entre as suposições de "criptografia baseada em código" e as suposições "baseadas em treliça" é a distribuição de ruído. É claro que existem exceções, por exemplo, criptosistemas baseados em código usando a métrica de classificação ou LPN binário, onde o ruído pode ser descrito como um pequeno peso de Hamming ou uma pequena distância euclidiana.
Em um caso o ruído é inspirado no "ruído físico", e no outro, é mais matemático e considera uma distância mais complexa (distância euclidiana ao invés de distância hamming).
Não tenho certeza sobre essas analogias de ruído "físico" e "matemático". Ambos os tipos de ruído podem ser modelos matemáticos úteis em diferentes cenários físicos, por exemplo, ruído de baixo peso de Hamming pode modelar bits invertidos durante a transmissão, enquanto o ruído gaussiano pode modelar pequenas perturbações em uma imagem de um sensor ruidoso. De qualquer forma, essas analogias não são realmente relevantes para a criptografia.
existe um teorema que certifica que todo protocolo criptográfico baseado em uma hipótese de código corretor de erros pode ser transformado em um protocolo mais eficiente baseado em rede (ou seja, com o mesmo nível de segurança e baseado em uma hipótese de rede mais fraca)?
Não conheço nenhum teorema geral como esse. Embora os protocolos baseados em rede sejam geralmente mais eficientes, nem sempre é esse o caso e depende muito do aplicativo criptográfico.
Um exemplo natural em que as redes batem os códigos é a troca de chaves. Aqui, protocolos baseados em rede, como Kyber , são muito mais simples e rápidos do que seus análogos baseados em código, como BIKE , em grande parte devido a uma etapa cara de correção de erros na configuração baseada em código, em comparação com técnicas de arredondamento baratas para corrigir erros na rede contexto.
Outro exemplo é o desafio de construir esquemas de criptografia linearmente homomórficos. Isso é bastante direto usando redes, mas ainda é um problema não resolvido de suposições baseadas em código. Há até evidências de que isso é impossível de se conseguir usando técnicas naturais de "aritmética" - veja o artigo de Applebaum, Avron e Brzuska ; este trabalho examina apenas aplicações específicas, mas pode conter os tipos de teoremas nos quais você está interessado.
Por outro lado, há casos em que o ruído de baixo peso de Hamming pode trazer benefícios de eficiência. Um exemplo bastante recente é ao gerar aleatoriedade correlacionada privada (por exemplo, triplos de multiplicação ou transferências aleatórias inconscientes) para uso em protocolos de computação multipartidários seguros. Usando suposições baseadas em código, existem técnicas eficientes para comprimir a aleatoriedade correlacionada em sementes muito mais curtas, que podem ser posteriormente expandidas. Essa técnica de compressão depende crucialmente da distribuição esparsa de ruído, e métodos análogos na configuração da rede são muito mais caros. (Veja, por exemplo, estes trabalhos )