Prova de reduções MLWE (e RLWE) para LWE
Em papéis criptográficos, criptoanálise de MLWE / RLWE / etc. é freqüentemente reduzido a LWE. Por que podemos fazer isso? Existe prova estrita de tais reduções?
Respostas
Não há redução conhecida de LWE para MLWE (ou para RLWE). Ou seja, pode ser que o MLWE e o RLWE estejam corrompidos, mas o LWE é seguro.
No entanto, isso parece altamente improvável. Para apoiar a segurança do LWE, temos reduções mostrando que quebrar a dureza do caso médio do LWE requer quebrar a dureza do pior caso de alguns problemas de rede - o que seria (na linguagem de Brakerski et al.) "Estilhaçante" . Agora, reduções semelhantes são válidas para MLWE e RLWE (veja também isto ): ambos podem ser baseados no pior caso de dureza de problemas de rede. A principal diferença é que RLWE requer dureza de pior caso sobre redes ideais, e MWLE requer dureza de pior caso em redes de módulo.
Algumas notas sobre o acima:
- tudo depende fortemente dos parâmetros. As suposições do estilo LWE são fortemente parametrizadas e dizer "redução" não diz muito se não deixarmos explícitos os parâmetros para os quais a redução funciona. As reduções que menciono acima são para a maioria das escolhas padrão de parâmetros (por exemplo, módulo polinomial).
- A dureza de pior caso sobre redes de módulo parece mais plausível do que a dureza de pior caso sobre redes ideais, por uma variedade de razões. No entanto, até alguma perda importante na redução, realmente temos reduções de RLWE para MLWE . Isso ilustra melhor ao mesmo tempo em que ser preciso com as escolhas dos parâmetros é importante ao discutir este tópico.
- A principal razão pela qual os criptógrafos preferem usar MLWE ou RLWE em vez de LWE é porque eles levam a esquemas muito mais eficientes. No entanto, RLWE é parametrizado por algum polinômio e requer suposições de dureza adaptadas a este polinômio muito específico. Isso é um pouco insatisfatório, porque realmente não entendemos bem o impacto da escolha do polinômio na segurança. No entanto, recentemente, um novo problema foi introduzido, o LWE de produto intermediário . Este último nos dá o melhor dos dois mundos: permite essencialmente os mesmos ganhos de eficiência que o RLWE ou MLWE padrão em muitas aplicações (veja o artigo, mas também seus acompanhamentos), embora seja tão seguro quanto o RLWE em relação a qualquer polinômio - portanto, para quebrá-lo, você precisaria quebrar RLWE para cada escolha possível do polinômio. Isso fornece uma base muito satisfatória para a segurança dessa suposição.
Se não me engano, no problema LWE você tem menos estrutura do que no RLWE / MLWE. Se houver menos estrutura, significa que o problema relacionado é mais difícil. Portanto, um ataque contra LWE funcionará também contra RLWE / MLWE. Pelo que eu sei, o interesse dessas variantes é mais sobre eficiência do que segurança.