Jos ei satu olemaan heitettäväksi sopivaa rahaa, noppaa tai vastaavaa, yksinkertainen ja hyvä protokolla on seuraava (=sovelma "kumpi käsi" -protokollasta). A kirjoittaa paperille satunnaisesti (esim. joskus aiemmin) keksimänsä bitin ja panee sen pöydälle ylösalaisin B:n ja itsensä näkyville. B keksii vastaavasti oman satunnaisen bittinsä ja ilmaisee sen, esim. kirjoittaa samalle paperille. Tulokseksi lasketaan bittien summa modulo 2, eli XOR.
Jos molemmat yrittävät saada bitistä esim. 1:n, niin tietysti se onnistuu. Kunhan toinenkin A:n tai B:n biteistä on satunnainen -- eikä siis erityisesti riipu toisen bitistä -- niin tulos on satunnainen eikä kumpikaan pysty sitä ennustamaan.
Miten vastaava tehtäisiin tietoverkon välityksellä? Mahdotontako, kuten Manuel Blum viittaa vuoden 1981 artikkelinsa otsikossa: Coin flipping by telephone: A protocol for solving impossible problems (Advances in cryptology, Report on CRYPTO'81, pp. 11-15.). Käytetään bittiin sitoutumista (id=329). Edellä tätä edusti se, että A ei voinut muuttaa paperille kirjoittamaansa bittiä. Etäprotokollassa A lähettää bittiin sitoutumisen B:lle joka lähettää A:lle oman bittinsä, minkä jälkeen A avaa sitoumuksensa ja tulos voidaan laskea. Harjoitus: Miten siis lasketaan ja mihin kryptografisiin oletuksiin menettely perustuu?
Etäprotokollissa on yhtenä ongelmana se, että toinen osapuoli yleensä saa tuloksen selville ennen toista. Vaikka tulosta ei voikaan muuttaa, sen voi ehkä tuhota tai sitä voi viivyttää.
Tuorein tutkimus tällä alalla näyttää koskevan kvanttikryptologian (id=376) ongelmaa. Siinä ei ole olemassa luotettavaa menetelmää bittiin sitoutumiseksi. Kvanttikrypton teoriassahan esim. RSA-moduulin tekijöihinjako ei ole mikään probleema. Rahanheitossa hyvä kvanttiprotokolla on sellainen, jossa toinen osapuoli ei pysty huijauksella parantamaan haluamansa lopputuloksen todennäköisyyttä yli 75%:n ! ( ks. esim. Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. Journal of Computer and System Sciences, Volume 68, Issue 2, pages 398-416, March 2004.)
Klassisessa kryptologiassa ei tarvitse kärsiä vääristymästä, kunhan käytettyjen primitiivien yksisuuntaisuuteen voidaan luottaa, ja yksinkertaisin riittävä primitiivihän on hash-funktio. Mutkikkaampia primitiivejä voidaan käyttää ja se voi olla tarpeen, jos rahanheitto on osa laajempaa kokonaisuutta. Yksi esimerkki toisenlaisesta protokollasta esiintyi 5. luennolla ja opetuksen aiheena oli, millaisia yllättäviä matemaattisia porsaanreikiä julkisen avaimen protokollissa voi olla. Seuraavassa katsotaan lähemmin toista julkisen avaimen protokollaa, jota voidaan (teoriassa) kätevästi soveltaa monipuolisempaankin uhkapeliin.
Protokolla alkaa sillä, että osapuolet valitsevat yhteisen RSA-moduulin ja kumpikin omat salaus- ja purkueksponenttinsa, joita ei kerrota toiselle (kun moduulin tekijät kerran tunnetaan, toisesta eksponentista voisi heti laskea toisen). Aloittava osapuoli A muodostaa kaksi viestiä, joista toisessa on "kruuna" ja toisessa "klaava" ja kummassakin lisäksi jokin satunnaisosa, jonka perusteella A voi myöhemmin todeta viestin autenttisuuden. Nämä viestit A salaa omalla eksponentillaan ja lähettää sekoitetussa järjestyksessä B:lle, joka valitsee satunnaisesti toisen, salaa sen omalla eksponentillaan ja palauttaa A:lle. Kun A korottaa tämän purkueksponenttiinsa, yhteisen moduulin ansiosta jäljelle jää vain B:n salaus, ja kun B saa tämän viestin takaisin, hän saa selville, kumman viestin oli valinnut. Kun hän palauttaa sen A:lle, tämä voi tarkistaa että satunnaisosa on oikein. Lopuksi kumpikin vielä paljastaa käyttämänsä eksponentit, ja tarkastavat sen perusteella ettei toinen huijannut. Harjoitus: Mitä huijausmahdollisuuksia olisi, ellei viimeistä vaihetta tehtäisi?
Jos tässä protokollassa kruunan ja klaavan sijasta viesteinä ovat 52 pelikortin koodit, A voi jakaa pokerikortit B:lle antamalla tälle ensin koko pakan kryptattuna ja purkamalla sitten (oman) kryptauksensa B:n valitsemasta, kryptaamasta ja palauttamasta viidestä kortista. Näin B saa selville oman pokerikätensä. Sen jälkeen hän valitsee jäljelläolevista viisi ja lähettää ne A:lle tämän kädeksi. Jos pelaajia on useampia, B lähettääkin C:lle kaikki jäljellä olevat ja C toimii A:n ja mahdollisten muiden pelaajien kanssa vastaavasti kuin B. Viimeinen siis lähettää A:lle viisi korttia, joista A purkaa oman salauksensa. Jos pelissä jaetaan lisää kortteja, niitä jakaa se, jolle loppupakka on jäänyt. Toisin kuin tavallisessa pokerissa lopussa on syytä katsoa kaikkien kortit. Harjoitus: Millaiset vaatimukset pokerinpeluun protokollalle oikeastaan pitäisi asettaa?
Tarkastellaan samalla, miten toteutuvat artikkelissa äänestysprotokollalle asetetut vaatimukset ja toivomukset, ja miten niistä muodostuu tavanomaisia luottamuksellisuuden, autenttisuuden ja eheyden vaatimuksia protokollan eri vaiheille.
Perusvaatimukset ovat:
Protokollan ytimenä on se, että kelpuuttajan roolissa oleva viranomainen (validator) allekirjoittaa sokeasti kelpoisuusmerkinnän, joka on valmiiksi täytetty äänestyslippu (artikkelin notaatiossa "V" niinkuin 'vote'), joka on salattu äänestäjän valitsemalla symmetrisellä avaimella ("se", tuloksena "Vse") ja sen jälkeen tiivistetty (tuloksena "m"). Tämän jälkeen tapahtuu sokaisu (satunnaislukuna "k", jolla eksponenttina kelpuuttajan julkinen "ve").
Artikkelin Sensus-protokolla on läheinen muunnos Fujioka-Okamoto-Ohtan vaaliprotokollasta (1993). Ainoa ero on, että Sensuksessa äänestäjän ei tarvitse odottaa kryptattujen äänten julkaisemista, vaan hän saa kuitin, jonka perusteella hän tietää äänensä tulleen "kuuluville" ja voi heti lähettää purkuavaimen. Kuitti on oleellisesti sama kuin kryptattu ääni, joten ero on pieni. Kuitin autenttisuuden osoittamiseksi siinä on nyt laskijan allekirjoitus. (Kuitti on "(Vse)td", missä "td" on laskijan yksityinen avain.) Tietenkin tässä pitää luottaa laskijaan sikäli, että se saa tietää äänet ennen määräajan loppumista.
Protokollan analyysi tarjoaa hyvän tilaisuuden oivaltaa, miten monipuolisesti vaatimusten toteutumista on tarkasteltava. Muuten voi jäädä huomaamatta sinänsä ilmeisiä ongelmia, kuten se, että toteutuksen teknisessä järjestelmässä voi olla ei-toivottu viestien jäljitysmahdollisuus tai kotiäänestys voi tapahtua vastoin yksilön tahtoa. Itse protokollassakin on ongelma, sillä vaaliviranomainen voi äänestää niiden puolesta, jotka jättävät äänestämättä. Tämän riskin vähentämiseksi jokaisen pitäisi antaa edes tyhjä ääni. Äänestämättä jättämisten minimoimiseksi järjestelmä voi edellyttää äänestäjäksi ilmoittautumisen siinä vaiheessa, kun äänioikeus myönnetään/todetaan. Kun ilmoittautuneiden lista on julkaistu, ja useimmat heistä tosiaan äänestävät, viranomaiselle ei jää paljon ääniä "omaan käyttöön". Viranomaisella on myös riski jäädä kiinni vilpistä, jos äänestämättä jättänyt "huomaa sittenkin äänestäneensä". Jos tällaisia valituksia tulee riittävän monta, päädytään ehkä oikaisuun. Siinä suhteessa tilanne muistuttaa jossain määrin mikromaksamisen protokollien riskien hallintaa luennolta 3.
Ongelmat ja niiden ratkaisut riippuvat paljon siitä, millaisessa ympäristössä vaali järjestetään. Jos kotiäänestyksiä ei ole, jäljitys- ja pakotusongelma poistuvat. Jälkimmäistä ei voine saavuttaa, jos äänestyspaikkaa ei rajoiteta. Jos taas äänestys tapahtuu kiinteissä vaalihuoneistoissa, verkkoteknisen jäljitysongelman tilalle voi tulla äänestyslaitteiden luotettavuuteen ja niiden lähellä tapahtuvaan salakuunteluun ja lokitietojen keruuseen perustuvia ongelmia. Vaikka laitteisiin ja virkailijoihin voitaisiinkin luottaa, voisi silti olla järkevää lisätä protokollaan salaus äänenpurkuavaimen lähetykseen. Symmetrinen avain tätä varten voisi olla asiakkaan koneen keksimä ja kulkea suojattuna asiakkaan ensimmäisessä viestissä laskijalle.
Teoriassa on hyvin yksinkertaista ottaa järjestelmään mukaan äänen vaihtamismahdollisuus (esim. toinen vaalikierros), tai jatkuva äänestys. Äänen ja sen kelpoisuutta osoittavan merkin mukana äänestäjä lähettää arvon f(s), missä f on yksisuuntainen funktio ja s satunnainen salainen arvo. Jos äänen haluaa vaihtaa, riittää lähettää vanha ääni (tai jokin indeksi), uusi ääni ja s, joka tällöin autentikoi äänestäjän anonyymisti. Jos samalla lähettää uuden arvon f(s'), operaation voi toistaa. Toistoja varten voisi myös soveltaa hash-arvojen ketjua kuten mikromaksuissa. Teoreettisesta yksinkertaisuudesta huolimatta joudutaan tekemään perusteellinen analyysi, jos tällainen halutaan ottaa mukaan johonkin toimivaan käytännön järjestelmään. Äänten osto- ja pakotusongelma ainakin lievenisivät, jos omaa ääntä voisi vaihtaa.
Äänestysprotokollien kanssa läheisesti tekemisissä ovat tarjouskilpailun tai huutokaupan protokollat. Niihin palataan monen osapuolen salaisen laskennan yhteydessä, joka on eräänlainen yleistys äänestyksestä. Huutokauppoja koskenee sama totuus, jonka Bruce Schneier julistaa Crypto-Gram-lehdessään (joulukuu 2000):
A secure Internet voting system is theoretically possible, but it would be the first secure networked application ever created in the history of computers.Avi Rubin pohdiskelee internet-äänestyksen turvallisuutta monipuolisesti artikkelissaan (syksy 2000) ja päätyy yhtä pessimistiseen tulokseen:
Given the current state of widely deployed computers in peoples' homes, the vulnerability of the Internet to denial of service attacks, and the unreliability of the Domain Name Service, we believe that the technology does not yet exist to enable remote electronic voting in public elections.Hänen mukaansa ainoa toivo on, että tulevaisuuden PC-koneissa toteutetaan sentyyppinen luotettu polku (trusted path), jollaista esim. vuonna 1999 perustettu Trusted Computing Platform Alliance (sittemmin TCG, Trusted Computing Group, ks. id=353) yrittää määritellä.
Muuallakin mutta erityisesti Yhdysvalloissa elektroninen äänestysjärjestelmä tarkoittaa yleensä paljon vaatimattomammalta kuulostavaa tavoitetta kuin äänestäjien toimintaa verkossa. Siinä on kyse äänestyskoneista, joilla monimutkainen vaalilippu voidaan täyttää ja äänet laskea. Sekin on hämmästyttävän monimutkainen ongelma, varsinkin jos otetaan huomioon, että äänestäjälle pitäisi muodostua jonkinlainen vakuuttuneisuus siitä, että ääni on tullut oikein talletetuksi. Joissain järjestelmissä on myös salaisuuden jakamisen tekniikalla toteutettu paperikuitti. Katso myös Rebecca Mercurin sivustoa Electronic Voting, jossa on mm. hänen väitöskirjansa "Electronic Vote Tabulation Checks & Balances" vuodelta 2000.
Yksi tuoreimpia äänestyksen protokollatutkimuksia on Lebren ym:n artikkeli: Internet voting: improving resistance to malicious servers in REVS (2004). Siinä mainittu REVS eli "Robust electronic voting system" on samojen tekijöiden protokolla vuodelta 2003 ja siitäkin on olemassa toteutus, ks. REVS-kotisivu (vuodelta 2004). Robustisuus tarkoittaa järjestelmän kykyä kestää tietynlaisia DoS-hyökkäyksiä ja -tilanteita.