Täällä on paljon kysymyksiä ”väärennettyjen piirien” yksityiskohdista ja ohjeista, mutta en ole nähnyt mitään, joka määrittäisi, mitkä väärät piirit ovat .
Mikä on sekaisin piiri? Mihin niitä on tarkoitus käyttää? Mitkä ovat niiden rajoitukset?
Hämmentyneiden piirien tunniste sanoo vain, että niitä käytetään turvallisessa monen osapuolen laskennassa. tässä vastauksessa todetaan kuitenkin, että ne sopivat vain kahden osapuolen laskelmiin?
Tämä kysymys etsii piirin määritelmää. Mitä eroa piirillä ja sekavalla piirillä on?
Kommentit
- Löydät hyvän Yao-käsikirjan ' s väärennettyjen piirien protokolla suojatulle kahden osapuolen laskennalle tässä kirjassa . Se ' on kallista, mutta paikallisella yliopistokirjastossasi saattaa olla.
- Ehdotan tätä videota ja diat
Vastaa
A piiri on vain tapa esittää laskenta. Piirissä ei ole mitään erityistä salausta. Se tarkoittaa vain suoraviivaista laskutoimitusta (ei silmukointia tai virtauksen säätörakenteita), joka koostuu vain bittien operaatioista, kuten AND, OR, NOT.
A väärennetty piiri on tapa ”salata laskenta”, joka paljastaa vain laskennan tuotoksen, mutta ei paljasta mitään syötteistä tai mahdollisista väliarvoista . Käytämme termiä ”piiri”, koska sotkuiset piirit toimivat ottamalla sinulle välitettävä laskenta, ilmaistuna piiriksi , ja tekemällä sitten joitain salaustietoja jokaiselle piirin toiminnolle (JA, TAI, EI) .
Jos haluamme olla hieman täsmällisempi, ”sekoitusohjelma” koostuu:
-
(marmori) tapa muuntaa (tavallinen) piiri $ C $ sekaisin piiriksi $ \ widehat C $.
-
(Koodaa) Tapa muuntaa mikä tahansa (tavallinen) tulo $ x $ piirille hämmentyneeksi syötteeksi $ \ widehat x $. Tarvitset salaisen satunnaisuuden, jota käytettiin piirin sekoittamiseen koodaamaan $ x $ muotoon $ \ widehat x $.
-
(Arvioi) Tapa ottaa väärennetty piiri $ \ widehat C $ ja väärennetty syöttää $ \ widehat x $ ja laskea piirin ulostulo $ C (x) $. Kuka tahansa voi tehdä tämän, sinun ei tarvitse tietää $ x $ tai salaa satunnaisuutta $ \ widehat C $: ssa arvioidaksesi ja oppiaksesi $ C (x) $.
Yksinkertaistan täällä. Mutta turvallisuuden pääajatus on, että $ \ widehat C $ ja $ \ widehat x $ vuotavat yhdessä vain enemmän tietoja kuin $ C (x) $. Erityisesti ne eivät paljasta mitään arvosta $ x $, mutta ne sallivat laskennan $ C (x) $ tekemisen (unohtamattomasti). Tätä tarkoitan ”laskennan salauksella”.
Hämmentyneiden piirien pääsovellus on turvallinen kahden osapuolen laskenta. Kuvittele, että Alicella on yksityinen panos $ x $ ja Bobilla on yksityinen panos $ y $. He sopivat jostakin toiminnosta $ f $ ja sopivat, että molemmat haluavat oppia $ f (x, y) $, mutta eivät halua vastustajansa oppivan mitään muuta kuin $ f (x, y ) Tämän saavuttamiseksi he voivat tehdä seuraavaa (tämä on Yaon klassinen protokolla):
-
Osapuolet sopivat tavasta ilmaista $ f $ a (tavallisena) ) piiri. Alice sekoittaa piirin $ f \ mapsto \ widehat f $. Hän lähettää $ \ widehat f $ Bobille ja oman ”väärennetyn syötteen” $ \ widehat x $.
-
Alice tietää, kuinka koodata kaikki syötteet arvolle $ f $ ”hämmentynyt” syöte, mutta vain Bob tietää yksityisen panoksensa $ y $. Joten osapuolet järjestävät Bobin hakemaan väärennetyn version $ \ widehat y $ ilman, että Alice oppii, mikä oli $ y $. Tämä voidaan tehdä primitiivillä, jota kutsutaan tietämättömäksi siirtoksi.
-
Nyt Bobilla on sekoitettu piiri $ \ widehat f $ ja sekava syöttö $ \ widehat x, \ widehat y $ tälle piirille. Hän voi sitten suorittaa arviointimenettelyn ja oppia $ f (x, y) $. Hän voi paljastaa $ f (x, y) $ Alicelle.
Voimme väittää, että protokolla paljastaa enintään $ f (x, y) $ seuraavassa tapa:
-
Alice ei näe tässä protokollassa muuta kuin lopullista vastausta $ f (x, y) $ (tietämättömän tiedonsiirron turvallisuus varmistaa, että hän ei opi mitään vaiheittain 2).
-
Vaikka Bob näkee $ \ widehat f $, $ \ widehat x $ ja $ \ widehat y $, sotkuisten piirien turvallisuus varmistaa, että nämä arvot eivät ” Älä paljasta mitään muuta kuin $ f (x, y) $.
Tämä lähestymistapa toimii, kun Alice & Bob on puolirehellinen (ts. he seuraavat protokollaa ohjeiden mukaan). Mutta kun Alice on pahantahtoinen, hän voi sekoittaa jonkin muun toiminnon $ f ”$ sovitun $ f $: n sijaan.Joten protokollaan on lisättävä muita asioita, jotta tämä ei tapahtuisi, kun haluamme turvallisuutta haitallisia vastustajia vastaan.
Viitemateriaali:
- Yao-rakenne ja sen todistus turvallisuudesta (video), Yehuda Lindell
- Todiste Yaon protokollasta suojatulle kahden osapuolen laskennalle , Yehuda Lindell & Benny Pinkas
- Ripustettujen piirien perustukset , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
- Lyhyt historia käytännön piikkipiirin optimoinnista , videoni Useat ensimmäiset diat kattavat väärennettyjen piirien ”klassisen” rakentamisen.
Kommentit
- Kuinka Bob ryöstää y tietämättä salaista satunnaisuutta, jonka Alice valitsi ryöstöjärjestelmän keksimisen yhteydessä?
- Hämmentetty koodaus toimii vähitellen. Ota Bob ensimmäinen bitti. Alice voi ajatella itsekseen: " jos Bob on syöttänyt bitin 0, hänen hämmentävän koodauksensa tulisi olla $ G_0 $. Jos hänellä on syöttöbitti 1, hänen sekaannetun koodauksensa tulisi olla $ G_1 $. " Hämärä siirto on primitiivinen, jossa Alice antaa kaksi merkkijonoa $ G_0, G_1 $ syötteenä. Bob antaa syötteeksi vähän $ b $ ja oppii $ G_b $ (mutta ei toisen $ G_ {1-b} $). Alice ei opi ' t $ b $. Osapuolet voivat suorittaa tietämättömän siirron jokaiselle Bob ' -signaalin bitille. Mitä tulee miten unohdettu siirto todella toimii, se on toinen kysymys;)
- Yaon ' sekaannettu piiri voi ' ei saa käyttää uudelleen. Voitteko ratkaista epäilykseni siitä, että " sallitaanko eri avainten määrittäminen joka kerta, kun sekoitettu piiri suoritetaan tai avaimet on kiinnitetty tulobiteille 0 ja 1 "