Biztonságos árverezés megvalósítása
1
Tartalomjegyzék
1. Árverések fajtái
3
2. Megoldandó probléma
5
2.1.
A matematikai modell
. . . . . . . . . . . . . . . . . . . . . .
2.2.
Biztonsági feltételek, fenyegetésmodell
2.3.
Megoldások hasonló problémákra
6
. . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . .
7
3. Biztonságos árverez® protokoll többtárgyas licitre
9
3.1.
A protokoll informális ismertetése . . . . . . . . . . . . . . . .
9
3.2.
Jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3.
Egy megvalósítási javaslat/ A protokoll részletes speci kációja
10
3.4.
3.3.1.
Regisztráció . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3.2.
Licitálás . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3.3.
Kiértékelés . . . . . . . . . . . . . . . . . . . . . . . . .
Megvalósítási lehet®ségek programozhatósági szempontból
11
. .
12
3.4.1.
Di e-Hellman kulcscsere . . . . . . . . . . . . . . . . .
13
3.4.2.
Schnorr aláírási algoritmus . . . . . . . . . . . . . . . .
13
2
1.
Árverések fa jtái
Az árverés ®sid®k óta a kereskedelem egy meghatározott fajtája. Jószágok eladása során abban az esetben népszer¶ igazán az árverés, mikor a vev®k többet tudhatnak az áru értékér®l, mint az eladó. Az árveréseknek a következ® f®bb típusait különböztetjük meg:
Angol árverés Az angol árverés ( rst price open outcry, highest-price sale, legmagasabb ár) talán az egyik legelterjedtebb árverezési fajta.
Szabályok:
Minden résztvev® szabadon emelheti a licitjét.
Ha már senki
nem emel, a legmagasabb licitet tett résztvev® kapja meg az árut és ki zeti érte a licitjét.
Stratégiák:
A résztvev®k licitjeik sorozatára vonatkozó stratégiája függ (i)
attól, hogy nekik mennyit ér az áru, (ii) el®zetes becsléseikt®l, hogy a többieknek mennyit ér az áru (iii) az összes résztvev® addigi licitjeit®l. A licitek felülírhatók, ahogy az információs halmaz változik. Az angol árverésnél a domináns stratégiához addig kell az el®z® liciteket minimális egységgel növelni, amíg el nem éri azt az árat, amennyit nekünk ér. A licitálás megáll, mikor eléri a második legmagasabb rezervációs árat. Az optimális stratégia független a kockázatkerülést®l, ha a résztvev®k pontosan tudják, hogy nekik mennyit ér az áru, ha viszont csak becsülni tudják, akkor a kockázatkerül® résztvev®k óvatosabban kell, hogy licitáljanak. Mindig ez a domináns stratégia függetlenül attól, hogy a vev®k kockázatsemlegesek-e vagy sem.
Változatok: •
•
az árver® azonos összegekkel emeli a licitet;
az árver® mindig akkora összeggel emeli a licitet, amennyit éppen megfelel®nek tart;
•
a licitálók emelik a licitet meghatározott szabályok szerint.
Szabad kilépéses licit A szabad kilépéses licit (open exit auction, open ascending auction) az angol árverés japán változata.
Szabályok:
Az ár folyamatosan emelkedik és minden játékos nyilvánosan
jelzi, ha kiszáll (és ezután már nem térhet vissza). Ekkor a gy®ztes a második legmagasabb rezervációs árat zeti.
3
Stratégiák:
Egyéni értékelés¶ tárgynál ez ekvivalens az angol árveréssel.
Közös (vegyes) értékelés¶ tárgynál viszont számíthat, hogy mi kerül nyilvánosságra a licitekb®l, pl. kik estek ki és mikor, így a két árverés nem ekvivalens.
Els®áras tender Els®áras tender ( rst price sealed bid, versenytárgyalás, titkos licites tender)
árverezési rendszert alkalmaztak például a magyar privatizáció során
Szabályok:
Mindenki leadja a licitjét úgy, hogy nincs információja a többi-
ekér®l. A legmagasabb licitet leadó résztvev® ki zeti a licitjét és elnyeri az árut.
Stratégiák:
A játékosok stratégiája annak függvénye, hogy nekik mennyit
ér az áru, illetve hogy becsléseik szerint a többieknek mennyit ér. A módszer hátránya, hogy a gy®ztes elbukja a két legnagyobb licit közti különbséget.
Vickrey-aukció Az els®áras tender egy változata a Vickrey-aukció (second price sealed-bid, másodlicites versenytárgyalás, második áras tender, latelista árverés), melyet William Vickrey tiszteletére neveztek el, aki 1996-ban Nobel-díjat kapott az árverezési rendszer viszgálatáért.
Szabályok:
Mindenki leadja a licitjét, úgy hogy nincs információja a töb-
biekér®l. A legmagasabb licitet leadó résztvev® ki zeti a második legmagasabb licitet és elnyeri az árut.
Ki zetés:
A gy®ztes ki zetése: amennyit neki ér az áru mínusz a második
legnagyobb licit.
Stratégiák:
Egyéni értékelés¶ tárgynál akkora kell legyen a licit, amennyit
az áru a résztvev®nek ér, azaz a licit a saját rezervációs ár.
Ha va-
laki kevesebbet licitál, akkor kevesebb az esélye, hogy nyer, ugyanakkor ugyanannyit zet, ha mégis gy®z.
Egyensúlyban tehát mindenki
a saját rezervációs árát licitálja és a második legnagyobbat zeti ki a gy®ztes. Ha a játékosok pontosan tudják, hogy nekik mennyit ér az áru, akkor semmi nem múlik a kockázatsemlegességen. Az angol árverés és a Vickrey tender kimenetel szempontjából ekvivalens.
4
Holland árverés A holland árverés (virágvásár, csökken® áras aukció, descending price auction) egy f®ként Hollandiában (sajtok és friss virágok eladásakor használt) licitálási forma az árveréseken.
Szabályok:
Az árver® kihirdeti a licitet, amit folyamatosan csökkent egészen
addig, míg valamelyik résztvev® megállítja és elviszi az árut azon az áron.
Ki zetés:
A gy®ztes ki zetése: a rezervációs ára mínusz a licitje.
Stratégiák:
A játékosok stratégiája annak függvénye, hogy nekik mennyit
ér az áru, illetve hogy becsléseik szerint a többieknek mennyit ér. A holland árverés ekvivalens az els®áras árveréssel, azaz egy-egy értelm¶ megfeleltetés van a két játék stratégiahalmazai között. Ennek az az oka, hogy semmi releváns információ nem derül ki az árverés folyamán, csak a végén, amikor már túl kés® van ahhoz, hogy bárki változtasson a stratégiáján. A rst price aukcióban egy licit irreleváns, hacsak nem az a legmagasabb, és a holland árverésben megállítási ár (stopping price) szintén irreleváns, ha nem az a legmagasabb.
2.
Megoldandó probléma
A kit¶zött feladat leginkább az els®áras árverésre hasonlít, lényegében annak egy általánosításának tekinthet®.
A különbség az, hogy itt ugyanabból a
tárgyból (pl. érmékb®l, bélyegekb®l, stb) többet bocsátanak licitre és azokra egyszerre kell licitálni. A licitben szerepeltetni kell a termékért ki zetend® egységárat, valamint a kívánt darabszámot. A licitre bocsájtott tárgyak számát mindenki számára ismertnek tételezzük fel.
Minden esetben a legma-
gasabb egységárat ajánló(k) a nyertes(ek). Amennyiben többen ugyanazt a legmagasabb árat licitálták, a tárgyakat az általuk kívánt darabszámok arányában osztjuk el. A feladat egzakt matematikai modellje a 2.1. alfejezetben található. A résztvev®k között van egy kitüntetett szerepl®, a licit vezet®je, akinek egyetlen szerepe, hogy jelezze, mikortól nem lehet ajánlatokat tenni. A résztvev®k közötti további kommunikációba nem szól bele, nem licitál és nem is számol semmit (lényegében egy felhúzott ébreszt®órának tekinthet®).
A
résztvev®k közül kizárólag róla feltételezünk megbízhatóságot, a többiekr®l semmit nem teszünk fel.
5
Miután lezárult az árverés, a résztvev®k számolnak, illetve kommunikálnak egymással és ennek eredményeképpen a végén mindenki (de csak az árverésben résztvev®k) számára nyilvánosságra kerülnek a nyertesek, nyertesek ajánlatai, valamint a nyertesek által elnyert tárgyak számai, minden más információ titokban marad. Ezen felül feltételezzük, hogy a résztvev®k között páronkénti biztonságos kommunikációra van lehet®ség. A pontos biztonsági feltételezések és lehetséges támadások a 2.2. alfejezetben kerülnek kifejtésre.
2.1. A matematikai modell n, a résztvev®ket pedig r1 , r2 , . . . , rn , r0 -lal. Jelölje a licitre bocsájtott tárgyak
Jelölje a licitben résztvev®k számát jelöljük továbbá az árverés vezet®jét számát
t.
Az általánosság megszorítása nélkül feltehetjük, hogy legfeljebb
véges sok árat licitálhatnak a résztvev®k, legyen ez a szám
v,
a lehetséges
ajánlható árak halmaza pedig legyen rendezve szigorúan monoton csökken® sorrendben: Az
i-edik
a1 > a2 > · · · > av . résztvev® licitjét jelölje li , ez a következ® párból áll:
li = (pi , di ), ahol pi ∈ {a1 , a2 , . . . , av }, 0 ≤ di ≤ t, di ∈ Z, ahol
pi
jelöli az általa ajánlott árat,
di
pedig a darabszámot.
2.2. Biztonsági feltételek, fenyegetésmodell A következ®kben összefoglaljuk a biztonságos árverezési rendszerekkel szemben támasztott követelényeket. 1.
Tökéletes licit-anonimitás
(Perfect bid anonymity):
Az árverez®
rendszert®l megköveteljük, hogy a résztvev®k valamely részének licitjeir®l csak a résztvev®k komplementere tudhasson meg bárminem¶ információt. Ez a követelmény a szokásos anonimitás követelmény egy er®sítése. 2.
Önellen®rizhet®ség (Self verifying):
Minden résztvev® ellen®rizni tudja
az árverés kimenetelét. 3.
Általánosan ellen®rizhet® protokoll (Universal verifying):
Minden
résztvev® ellen®rizheti, hogy az összes licit gyelembe lett-e véve az árverés során. 4.
Igazságosság
(Fairness): Senkinek sincs semminem¶ információja a
licitekr®l/darabszámokról az árverés lezárásáig és akkor is csak a nyertes(ek)é kerül nyilvánosságra.
6
5.
Csalók elkapása (Catching cheaters):
A résztvev®k ki tudják mutatni,
ha csalás történt, és a csalót azonosítani tudják. 6.
Jegyz®könyvezhet®ség
(Opportunity to keep the transcript):
Ha
szükséges, az árverésr®l hiteles jegyz®könyv készíthet®. 7.
Technológiai függetlenség (Technology independent):
A licitálónak
csak a protokoll biztonságában és a saját eszközének helyesen m¶ködésében kell bíznia. 8.
Nyílt forráskód
(Open source, open code): A protokoll biztonsága
nem a megfelel® algoritmus titkosságától függ.
2.3. Megoldások hasonló problémákra Ha nagyon messzir®l tekintünk a feladatra, akkor valójában egy nagyon általános és sokat vizsgált problémának, az úgynevezett biztonságos többrésztvev®s számításoknak (az angol szakirodalomban secure multiparty compu-
tation) egy speciális esetével állunk szemben.
Az problémát el®ször Yao
vetette fel 1982-ben írt cikkében [11], legáltalánosabban a következ®képpen fogalmazható meg:
Biztonságos többrésztvev®s számítások probléma Adott r1 , r2 , . . . , rn résztvev®, mindegyik egy
n-változós
ri -nek
van egy saját titkos
si
értéke, valamint legyen
F
függvény, ami minden résztvev® számára ismert. A cél, hogy
a résztvev®k kiszámítsák az
F
függvény értéket az
(s1 , s2 , . . . , sn )
helyen, oly
módon, hogy semelyik résztvev® sem tudjon meg semmi olyan információt, ami ne következne a végeredényb®l, a saját titkos értékéb®, valamint az
F
függvényb®l.
Hogy az utolsó mondat kicsit világosabb legyen, ebben általában az is benne foglaltatik, hogy senkinek ne legyen semmilyen információja a többi résztvev® titkos értékér®l. (De ez nem minden esetben van így, például két résztvev® esetén legyen a kiszámítandó függvény a bemenetek összege, ekkor nyilván mindketten ki tudják számítani a másik titkos értékét is.) A témáról remek összefoglalót ad Cramer irománya [3]. Goldreich, Micali és Widgerson megmutatták, hogy az általános feladat megoldható abban az esetben, ha a résztvev®k többsége nem csal, lásd [6]. Valójában egy er®sebb eredményt bizonyítottak: az általuk adott konstrukciónál nem csak az lehetetlen, hogy a csalók nemkívánt titkokhoz jussanak, hanem az is biztosítva van, hogy amennyiben a csalók félbehagyják a protokollt, a becsületes résztvev®k nélkülük is ki tudják számítani a végeredményt (ezt robosztusságnak nevezik). A konstrukció két lényeges épít®köve
7
a nullismeret¶ bizonyítás (zero-knowledge proof ), illetve az ellen®rizhet® titokmegosztás (veri able secret sharing). A konstrukció hátránya, hogy nem
hatékony, gyakorlatban nem alkalmazható. A mi esetünkben ezenfelül nem tehet® fel az sem, hogy a résztvev®knek legfeljebb a fele nem becsületes. A biztonságos többrésztvev®s számításoknak rengeteg alkalmazása van, többek között a biztonságos szavazás, illetve árverezés. A fentebb felsoroltak közül a mi esetünk leginkább az els®áras aukcióra hasonlít, így erre adott egyéb megoldások közül ismertetünk néhányat. Brandt egy cikkében [1] mindjárt három megoldást is javasol, ebb®l az els®t ismertetjük részletesebben, mivel hasonló elgondolásokat használunk majd a feladat megoldásához. A modellben páronkénti titkos csatornát tételeznek fel, valamint a 2.1. alfejezetben ismertetett paramétereket használjuk (n résztvev®,
v
licitálható ár, de csak egyetlen termék). Az
i-edik
résztvev®
a következ®ket csinálja: 1. minden
j
licitálható árra választ egy véletlen
Yij
értéket, majd ezeket
egymás után f¶zi és mindenkinek elküldi ennek a hash értékét, vagyis
hash(Yi1 ||Yi2 || . . . ||Yiv )-t, 2. ha az
aJ
ahol
árra licitál, akkor az
hash(.) YiJ -t,
egy biztonságos hash-függvény.
minden más
j 6= J -re
pedig a 0-t
osztja szét additívan a többi résztvev®nek. Ez azt jelenti, hogy választ
n
darab független véletlen értéket, amelyeknek az összege
és az összeg 3. minden
j
k -adik
tagját elküldi a
k -adik
YiJ
(vagy 0)
résztvev®nek.
árra összeadja a 2. lépésben a többiekt®l kapott, erre a
j -re
vonatkozó értékeket és ezt elküldi az összes többi résztvev®nek 4. minden
j
árra összeadja a 3. lépésben a többiekt®l kapott, erre a
j -re
vonatkozó értékeket Az a résztvev® nyer, akinek ez az összeg szerepel az
Yij
értékei között, a
nyertes ár pedig az a legels® ár, amelyikre ez nem nulla. A második megoldás ett®l mindössze annyiban tér el, hogy nem additív, hanem multiplikatív csoportban dolgozik, így az összegek a hatványkitev®kben jelennek meg, valamint az összegeket elmaszkolja véletlen szorzókkal. A harmadik megoldásban nehezebb problámát old meg, a fent ismertetett második áras aukciót, itt további trükközések szükségesek ahhoz, hogy csak a második legmagasabb ár kerüljön nyilvánosságra a protokoll végén. Felsorolunk néhány további megoldást els®áras árverésekre a részletek ismertetését mell®zve. Az els® kriptográ ai eszköztárat felvonultató megoldás Franklin és Reiter nevéhez f¶z®dik [5], a protokoll f®bb épít®kövei a titokmegosztások, elektronikus pénz és digitális aláírások.
8
Peng, Boyd és Dawson [8] homomorf titokmegosztásokat használ, amivel nagyobb biztonság érhet® el, mint a hagyományos titokmegosztásokat használó rendszereknél. Brandt egy kés®bbi cikkében [2] homomorf titkosításokat használ az árverési protokoll konstrukciójához. Suzuki, Kobayashi és Morita [10] megoldásában hash-láncokat használ. Nojoumian és Stinson [7] friss cikkében szintén három megoldást javasol, a korábbiaktól annyiban eltérve, hogy a javasolt protokollok feltétel nélküli biztonságot garantálnak.
3.
Biztonságos árverez® protokoll többtárgyas licitre
3.1. A protokoll informális ismertetése A protokollt három f®bb fázisra bontjuk, ezek a következ®k:
Regisztráció
Els® lépésként az árverést lebonyolító nyilvánosságra hozza az
árverés paramétereit (a tárgyak darabszámát, a licitálható árakat, illetve a kés®bbi kommunikációhoz szükséges biztonsági paramétereket). Ebben a lépésben építik ki az árverésben résztvev®k a biztonságos kommunikációs csatornákat. Ez a lépés o ine is elvégezhet®, nem szükséges közvetlenül az árverés el®tt megtenni, erre bármilyen nyilvános biztonságos felület elegend®.
Licitálás
Minden résztvev® eldönti, hogy hány darab tárgyért mekkora árat
hajlandó zetni. Ezután ezeket egy véletlen sorozattal, valamint ennek a három sorozatot digitálisan aláírva összehasheli és elküldi a többi résztvev®nek (vagy kiírja egy mindenki által elérhet® nyilvános felületre), ez lesz a boríték, amiben a licit van. Az árverést lebonyolító jelzi a licitálás végét, az ez után érkez® liciteket már nem vesszük gyelembe, valamint a továbbiakban csak azokat tekintjük résztvev®nek, akik licitáltak.
Kiértékelés
Itt egy ciklusban a legnagyobb ártól lefelé megnézik a résztve-
v®k, hogy az aktuális árra érkeztek-e licitek, ha nem, mennek a következ® legmagasabb árra. Ha igen, akkor ez a nyertes ár, akkor az erre az árra licitálók kinyitják a borítékaikat oly módon, hogy az ehhez tartozó darabszámot és véletlen értéket nyilvánosságra hozzák. Ekkor mindenki számára nyilvános lesz a nyertes ár és darabszám is, valamint megbizonyosodhatnak arról, hogy nem történt csalás. Ha az adott árra
9
licitálók összes darabszáma kisebb, mint ahány tárgy van összesen, akkor minden gy®ztes annyit kap, amennyire licitált, egyébként pedig elosztják a nyertesek között a tárgyakat a darabszámuk arányában.
3.2. Jelölések Az árveréssel kapcsolatos paraméterek a következ®ek:
• n:
a licitben résztvev®k száma
• r0 :
az árverés vezet®je
• r1 , r2 , . . . , rn :
a licitáló résztvev®k
• t:
a licitre bocsájtott tárgyak száma
• v:
lehetséges ajánlható árak száma
• a1 > a2 > · · · > av :
a lehetséges ajánlható árak halmaza
A felhasznált kriptográ ai algoritmusokkal kapcsolatos paraméterek a következ®ek:
• Hash(.) : • si :
az
ri
kriptográ ailag biztonságos ütközésmentes hash-függvény
résztvev® kommunikációhoz használt titkos kulcsa
• Signs (m) :
az
m
üzenet digitálisan aláírva az
s
kulccsal a
Sign(.)
digi-
tális aláírási algoritmussal
• pi : • di :
az az
ri
résztvev® által ajánlott ár
ri
résztvev® által ajánlott darabszám, binárisan
dlog2 te
biten
ábrázolva
• li := (pi , di ),
az
ri
résztvev® licitje
3.3. Egy megvalósítási javaslat/ A protokoll részletes speci kációja Az alábbiakban a protokoll fent ismertetett fázisait fejtjük ki részletesebben.
10
3.3.1. Regisztráció 1.
r0
nyilvánosságra hozza a biztonsági paramátereket: milyen titkosítást,
hash-függvényt (Hash(.)), digitális aláírást (Sign(.)) használnak a protokoll során, valamint ezek paramétereit 2. a résztvev®k kiépítik a páronkénti titkosított kommunikációs csatornákat a fenti paraméterek alapján.
A továbbiakban feltesszük, hogy
minden kommunikáció ezeken a csatornákon keresztül történik. 3.
r0
titkos csatornán elküldi minden
ri
licitálóknak az árverés paraméte-
reit:
(t, v, a1 > a2 > · · · > av )
3.3.2. Licitálás 1.
r0
nyilvánosságra hozza a licitálásra vonatkozó id®t és jelzi a licitálás
megkezdését 2. minden
ri
résztvev® megválasztja az általa ajánlott
pi
árat és
di
darab-
számot 3. minden
ri
résztvev® megválaszt egy
zi
x hosszúságú véletlen bináris
vektort és minden más résztvev®nek elküldi az alábbi kötelezvényt:
Bi = Hash(pi ||di ||zi ||Signsi (pi ||di ||zi )) 4.
r0
ellen®rzi, hogy tart-e még a licit és ha igen, akkor aláírja a kötelez-
vényt és visszaküldi
ri -nek: Signs0 (Bi ).
A végén ezzel lehet igazolni,
hogy érvényes a licit. 5.
r0
jelzi a licit végét (mindenkinek elküld egy "Vége a licitnek" üzene-
tet).
3.3.3. Kiértékelés Az általánosság megszorítása nélkül feltehetjük, hogy minden résztvev®nek van érvényes licitje, egyébként átparaméterezzük a feladatot. 1.
j := 1
2.
r0
erre futtassunk egy ciklust
jelzi az értékelés kezdetét, ekkor a
tározott
T
aj
árra licitálóknak el®re megha-
id® áll rendelkezésre, hogy jelentkezzenek a licitjükkel
11
3. ha nincs jelentkez®, akkor
j := j + 1
és ugrás a 1. lépésre, egyébként
továbbmegyünk 4. ekkor a nyertes ár a
aj .
tegyük fel, hogy a
ri1 , ri2 , . . . , rib
résztvev®k
licitáltak erre az árra
ri nyertes elküldi minden másik réztvev®nek a Licitálás 3. pontjában választott zi értékét és di darabszámát és az Signsi (pi ||di ||zi ) aláírást. Ekkor ezekb®l, valamint a korábban küldött Bi kötelezvény-
5. minden
b®l mindenki le tudja ellen®rizni, hogy valóban erre az árra licitáltak a nyertesek, valamint ha igény van rá, a nyertesek meg tudják mutatni, hogy
r0
6. legyen
aláírta-e a licitjüket.
d := di1 + di2 + · · · + dib
annyi darab tárgyat nyer el, nyertes
bdi /dc
d ≤ t, akkor minden nyertes pontosan amennyire licitált, egyébként pedig az ri ha
darab tárgyat nyer el. A ciklus itt megáll.
3.4. Megvalósítási lehet®ségek programozhatósági szempontból Az alábbiakban néhány konkrét megvalósításhoz szükséges javaslatot ismertetünk.
(G, ·) ciklikus csoportot q elemmel, amelyben nehéz megoldani a Diszkrét Logaritmus Problémát és annak egy g generátorelemét, valamint egy biztonságos ütközésmentes Hash(.) hash-függvényt
1.
r0
választ egy
2.
r0
nyilvánosságra hozza a biztonsági paramátereket:
(G, q, g, Hash(.)) 3. az
ri
résztvev® választ magának egy véletlen
értéket (i
= 0, 1, . . . , n).
si ∈ {0, 1, 2, . . . , q − 1}
Ez lesz a kommunikációhoz használt titkos
kulcsa. 4. az az
ri si
résztvev® (i
= 0, 1, . . . , n)
rj (j 6= i résztvev®nek s kulcsát, g i -t. A kés®bbiekben
elküldi minden
titkos kulcshoz tartozó nyilvános
ez szükséges a digitális aláíráshoz, illetve ennek segítségével építik fel a páronkénti titkosított kommunikációs csatornákat.
Ez utóbbira a
Di e-Hellman kulcscsere protokollt javasoljuk [4], lásd 3.4.1 5. digitális aláírásokhoz a Schnorr aláírási algoritmust [9] javasoljuk, lásd 3.4.2
12
3.4.1. Di e-Hellman kulcscsere A Di e-Hellman kulcscsere egy lehetséges módja, hogy két résztvev®
pj
pi
és
egymással titkos kommunikációs csatornát építsen ki nyilvános kulcsok
segítségével. Az eljárás a következ® négy lépésb®l áll:
Kulcsgenerálás a pi résztvev® választ magának egy véletlen si ∈ {0, 1, 2, . . . , q− 1}
értéket. Ez lesz akommunikációhoz használt titkos kulcsa, az ehhez s tartozó nyilvános kulcsa pedig yi = g i (ugyanez pj -re is).
Kulcscsere
a
pi
átküldi
pj -nek yi -t, valamint pj átküldi pi -nek yj -t. ekkor s g si sj = yi j = yjsi értéket, ez lesz a közös
mindketten ki tudják számolni kulcsuk
Titkosítás
az
M
üzenet titkosításához
pi
kiszámolja
e = M g si sj -t és átküldi
pj -nek
Visszafejtés pj kiszámolja
az
yi
M -et
sj titkos kulcsa q−s M = e(yi j )
nyilvános kulcs és saját a következ® módon:
segítségével
3.4.2. Schnorr aláírási algoritmus Az aláírási algoritmus a következ® három f® fázisból áll:
Kulcsgenerálás a pi résztvev® választ magának egy véletlen si ∈ {0, 1, 2, . . . , q− 1} értéket.
Ez lesz az aláíráshoz használt titkos kulcsa, az ehhez tartozó s nyilvános kulcsa pedig yi = g i .
Aláírás
tegyük fel, hogy a
pi
résztvev® szeretné digitálisan aláírni az
M
üzenetet, ehhez a következ® lépések szükségesek:
•
választ egy véletlen
k ∈ {1, 2, . . . , q − 1}
•
legyen
e = Hash(m||g )
•
legyen
s = (k − si e) mod q
Ekkor az
Ellen®rzés
értéket
k
M
üzenet aláírása az
(e, s)
rendezett pár.
tetsz®leges résztvev® szeretné leellen®rizni az
segítségével, hogy az
(e, s) pár valóban az M
résztvev® írta alá:
•
legyen
rv = g s yie
•
legyen
ei = Hash(M ||rv )
Amennyiben
e = ev ,
akkor az aláírás helyes.
13
yi
nyilvános kulcs
üzenethez tartozik és a
pi
Hivatkozások [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) 201216
[3] Ronald Cramer: Introduction to Secure Computation, Lectures on Data Security, LNCS 1561 (1991) 1662 [4] Whit eld Di e, Martin E. Hellman: New Directions in Cryptography, IEEE Transactions on Information Theory,
22 (1976) 644654
[5] M. K. Franklin, M. K. Reiter: The design and implementation of a secure auction service, IEEE Transactions on Software Engineering,
22
(1996),
302312 [6] Oded Goldreich, Silvio Micali, Avi Widgerson: How to play ANY mental game, Proceeding of STOC '87 (1987) [7] Mehrdad Nojoumian, Douglas R. Stinson: Unconditionally Secure FirstPrice Auction Protocols Using a Multicomponent Commitment Scheme, In Proceedings of ICICS'2010. (2010) 266280. [8] 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) 8498. [9] Claus-Peter Schnorr: E cient Signature Generation by Smart Cards, J. Cryptology
4 (3) (1991) 161174.
[10] Koutarou Suzuki, Kunio Kobayashi and Hikaru Morita: E cient Sealedbid Auction using Hash Chain, Information Security and Cryptology ICISC 2000, LNCS 2015 (2001) 183191. [11] Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982 (1982) 160164.
14
