Studiecirkel i teoretisk datalogi / Reading group in cryptography

The information about the reading group is given below in Swedish. If you only speak English and you are interested, then please contact Douglas Wikström.

See also the information about the official seminars of the Theoretical Computer Science Group, and the Informal PhD Student Seminars.

Vårt fokus i studiecirkeln är att förstå idéer och tekniker inom kryptografin, vilket betyder att ämnet för dagen inte nödvändigtvis är ett enskilt papper eller resultat, även om vi oftast kommer att ha ett eller flera papper som utgångspunkt. Tanken är att varje möte ska ta en till två timmar beroende på ämne.

För att vi skall kunna gå snabbt framåt under mötena förväntas deltagarna förstå vad vi har gått igenom under tidigare möten. En kort beskrivning av vad som avhandlas under varje möte kommer att läggas upp på den här sidan, ofta med länkar till relevant literatur.

Om du är intresserad av att delta kan du kontakta Douglas Wikström.

Höstterminen 2010

Tidigare Terminer

Vårterminen 2009

Måndag 12 januari, kl 13:15, Rum 1537: Bevisbart säkra mixnät, Del 1. (Douglas Wikström)

Jag kommer först att berätta vad mixnät är och vilka de naturliga säkerhetskraven är. Sedan kommer jag beskriva några olika mix-nät översiktligt för att sedan fokusera på det konkreta exempel som jag har implementerat. Planen är att under resten av tiden och följande tillfällen gå igenom alla delprotokoll som behövs, vilka krav man bör ställa på dessa, och hur de interagerar i praktiken och bevistekniskt.

Tisdag 20 januari, kl 10:00, Rum 4523: Bevisbart säkra mixnät, Del 2. (Douglas Wikström)

Jag kommer att kortfattat repetera förra tillfällets innehåll och göra klart gemensam robust dekryptering. Sen kommer jag gå igenom problemet med formbara kryptotexter i inskicksfasen och hur det kan lösas. Slutligen går jag igenom Pedersen verifiable secret sharing och distribuerad slantsingling.

Tisdag 27 januari, kl 10:00, Nadabiblioteket: Bevisbart säkra mixnät, Del 3. (Douglas Wikström)

Jag skissar ett så kallat "proof of a shuffle" som visar att en mix-server gör vad den ska.

Måndag 2 februari, kl 15:15, Rum 1537: RSA-baserat nyckelutbyte, OAEP, RSA-KEM. (Gustaf Dellkrantz)

Tisdag 10 februari, kl 10:15, Rum 1635: Broadcastkryptering. (Gunnar Kreitz)

Jag tänkte prata lite om broadcast-kryptering. Tanken är att jag börjar med det klassiska, symmetriska problemet och skissar upp någon enkel lösning [1 eller 2]. Sen kommer det definition av säkerhet och bevis(skiss) för att en egenskap som kallas "key indistinguishability" implicerar säkerhet enligt den givna definitionen [1].

Sannolikt hinner och orkar vi sedan fortsätta in på lite nyare jaktmarker och tittar på ett system som utnyttjar bilinjära avbildningar [3] och kanske till och med ett med multilinjära avbildningar [4].

Referenser: [1], [2], [3], [4].

Tisdag 17 februari, kl 10:15, Rum 1635: Pseudoslumpgeneratorer säkra mot kretsar med litet djup. (Per Austrin)

Per ändrade lite i sin ämnesbeskrivning. Jag kommer prata om bevisbart bra pseudoslumpgeneratorer mot kretsar av litet djup, specifikt följande fråga: vad är den minsta mängd oberoende som garanterat är tillräcklig för att en fördelning ska vara en bra pseudoslumpfördelning mot kretsar av djup d? En klassisk förmodan av Linial och Nisan från 1990 gör gällande att en polylogaritmisk mängd oberoende är tillräcklig. Denna förmodan bevisades nyligen i ett vackert resultat av Braverman [1], byggandes på framsteg förra året av Bazzi [2] och Razborov [3].

Referenser: [1], [2], [3]

Gammal innehållsbeskrivning. Jag kommer prata om bevisbart bra pseudoslumpgeneratorer mot polynom av låg grad. Det bygger på en serie papper [1,2,3] som nyligen (2007) publicerats, och som kulminerade i ett resultat av Viola [3]. Konstruktionerna bygger på en klassisk konstruktion av Naor & Naor från 1990 mot linjära funktioner [4], och jag tänkte också gå igenom denna.

Referenser: [1] [2] [3] [4]

Måndag 23 februari, kl 15:15, Rum 1635: Cramer och Shoup's CCA2-säkra kryptosystem. (Björn Terelius)

Jag tänkte definiera CCA2 (adaptive chosen ciphertext attack) och sedan prata om Cramer's och Shoup's kryptosystem [1] och beviset för att det är CCA2-säkert. Eventuellt fortsätter vi sedan med att skissa mer generella konstruktioner [2] av CCA2-säkra kryptosystem.

Referenser: [1] [2]

Tisdag 7 april, kl 10:15, Rum 1537: Verifiering av säkerhetsprotokoll med Pi-calculus och ProVerif (Karl Palmskog)

Jag kommer att ge en överblick av hur man inom formella metoder använder applied pi-calculus [1], en formalism för att uttrycka och resonera algebraiskt om parallella processer, för att bevisa önskvärda egenskaper hos säkerhetsprotokoll. Specifikt kommer jag att gå igenom syntax och semantik för applied pi-calculus och en modell i formalismen av protokollet encrypted key exchange [2]. Avslutningsvis kommer jag att ge en skiss på hur den automatiska verifieringen av sådana protokoll går till i verktyget ProVerif [3].

Referenser: [1] [2] [3]