驗證祕密的等價性

Question

Alice &鮑勃是祕密的四人代理人，他們可能在美國，俄羅斯或中國工作。他們想要制定一個計劃：

1. 如果他們都是爲同一方工作，請相互證明以便他們可以自由交談。

2. 如果他們正在爲不同的方面工作，不暴露他們在哪一邊的任何額外的信息。

哦，並且由於他們所做的事情很敏感，沒有可以爲他們做比較的可信第三方。

什麼協議能夠滿足這兩個需求？

理想情況下，任何協議也可以推廣到多個參與者和多個國家，但這不是必需的。

我困惑過了一段時間，我無法找到一個滿意的解決方案，這主要是由於條件2

編輯：下面是促使我尋找一個解決原來的問題。 「查理」有一些他與我分享的個人照片，我後來發現他也與「鮑勃」分享了他們。我們都想知道我們是否有相同的照片，但同時，如果查理沒有與我們任何一個人分享某張照片，他可能有一個很好的理由不會泄漏，我們也不想泄漏信息。

我的第一個想法是我們每個人都連接所有的照片，並提供MD5總和。如果他們匹配，那麼我們有相同的照片，但如果他們沒有，那麼任何一方都不知道對方有哪些照片。不過，我很快意識到這個方案仍然會泄漏信息，因爲鮑勃可以爲每張照片的子集生成MD5，如果其中任何一張匹配了我的總和，他就會知道我沒有的照片。我還沒有找到一個令人滿意的解決方案來解決這個問題，但我想我會推廣它，以避免人們關注我的具體情況。

Answer 1

對於這兩個問題，您可以使用Secure two-party computation等效算法。有很多方案，例如Damgard，Fitzi，K​​iltz，Nielsen和Toft的方案：Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation。

當然，代理人可以嘗試從另一方冒充代理人，以獲得1/3機會來發現另一代理人的真實面，但這似乎是不可避免的。

一個更簡單的照片的問題，這應該是幾乎一樣的安全多方計算好方案，如下：

1. Alice和Bob排序他們的照片，並生成一個SHA-512散列。
2. Alice將她的散列的第一位發送給Bob。
3. Bob將該位與他的散列的第一位進行比較。如果不同，他們知道他們收到了不同的照片。否則，他們繼續。
4. Bob將他的散列的第二位發送給Alice。
5. Alice檢查這一點並決定是否繼續。
6. 繼續，直到協議中止或檢查所有位。

Answer 2

RSA不在這裏工作嗎？每個國家都知道自己的私鑰，發佈公鑰，只有相同的國家才能解密信息。然而，我想第二個人會知道，第一個人不是和他們在同一方。

嗯。

Answer 3

Public Key Cryptography怎麼樣？

Answer 4

所以他們保證是四倍代理？那就是他們保證祕密爲一個派別工作，而假裝工作一秒鐘，假裝工作三分之一，假裝工作四分之一？它們僅限於美國，俄羅斯或中國？如果是這樣的話，那意味着至少會有一個派系假裝爲同事工作。這似乎否定了他們成爲四人代理人的能力，因爲他們當中有一個不能爲美國人工作，同時暗中爲美國人工作，同時爲美國人祕密工作，同時爲美國人祕密工作。

你說理想的解決方案會推廣到任意數量的狀態和間諜堆棧。特務的程度可以高於，等於或低於州的數量？這可能很重要。另外，愛麗絲是否總是保證與鮑勃具有相同的代理人水平？即他們總是會成爲三重代理人，或總是由五元代理人？模數操作員想起...

更多詳情請。

作爲一個潛在的答案，你可以枚舉狀態到一個位域。美國= 1俄羅斯= 2，中國= 4，馬達加斯加= 8，圖瓦= 16等。構建一個基本上是與門的設備。愛麗絲建造並帶來一半，鮑勃建立並帶來另一半。用布分開，每按一下他們真正爲之工作的狀態的按鈕。如果與門的輸出高，那麼它們在同一側。如果沒有，那麼他們就悄悄地取下布，然後與他們的機器的兩半分開，以便不能通過指紋確定按鈕。

這不是理論性的或嚴謹的，而是實用的。

Answer 5

有趣。

我認爲，不管是什麼方案，它都需要涉及一個隨機失敗的組件。這是因爲相互矛盾的要求。你需要一個計劃，即使他們在同一方面，偶爾也是行不通的。因爲如果它一直有效，他們會立即能夠確定它們不在同一側。

你的觀點'B'也含糊不清。你說你不想公開他們在哪一方。這是否意味着信息不能指向具體是其中一方？如果愛麗絲認爲鮑勃來自其中一人，這可以嗎？

另外，你有沒有嘗試過發郵件給cryptography mailing list？可能會在那裏得到更好的迴應。這是一個有趣的思考:)

Answer 6

這裏是我來解決最靠近：

假設有一個函數doubleHash這樣

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

愛麗絲生成一個62位祕密並將2位國家代碼附加到它的末尾，將其哈希並給出Bob doubleHash（a）。

Bob做同樣的事情，並給予愛麗絲doubleHash（b）。

Alice將原始祕密附加到Bob給予她的散列上，將其散列並將其發佈爲doubleHash（a + doubleHash（b））。

Bob做同樣的事情，併發布doubleHash（b + doubleHash（a））。

如果兩個哈希匹配，那麼它們來自同一個國家。另一方面，如果它們不匹配，那麼Bob就不能解密哈希，因爲他不知道Alice的祕密，反之亦然。

但是，這樣的方案依賴於doubleHash函數的存在，我不確定這樣的事情是否可能。

Answer 7

對於你的照片問題，爲你的照片的所有子集創建散列;隨機選擇其中的一個子集，並隨機生成一定數量的散列值進行混洗。鮑勃也是這樣做的，你們交換了這些集合。如果Bob向您發送的哈希值與您通過散列照片子集生成的哈希值相比所產生的哈希值的比例與您的期望值顯着不同，那麼很可能您的照片語料庫與他的顯着不同。如果您認爲隨機哈希的比例很高，那麼您可能無法檢測到您的照片集中的細微差異;如果比例較低，則可能會泄露有關丟失照片的信息;你將不得不爲折衷選擇一個合適的點。

Answer 8

最簡單的事情，我能想到的與將可能的工作是這樣的照片：

1. 哈希所有的照片，和4096位散列。
2. 按照散列值對照片進行排序。 （哈希是最後一個，只是一個大數字的字符串表示）
3. 使用該排序順序，使用流式系統對這些照片進行管道和散列，就好像它們是單個文件一樣。
4. 分享你的哈希。
5. 如果哈希匹配，則具有相同的文件。 （不正確的正匹配的低風險低，但在4K散列，它有點不太可能）

有當然，也有一些不足的位置：

1. 不要共享你有多少張照片有。這樣做可以允許擁有更多照片的派對對數據進行智能排列，並從他們懷疑可能沒有的散列集合中刪除照片，並以數字作爲指導，並找到（以極大的計算開支爲代價）一組與您的散列匹配的圖像。
2. 他們可以在沒有數字的情況下做1，但更難，而且如果他們實際上沒有照片，他們就會走運。
3. 他們可以使用隨機數字生成器創建一個假哈希，並將其發送給您，當您擁有相同的數據時，給您的印象是您擁有不同的數據集。

上述弱點也是在你的國家代碼識別系統普遍，當然除了，你有遠少熵的方式來獲得，其遠容易欺騙系統。 （因此，通過純粹的暴力來弄清楚他們是誰，或者通過暴力破解你自己，無論你的散列算法有多麼華麗） 如果情況並非如此，那麼你應該已經通過你工作的機構發現，因爲可靠和安全的東西將會是一種安全的背景檢查方式。

Answer 9

的照片場景是不可能實現的：

你的方案爲您命名的原因是不可能的。

考慮一個函數f，它需要兩組照片s1和s2。 如果s1 = s2，則f（s1，s2）返回true，如果s1！= s2則返回false。 也就是說，這個函數實現你想要的方案。

鮑勃可以隨時提供他擁有的照片的子集，並瞭解哪張照片的查理沒有。 沒有辦法解決這個問題，任何擁有你想要的屬性的函數都不能擁有你想要的安全性。

間諜情景更是不可能的：

由於Kent Fredric指出間諜方案具有更大的固有缺陷。 它具有照片場景中的所有問題，加上只有四個祕密的額外弱點。

在照片場景中，Bob很可能會隨機猜測Charlies照片中的一張。 Bob在間諜場景中猜測Alices選擇（1/4）是微不足道的。 間諜只有四個他們可以屬於的國家，因爲他們都是四個代理人，他們都知道每個國家的所有密碼字。因此，鮑勃可以假裝爲中國人工作來測試愛麗絲。

不同類型的解決方案：

一些海報已經注意到，能夠實現安全性，如果你減弱f的精度提高。 當然，如果不準確的話是什麼意思。我提出了一種不同類型的解決方案。

• 不要讓它們多次比較相同的 照片。

希望開始比較的一方必須首先證明這是一個新的比較，並且不使用之前的任何圖片。

編輯：問題與雙哈希

我提出有關doublhash協議的一些假設，但...

1. 對於照片方案中，doublehash協議不大於f好，因爲62位密碼必須由一組照片構成，以便進行比較以獲得有意義的結果。原始問題中提到的子集攻擊在這裏仍然適用。嘗試使用所有照片的子集來暴力化你可以產生的祕密，因此鮑勃可以看到他是否能夠產生與艾麗絲相同的祕密。

使用doublehash屬性Bob仍然可以暴力破解這個祕密。

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

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

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

賓果，aliceSecret == s3。

DoubleHash是僅作爲強，因爲它是難以暴力破解A或B

Implementating DoubleHash

相反doubleHash（A + doubleHash（b）中），試圖doubleHash（一個，MD5（二））。 DoubleHash（A + doubleHash（B））是不好的，因爲鮑勃可能產生衝突的哈希值，像這樣：

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

下面是使用新配方doubleHash的實現，

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

人們還可以使用在blind signatures之後的數學暗示doubleHash的版本。