Er zijn hier veel vragen over de details en how-to “s van” verminkte circuits “, maar ik heb niets gezien dat definieert wat onleesbare circuits zijn .

Wat is precies een vervormd circuit? Waar zijn ze voor bedoeld? Wat zijn hun beperkingen?

De tag voor verminkte circuits zegt alleen dat ze worden gebruikt in veilige berekeningen met meerdere partijen. dit antwoord stelt echter dat ze “alleen geschikt zijn voor berekeningen met twee partijen?

Deze vraag zoekt naar de definitie van een “circuit”. Wat is het verschil tussen een circuit en een vervormd circuit?

Opmerkingen

  • Je vindt een goede uiteenzetting van Yao ' s vervormde circuits-protocol voor veilige berekeningen van twee partijen in dit boek . Het ' is duur, maar je plaatselijke universiteitsbibliotheek heeft het misschien.
  • Ik raad deze video , en dias

Antwoord

Een circuit is slechts een manier om een berekening weer te geven. Er is niets specifieks cryptografisch aan een circuit. Het betekent gewoon een lineaire berekening (geen looping of flow-control constructies) die alleen bestaat uit bewerkingen op bits , zoals AND, OR, NOT.

A verminkt circuit is een manier om “een berekening te versleutelen” die alleen de uitvoer van de berekening onthult, maar niets onthult over de invoer of enige tussenliggende waarden . We gebruiken de term “circuit” omdat verminkte circuits werken door de berekening die u belangrijk vindt, uitgedrukt als een circuit , en vervolgens wat cryptografische dingen uit te voeren voor elke bewerking (EN, OF, NIET) in het circuit .

Als we wat nauwkeuriger willen zijn, bestaat een “vervormingsschema” uit:

  • (Garble) Een manier om een (gewoon) circuit $ C $ in een verminkt circuit $ \ widehat C $.

  • (coderen) Een manier om elke (gewone) invoer $ x $ te converteren voor het circuit in een verminkte invoer $ \ widehat x $. Je hebt de geheime willekeur nodig die werd gebruikt om het circuit te misleiden om $ x $ in $ \ widehat x $ te coderen.

  • (Evalueer) Een manier om een verminkt circuit $ \ widehat C $ en vervormde input $ \ widehat x $ en bereken de circuitoutput $ C (x) $. Iedereen kan dit doen, je hoeft $ x $ of de geheime willekeur in $ \ widehat C $ niet te kennen om $ C (x) $ te evalueren en te leren.

Ik vereenvoudig hier een beetje. Maar het belangrijkste idee van beveiliging is dat $ \ widehat C $ en $ \ widehat x $ samen niet meer informatie lekken dan $ C (x) $. In het bijzonder onthullen ze niets over $ x $, maar ze laten de berekening $ C (x) $ toe (onbewust). Dit is wat ik bedoel met “het versleutelen van een berekening”.

De belangrijkste toepassing voor verminkte schakelingen is veilige twee-partijberekeningen. Stel je voor dat Alice privé-invoer $ x $ heeft en Bob privé-invoer $ y $. Ze zijn het eens over een functie $ f $ en zijn het erover eens dat ze allebei $ f (x, y) $ willen leren, maar niet willen dat hun tegenstander iets meer leert dan $ f (x, y) ) $. Om dit te bereiken, kunnen ze het volgende doen (dit is het klassieke protocol van Yao):

  1. De partijen zijn het eens over een manier om $ f $ uit te drukken als een (gewone ) circuit. Alice vervormt het circuit $ f \ mapstom \ widehat f $. Ze stuurt $ \ widehat f $ naar Bob evenals haar eigen “verminkte invoer” $ \ widehat x $.

  2. Alice weet hoe ze elke invoer voor $ f $ moet coderen in een “verminkte” invoer, maar alleen Bob kent zijn privé-invoer $ y $. Dus regelen de partijen dat Bob een verminkte versie $ \ widehat y $ ophaalt zonder dat Alice erachter komt wat $ y $ was. Dit kan gedaan worden met een primitief genaamd onbewust overdracht.

  3. Nu heeft Bob het verminkte circuit $ \ widehat f $ en een verminkte invoer $ \ widehat x, \ widehat y $ voor dat circuit. Hij kan dan de evaluatieprocedure uitvoeren en $ f (x, y) $ leren. Hij kan $ f (x, y) $ aan Alice onthullen.

We kunnen stellen dat het protocol niet meer dan $ f (x, y) $ onthult in het volgende manier:

  • Alice ziet niets anders dan het laatste antwoord $ f (x, y) $ in dit protocol (de beveiliging van onbewuste overdracht zorgt ervoor dat ze niets leert 2).

  • Ook al ziet Bob $ \ widehat f $, $ \ widehat x $ en $ \ widehat y $, de beveiliging van verminkte circuits zorgt ervoor dat deze waarden niet ” t onthullen iets anders dan $ f (x, y) $.

Deze benadering werkt wanneer Alice & Bob half eerlijk is (dwz ze volgen het protocol volgens de instructies). Maar als Alice kwaadaardig is, kan ze een andere functie $ f “$ onleesbaar maken in plaats van de $ f $ die ze afgesproken hadden.Er moeten dus andere dingen aan het protocol worden toegevoegd om dit te voorkomen, wanneer we beveiliging tegen kwaadwillende tegenstanders willen.

Referentiemateriaal:

Opmerkingen

  • Hoe vervormt Bob y zonder de geheime willekeur te kennen die Alice koos toen ze het vervormingsschema bedacht?
  • De verminkte codering werkt bit voor bit. Neem Bob s eerste bit. Alice kan bij zichzelf denken: " als Bob bit 0 heeft ingevoerd, dan zou zijn verminkte codering $ G_0 $ moeten zijn. Als hij bit 1 heeft ingevoerd, moet zijn verminkte codering $ G_1 $ zijn. " Onbewuste overdracht is een primitief waarbij Alice twee strings $ G_0, G_1 $ geeft als input. Bob geeft een beetje $ b $ als invoer en leert $ G_b $ (maar niet de andere $ G_ {1-b} $). Alice leert niet ' $ b $. De partijen kunnen een onwetende overdracht uitvoeren voor elk bit van Bob ' s invoer. Wat betreft hoe onbewust overdracht echt werkt, dat is een andere vraag;)
  • Naast Yao kan ' s verminkte circuit ' kan niet opnieuw worden gebruikt. Kunt u alstublieft mijn verwarring oplossen dat " Is het toegestaan om verschillende sleutels toe te wijzen telkens wanneer een vervormd circuit wordt uitgevoerd of wanneer sleutels zijn vastgelegd voor invoerbit 0 en 1 "

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *