Guilin Wangin Bibliography on Digital Signatures antaa käsityksen, miten monipuolista tutkimusta allekirjoitusaiheesta nykyään tehdään. Paljon on kyse viilauksista tehokkuuden ja todistusten osalta: Esimerkkinä Kiayias ja Yung esittävät vuonna 2004, että heidän ryhmäallekirjoitusalgoritminsa on ensimmäinen, joka on sekä tehokas että todistetusti turvallinen. Toisaalta löytyy uudentyyppisiä variaatioita täyttämään tehtäviä, joilla ei vielä käytännössä ole suurta kysyntää. Ainakin Schneier toteaa kirjassaan vuonna 1996, ettei hän tiedä käyttöä unohtavalle allekirjoitukselle, joka toimii samaan tapaan kuin Oblivious transfer, mutta viestin sijasta siinä muodostuu (tai ei muodostu) allekirjoitus.
Nyt tarkastellaan sellaista valtuutetun B tekemää allekirjoitusta, jonka voi todentaa vain ennalta -- jo alkuperäisen valtuuttajan A toimesta -- määrätty taho C, ’designated verifier’. Tällainen ominaisuus voi liittyä myös muunlaisiin allekirjoituksiin, esim kieltämättömään, kuten em. TTJ-sivulla mainitaan.
Tarkastellaan esimerkkinä protokollaa em. Guiling Wangin artikkelista (2004). Tätä varten luennolla kerrataan lyhyesti ElGamalin allekirjoitus, jotta käyttöön tuleva Schnorrin muunnos siitä tuntuu luontevalta. Juonena siinä on on-line -laskennan suorittaminen modulo q, kun q on vain parisataabittinen tekijä 1000-bittiselle (p-1):lle. Etukäteistä eli off-line -laskentaa tehdään modulo p. Vastaava keino on käytössä myös DSA:ssa (siitä ja ElGamalista ks. id=233). Kaikissa näissä systeemeissä yksityistä avainta x vastaava julkinen avain on y=gx mod p.
Tavanomaisen Schnorr-allekirjoituksen lisäksi käyttöön tulee sen 'two-party' -muunnos: kahden osapuolen allekirjoitus tarkoittaa tässä sitä, että sen muodostamiseen tarvitaan molempien yksityistä avainta. Julkinen avain on tällöin muotoa y=gx1+x2 mod p, eikä osapuolten tarvitse paljastaa x:iänsä, sillä y:n saa myös tulona y=gx1·gx2 mod p.
Nyt osapuolet ovat alkuperäinen allekirjoittaja A ja valtuutettu B, jotka luovat tällä tavalla B:lle avainparin valtuutetun allekirjoituksia varten. Valtuutetun yksityinen avain (xP, summamuotoinen) tulee tällöin kokonaan B:n tietoon, eikä A tiedä sitä. Vastaava julkinen avain (yP) voidaan laskea muista tiedoista. (Kahden osapuolen allekirjoituksia ja erityisesti 2Schnorr löytyy Nicolosin ym:n artikkelista Proactive Two-Party Signatures for User Authentication, jossa erityisenä sovelluskohteena on SFS-tiedostojärjestelmä, ks. id=522, jossa on esillä "SFS-RO".)
Wangin artikkeli on hyvin tiivis (4 sivua) ja sisältää muutaman varsin monipolvisen allekirjoitus- ja todennuslaskelman. Artikkelin johdannossa määritellään valtuuskäsitteitä. Sitten esitellään aiempi DYD-protokolla (Dai, Yang & Dong, 2003) ja osoitetaan siinä olevia heikkouksia. Sitä modifioidaan uudeksi protokollaksi em. kahden osapuolen allekirjoituksen avulla. Siihen otetaan mukaan myös ns. ’warrant’-kenttä eli valtuuskirja, jonka mukaisesti valtuutetun allekirjoitus voi koskea muitakin kuin yhtä määrättyä dokumenttia. Valtuuskirjassa määrätään myös osapuolet, erityisesti todentajat. Lähinnä vain viittamalla aiempiin todistuksiin artikkeli näyttää/väittää uuden protokollan olevan turvallinen. Lopussa on lyhyt maininta verkkokauppaan liittyvästä sovellusmahdollisuudesta.
Wangin artikkeli otetaan mukaan kurssille, mutta sitä ei tarvitse ruotia ytimiä myöten. Sen sijaan pitäisi oppia näkemään kokonaisuutta kaavojen takaa ja kaavoistakin niiden rakennetta. Lisäksi pitäisi pystyä muodostamaan arvioita turvallisuusargumenttien luonteesta, protokollan tehokkuudesta (jota artikkeli ei analysoi) sekä yleisestä soveltuvuudesta. Viimeksi mainittuun vaikuttaa mm. se, että vaikka C olisi jälleenmyyjä B:n asiakas, tuottaja A tarvitsee tiedon C:stä. Aiemmasta DYD-protokollasta poiketen Wangin protokolla ei edellytä, että A soveltaisi C:n julkista avainta. Jää siis arvioitavaksi myös, missä määrin uusi protokolla on A:n kannalta tyyppiä "designated verifier".
Artikkelin kaavoihin tutustuessa täytynee ainakin seuraavat symbolit opetella tilapäisesti ulkoa, koska ne toistuvat pitkin matkaa:
Uusi protokolla tuottaa varsinaisen allekirjoituksen samalla tavalla kuin DYD-skeema. Valtuuskirjan ohella uudistusta on siis vain proxy-avainten luonti. Se tapahtuu luomalla 2Schnorr-allekirjoitus valtuuskirjalle. Tällaisen allekirjoituksen todentaminen tapahtuu tavallisella Schnorr-todennuksen yhtälöllä ja artikkelin esittely lähtee liikkeelle juuri siitä (yhtälöstä (5)). Valtuutetun avainpari ei tietenkään ole sama kuin 2Schnorr-allekirjoitus, mutta yksityinen avain xP on allekirjoituksen toinen puolikas.
Sensoriverkon solmuissa on heikko laskentateho ja niiden joukossa voi olla vallattujakin solmuja. Kolmannessa luennossa mainittua autentikointipuuta soveltaen tähän on kehitelty tehokas joidenkin solmujen yhdessä tekemä allekirjoitus: Seys, Preneel: Efficient Cooperative Signatures: A Novel Authentication Scheme for Sensor Networks, 2005.
Erikoisten sovellusten laatijoille on tarjolla runsaasti variaatioita, joista kaikkia ei ole vielä tutkittu. Zhengjun Cao on jaotellut allekirjoituksen peruspiirteitä ja todennut yhdistelmiä olevan 21140 kappaletta (Classification of Signature-only Signature Models 2006). Peruspiirteiksi hän otti nämä viisi:
Cao on löytänyt kirjallisuudesta ison joukon sovelluksia ja sijoittaa niitä malliinsa. Vain yksi on sellainen, että useammassa kuin kahdessa pääluokassa valitaan tavanomaisesta allekirjoituksesta poikkeava järjestely.
TTJ:ssä (id=65) on esillä Feige-Fiat-Shamirin autentikointiprotokolla, jossa todistaja osoittaa todentajalle tuntevansa yksityisen avaimensa, joka sekin on julkisen avaimen eräänlainen neliöjuuri. Protokollassa noudatetaan nollatietotodistuksille tavallista periaatetta "sitoutuminen-haaste-vaste", joka on sovellus "cut and choose" -periaatteesta. Se on arkinenkin reilun jaon aikaansaamisen menetelmä (toinen leikkaa kakun puoliksi ja toinen valitsee).
Lisätietoa: Helger Lipmaan linkkisivu. Uusia nollatietoprotokollia löytyy kokeilutoteutuksinakin (W.Teepe: New Protocols for Proving Knowledge of Arbitrary Secrets While not Giving Them Away, 2004). Protokollia käsittelevä artikkeli mainitsee sovelluksena Hollannin poliisin hankkeen rikostutkinnan päällekkäisten kohteiden selvittämiseksi. Kyseessä on pohjimmaltaan monen osapuolen laskenta ja operaationa AND.
Vaikka kortteihin on merkitty numeroita ja värejä, laskennassa on tyydyttävä binääriseen aritmetiikkaan, eli Boolen funktioihin. Niitä toteutetaan yksi looginen portti kerrallaan siten, että syötteitä on kaksi ja tuloksia yksi. Negaatiossa luonnollisesti on vain yksi syöte. Lisäksi tarvitaan bitin monistusta, jolloin yhdestä syötteestä saadaan kaksi samanlaista tulosta.
Korttilaskentaan on erilaisia mekanismeja. Tässä esitettävä perustuu artikkeliin V.Niemi, A.Renvall: Solitaire Zero Knowledge (1999). Nimensä mukaisesti artikkeli esittelee myös, miten pasianssia pelaamalla voi esittää nollatietotodistuksen, nimittäin sille, että pelaaja tietää jonkin bittikombinaation, jolla tietty Boolen funktio saa arvon 1. Tähän ei mennä syvemmälle, vaan katsotaan laskennan periaatetta.
Yhden bitin koodaamiseen tarvitaan kaksi korttia ja muissa operaatioissa paitsi negaatiossa ja XOR:ssa tarvitaan muutama apukortti. Operaatio suoritetaan bittien ja apukorttien muodostamassa pakassa, jota käsiteltäessä vain korttien selkäpuolet ovat näkyvissä. Pakassa olevien korttien arvot tiedetään, mutta ei järjestystä. Käsittelyn ohjaamiseksi katsotaan ajoittain yhden kortin arvo. Kryptologisena operaationa on pakan nostaminen eli leikkaaminen. Tämä voidaan toteuttaa esim. siten, että kukin pelaaja nostaa pakkaa näyttämättä toisille, montako korttia hän siirtää.
Useassa tapauksessa pakasta halutaan poistaa jokin kortti. Tämä voidaan tehdä toistamalla nosto kunnes päällimmäisenä on haettu kortti. Kunhan nostojen välillä ei katsota enempää kuin yhtä korttia, muiden korttien järjestyksestä ei silloin tiedetä mitään uutta.
Koodaus ja laskenta edellyttävät, että korteille on määritelty suuruusjärjestys. Tässä riittää tarkastella tietyn maan kortteja, jolloin järjestys on luonnollinen 1,2,...,13. Bitti nolla koodataan siten, että pienempi kortti on suuremman päällä (kun siis selkäpuoli on ylöspäin). Ykkösbitissä järjestys on toisinpäin. Tästä nähdään heti, että negaation muodostaminen on erittäin yksinkertaista, vaikka bittiä ei tunnettaisi.
Kahden bitin x ja y välisiä operaatioita varten oletetaan, että syötteinä on kortit a, A, b ja B, missä a<A<b<B. Seuraavissa taulukoissa pakat on lueteltu ylhäältä lukien, siis vasemmanpuoleinen kortti on päällimmäinen kun selkäpuoli on ylöspäin.
Poistetaan A ja b eli arvoltaan keskimmäiset bittikortit pakasta ja siirretään lisäkortti '-' päällimmäiseksi. Lopputulos näkyy taulukosta. Kun siitä poistetaan päällimmäinen kortti jäljellä olevat bitit koodaavat AND-operaation oikean tuloksen.
kort- pakka
x y teina alussa lopussa tulos
---------------------------------
0 0 aA bB -abAB -aB 0
0 1 aA Bb -aBAb -aB 0
1 0 Aa bB -AbaB -aB 0
1 1 Aa Bb -ABab -Ba 1
kort- pakka
x y teina alussa lopussa tulos
---------------------------------
0 0 aA bB -baBA -aB 0
0 1 aA Bb -BabA -Ba 1
1 0 Aa bB -bABa -Ba 1
1 1 Aa Bb -BAba -Ba 1
AND:n ja OR:n muistisääntönä voi ajatella, että lisäkortin jälkeen aloitetaan
pienemmällä (AND) tai isommalla (OR) sen mukaan kumpaa tulosta operaatio
"suosii", ja lopputulos näkyy "korostetusti" siitä, että korttien numeroero on
suurin mitä syötteistä saadaan aikaan.
kort- pakka
x y teina alussa lopussa tulos
---------------------------------
0 0 aA bB abAB BaA 0
0 1 aA Bb aBAb BAa 1
1 0 Aa bB AbaB BAa 1
1 1 Aa Bb ABab BaA 0
Jos merkkikortiksi jätettäisiin B:n sijasta A (eli a poistettaisiin), sen alle jäävät
beta-kortit koodaisivat XOR:n negaation eli ekvivalenssin. Pelkkä XOR tai
ekvivalenssi eivät ole tietenkään kiinnostavia salatun laskennan kannalta, koska
tulos paljastaa vastapuolen syötteen.
Kopiointioperaation tarkoituksena on muuttaa uudet beta-kortit koodaamaan sama bitti kuin syötteenä olevat alfa-kortit eli aA tai Aa, joiden järjestystä ei tiedetä. Beta-korttien ei nyt tarvitse olla suurempia kuin alfojen, mutta edelleen tietysti b<B. Aluksi beta-kortit sekoitetaan. Pakan päällimmäiseksi tulee lisäkortti '-', sen alle alfat, sitten toinen lisäkortti '+' ja alimmaksi betat. Pakka on tässä vaiheessa siis yksi seuraavista:
-aA+bB -aA+Bb -Aa+bB -Aa+BbNostetaan pakkaa, kunnes päällimmäisenä on jokin bittikortti. Katsotaan sen lisäksi pinon neljäs kortti. Se on toisen bitin koodauksessa vastaava kortti kuin pinon päällimmäinen. Tästä tiedetään, ovatko bitit jo alunperin samat vai edustavatko beta-kortit alfa-korttien komplementtia. Jotta bitit saadaan talteen, palautetaan pakkaa alkuperäiseen järjestykseen, eli nostetaan, kunnes päällimmäisenä on '-'. Jos sitä ennen päällimmäiseksi osuu '+', niin tietenkin voidaan nostaa deterministisesti vielä kolme korttia. Nyt pakasta voidaan poimia alkuperäiset alfa-kortit sekä beta-kortit, jotka joko sellaisenaan tai vaihdettuina koodaavat saman bitin kuin alfa-kortit.