Kryptoprotokollat, luento 7 (A), 23.3.2009

• Unohtava tiedonsiirto
• Monen osapuolen salainen laskenta
  yleistä, sovelluksia ja esimerkki. Lisää B-osassa.
• Huutokauppa

Unohtava tiedonsiirto

Ensimmäinen OT-systeemi on Rabinilta vuodelta 1981, ja sitä esitellään Matemaattisen kryptologian kurssilla (vrt. myös em. TTJ-sivu). Seuraavassa esitellään yleisempi OT-toteutus. Todetaan ensin, että sittemmin on kehitetty myös luonnollinen yhdistelmä OT:stä ja bittiin sitoutumisesta: committed (tai: verifiable) oblivious transfer (Crépeau 1990). Siinä lähettäjä A sitoutuu aluksi kahteen bittiin a₀ ja a₁ ja B bittiin b. Protokollan jälkeen B on sitoutunut bittiin a_b eikä tiedä mitään A:n toisesta bitistä. Toisaalta A ei lopussa tiedä mitään bitistä b. Sitoutumisvaiheesta on hyötyä osapuolille siinä, että kumpikin voi olla varma, että toinen on noudattanut OT-protokollaa oikein niille syötteille, jotka tämä ilmoittaa. Tavallisessa OT:ssä tähän tarvitaan jokin erillinen kryptopalikka tai ylemmän tason protokolla.

Tavanomaisella OT:llä on kaksi muotoa, jotka voidaan muuntaa toisikseen. Edellä tuli jo näkyviin se muoto, jossa B valitsee ja saa toisen A:n biteistä tietämättä sitä etukäteen eikä A tiedä kumman B valitsi. Toinen muoto on sellainen, jossa A lähettää bitin ja B saa sen todennäköisyydellä 0,5 ilman, että A tietää kuinka kävi. Yleistyksiä on monenlaisia. Ilmeistä on, että yhden bitin sijalla voi olla bittijono, ja kahden bittijonon tilalla useita, joista B valitsee ja saa yhden (1-out-of-n OT).

Tarkastellaan tapausta "yksi-kahdesta". Olkoon A:lla kaksi viestiä m₁ ja m₂, ja B haluaa niistä toisen. Protokolla voidaan muodostaa RSA:n avulla pimittäen valintoja ja viestejä salauksen avulla toiselta osapuolelta vähän samaan tapaan kuin tehtiin rahanheitossa 6. luennolla. Oleellinen ero on siinä, että julkisen moduulin n tekijät ovat ja pysyvät vain A:n hallussa. Lisäksi A:lla on avainpari eli salaus- ja purkueksponentti kumpaakin viestiä varten: e_i ja d_i, i=1,2.

Aluksi A lähettää moduulin n ja salauseksponentit e₁ ja e₂ B:lle, joka tekee valintansa "b" salaamalla generoimansa satunnaisen AES-avaimen k eksponentilla e_b. Tuloksen B lähettää A:lle, joka ei tiedä kumpaa eksponenttia B käytti, sillä kummallakin purkueksponentilla tulee yhtä satunnaisen näköinen bittijono, joka kelpaa AES-avaimeksi. Nämä purkamiset A tekeekin ja käyttää d_i:llä purettua bittijonoa AES-avaimena salaamaan viestin m_i, i=1,2. Kun B sitten saa näin salatut viestit, hän voi purkaa tarkalleen toisen, m_b:n, eikä A tiedä kumman.

Jos protokolla lopetetaan tähän, A:lla on mahdollisuus huijata salaamalla viestit väärässä järjestyksessä tai molemmilla avaimilla saman viestin. Tämä voidaan torjua, jos jossain myöhemmässä vaiheessa A kertoo purkueksponenttinsa. Tällöin B saa selville molemmat viestit. Tietysti silloinkin on mahdollista, että kumpikaan viesti ei ollut B:n kannalta kiinnostava.

Kuten esim. Helger Lipmaan linkkisivulta näkyy, OT-tutkimus on edelleen vilkasta. Joitakin suuntia siinä ovat -- kuten muissakin protokollissa -- uudentyyppiset modifikaatiot, tehokkuuden kasvattaminen, turvallisuustodistusten vaatimien oletusten heikentäminen. Tavallinen 1-out-of-n OT voidaan esimerkiksi tehdä siten, että tarvitaan vain (keskimäärin) yksi modulaarinen potenssilasku siirtoa kohti. Edellähän tarvittiin kolme. [M.Naor, B.Pinkas: Efficient Oblivious Transfer Protocols. Proc. of SODA 2001]

Monen osapuolen laskenta

Yleistä

Lisäksi halutaan tietenkin, että funktion arvo on oikein, mutta tämä voi olla suhteessa vain siihen, minkä arvon kukin syöttää. Jos esim. osapuolet haluavat laskea keskimääräisen ikänsä tai palkkansa, mikään ei estä(ne) ketään valehtelemasta.

Funktio toimii vähän niinkuin "automaattinen vaaliuurna": syötteenä ovat vaaliliput, ja uurna laskee vaalituloksen näyttämättä lippuja kenellekään. Tarkoituksena siis on, että laskenta voitaisiin suorittaa ilman luotettua osapuolta. Siis senkään vertaa tietoa muuttujista ei saa paljastua, kuin ääntenlaskija saa tietoa vaalilipuista. (Jos siis esim. konjunktio = 0, tiedetään vain, että ainakin yksi muuttuja on 0, ei sitä, kuinka moni.)

Ilmeisiä sovelluksia ovat huutokauppa ja salainen äänestys. Tavanomaisen äänestyksen lisäksi äänillä voi olla muitakin painokertoimia kuin 1 ja joillakin äänestäjillä eritasoisia veto- ja "vasta"-veto-oikeuksia (siis esim. niin että veto ja vasta-veto kumoavat toisensa). Tällaisessa sovelluksessa ei tarvitse huolestua valehtelemisesta, mutta tuloksen oikeellisuus voi olla hyvinkin kriittinen. Joissain äänestyksissä voi olla tärkeää tietää vain tulos (esim. enemmistön mielipide), ei sitä, kuinka suuri osa oli mitäkin mieltä. Esimerkki tällaisesta on uuden työntekijän vaali: kun valinta on tehty, muiden ehdokkaiden saamalla kannatuksella ei ole myönteistä merkitystä.

Protokollan täytyy sietää huijareita. Tyypillinen teoreettinen tulos on sellainen, että laskenta voidaan suorittaa turvallisesti, jos enintään kolmasosa "pelaajista on hyökkääjiä" (eli ovat esim. jonkin ulkopuolisen tahon korruptoimia). Voidaan myös erotella aktiiviset ja passiiviset hyökkääjät. Edelliset sotkevat protokollaa, jälkimmäiset voivat vain vahingoittaa salaisuuden säilymistä.

Seuraavassa mainitaan ensin muutama sovellus. Sitten esitellään yksi klassinen esimerkki vuodelta 1982 artikkelista, jossa koko laskentamalli ensi kertaa keksittiin.

Lisätietoja aihepiiristä löytyy Helger Lipmaan linkkisivulta tai Ueli Maurerin tutkimusryhmän sivulta. Siellä todettiin mm. näin: "MPC protocols tend to be very complicated and weird. It is difficult to understand (and teach) these protocols, and even more difficult to verify and prove their correctness. Simplifying protocols and splitting them up into primitives is hence an important step towards deeper understanding and verifiable security proofs." Toteamusta ei enää (2009) löydy tässä muodossa, joten ehkä tavoitteeseen ei ole kunnolla päästy. Yksi keskeinen ongelma on protokollien yhdistäminen ja siitä on eri taholla tehty laaja tutkimus: Yehuda Lindell: Composition of Secure Multi-Party Protocols. A Comprehensive Study. LNCS 2815. 2003.

Sovelluksia

• Matemaattisia tehtäviä, joita voidaan soveltaa monissa muissa yhteyksissä:
  • Skalaaritulon laskenta: kaksi osapuolta, joista kummallakin salainen vektori.
  • Lineaarisen yhtälöryhmän ratkaisu siten, että kukin osapuoli tuottaa osan yhtälöistä - myös niin, että yhtälöitä tulee enemmän kuin muuttujia, jolloin ratkaisua etsitään pienimmän neliösumman (PNS) mielessä.
  • Vastaavasti voidaan interpoloida tarkasti tai PNS-menetelmällä esim. eri osapuolten antamien (x,y)-pisteiden kautta kulkevaa polynomia (x:t erillisiä).
  • Lineaarinen optimointitehtävä: Pitää maksimoida yhteinen tavoitefunktio, joka on muuttujien lineaarikombinaatio f= g₁x₁+...+g_kx_k, kun osapuolet antavat yksityisiä rajoitteita, jotka ovat muotoa a₁x₁+...+a_kx_k <= a. Tässä siis kertoimet a_i sekä a ovat yhden osapuolen salaisuuksia. Muilla on omansa. Käytännön sovelluksia löytyy talouselämän alueelta yhteishankkeista.
• Tietokantaoperaatioita
  • Yksityinen tiedon nouto eli PIR-ongelma (Private Information Retrieval): tietokannan asiakas haluaa ja saa tietyn tiedon kannasta mutta ei joudu paljastamaan minkä. Jos lisäksi vaaditaan, ettei hän saa muuta kuin juuri sen, palataan unohtavaan tiedosiirtoon.
  • Kysely, jossa suoran noudon sijasta tehdään haku, jossa asiakkaan hakusanankin pitää pysyä salassa. Tätä voidaan soveltaa tarkan tai likimääräisen osuvuuden kautta. Esimerkki tunkeutumisen havainnoinnista: Tietokanta voi sisältää yhteen yritykseen tehtyjen tunkeutumisten tietoja. Kyselijällä voi olla omaan tietojärjestelmään kohdistuneen tuoreen tapauksen piirteitä, joiden perusteella hän voi löytää kannasta tietoja hyökkääjästä.
  • Tiedon louhinta: osapuolilla on salassa pidettävät tietokantansa, mutta niiden muodostamassa kokonaisuudessa haluttaisiin tehdä luokitusta, klusterointia, yhteenvetoja yms. Esimerkki tunkeutumisen havainnoinnista: yritykset haluavat yhdistää tunkeutumistietokantojensa tietoja uusien hyökkäysten tunnistamiseksi.
• Geometrisia
  • Osapuolet haluavat selvittää, leikkaavatko heidän tiedossaan olevat kuviot toisensa (esim. suunnitellut markkina-alueet). Tähän voisi soveltaa esim. bittivektoreiden skalaarituloa (eroaako nollasta).
  • Kuuluuko toisen osapuolen piste toisen monikulmioon. (Artikkelissa puhutaan jälkimmäisen osapuolen täsmäpommituksista, joilta kohdealueella olevat liittolaisen salaiset toiminnot haluavat suojautua!)
  • Yleistys edellisestä: montako toisen osapuolen pistettä sijaitsee toisen osapuolen alueessa?
  • Jos kummallakin osapuolella on joukko omia pisteitä, voidaan kysyä esim.,
    • mitkä ovat kaksi lähinnä toisiaan sijaitsevaa eri osapuolen pistettä.
    • minkä pisteiden kautta piirretty konveksi murtoviiva sisältää kaikki pisteet (tasossa, yleistys useampaan ulottuvuuteen on mahdollinen)
• Tilastollisia analyyseja
  • Nämä muistuttavat yhtäältä em. "matemaattisia" ongelmia, toisaalta tietokantaoperaatiota: Voidaan olla kiinnostuneita osapuolten datajoukkojen välisistä korrelaatioista tai regressiokäyristä.

Vertailuongelma

Oletetaan että A:n syöte on i ja B:n on j, ja kumpikin on väliltä 1..100. Funktiona on vertailu: onko i suurempi kuin j ?

1. A --> B:   E(x,i)
   x on satunnaisluku ja E on tietty funktio, joka sisältää salausta B:n julkisella avaimella. B ei silti saa selville x:ää eikä i:tä.
2. B pystyy E(x,i):n perusteella valitsemaan alkuluvun p ja muodostamaan lukujonon z₁, ..., z₁₀₀ siten, että z_i on kongruentti x:n kanssa modulo p. Tehtyään näin B lähettää:
   B --> A:   z₁,...,z_j, z_j+1+1,..., z₁₀₀+1,   p
3. Harjoitus: Miten A saa selville vertailun tuloksen? Kertooko A sen B:lle?

Tarkennukset:

• E := E(x,i) = K_B(x) - i, missä K_B on B:n julkinen avain.
• z_u = K_B^-1( E +u) modulo p,   u=1,...,100. Tässä p on valittu niin, että se on muutamalla kertaluvulla x:ää pienempi (A on kertonut x:n bittimäärän) ja kaikki z_u:t eroavat toisistaan vähintään kahdella eikä mikään ole 0. (Valitaan uusi p kunnes näin on.)

Huutokauppa

Päivän artikkelissa Design Issues for Electronic Auctions (2005) esitellään huutokaupan perusmallit ja arvioidaan erilaisia rakenteita niiden elektronisoimiseksi. Jotkin kirjallisuudessa esiintyneet rakenteet todetaan tehottomiksi, jotkin turvattomiksi. Vain yhteen protokollaan viitataan kaavojen tarkkuudella (Boyd ym., 2000). Siitä kaivetaan esiin impersonointihyökkäys, jolla viaton osapuoli saadaan näyttämään tarjouksensa kiistäjältä. Muista turvaongelmista artikkeli käsittelee tarkimmin eräänlaista DoS-hyökkäystä, kahdessakin yhteydessä: Huutokaupan voi joissakin protokollissa vesittää joko liian monilla tarjouksilla tai sellaisilla samansuuruisilla tarjouksilla, jotka aiheuttavat uusinnan, koska ovat jäljittämättömiä.

Artikkelin suositukset keskittyvät ryhmäallekirjoituksen käyttämiseen (vrt. id=328), joskin esitys on vain yleisellä tasolla. Artikkelin mukaan turvatavoitteina pidetään yleisesti, että tarjouksia ei voi

• väärentää,
• kiistää eikä
• kytkeä tarjoajaan.
• Lisäksi tuloksen pitäisi olla julkisesti todennettavissa, ja
• järjestelmää ei saa voida sekoittaa sääntöjen vastaisilla toimilla.

• Luottamus:
  • Luotetaan pelkkään yhteen huutokaupan pitäjään. Näin on kaikissa Internet-palveluissa, silti tämä on "vähiten hyväksyttävissä". Toimivaksi ja luotettavaksi osoittautuminen ei kaikissa tapauksissa olekaan mahdollista, mutta jonkinlainen mainejärjestelmä tässä toki auttaa. Artikkeli ei käsittele sellaisia.
  • Tuomarina on luotettu kolmas osapuoli. Hyvä, jos kaikki voivat luottaa siihen.
  • Kynnysluottamus, kun huutokaupan pitäjä on hajautettu usealle palvelimelle, on mahdollinen mutta monimutkainen ja haavoittuva rakenne.
  • Kahden eri tahon hallussa olevan palvelimen riittävän erillinen yhteistyö on rakenne, johon artikkeli suhtautuu myönteisimmin. Se on suosituksenkin taustalla: toisena osapuolena on rekisteröijä, joka muodostaa ryhmäavaimen.
  • Ilman keskitettyä palvelua toimiva eli tavallaan P2P-tyyppinen huutokauppa on "täydellinen" mutta hyvin monimutkainen ratkaisu eikä myöskään sovi jatkuvaan huutokauppaan, jossa ostajien ja mahdollisesti myyjienkin joukko voi muuttua kaupankäynnin kuluessa.
• Anonymiteetti edellyttää käytännössä vähintään kahta palvelinta. Lisäksi rekisteröitymisen ja tarjousten teon vaiheet pitää eriyttää. Jatkuvassa huutokaupassa tämä ei käy, joten artikkeli väittää anonymiteetin murtuvan Wangin & Leungin protokollassa (2004).
• Tarjousten autentikointi: Artikkeli väittää että em. Boydin ym:n protokolla olisi ehkä ainoa, jossa tarjoukset voi autentikoida.
• Hinnan määräytyminen: on mahdollista mutta ei sittenkään kovin käytännöllistä, että tarjoukset on rajoitettu tiettyyn suppeaan joukkoon hintoja.
• Maksuunpano: miten saadaan voittaja maksamaan. Artikkeli väittää, että bittikäteissysteemien yhdistäminen tähän on turhan raskas ratkaisu, kun tavoitteeksi riittää oikeastaan vain kiistämättömyys.