Biztons´agos ´arverez˝o protokoll
∗
Ligeti P´eter, M´erai L´aszl´o
Kivonat ´ Arverez˝ o elj´ ar´ asok matematikai modellez´es´en´el gyakran el˝ofordulnak biztons´ agi felt´etelek, amiket az adott rendszernek teljes´ıtenie kell. Az altalunk vizsg´ ´ alt v´ altozatn´al t¨obb egyforma ´ert´ekt´argyra licit´alnak a r´esztvev˝ ok ´ ar-darabsz´ am p´arokkal, ahol a legmagasabb ´arakat aj´anl´ok nyernek. A kidolgozott elj´ar´as egyik el˝onye, hogy a nyertesek licitjein k´ıv¨ ul semmi inform´ aci´ o nem ker¨ ul nyilv´anoss´agra, de sz´amos tovv´abbi k¨ ovetelm´enynek is eleget tesz.
1.
´ Arver´ esek fajt´ ai
Az ´arver´es o˝sid˝ok o´ta a kereskedelem egy meghat´arozott fajt´aja. J´osz´agok elad´asa sor´an abban az esetben n´epszer˝ u igaz´an az a´rver´es, mikor a vev˝ok t¨obbet tudhatnak az ´aru ´ert´ek´er˝ol, mint az elad´o. Az al´abbiakban r¨oviden ismertetj¨ uk a a´rver´esek f˝obb t´ıpusait. Az angol ´arver´es (first price open outcry, highest-price sale, legmagasabb ´ar) tal´an az egyik legelterjedtebb ´arverez´esi fajta. Az angol a´rver´esn´al minden r´esztvev˝o szabadon emelheti a licitj´et. Ha m´ar senki nem emel, a legmagasabb licitet tett r´esztvev˝o kapja meg az a´rut ´es kifizeti ´erte a licitj´et. A szabad kil´ep´eses licit (open exit auction, open ascending auction) az angol a´rver´es jap´an v´altozata. Itt az ´ar folyamatosan emelkedik ´es minden j´at´ekos nyilv´anosan jelzi, ha kisz´all (´es ezut´an m´ar nem t´erhet vissza). Ekkor a gy˝oztes a m´asodik legmagasabb rezerv´aci´os ´arat fizeti. Els˝o´aras tender (first price sealed bid, versenyt´argyal´as, titkos licites tender) a´rverez´esi rendszert ∗
A munka r´eszben az Orsz´agos Kutat´asi Alapprogramok (OTKA) PD100712 ´es K100291 sz´ am´ u projektek, illetve a KMOP-1.1.1-09/1-2009-0042 sz´am´ u projekt t´ amogat´ as´ aval k´esz¨ ult.
1
alkalmaztak p´eld´aul a magyar privatiz´aci´o sor´an. Ebben a v´altozatban mindenki leadja a licitj´et u ´gy, hogy nincs inform´aci´oja a t¨obbiek´er˝ol. A legmagasabb licitet lead´o r´esztvev˝o kifizeti a licitj´et ´es elnyeri az ´arut. A m´odszer h´atr´anya, hogy a gy˝oztes elbukja a k´et legnagyobb licit k¨ozti k¨ ul¨onbs´eget. Az els˝oa´ras tender egy v´altozata a Vickrey-aukci´o (second price sealed-bid, m´asodlicites versenyt´argyal´as, m´asodik a´ras tender, filatelista ´arver´es), melyet William Vickrey tisztelet´ere neveztek el, aki 1996-ban Nobel-d´ıjat kapott az a´rverez´esi rendszer viszg´alat´a´ert. Az el˝oz˝oh¨oz hasonl´oan mindenki leadja a licitj´et, u ´gy hogy nincs inform´aci´oja a t¨obbiek´er˝ol. A legmagasabb licitet lead´o r´esztvev˝o kifizeti a m´asodik legmagasabb licitet ´es elnyeri az a´rut. Az angol a´rver´es ´es a Vickrey tender kimenetel szempontj´ab´ol ekvivalens. A holland ´arver´es (vir´agv´as´ar, cs¨okken˝o a´ras aukci´o, descending price auction) egy f˝ok´ent Hollandi´aban (sajtok ´es friss vir´agok elad´asakor haszn´alt) licit´al´asi forma az ´arver´eseken. Az a´rver˝o kihirdeti a licitet, amit folyamatosan cs¨okkent eg´eszen addig, m´ıg valamelyik r´esztvev˝o meg´all´ıtja ´es elviszi az a´rut azon az a´ron. A holland a´rver´es ekvivalens az els˝oa´ras a´rver´essel, azaz egy-egy ´ertelm˝ u megfeleltet´es van a k´et j´at´ek strat´egiahalmazai k¨oz¨ott. Ennek az az oka, hogy semmi relev´ans inform´aci´o nem der¨ ul ki az a´rver´es folyam´an, csak a v´eg´en, amikor m´ar t´ ul k´es˝o van ahhoz, hogy b´arki v´altoztasson a strat´egi´aj´an.
2.
Megoldand´ o probl´ ema
A kit˝ uz¨ott feladat legink´abb az els˝oa´ras a´rver´esre hasonl´ıt, l´enyeg´eben annak egy ´altal´anos´ıt´as´anak tekinthet˝o. A k¨ ul¨onbs´eg az, hogy itt ugyanabb´ol a t´argyb´ol (pl. ´erm´ekb˝ol, b´elyegekb˝ol, stb) t¨obbet bocs´atanak licitre ´es azokra egyszerre kell licit´alni. A licitben szerepeltetni kell a term´ek´ert kifizetend˝o egys´eg´arat, valamint a k´ıv´ant darabsz´amot. A licitre bocs´ajtott t´argyak sz´am´at mindenki sz´am´ara ismertnek t´etelezz¨ uk fel. Minden esetben a legmagasabb egys´eg´arat aj´anl´o(k) a nyertes(ek). Amennyiben t¨obben ugyanazt a legmagasabb a´rat licit´alt´ak, a t´argyakat az a´ltaluk k´ıv´ant darabsz´amok ar´any´aban osztjuk el. A feladat egzakt matematikai modellje a 2.1. alfejezetben tal´alhat´o. A r´esztvev˝ok k¨oz¨ott van egy kit¨ untetett szerepl˝o, a licit vezet˝oje, akinek egyetlen szerepe, hogy jelezze, mikort´ol nem lehet aj´anlatokat tenni. A r´esztvev˝ok k¨oz¨otti tov´abbi kommunik´aci´oba nem sz´ol bele, nem licit´al ´es nem is sz´amol semmit (l´enyeg´eben egy felh´ uzott ´ebreszt˝oo´r´anak tekinthet˝o). A 2
r´esztvev˝ok k¨oz¨ ul kiz´ar´olag r´ola felt´etelez¨ unk megb´ızhat´os´agot, a t¨obbiekr˝ol semmit nem tesz¨ unk fel. Miut´an lez´arult az ´arver´es, a r´esztvev˝ok sz´amolnak, illetve kommunik´alnak egym´assal ´es ennek eredm´enyek´eppen a v´eg´en mindenki (de csak az a´rver´esben r´esztvev˝ok) sz´am´ara nyilv´anoss´agra ker¨ ulnek a nyertesek, nyertesek aj´anlatai, valamint a nyertesek a´ltal elnyert t´argyak sz´amai, minden m´as inform´aci´o titokban marad. Ezen fel¨ ul felt´etelezz¨ uk, hogy a r´esztvev˝ok k¨oz¨ott p´aronk´enti biztons´agos kommunik´aci´ora van lehet˝os´eg. A pontos biztons´agi felt´etelez´esek ´es lehets´eges t´amad´asok a 2.2. alfejezetben ker¨ ulnek kifejt´esre.
2.1.
A matematikai modell
Jel¨olje a licitben r´esztvev˝ok sz´am´at n, a r´esztvev˝oket pedig r1 , r2 , . . . , rn , jel¨olj¨ uk tov´abb´a az a´rver´es vezet˝oj´et r0 -lal. Jel¨olje a licitre bocs´ajtott t´argyak sz´am´at t. Az a´ltal´anoss´ag megszor´ıt´asa n´elk¨ ul feltehetj¨ uk, hogy legfeljebb v´eges sok a´rat licit´alhatnak a r´esztvev˝ok, legyen ez a sz´am v, a lehets´eges aj´anlhat´o a´rak halmaza pedig legyen rendezve szigor´ uan monoton cs¨okken˝o sorrendben: a1 > a2 > · · · > av . Az i-edik r´esztvev˝o licitj´et jel¨olje li , ez a k¨ovetkez˝o p´arb´ol a´ll: li = (pi , di ), ahol pi ∈ {a1 , a2 , . . . , av }, 0 ≤ di ≤ t, di ∈ Z, ahol pi jel¨oli az a´ltala aj´anlott a´rat, di pedig a darabsz´amot.
2.2.
Biztons´ agi felt´ etelek, fenyeget´ esmodell
A k¨ovetkez˝okben o¨sszefoglaljuk a biztons´agos a´rverez´esi rendszerekkel szemben t´amasztott k¨ovetel´enyeket, z´ar´ojelben a megfelel˝o angol terminol´ogi´aval. 1. T¨ ok´ eletes licit-anonimit´ as (Perfect bid anonymity): Az ´arverez˝o rendszert˝ol megk¨ovetelj¨ uk, hogy a r´esztvev˝ok valamely r´esz´enek licitjeir˝ol csak a r´esztvev˝ok komplementere tudhasson meg b´arminem˝ u inform´aci´ot. Ez a k¨ovetelm´eny a szok´asos anonimit´as k¨ovetelm´eny egy er˝os´ıt´ese. ¨ 2. Onellen˝ orizhet˝ os´ eg (Self verifying): Minden r´esztvev˝o ellen˝orizni tudja az ´arver´es kimenetel´et.
3
´ 3. Altal´ anosan ellen˝ orizhet˝ o protokoll (Universal verifying): Minden r´esztvev˝o ellen˝orizheti, hogy az o¨sszes licit figyelembe lett-e v´eve az a´rver´es sor´an. 4. Igazs´ agoss´ ag (Fairness): Senkinek sincs semminem˝ u inform´aci´oja a licitekr˝ol/darabsz´amokr´ol az ´arver´es lez´ar´as´aig ´es akkor is csak a nyertes(ek)´e ker¨ ul nyilv´anoss´agra. 5. Csal´ ok elkap´ asa (Catching cheaters): A r´esztvev˝ok ki tudj´ak mutatni, ha csal´as t¨ort´ent, ´es a csal´ot azonos´ıtani tudj´ak. 6. Jegyz˝ ok¨ onyvezhet˝ os´ eg (Opportunity to keep the transcript): Ha sz¨ uks´eges, az ´arver´esr˝ol hiteles jegyz˝ok¨onyv k´esz´ıthet˝o. 7. Technol´ ogiai f¨ uggetlens´ eg (Technology independent): A licit´al´onak csak a protokoll biztons´ag´aban ´es a saj´at eszk¨oz´enek helyesen m˝ uk¨od´es´eben kell b´ıznia. 8. Ny´ılt forr´ ask´ od (Open source, open code): A protokoll biztons´aga nem a megfelel˝o algoritmus titkoss´ag´at´ol f¨ ugg.
2.3.
Megold´ asok hasonl´ o probl´ em´ akra
Ha nagyon messzir˝ol tekint¨ unk a feladatra, akkor val´oj´aban egy nagyon a´ltal´anos ´es sokat vizsg´alt probl´em´anak, az u ´gynevezett biztons´agos t¨obbr´esztvev˝os sz´am´ıt´asoknak (az angol szakirodalomban secure multiparty computation) egy speci´alis eset´evel ´allunk szemben. Az probl´em´at el˝osz¨or Yao vetette fel 1982-ben ´ırt cikk´eben [9], leg´altal´anosabban a k¨ovetkez˝ok´eppen fogalmazhat´o meg: Biztons´ agos t¨ obbr´ esztvev˝ os sz´ am´ıt´ asok probl´ ema Adott r1 , r2 , . . . , rn r´esztvev˝o, mindegyik ri -nek van egy saj´at titkos si ´ert´eke, valamint legyen F egy n-v´altoz´os f¨ uggv´eny, ami minden r´esztvev˝o sz´am´ara ismert. A c´el, hogy a r´esztvev˝ok kisz´am´ıts´ak az F f¨ uggv´eny ´ert´eket az (s1 , s2 , . . . , sn ) helyen, oly m´odon, hogy semelyik r´esztvev˝o sem tudjon meg semmi olyan inform´aci´ot, ami ne k¨ovetkezne a v´egered´enyb˝ol, a saj´at titkos ´ert´ek´eb˝o, valamint az F f¨ uggv´enyb˝ol. Hogy az utols´o mondat kicsit vil´agosabb legyen, ebben a´ltal´aban az is benne foglaltatik, hogy senkinek ne legyen semmilyen inform´aci´oja a t¨obbi 4
r´esztvev˝o titkos ´ert´ek´er˝ol. (De ez nem minden esetben van ´ıgy, p´eld´aul k´et r´esztvev˝o eset´en legyen a kisz´am´ıtand´o f¨ uggv´eny a bemenetek o¨sszege, ekkor nyilv´an mindketten ki tudj´ak sz´am´ıtani a m´asik titkos ´ert´ek´et is.) A t´em´ar´ol remek ¨osszefoglal´ot ad Cramer irom´anya [3]. Goldreich, Micali ´es Widgerson megmutatt´ak, hogy az ´altal´anos feladat megoldhat´o abban az esetben, ha a r´esztvev˝ok t¨obbs´ege nem csal, l´asd [5]. Val´oj´aban egy er˝osebb eredm´enyt bizony´ıtottak: az a´ltaluk adott konstrukci´on´al nem csak az lehetetlen, hogy a csal´ok nemk´ıv´ant titkokhoz jussanak, hanem az is biztos´ıtva van, hogy amennyiben a csal´ok f´elbehagyj´ak a protokollt, a becs¨ uletes r´esztvev˝ok n´elk¨ ul¨ uk is ki tudj´ak sz´am´ıtani a v´egeredm´enyt (ezt robosztuss´agnak nevezik). A konstrukci´o k´et l´enyeges ´ep´ıt˝ok¨ove a nullismeret˝ u bizony´ıt´as (zero-knowledge proof), illetve az ellen˝orizhet˝o titokmegoszt´as (verifiable secret sharing). A konstrukci´o h´atr´anya, hogy nem hat´ekony, gyakorlatban nem alkalmazhat´o. A mi eset¨ unkben ezenfel¨ ul nem tehet˝o fel az sem, hogy a r´esztvev˝oknek legfeljebb a fele nem becs¨ uletes. A biztons´agos t¨obbr´esztvev˝os sz´am´ıt´asoknak rengeteg alkalmaz´asa van, t¨obbek k¨oz¨ott a biztons´agos szavaz´as, illetve ´arverez´es. A fentebb felsoroltak k¨oz¨ ul a mi eset¨ unk legink´abb az els˝oa´ras aukci´ora hasonl´ıt, ´ıgy erre adott egy´eb megold´asok k¨oz¨ ul ismertet¨ unk n´eh´anyat. Brandt egy cikk´eben [1] mindj´art h´arom megold´ast is javasol, ebb˝ol az els˝ot ismertetj¨ uk r´eszletesebben, mivel hasonl´o elgondol´asokat haszn´alunk majd a feladat megold´as´ahoz. A modellben p´aronk´enti titkos csatorn´at t´eteleznek fel, valamint a 2.1. alfejezetben ismertetett param´etereket haszn´aljuk (n r´esztvev˝o, v licit´alhat´o a´r, de csak egyetlen term´ek). Az i-edik r´esztvev˝o a k¨ovetkez˝oket csin´alja: 1. minden j licit´alhat´o a´rra v´alaszt egy v´eletlen Yij ´ert´eket, majd ezeket egym´as ut´an f˝ uzi ´es mindenkinek elk¨ uldi ennek a hash ´ert´ek´et, vagyis hash(Yi1 ||Yi2 || . . . ||Yiv )-t, ahol hash(.) egy biztons´agos hash-f¨ uggv´eny. 2. ha az aJ a´rra licit´al, akkor az YiJ -t, minden m´as j 6= J-re pedig a 0-t osztja sz´et addit´ıvan a t¨obbi r´esztvev˝onek. Ez azt jelenti, hogy v´alaszt n darab f¨ uggetlen v´eletlen ´ert´eket, amelyeknek az o¨sszege YiJ (vagy 0) ´es az ¨osszeg k-adik tagj´at elk¨ uldi a k-adik r´esztvev˝onek. 3. minden j a´rra o¨sszeadja a 2. l´ep´esben a t¨obbiekt˝ol kapott, erre a j-re vonatkoz´o ´ert´ekeket ´es ezt elk¨ uldi az o¨sszes t¨obbi r´esztvev˝onek 4. minden j a´rra o¨sszeadja a 3. l´ep´esben a t¨obbiekt˝ol kapott, erre a j-re vonatkoz´o ´ert´ekeket 5
Az a r´esztvev˝o nyer, akinek ez az ¨osszeg szerepel az Yij ´ert´ekei k¨oz¨ott, a nyertes a´r pedig az a legels˝o a´r, amelyikre ez nem nulla. A m´asodik megold´as ett˝ol mind¨ossze annyiban t´er el, hogy nem addit´ıv, hanem multiplikat´ıv csoportban dolgozik, ´ıgy az o¨sszegek a hatv´anykitev˝okben jelennek meg, valamint az ¨osszegeket elmaszkolja v´eletlen szorz´okkal. A harmadik megold´asban nehezebb probl´am´at old meg, a fent ismertetett m´asodik ´aras aukci´ot, itt tov´abbi tr¨ ukk¨oz´esek sz¨ uks´egesek ahhoz, hogy csak a m´asodik legmagasabb ´ar ker¨ ulj¨on nyilv´anoss´agra a protokoll v´eg´en. Felsorolunk n´eh´any tov´abbi megold´ast els˝oa´ras a´rver´esekre a r´eszletek ismertet´es´et mell˝ozve. Az els˝o kriptogr´afiai eszk¨ozt´arat felvonultat´o megold´as Franklin ´es Reiter nev´ehez f˝ uz˝odik [4], a protokoll f˝obb ´ep´ıt˝ok¨ovei a titokmegoszt´asok, elektronikus p´enz ´es digit´alis al´a´ır´asok. Peng, Boyd ´es Dawson [7] homomorf titokmegoszt´asokat haszn´al, amivel nagyobb biztons´ag ´erhet˝o el, mint a hagyom´anyos titokmegoszt´asokat haszn´al´o rendszerekn´el. Brandt egy k´es˝obbi cikk´eben [2] homomorf titkos´ıt´asokat haszn´al az ´arver´esi protokoll konstrukci´oj´ahoz. Suzuki, Kobayashi ´es Morita [8] megold´as´aban hash-l´ancokat haszn´al. Nojoumian ´es Stinson [6] friss cikk´eben szint´en h´arom megold´ast javasol, a kor´abbiakt´ol annyiban elt´erve, hogy a javasolt protokollok felt´etel n´elk¨ uli biztons´agot garant´alnak.
3. 3.1.
Biztons´ agos ´ arverez˝ o protokoll t¨ obbt´ argyas licitre A protokoll inform´ alis ismertet´ ese
A protokollt h´arom f˝obb f´azisra bontjuk, ezek a k¨ovetkez˝ok: Regisztr´ aci´ o Els˝o l´ep´esk´ent az ´arver´est lebonyol´ıt´o nyilv´anoss´agra hozza az a´rver´es param´etereit (a t´argyak darabsz´am´at, a licit´alhat´o ´arakat, illetve a k´es˝obbi kommunik´aci´ohoz sz¨ uks´eges biztons´agi param´etereket). Ebben a l´ep´esben ´ep´ıtik ki az a´rver´esben r´esztvev˝ok a biztons´agos kommunik´aci´os csatorn´akat. Ez a l´ep´es offline is elv´egezhet˝o, nem sz¨ uks´eges k¨ozvetlen¨ ul az ´arver´es el˝ott megtenni, erre b´armilyen nyilv´anos biztons´agos fel¨ ulet elegend˝o. Licit´ al´ as Minden r´esztvev˝o eld¨onti, hogy h´any darab t´argy´ert mekkora ´arat hajland´o fizetni. Ezut´an ezeket egy v´eletlen sorozattal, valamint ennek 6
a h´arom sorozatot digit´alisan al´a´ırva ¨osszehasheli ´es elk¨ uldi a t¨obbi r´esztvev˝onek (vagy ki´ırja egy mindenki ´altal el´erhet˝o nyilv´anos fel¨ uletre), ez lesz a bor´ıt´ek”, amiben a licit van. Az ´arver´est lebonyol´ıt´o ” jelzi a licit´al´as v´eg´et, az ez ut´an ´erkez˝o liciteket m´ar nem vessz¨ uk figyelembe, valamint a tov´abbiakban csak azokat tekintj¨ uk r´esztvev˝onek, akik licit´altak. Ki´ ert´ ekel´ es Itt egy ciklusban a legnagyobb ´art´ol lefel´e megn´ezik a r´esztvev˝ok, hogy az aktu´alis ´arra ´erkeztek-e licitek, ha nem, mennek a k¨ovetkez˝o legmagasabb ´arra. Ha igen, akkor ez a nyertes a´r, akkor az erre az ´arra licit´al´ok kinyitj´ak” a bor´ıt´ekaikat oly m´odon, hogy az ehhez tartoz´o ” darabsz´amot ´es v´eletlen ´ert´eket nyilv´anoss´agra hozz´ak. Ekkor mindenki sz´am´ara nyilv´anos lesz a nyertes ´ar ´es darabsz´am is, valamint megbizonyosodhatnak arr´ol, hogy nem t¨ort´ent csal´as. Ha az adott ´arra licit´al´ok o¨sszes darabsz´ama kisebb, mint ah´any t´argy van ¨osszesen, akkor minden gy˝oztes annyit kap, amennyire licit´alt, egy´ebk´ent pedig elosztj´ak a nyertesek k¨oz¨ott a t´argyakat a darabsz´amuk ar´any´aban.
3.2.
Jel¨ ol´ esek
Az ´arver´essel kapcsolatos param´eterek a k¨ovetkez˝oek: • n : a licitben r´esztvev˝ok sz´ama • r0 : az a´rver´es vezet˝oje • r1 , r2 , . . . , rn : a licit´al´o r´esztvev˝ok • t : a licitre bocs´ajtott t´argyak sz´ama • v : lehets´eges aj´anlhat´o ´arak sz´ama • a1 > a2 > · · · > av : a lehets´eges aj´anlhat´o a´rak halmaza A felhaszn´alt kriptogr´afiai algoritmusokkal kapcsolatos param´eterek a k¨ovetkez˝oek: • Hash(.) : kriptogr´afiailag biztons´agos u ¨tk¨oz´esmentes hash-f¨ uggv´eny • si : az ri r´esztvev˝o kommunik´aci´ohoz haszn´alt titkos kulcsa 7
• Signs (m) : az m u ¨zenet digit´alisan al´a´ırva az s kulccsal a Sign(.) digit´alis al´a´ır´asi algoritmussal • pi : az ri r´esztvev˝o a´ltal aj´anlott a´r • di : az ri r´esztvev˝o a´ltal aj´anlott darabsz´am, bin´arisan dlog2 te biten a´br´azolva • li := (pi , di ), az ri r´esztvev˝o licitje
3.3.
Egy megval´ os´ıt´ asi javaslat/ A protokoll r´ eszletes specifik´ aci´ oja
Az al´abbiakban a protokoll fent ismertetett f´azisait fejtj¨ uk ki r´eszletesebben. 3.3.1.
Regisztr´ aci´ o
1. r0 nyilv´anoss´agra hozza a biztons´agi param´atereket: milyen titkos´ıt´ast, hash-f¨ uggv´enyt (Hash(.)), digit´alis al´a´ır´ast (Sign(.)) haszn´alnak a protokoll sor´an, valamint ezek param´etereit 2. a r´esztvev˝ok ki´ep´ıtik a p´aronk´enti titkos´ıtott kommunik´aci´os csatorn´akat a fenti param´eterek alapj´an. A tov´abbiakban feltessz¨ uk, hogy minden kommunik´aci´o ezeken a csatorn´akon kereszt¨ ul t¨ort´enik. 3. r0 titkos csatorn´an elk¨ uldi minden ri licit´al´oknak az a´rver´es param´etereit: (t, v, a1 > a2 > · · · > av ) 3.3.2.
Licit´ al´ as
1. r0 nyilv´anoss´agra hozza a licit´al´asra vonatkoz´o id˝ot ´es jelzi a licit´al´as megkezd´es´et 2. minden ri r´esztvev˝o megv´alasztja az a´ltala aj´anlott pi a´rat ´es di darabsz´amot 3. minden ri r´esztvev˝o megv´alaszt egy zi fix hossz´ us´ag´ u v´eletlen bin´aris vektort ´es minden m´as r´esztvev˝onek elk¨ uldi az al´abbi k¨otelezv´enyt: Bi = Hash(pi ||di ||zi ||Signsi (pi ||di ||zi )) 8
4. r0 ellen˝orzi, hogy tart-e m´eg a licit ´es ha igen, akkor al´a´ırja a k¨otelezv´enyt ´es visszak¨ uldi ri -nek: Signs0 (Bi ). A v´eg´en ezzel lehet igazolni, hogy ´erv´enyes a licit. 5. r0 jelzi a licit v´eg´et (mindenkinek elk¨ uld egy ”V´ege a licitnek” u ¨zenetet). 3.3.3.
Ki´ ert´ ekel´ es
Az a´ltal´anoss´ag megszor´ıt´asa n´elk¨ ul feltehetj¨ uk, hogy minden r´esztvev˝onek van ´erv´enyes licitje, egy´ebk´ent a´tparam´eterezz¨ uk a feladatot. 1. j := 1 erre futtassunk egy ciklust 2. r0 jelzi az ´ert´ekel´es kezdet´et, ekkor a aj a´rra licit´al´oknak el˝ore meghat´arozott T id˝o a´ll rendelkez´esre, hogy jelentkezzenek a licitj¨ ukkel 3. ha nincs jelentkez˝o, akkor j := j + 1 ´es ugr´as a 1. l´ep´esre, egy´ebk´ent tov´abbmegy¨ unk 4. ekkor a nyertes ´ar a aj . tegy¨ uk fel, hogy a ri1 , ri2 , . . . , rib r´esztvev˝ok licit´altak erre az ´arra 5. minden ri nyertes elk¨ uldi minden m´asik r´eztvev˝onek a Licit´al´as 3. pontj´aban v´alasztott zi ´ert´ek´et ´es di darabsz´am´at ´es az Signsi (pi ||di ||zi ) al´a´ır´ast. Ekkor ezekb˝ol, valamint a kor´abban k¨ uld¨ott Bi k¨otelezv´enyb˝ol mindenki le tudja ellen˝orizni, hogy val´oban erre az ´arra licit´altak a nyertesek, valamint ha ig´eny van r´a, a nyertesek meg tudj´ak mutatni, hogy r0 al´a´ırta-e a licitj¨ uket. 6. legyen d := di1 + di2 + · · · + dib ha d ≤ t, akkor minden nyertes pontosan annyi darab t´argyat nyer el, amennyire licit´alt, egy´ebk´ent pedig az ri nyertes bdi /dc darab t´argyat nyer el. A ciklus itt meg´all.
9
Hivatkoz´ asok [1] Felix Brandt: Secure and Private Auctions without Auctioneers, Technical Report FKI-245-02 (2002) [2] Felix Brandt: How to obtain full privacy in auctions, International Journal of Information Security, 5 (4) (2006) 201–216 [3] Ronald Cramer: Introduction to Secure Computation, Lectures on Data Security, LNCS 1561 (1991) 16–62 [4] M. K. Franklin, M. K. Reiter: The design and implementation of a secure auction service, IEEE Transactions on Software Engineering, 22 (1996), 302–312 [5] Oded Goldreich, Silvio Micali, Avi Widgerson: How to play ANY mental game, Proceeding of STOC ’87 (1987) [6] Mehrdad Nojoumian, Douglas R. Stinson: Unconditionally Secure FirstPrice Auction Protocols Using a Multicomponent Commitment Scheme, In Proceedings of ICICS’2010. (2010) 266–280. [7] Kun Peng, Colin Boyd, Ed Dawson: Optimization of Electronic FirstBid Sealed-Bid Auction Based on Homomorphic Secret Sharing, Progress in Cryptology – Mycrypt 2005, LNCS 3715 (2005) 84–98. [8] Koutarou Suzuki, Kunio Kobayashi and Hikaru Morita: Efficient Sealedbid Auction using Hash Chain, Information Security and Cryptology – ICISC 2000, LNCS 2015 (2001) 183–191. [9] Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982 (1982) 160–164.
10
