Kryptoprotokollat, luento 7 (B) 2.4.2008

Unohtava tiedonsiirto (jatkoa A-osaan)
Monen osapuolen laskenta
- Miljonäärit
- Yhteys salaisuuden jakamiseen
- Yhteen- ja kertolaskua, kaksi artikkelisivua

Osa luennosta perustuu vahvasti kahteen artikkeliin, joita tässä tekstissä käsitellään vain asettamalla joitakin tehtäviä, joita luennolla tai itse lukiessa voi tarkastella.

Unohtava tiedonsiirto

Tehtävät

M. Naor, B. Pinkas: Efficient Oblivious Transfer Protocols.

Mainitaanko artikkelissa A-osan luennossa esillä ollut OT-protokolla?
Millainen motivaatio esitetään sille, että OT-ajoja voi samojen osapuolten välillä olla useita ja miten uudet protokollat "selviytyvät" tällaisessa tilanteessa? Huomaa luvun 3 lopussa oleva esimerkki.
Esitä määritelmät käsitteille (a) lähettäjän ja (b) vastaanottajan turvallisuus (x) laskennallisesti ja (y) informaatioteoreettisesti. Mikä on satunnaisoraakkelimallin merkitys tässä?
Laadi artikkelin esittämistä protokollista taulukko, jossa vertaat keskeisiä ominaisuuksia.
Esitä protokolla 3.1 ja perustelu sille, miksi se toimii ja mihin sen turvallisuus perustuu.

Monen osapuolen laskenta

Tässä tarkastellaan ensin artikkelin pohjalta uudenlaista ratkaisua vertailuongelmaan. Sitten verrataan monen osapuolen laskentaa salaisuuden jakamiseen. Lopuksi esitellään varsin yksinkertainen mutta silti melko yleinen protokolla yhteen- ja kertolaskujen suorittamiseksi.

Miljonäärien probleema, toisenlainen ratkaisu

Tehtävät

Ioannis Ioannidis, Ananth Grama: An Efficient Protocol for Yao's Millionaires' Problem.

Artikkelissa sanotaan, että Yaon protokollalla on eksponentiaalinen kompleksisuus. Mitä tämä tarkoittaa ja miten se näkyy protokollassa, joka oli esillä A-osassa?
Mikä on protokollan tavoite ja turvallisuusvaatimus?
Kirjoita protokolla auki algoritmin tapaan.
Esitä tiivistäen miksi se toimii ja mihin turvallisuus perustuu.

Vastauksia varten artikkeliin täytyy tehdä pari täsmennystä luvussa 3:

vaiheessa 1 matriisi A pitää alustaa nollaksi.
vaiheessa 2a joka rivillä satunnaisosuuden pitää olla sama molemmissa sarakkeissa.
vaiheissa 2b ja 3 syötebittijonot a ja b pitää indeksoida LSB:stä alkaen. (LSB:n indeksi näillä on siis 1 ja MSB:n indeksinä d.)

Näitä asioita voi havainnollistaa Excel-taululla. Jokin korjaus/täsmennys artikkelin tulkintaan (ehkä nimenomaan havainnollistukseen) silti vielä tarvitaan, jotta tilanne a=b ratkeaisi oikein. Artikkelin väittämää c-bittijonon vasemman päädyn 11-paria ei tauluun muodostu.

Miljonäärin probleema on skalaarin vertailua. Yksi yleistys sille on kahden vektorin vertailu: ovatko kaikki komponentit toisessa pienempiä kuin toisessa. Tätä ei voi suoraan ratkaista eo. protokollalla komponenteittain, jos niiden suuruusjärjestys ei saa paljastua muulloin kuin kysytyssä tapauksessa. Yhtä protokollaa tähän ehdottaa M.H.Ibrahim artikkelissaan Two-Party Private Vector Dominance: The All-Or-Nothing Deal.

Yhteys salaisuuden jakamiseen

TTJ:ssä (id=330) oli esillä (k,n)-kynnyskaavio, jossa n:ään osaan jaetun salaisuuden selvittäminen tapahtuu minkä tahansa k:n jako-osan perusteella. Jos jako-osien k omistajaa ryhtyvät laskemaan ja poissaolijoiden argumentit ajatellaan vaikka nolliksi, tilanne muistuttaa monen osapuolen laskentaa. Erona on se, että salaisuutta purettaessa argumentteja ei tarvitse pitää salassa, ja funktiolla on vain kaksi arvoa: salaisuus aukeaa tai sitten ei. Kaiken lisäksi salaisuus on alunperin jo ollut jonkin luotetun osapuolen tiedossa.

Salaisen laskennan ja salaisuuden jakamisen välillä on syvempikin yhteys. Yleisempiä laskentaprotokollia varten tarvitaan salaisuuden jakamista. Täydennetään tätä varten aiempaa tietoa hieman.

Salaisuuden jakaminen (halkominen) on mahdollista yleisemmälläkin yhteenlaskulla kuin tutulla XOR-operaatiolla, joka on yhteenlaskua modulo 2. Mikä tahansa äärellinen ryhmä G kelpaa tähän tarkoitukseen. Jos salaisuus pitää pilkkoa n osaan valitaan n-1 satunnaista G:n alkiota. Kun ne vähennetään s:stä saadaan n:s osa. Mitkään alle n osaa eivät kerro s:stä mitään, mutta kaikkien n:n osan summa on s.

TTJ:ssä oli esillä kaksi erityistä menetelmää (k,n)-kaavioiden muodostamiseen (lineaarialgebra ja polynomit). Yksi helppo keino saada aikaan (2,n)-kaavio on antaa kullekin n:stä osapuolesta muut paitsi yksi osa n:ään osaan halkaistusta salaisuudesta. Esimerkiksi (2,3)-kaavio saadaan jos s=s₁+s₂+s₃ ja kukin osapuoli i (i=1,2,3) tietää muut osat paitsi s_i:n.

Yhteen- ja kertolaskua

Tässä jaksossa käsitellään esimerkin kautta kolmen osapuolen välinen protokolla, joka säilyttää osapuolten salaisuudet (peräti informaatioteoreettisessa mielessä), kunhan aktiivisia hyökkääjiä ei ole eivätkä mitkään kaksi osapuolta lyöttäydy yhteen kolmannen tietojen paljastamiseksi. Idean voi melko suoraan yleistää useampaan osapuoleen. Silloin kullekin osapuolelle pitää jakaa useampia (saman) salaisuuden osia ja turvallisuuden yleiseksi ehdoksi tulee, että alle puolet osallistujista saavat olla mukana passiivisessa salaliitossa. Yleinen teoria löytyy artikkelista U.Maurer: Secure Multi-Party Computation Made Simple.

Olkoot osapuolina A=1, B=2, C=3. Kirjain i indeksoi osapuolia ja se pyörähtää 3:n jälkeen takaisin 1:een (eli 4=1 modulo 3). Tässä sovelletaan (2,3)-kaaviota siten, että i tietää osat s_i ja s_i+1 (missä s₄ tarkoittaa siis s₁:ä)

Laskennassa on summan lisäksi mukana tulo, joten ryhmä-struktuuri ei riitä. Sopiva rakenne on äärellinen kunta. Käytetään esimerkkinä lukujen 0,...,10 muodostamaa äärellistä kuntaa modulo 11.

Halutaan laskea (x+y)z oheisen taulukon neljän ensimmäisen sarakkeen tietojen mukaan. Muut sarakkeet kertovat laskun välituloksia.

i nimi syöte s esim. s₁+s₂+s₃ w₁+w₂+w₃ t₁+t₂+t₃
1 A x 8 1+3+4 5+1+_ 3
2 B y 5 4+9+3 _+1+7 6
3 C z 7 5+10+3 5+_+7 5

Lasku etenee vaiheittain:

A ja B jakavat (2,3)-kaavion mukaisesti kaikille x:n ja y:n. (osat mainittu s-sarakkeessa).
Lasketaan summa w=x+y siten, että tulos on (2,3)-jaettuna salaisuutena. Tämä tapahtuu yksinkertaisesti siten, että kukin laskee x:stä ja y:stä tietämänsä vastinosat yhteen: w_j := x_j+y_j. Kunkin tietämät osat on mainittu w-sarakkeessa.
C jakaa z:n (2,3)-kaavion mukaisesti (s-sarakkeen 3. rivi).
Lasketaan tulo t=wz: Kukin laskee tarpeelliset osatulot (kolme kpl) ja laskee ne yhteen: Osapuoli i laskee
t_i = w_iz_i+ w_iz_i+1+ w_i+1z_i
Tulos t on nyt (3,3)-kaavion mukaisesti eri osapuolilla (t-sarake). Jos se olisi vain jonkin laskun välitulos (ja seuraava operaatio olisi tulo), se pitäisi jakaa (2,3)-kaavion mukaisesti kaikille. Koska t on nyt lopputulos, kukin osapuoli kertoo tuloksensa eli t_i:n toisille ja saadaan t=t₁+t₂+t₃=3.

Harjoitus. Kokeillaan, onnistutaanko tekemään tämä myös luennolla.

Myös polynomimenetelmällä jaetuilla salaisuuksilla voidaan laskea. Tuloskin on vastaavalla tavalla jaettu salaisuus. Kahden (salaisuuksina) jaetun luvun tulon laskemisesta on alle kahden sivun mittainen hyvinkin ymmärrettävissä oleva esitys: [Gennaro & al.: 1998, 22 PS-sivua] sivuilla 5 ja 6.

Alussa käsitellyn OT-artikkelin kirjoittaja Pinkas on ollut mukana kehittämässä työkalua kahden osapuolen laskentaa varten. Tuloksia voi tarkastella artikkelissa Fairplay - A Secure Two-Party Computation System (Malkhi ym. 2004).

i	nimi	syöte s	esim.	s₁+s₂+s₃	w₁+w₂+w₃	t₁+t₂+t₃
1	A	x	8	1+3+4	5+1+_	3
2	B	y	5	4+9+3	_+1+7	6
3	C	z	7	5+10+3	5+_+7	5