Menu

Kryptologi og kompleksitetsteori

Effektivitet af kryptografiske systemer og protokoller har været fokus for vores seneste arbejde indenfor kryptologi. Mange kryptografiske protokoller involverer etablering af predikater om en streng X, som kun er til rådighed i såkaldt "committed" form. Dvs. at de enkelte bit i X er indkrypteret enkeltvis ved hjælp af en "bit-commitment" metode, som har nogle standard kryptografiske egenskaber. Et diskret bevis er et ikke-interaktivt kryptografisk bevis for et vilkårligt predikat F over X. Eksempelvis kunne X være en "commitment" til en udbudspris i en udbudsrunde med hemmelige bud. Et interessant predikat i dette scenarie kunne inkludere F(X) = X>100 med den betydning, at buddet er større end 100. Et diskret bevis afslører ingen information om X andet end, hvad der kan deduceres fra F(X) (sand eller falsk). Predikatet F defineres af en verifikationskreds C, som kun består af AND, NOT og XOR komponenter. Længden af disse diskrete beviser er lineær i antallet af AND komponenter i C og påvirkes ikke af antallet af NOT eller XOR komponenter. Denne opdagelse har ført til et studie af den multiplikative kompleksitet af Boolske funktioner. Dvs. det mindste antal binære AND komponenter, der er nødvendige for at konstruere en kreds, som repræsenterer funktionen, når kun XOR, AND og NOT komponenter må bruges.

Dette studie af multiplikativ kompleksitet er ved at blive udvidet til generelle teknikker til at reducere komponentkompleksiteten af kryptografiske funktioner, heriblandt AES.

Meget af dette arbejde er fælles med René Peralta fra National Institute for Standards and Technology (NIST) i USA.

Videnskabelig medarbejder
Joan Boyar

Vi samler statistik ved hjælp af cookies for at forbedre brugeroplevelsen.  Læs mere om cookies

Acceptér cookies