Oded Regev
Mer info
- Känd för
- Learning With Errors (LWE), Regevs kvantfaktorisering
- Verksam vid
- New York University
Israelisk datavetare vars problem Learning With Errors blev fundamentet för det mesta av post-kvantkryptografin.
I en artikel från 2005 formulerade Regev LWE: givet ett antal linjära ekvationer modulo ett tal, där varje ekvation fått ett litet slumpfel, hitta lösningen. Utan felen är det skolalgebra; med dem är det, visade han, minst lika svårt som välkända gitterproblem i värsta fall – problem som inte heller kvantdatorer har något känt knep mot. Han konstruerade samtidigt ett krypteringssystem ovanpå.
LWE och dess strukturerade varianter ligger under ML-KEM och ML-DSA, NIST:s standarder från 2024, och under fullt homomorf kryptering. Regev fick Gödelpriset 2018. År 2023 presenterade han dessutom en kvantalgoritm för faktorisering som behöver färre kvantgrindar än Shors – ett sällsynt bidrag till båda sidor av samma kapprustning.