Cryptology in the Crowd

Abstract

Uhell skjer: Kanskje mistet du nøkkelen til huset, eller hadde PIN-koden til innbruddsalarmen skrevet på en dårlig plassert post-it lapp. Og kanskje endte de slik opp i hendene på feil person, som nå kan påføre livet ditt all slags ugagn: Sikkerhetssystemer gir ingen garantier når nøkler blir stjålet og PIN-koder lekket. Likevel burde naboen din, hvis nøkkel-og-PIN-kode rutiner er heller vanntette, kunne føle seg trygg i vissheten om at selv om du ikke evner å sikre huset ditt mot innbrudd, så forblir deres hjem trygt.

Det er tilsvarende for kryptologi, som også lener seg på at nøkkelmateriale hemmeligholdes for å kunne garantere sikkerhet: Intuitivt forventer man at kjennskap til ett systems hemmelige nøkkel ikke burde være til hjelp for å bryte inn i andre, urelaterte systemer. Men det har vist seg overraskende vanskelig å sette denne intuisjonen på formell grunn, og flere konkurrerende sikkerhetsmodeller av varierende styrke har oppstått. Det blir dermed naturlig å spørre seg: Hvilken formalisme er den riktige når man skal modellere realistiske scenarioer med mange brukere og mulige lekkasjer? Eller: hvordan bygger man kryptografi i en folkemengde?

Artikkel I begir seg ut på reisen mot et svar ved å sammenligne forskjellige flerbrukervarianter av sikkerhetsmodellen IND-CCA, med og uten evnen til å motta hemmelige nøkler tilhørende andre brukere. Vi finner et delvis svar ved å vise at uten denne evnen, så er noen modeller faktisk å foretrekke over andre. Med denne evnen, derimot, forblir situasjonen uavklart.

Artikkel II tar et sidesteg til et sett relaterte sikkerhetsmodeller hvor, heller enn å angripe én enkelt bruker (ut fra en mengde av mulige ofre), angriperen ønsker å bryte kryptografien til så mange brukere som mulig på én gang. Man ser for seg en uvanlig mektig motstander, for eksempel en statssponset aktør, som ikke har problemer med å bryte kryptografien til en enkelt bruker: Målet skifter dermed fra å garantere trygghet for alle brukerne, til å gjøre masseovervåking så vanskelig som mulig, slik at det store flertall av brukere kan forbli sikret.

Artikkel III fortsetter der Artikkel I slapp ved å sammenligne og systematisere de samme IND-CCA sikkerhetsmodellene med en større mengde med sikkerhetsmodeller, med det til felles at de alle modellerer det samme (eller lignende) scenarioet. Disse modellene, som går under navnene SOA (Selective Opening Attacks; utvalgte åpningsangrep) og NCE (Non-Committing Encryption; ikke-bindende kryptering), er ofte vesentlig sterkere enn modellene studert i Artikkel I. Med et system på plass er vi i stand til å identifisere en rekke hull i litteraturen; og dog vi tetter noen, etterlater vi mange som åpne problemer.

Accidents happen: you may misplace the key to your home, or maybe the PIN to your home security system was written on an ill-placed post-it note. And so they end up in the hands of a bad actor, who is then granted the power to wreak all kinds of havoc in your life: the security of your home grants no guarantees when keys are stolen and PINs are leaked. Nonetheless your neighbour, whose key-and-pin routines leave comparatively little to be desired, should feel safe that just because you can’t keep your house safe from intruders, their home remains secured.

It is likewise with cryptography, whose security also relies on the secrecy of key material: intuitively, the ability to recover the secret keys of other users should not help an adversary break into an uncompromised system. Yet formalizing this intuition has turned out tricky, with several competing notions of security of varying strength. This begs the question: when modelling a real-world scenario with many users, some of which may be compromised, which formalization is the right one? Or: how do we build cryptology in a crowd?

Paper I embarks on the quest to answer the above questions by studying how various notions of multi-user IND-CCA compare to each other, with and without the ability to adaptively compromise users. We partly answer the question by showing that, without compromise, some notions of security really are preferable over others. Still, the situation is left largely open when compromise is accounted for.

Paper II takes a detour to a related set of security notions in which, rather than attacking a single user, an adversary seeks to break the security of many. One imagines an unusually powerful adversary, for example a state-sponsored actor, for whom brute-forcing a single system is not a problem. Our goal then shifts from securing every user to making mass surveillance as difficult as possible, so that the vast majority of uncompromised users can remain secure.

Paper III picks up where Paper I left off by comparing and systemizing the same security notions with a wider array of security notions that aim to capture the same (or similar) scenarios. These notions appear under the names of Selective Opening Attacks (SOA) and Non-Committing Encryption (NCE), and are typically significantly stronger than the notions of IND-CCA studied in Paper I. With a system in place, we identify and highlight a number of gaps, some of which we close, and many of which are posed as open problems.