Wiskundemeisjes

De favoriete (nog levende!) wiskundige van... (23)

Deze keer vragen we aan Ronald Cramer wie zijn favoriete (nog levende!) wiskundige is. Cramer is leider van de onderzoeksgroep Cryptology and Information Security op het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam en hoogleraar Cryptologie aan de Universiteit Leiden. Hij wil geen absolute favoriet aanwijzen, maar wil wel verklappen wie één van zijn favorieten is: Avi Wigderson.

Avi Wigderson

Wigderson werd in 1956 geboren in Haifa en is sinds 1999 hoogleraar discrete wiskunde en theoretische informatica aan de School of Mathematics van het Institute for Advanced Study te Princeton.

Ronald Cramer legt uit hoe de cryptologie sinds de jaren veertig een stormachtige ontwikkeling heeft doorgemaakt, en wat Wigdersons aandeel daarin is.

Cryptologie stond al eeuwenlang bekend als de kunst van het geheimschrift. In de jaren veertig kwam Claude Shannon van MIT met een wiskundige theorie van communicatie. Daarmee werd de basis gelegd voor een wiskundige basis van de cryptologie. De ontwikkeling van de public key cryptologie in de jaren zeventig was de volgende grote stap voorwaarts. Daarmee werd namelijk een oplossing voorgesteld voor de paradox van de geheime geheime-sleuteluitwisseling: voor veel cryptologische systemen heb je een geheime sleutel nodig, maar die moet natuurlijk ook uitgewisseld worden tussen de partijen die met elkaar willen kunnen communiceren. Daarna kwam de digitale handtekening, weer een volstrekt nieuwe toepassing.

Tegenwoordig is cryptologie overal, het wordt bijvoorbeeld veel gebruikt op internet en bij mobiele telefonie. In de nabije toekomst krijgen de huidige technieken (die vooral gebaseerd zijn op RSA) mogelijk grotere concurrentie van elliptische-krommencryptologie, en wie weet zelfs van de quantumcryptologie.

Tot en met de jaren zeventig ging cryptologie vooral over uni-laterale veiligheid: het beveiligen van communicatiekanalen tegen indringers (geheimhouden van de boodschap, of kunnen controleren dat de boodschap echt afkomt van de persoon waarvan je wil dat de boodschap komt): de ``good guys'' beschermen tegen de ``bad guys''. In de jaren tachtig deed de multi-laterale veiligheid zijn intrede. Een voorbeeld hiervan vormen de zogenaamde zero knowledge bewijzen, waarmee je in principe een sceptische partij van de ``waarachtigheid van stellingen kunt overtuigen'' zonder ook maar iets van je bewijzen prijs te geven. Dat is een speciaal geval van secure computation, waarmee partijen die elkaar geen geheime data willen toevertrouwen toch kunnen samenwerken en veilig functies kunnen uitrekenen op die wederzijds geheime data.

Samen met Oded Goldreich en Silvio Micali liet Avi Wigderson in het midden van de jaren tachtig eerst zien dat zero knowledge bewijzen mogelijk waren voor ``alle stellingen die een bewijs toelaten dat efficiënt getoetst kan worden,'' de zogenaamde NP-talen. In een volgende artikel lieten ze zien dat alle functies die efficiënt berekend kunnen worden ook veilig berekend kunnen worden (veilig in de zin van secure computation en onder de aanname dat hooguit een zekere fractie van de partijen samenzweert). Dat verschafte de cryptologie in één klap schitterende nieuwe vergezichten, aangezien heel veel veiligheidsproblemen in principe opgevat kunnen worden als secure computation problemen. Hoewel ze theoretisch efficiënt zijn, zijn hun methoden allerminst praktisch. Er bleef dus veel werk over, en dat is nog altijd in volle gang.

De klap op de vuurpijl kwam in 1988. Shafi Goldwasser, Michael Ben-Or en weer Avi Wigderson lieten toen zien dat die stelling zelfs bewezen kan worden zonder enige aannames op beperkingen op de rekenkracht van mogelijke aanvallers en dus in wezen informatie-theoretisch (of combinatorisch) van aard is, in plaats van complexiteits-theoretisch. Met andere woorden, de stelling geldt ook als er een aanvaller zou komen die efficiënt grote getallen kan factorizeren of die een quantumcomputer heeft. Overigens, deze fundamentele stelling werd tegelijkertijd en onafhankelijk bewezen op het CWI, door David Chaum, Ivan Damgaard en Claude Crépeau.

Cramers eigen onderzoek in de cryptologie is zeer sterk beïnvloed door dit resultaat. In de afgelopen jaren zijn daarbij interessante verbindingen ontstaan tussen informatietheoretisch veilige secure computation aan de ene kant, en combinatoriek, coderingstheorie, algebraïsche meetkunde en algebraïsche getaltheorie aan de andere kant. Cramer heeft daar op het International Congress of Mathematicians (ICM) in Madrid in 2006 zeer genoeglijk met Wigderson over gesproken.

Avi Wigderson werkt nu al drie decennia aan talloze onderwerpen in de combinatoriek, complexiteitstheorie, algoritmen en cryptologie. Wat zijn werk steeds kenmerkt is zijn vermogen tot het leggen van diepe, vruchtbare verbanden tussen problemen uit de theoretische informatica en de zuivere wiskunde. In 1994 werd Wigderson op het ICM in Zürich met de Nevanlinna-prijs onderscheiden vanwege zijn grensoverschrijdende werk. Sindsdien heeft hij allerminst stilgezeten. Cramer vindt zijn recente werk over randomness extractors (samen met Omer Reingold en Salil Vadhan) bijvoorbeeld weer een schitterend resultaat.