Kompleksitetsteori er den del af datalogien, der beskæftiger sig med hårdheden af algoritmiske problemer, ofte ved hjælp af kompleksitetsklasser som de velkendte P og NP. Der findes tilsvarende kompleksitetsklasser inden for kvantecomputere. Vi arbejder i øjeblikket med kompleksiteten af online-problemer, problemer, hvor input-anmodningerne ankommer sekventielt, og hver skal betjenes med uigenkaldelige beslutninger, før den næste anmodning ankommer. Indtil for nylig arbejdede vi også med kompleksiteten af boolske kredsløb for funktioner relateret til kryptologi. Dette omfattede multiplikativ kompleksitet, antallet af AND-gates, der er nødvendige og tilstrækkelige til at beregne en funktion ved kun at bruge AND-, XOR- og NOT-gates.
Kryptologi involverer design af systemer til kryptering og dekryptering, digitale signaturer, sikre protokoller og mulighederne for at bryde disse systemer og protokoller. Vi har arbejdet meget med zero-knowledge-protokoller. Gruppens nuværende forskning fokuserer på digitale signaturordninger, hvor sikkerhed mod modstandere med (teoretisk) adgang til kvantecomputere overvejes. Derudover har en ph.d.-studerende i gruppen, Simon Erfurth, skrevet en MS-afhandling om sikkerheden af en protokol mod en modstander med (teoretisk) adgang til kvantecomputere.
Kompleksiteteteori og kryptologi
