Nederlands
Menu

Wat is Getaltheoretische transformatie?

Een transformatie die het idee van de snelle fouriertransformatie toepast op gehele getallen modulo een priemgetal. Ze vervangt de vermenigvuldiging van polynomen door een transformatie, een vermenigvuldiging per coëfficiënt en een inverse transformatie, en vermindert zo de ongeveer n² vermenigvuldigingen die bij graad n nodig zijn tot ongeveer n log n. Er zijn alleen exacte berekeningen met gehele getallen nodig, zonder afrondingsfouten. Ze vormt de kern van de berekeningen in op roosters gebaseerde post-kwantumcryptografie zoals ML-KEM en ML-DSA, en er wordt gewerkt aan versnelling met speciale schakelingen.

Japanse benaming: 数論変換

“Getaltheoretische transformatie” komt voor in 1 oefenvragen uit 1 onderwerpen, bijv. Hardwarebeveiliging: nieuwste ontwikkelingen.

Vakgebied: Hardwarebeveiliging: nieuwste ontwikkelingen

Nu oefenen: vragen over Getaltheoretische transformatie

Bij op roosters gebaseerde post-kwantumcryptografie worden vaak polynomen van graad n = 256 met elkaar vermenigvuldigd. Als de naïeve methode, waarbij alle paren coëfficiënten met elkaar worden vermenigvuldigd, ongeveer n² vermenigvuldigingen nodig heeft en de methode met de getaltheoretische transformatie (NTT) ongeveer n log₂ n, welke waarde ligt dan het dichtst bij de factor waarmee de NTT het aantal vermenigvuldigingen vermindert?

  1. AOngeveer 1/8
  2. BOngeveer 1/32
  3. COngeveer 1/256
Antwoord en toelichting tonen

Antwoord: B. Ongeveer 1/32

De naïeve methode heeft n² = 256² = 65.536 vermenigvuldigingen nodig en de methode met de NTT n log₂ n = 256 × 8 = 2048, dus 65.536 ÷ 2048 = 32, een vermindering tot ongeveer 1/32. De getaltheoretische transformatie past het idee van de snelle fouriertransformatie toe op gehele getallen modulo een priemgetal, en na de transformatie is alleen nog een vermenigvuldiging per coëfficiënt nodig. ML-KEM rekent met coëfficiënten modulo q = 3329 en is ontworpen om met de NTT te worden berekend, dus NTT-schakelingen vormen een centraal onderdeel van versnellers voor post-kwantumcryptografie. Daarnaast gebruiken ML-KEM en ML-DSA veel functies uit de SHA-3-familie (SHAKE) om matrices en willekeurige waarden te maken, dus ook versnellers daarvoor zijn effectief.

“Getaltheoretische transformatie” in de toelichting

Vragen met “Getaltheoretische transformatie” (1)

  1. Bij op roosters gebaseerde post-kwantumcryptografie worden vaak polynomen van graad n = 256 met elkaar vermenigvuldigd. Als de naïeve methode, waarbij alle paren coëfficiënten met elkaar worden vermenigvuldigd, ongeveer n² vermenigvuldigingen nodig heeft en de methode met de getaltheoretische transformatie (NTT) ongeveer n log₂ n, welke waarde ligt dan het dichtst bij de factor waarmee de NTT het aantal vermenigvuldigingen vermindert?

Verwante termen

Post-kwantumcryptografie (PQC) Snelle fouriertransformatie (FFT) Modulo-operatie ML-KEM Arm CCA (Confidential Compute Architecture) CHERI Confidential computing Control-flow-integriteit (control-flow integrity) DICE (Device Identifier Composition Engine) FIPS 140-3

Naar de woordenlijst