Bitkötési protokoll - titkosítás
bites protokollt
Tájékoztatásképpen a bitkötési protokoll két résztvevő (a feladó és a vevő) titkosítási protokollja, amelyen keresztül a feladó az alábbiak szerint ad át tetszőleges $ b $ bitet a címzettnek. Először a kötési lépést végezzük. amelyen a feladó általában (interaktív módon) információt küld a címzettnek körülbelül $ b $ -ra, amit blobnak neveznek. de nem maga a $ b $ értéke. Ezután a közzétételi lépésben a feladó elküldi a $ b $ értéket a címzettnek, és bizonyítja neki, hogy ez az érték valóban megegyezik a kötési szakaszban kapott blobgal. Ezt a folyamatot blob expanziónak hívják $ b $ -ra. A bitkötési protokollnak meg kell felelnie a következő feltételeknek.
A bitekre való kötődésre vonatkozó protokollokat nagyszámú kriptográfiai protokoll létrehozására használják. Különösen az ilyen protokollok tartalmaznak olyan számítási számításokat is, amelyeknek számítása nulla, és a $ \ mathrm $ osztály nyelvét teljesen nulla megjelenítéssel rendelkező arguments.
A bitkötési protokollok informális jelentését a következő "protokoll" segítségével lehet bemutatni a valós életből. A kötési szakaszban a feladó a $ b $ bit értékét egy papírlapra írja, elhelyezi ezt a lapot a széfbe, és átadja ezt a biztonsági kódot (a kulcs nélkül) a címzettnek. Ebben az esetben a blob szerepe egy biztonságos, a $ b $ értékű. A közzétételi szakaszban a feladó elküldi a $ b $ értéket és a kulcsot a biztonságosnak a címzettnek. A vevő a fogadott billentyűvel megnyitja a széfet, és felismeri a blokknak megfelelő $ b $ beérkezett értéket, ha és csak akkor, ha ez egybeesik a biztonságos papírlapra rögzített értékével.
Folytatjuk a formális meghatározásokat. Modell protokoll kötelező a bit pár $ (\ cal S, \ cal R) $ interaktív valószínűségi polinomiális algoritmusok, ahol $ \ cal S $ szimulálja becsületes feladó és $ \ cal R $ - tisztességes címzettnek. A $ \ mathcal S $ és $ \ mathcal R $ közös bemenete $ 1 ^ n $, ahol $ n \ in \ mathbb N $ a stabilitási paraméter. Ezenkívül $ \ mathcal S $ algoritmust adunk a $ b $ bit bemenetére.
Az általánosság elvesztése nélkül feltételezzük, hogy a közzétételi lépés elküldi a küldőnek a $ b $ bit értékét és a feladó által a kötési szakaszban használt $ s $ bináris stringet. Ezután ellenőrizze a címzett $ megfelelő bit b $ Blob, hogy teszt megegyezik egy sorozata által vett üzenetek akkor abban a szakaszban a kötésben, $ \ operatorname ^ _ (1 ^ n) $, ahol $ R $ - véletlenszerű karakterlánc értéket használjuk a címzett a szakaszában a kötelező. A közzététel ilyen fázisát kanonikusnak nevezik. A fenti érvelés azt mutatja, hogy a bit-kötési protokoll meghatározásához elég csak a feladó és a vevő akcióinak leírása csak a kötési szakaszban. Ezzel az elgondolással azt gondoljuk, hogy a $ \ mathcal S $ és $ \ mathcal R $ algoritmusok csak a bit-to-bites protokoll kötését hajtják végre.
A titoktartás és az egyedüllét informális feltételei többféleképpen formalizálhatók. A bit-kötési protokollra vonatkozó minimumkövetelmény a számítástechnikai titkosság és a számítógépes egyediség tekintetében a következő feltételek teljesítése.
1. meghatározás számítási titoktartás; lásd még [1]
A bithez való kötés $ (\ mathcal S, \ mathcal R) $ protokollja kielégíti a számítógépes titkosság állapotát. ha bármilyen interaktív polinom valószínűségi algoritmus $ \ cal R „$ a család valószínűségi változók \ [\ left (\ left \ operatorname ^ _ (1 ^ n) \, \ right |. \ n \ in \ mathbb N \ right) \ quad \ text \ quad \ left (\ left \ operatorname ^ _ (1 ^ n) \, \ right |. \ n \ in \ mathbb n \ right) \] számítási megkülönböztethetetlen.
A 2. meghatározás számítási szempontból egyértékű; lásd még [1]
A bithez való kötés $ (\ mathcal S, \ mathcal R) $ protokollja kielégíti a számítógépes egyediség feltételét. ha minden interaktív polinomiális valószínűség algoritmushoz $ \ mathcal S '$, minden polinomiális valószínűség algoritmust $ \ mathcal A $ és bármely polinomiális $ p $, a mennyiség \ begin \ Pr_r \ left (\ vphantom> \ Pr \ left (\ cal A \ bal (1 ^ n, \ operatorname ^ _ (1 ^ n) \ right) = (s_0, s_1), \ jobbra. \ Jobb. \\ \ Qquad \ qquad \ left. \ Bal. \ Operatorname ^ _ (1 ^ n) = \ operatorname ^ _ (1 ^ n) = \ operatorname ^ _ (1 ^ n) \ right) \ geqslant \ frac1 \ right) \ vége hanyagul kicsi a $ n \ in \ mathbb N $ függvényében. Vannak külső valószínűsége átvette a véletlenszerű sorban algoritmus $ r $ $ \ cal R $, és a belső - a véletlen sorozatot algoritmus $ s $ $ \ cal S „$ és gyors véletlenszerű algoritmus $ \ cal A $ fix értéke $ r $.Definíció 3 bit-kötési protokoll
A bithez való kötődés protokollja a fenti típusú algoritmusok $ (\ mathcal S, \ mathcal R) $ párja, amely kielégíti a számítási titkosság és a számítógépes egyediség feltételeket.
A definíciók az 1. és 2. algoritmusokat $ \ cal S '$ és $ \ mathcal R' $ modellek rendre tisztességtelen feladó és tisztességtelen recipiens, és az algoritmus $ \ mathcal A $ kell érdemben $ \ operatorname ^ _ (1 ^ n) $ ( egy ismert stabilitási paraméterrel) talál egy pár vonalat, amelyek lehetővé teszik a tisztességtelen feladó számára, hogy mind a $ 0 $, mind a $ 1 $ blobokat megnyitja.