Oded Regev
Mais informações
- Conhecido por
- Learning With Errors (LWE), algoritmo quântico de fatoração de Regev
- Vínculos
- New York University
Cientista da computação israelense cujo problema Learning With Errors virou a base de quase toda a criptografia pós-quântica.
Em um artigo de 2005, Regev formulou o LWE: dado um conjunto de equações lineares módulo algum número, cada uma perturbada por um pequeno erro aleatório, recuperar a solução. Sem os erros, é álgebra de colégio; com eles, ele mostrou, o problema é pelo menos tão difícil quanto problemas de reticulados de pior caso bem estudados – para os quais os computadores quânticos também não têm nenhum truque conhecido. No mesmo artigo, ele construiu um esquema de criptografia em cima disso.
O LWE e suas variantes estruturadas sustentam o ML-KEM e o ML-DSA, padrões do NIST de 2024, além da criptografia totalmente homomórfica. Regev recebeu o Prêmio Gödel em 2018. Em 2023, publicou ainda um algoritmo quântico de fatoração que precisa de menos portas lógicas que o de Shor – uma contribuição rara para os dois lados da mesma corrida armamentista.