Ověření rovnocennosti tajemství

hlasů
4

Alice a Bob jsou oba tajní agenti čtyřlůžkové, kteří by mohli pracovat pro USA, Rusko nebo Čína. Chtějí přijít s plánem, který by:

  1. Jsou-li oba pracují na stejné straně, dokázat to k sobě, aby mohli svobodně mluvit.

  2. Pokud pracují na různých stranách, nevystavuje žádné dodatečné informace, na které straně jsou na.

Oh, a vzhledem k citlivé povaze toho, co dělají, není důvěryhodná třetí strana, která může udělat srovnání pro oba.

Jaký protokol by měl být schopen uspokojit oba tyto potřeby?

V ideálním případě by jakýkoli protokol by být také schopen zobecnit na více účastníků a násobky států, ale to není podstatné.

Jsem zmatený nad ní na chvíli a nemůžu najít uspokojivé řešení, zejména kvůli stavu 2.

edit: Tady je původní problém, že mě motivovalo, abych hledat řešení. „Charlie“ Měl nějaké osobní fotky, že sdílené se mnou a později jsem zjistil, že mu také sdílel je s „Bob“. Oba jsme chtěli vědět, jestli jsme měli stejnou sadu fotek, ale zároveň, jestli Charlie nesdílí určitý foto s jedním z nás, pravděpodobně měl dobrý důvod, proč jsme nechtěli úniku informace.

Moje první myšlenka by byla pro každého z nás zřetězit všechny dostupné fotografie a poskytnout MD5 součet. Kdyby uzavřeno, pak jsme měli stejné fotografie, ale kdyby ne, ani jedna strana by vědět, jaké fotky druhý měl. Nicméně, jsem si uvědomil, že brzy poté, co tento systém bude stále unikat informace, protože Bob mohl generovat MD5 pro každou dílčí sadu fotografií, které měl, a pokud některý z nich souhlasilo mou částku, měl by vědět, jaké fotky jsem neměl. Ještě jsem se najít uspokojivé řešení tohoto konkrétního problému, ale myslel jsem, že bych to zobecnit, aby se zabránilo lidem, se zaměřením na údaje o mé situaci.

Položena 26/08/2009 v 23:52
zdroj uživatelem
V jiných jazycích...                            


9 odpovědí

hlasů
1

Pro oba problémy, můžete použít Secure dvou stran výpočetní rovnosti algoritmus. Existuje mnoho programů, například tím, že Damgardův, Fici, Kiltz, Nielsen a Toft: Bezpodmínečně Secure Constant Round Multi-Party výpočtu pro rovnost, srovnání, bity a umocňování .

Samozřejmě agent by mohl pokusit se představovat jako zástupce z jiné strany získat 1/3 možnost poznat pravou stranu jiného agenta, ale to se zdá nevyhnutelný.

Mnohem jednodušší režim foto-problému, který by měl být skoro stejně dobré jako bezpečné multiparty výpočtu, je následující:

  1. Alice a Bob třídí své obrázky a vytvářet SHA-512 hash.
  2. Alice pošle první bit její hash k Bobovi.
  3. Bob porovnává bit prvního bitu jeho hash. Pokud se liší, vědí, že se jim dostalo různé snímky. V opačném případě budou pokračovat.
  4. Bob pošle druhý kousek jeho hash k Alici.
  5. Alice tento bit zkontroluje a rozhodne, zda bude pokračovat.
  6. Pokračovat, dokud protokol přeruší nebo byly zkontrolovány všechny bity.
Odpovězeno 09/09/2009 v 11:24
zdroj uživatelem

hlasů
1

Pro vaše fotografie problém vyřešit, vytvořte hash pro všech podskupin vašich fotografií; náhodně vybrat podmnožinu z nich, a náhodné v dohodnutém množství náhodně generovaných hash hodnoty. Bob dělá to samé, a vyměňovat si tyto soubory. V případě, že podíl hodnoty hash, co Bob vás poslal, který odpovídá ty, které mohou vést k hešováním podmnožiny vašich fotografií se výrazně liší od toho, co jste očekávali, je pravděpodobné, že máte výrazně jiný korpus fotografií z něj. V případě, že podíl nahodilých hash Souhlasíte je vysoká, riskujete, že nemůže objevit malé rozdíly ve svých sbírek fotografií; v případě, že podíl je nízký, riskujete vystavení informace o chybějících fotografie; budete muset vybrat vhodný bod pro kompromis.

Odpovězeno 27/08/2009 v 00:44
zdroj uživatelem

hlasů
1

Takže jsou zaručeně čtyřlůžkových agenti? To znamená, že je zaručeno, že se tajně pracuje pro jednu frakci, zatímco předstírá, že bude pracovat pro sekundy, když předstíral, že pracovat pro třetina zatímco předstírá, že pracovat čtvrtina? Ty jsou omezeny pouze na USA, Rusko nebo Čína? Pokud ano, pak to znamená, že bude vždy existovat alespoň jedna frakce jsou oba předstírat, že pracovat a současně vlastně pracuje. Zdá se, že negovat jejich schopnost být čtyřlůžkových agenty, protože zcela jistě jeden z nich není možné pracovat pro Američany, zatímco tajně pracuje pro Američany, zatímco tajně pracuje pro Američany, zatímco tajně pracuje pro Američany.

Říkáte, že ideálním řešením by zobecnit libovolném počtu států a špionážní sloupků. Může míra tajného agenta-nost být buď vyšší, rovna nebo nižší než počet stavů? To by mohlo být důležité. Také je Alice vždy zaručeno, že mají stejný stupeň agenta-nost jako Bob? tedy budou vždy oba třílůžkových látky nebo aby byla vždy jak pětinásobný agenty? Operátor modulo napadne ...

Další podrobnosti prosím.

Jako potenciální odpověď, můžete vyjmenovat stavy do bitfield. USA = 1 Russia = 2, Čína = 4, Madagascar = 8, Tuva = 16 atd postavit zařízení, které je v podstatě AND gate. Alice buduje a přináší jednu polovinu a Bob staví a přináší jiný. Odděleny hadříkem, každý z nich stiskněte tlačítko stavu, ve kterém se opravdu pracovat pro. V případě, že výstup AND brány je vysoká, pak jsou na stejné straně. Pokud tomu tak není, pak se klidně sundat hadřík a odjíždějí s příslušnými polovinami svém počítači tak, že tlačítko není možné určit pomocí otisku prstu.

To není teoretická nebo přísné, ale praktické.

Odpovězeno 27/08/2009 v 00:03
zdroj uživatelem

hlasů
0

Photo scénář je nemožné dosáhnout:

Váš program je nemožné z důvodů, které si jen vzpomenete.

Uvažujme funkci f, která trvá dvě sady fotografií, S1 a S2. f (S1, S2) vrací true, jestliže s1 = s2 a false, jestliže s1! = s2. To znamená, že tato funkce zavádí systém, který chcete.

Bob může vždy dodat podmnožinu Fotografie není to co má, a zjistit, které fotografii Charlie nemá. Neexistuje žádný způsob, jak vyřešit tento problém, jakákoli funkce, která má tu vlastnost, kterou chcete nemůže mít jistotu, kterou chcete.

Špion Scénář je ještě Impossible:

Jako Kent Fredric poukázal scénář špionážní má ještě větší inherentní slabiny. Má všechny problémy foto scénáře, plus další slabinu má jen čtyři tajemství.

V foto scénáře, že by bylo velmi nepravděpodobné, že by Bob náhodně uhodnout jeden ze Charlies fotografiemi. To je triviální ve špionážní scénáře Bob uhodnout Alices volby (1/4). Tyto spys mají jen čtyři země, které může patřit k, protože jsou oba čtyřlůžkových agenti oba znají všechny tajné kódová slova pro každou zemi. Tak, Bob mohl předstírat, že pracuje pro Číňany testovat Alice.

Jiný typ řešení:

Některé plakáty si všimli, bezpečnost může být zvýšena, pokud oslabit přesnost f. Samozřejmě, pokud to není správné to, co má smysl. Navrhuji jiný typ řešení.

  • Nenechte srovnat stále stejné Fotografování více než jednou.

Strana, která si přeje zahájit srovnávání musí nejprve prokázat, že se jedná o nový srovnání a nepoužívá některý z obrazů z dřívějška.

Edit: Problémy s Double Hash

Dělám nějaké předpoklady o protokolu doublhash, ale ...

  1. Pro režim fotografického je doublehash protokol není o nic lepší než f, protože 62 bit tajné musí být konstruována z řady fotografií pro srovnání, aby meaningfull. Podmnožina útoku bylo uvedeno v původní otázce stále platí zde. Vyzkoušet všechny podmnožiny snímků k hrubé síle tajemství můžete vytvářet, tedy Bob může zjistit, jestli dokáže generovat stejné tajemství jako Alice.

Použití doublehash vlastnost Bob je stále možné hrubou silou tajného.

doubleHash(s1+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a))

doubleHash(s2+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a))

doubleHash(s3+doubleHash(b)) == doubleHash(aliceSecret+doubleHash(a))

Bingo, aliceSecret == S3.

DoubleHash je jen tak silný, jak je to těžké BruteForce buď A nebo B

Implementating DoubleHash

Namísto doubleHash (a + doubleHash (b)), zkuste doubleHash (a, md5 (b)). DoubleHash (a + doubleHash (b)), je špatné, protože Bob mohl generovat kolize hash jako tak:

doubleHash((12 + doubleHash(34)) + doubleHash(5678))  
= doubleHash((34 + doubleHash(12)) + doubleHash(5678))
= doubleHash(5678 + doubleHash(12 + doubleHash(34)) 
= doubleHash(5678 + doubleHash(34 + doubleHash(12)) 

Zde je implementace doubleHash pomocí nové formulace,

Doublehash(a, hashOfB){
   hashOfA = md5(a)
   combinedHash = hashOfA xor hashOfB
   return md5(combinedHash)
}

Dalo by se také použít matematiku za slepých podpisů impliment verzi doubleHash.

Odpovězeno 28/08/2009 v 06:58
zdroj uživatelem

hlasů
0

Nejjednodušší věc, kterou můžu myslet s fotografiemi, které by pravděpodobně pracovat je takto:

  1. Hash všechny dostupné fotografie s 4096 bitů hash.
  2. Třídit fotografie podle hash hodnoty. (Hashes jsou konec konců, jen řetězec reprezentace velkého počtu)
  3. pomocí tohoto pořadí řazení pomocí streaming systém pro trubku a prejt, ty fotky, jako by se jednalo o ojedinělý soubor.
  4. Podělte se o své hodnoty hash.
  5. V případě shody hash, máte stejné soubory. (Nízké nízké riziko nesprávného pozitivním výsledku, ale 4K hashování, jeho poněkud nepravděpodobné)

Existuje samozřejmě několik nedostatky se zde:

  1. Nesdílejí, kolik fotografií máte. V opačném případě by mohlo umožnit stranu s větším počtem fotografií dělat inteligentní permutace dat a odstranit snímky z hashe nastavit u kterých existuje podezření pravděpodobně nemáte, pomocí čísla jako vodítko, a najít (při velké výpočetní nákladů mysli) sada obrázků, které odpovídá vašemu hash.
  2. Mohou tak učinit 1 bez čísla, ale jeho těžší, a smůlu v případě, že skutečně mají méně fotografií.
  3. Mohly by vytvořit falešnou hash, jen s generátorem náhodných čísel, a odeslat ji na vás, takže máte dojem, že měli různé datové sady, když jste ve skutečnosti měl stejný.

Výše uvedené nedostatky jsou také převládající v systému identifikace kódu země, samozřejmě s výjimkou, máte mnohem menší entropii se dostat do cesty, a jeho mnohem jednodušší podvodu systém. (A tedy mnohem mnohem mnohem snazší zjistit, kdo jsou pouhou hrubou silou, nebo se sami vypracovali hrubou silou, bez ohledu na to, jak ozdobný vaše hash algoritmu je) Kdyby tomu tak nebylo, bys již bylo konstatováno ze strany samotných agentur, pro kterou pracujete, protože něco, spolehlivé a bezpečné bude jistý oheň způsob, jak provést bezpečné ověřením.

Odpovězeno 27/08/2009 v 02:06
zdroj uživatelem

hlasů
0

Zde je nejbližší jsem přišel do roztoku:

Předpokládejme, že existuje funkce taková, že doubleHash

doubleHash(a+doubleHash(b)) == doubleHash(b+doubleHash(a))

Alice vygeneruje 62 bitový tajemství a připojí kód 2 bitů zemi až do konce to, hash ji a dává Bob doubleHash (a).

Bob dělá totéž a dá Alici doubleHash (b).

Alice připojí původní tajemství hash, který jí dal Bob, hash ho a zveřejňuje jako doubleHash (a + doubleHash (b)).

Bob dělá totéž a publikuje doubleHash (b + doubleHash (a)).

Pokud odpovídají obě hodnoty hash, pak jsou ze stejné země. Na druhou stranu, pokud se neshodují, pak Bob nemůže rozluštit hash, protože neví, Alicin tajné a naopak.

Nicméně, takový systém se opírá o existenci funkce doubleHash a nejsem si jistý, jestli je to možné něco takového.

Odpovězeno 27/08/2009 v 00:28
zdroj uživatelem

hlasů
0

Zajímavý.

Myslím, že bez ohledu na to, jaký systém, bude to muset zahrnovat komponentu náhodné selhání. To je z důvodu protichůdných požadavků. Budete potřebovat program, který příležitostně, i když jsou na stejné straně, nefunguje. Protože jestli to vždycky fungovalo, okamžitě by bylo možné určit, které nejsou na stejné straně.

Své místo v ‚B‘, je také nejasné. Říkáte, že nechcete vystavit čí straně jsou na. Znamená to, že informace nemůže ukazovat na konkrétně jednu ze stran? Je to v pořádku, pokud Alice myslí, že Bob je buď z jedné z ostatních?

Také jste se snažil mailování to do mailing listu kryptografie ? Může získat lepší odezvu tam. Je to zajímavá přemýšlet :)

Odpovězeno 27/08/2009 v 00:21
zdroj uživatelem

hlasů
-1

Nebude RSA pracovat tady? Každý národ ví, že jeho soukromý klíč, můžete publikovat svůj veřejný klíč, a to pouze národy, které jsou stejné lze dešifrovat informace. Myslím, že druhá osoba bude vědět, že první není na stejné straně jako jsou, nicméně.

Hmm.

Odpovězeno 26/08/2009 v 23:57
zdroj uživatelem

hlasů
-2

Jak se o kryptografii veřejného klíče ?

Odpovězeno 26/08/2009 v 23:59
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more