3

私は、お互いを信頼していない 2 つのクライアント間で既知の値 (トランプのデッキなど) の配列をシャッフルする方法を探しています。

これまでのところ私は考えています...

for each item in array:
  A tells B random number to use (Ra1) <~ prevent B from using pre-calculated password
  B creates secret random number, and shows hash to A <~ can prove this number is used
  B adds his own secret random number (Ra1+Rb1) <~ prevent A from using pre-calculated password
  B encrypts a random array value using the combined password (Ra1+Rb1), removing from the stack
  B gives encrypted value to A
  A re-encrypts the value <~ prevent B from recognizing his package later
  A stores at random index in new array of unknown items

A shows the full array to B <~ B can be confident that the array will not be tampered with
A does not know what is in each package, nor does B
B can now choose a package for himself, and A can then provide the password for that package, allowing B to recognize his package, and know the contents.
A can also choose a package, and request the key to unlock it form B.

After all transactions are agreed, and secrecy is no longer required, all secrets are revealed by both parties, who can both then verify the contents of the boxes

これはすべて私には非常に複雑に思えます-そして、当事者が信頼できる、または信頼できる必要がないような方法でA、B、およびCに対して機能させる方法を想像できません(後でキーを提供しない可能性があります-間のトランザクションを妨害します他の当事者）。

概要

理想的には、少なくとも 2 人の利害関係者が相互に情報を提供している限り、デックとカードをすべての関係者が後で検証できるように、2 つの信頼できない関係者の間でカードのデッキをシャッフルするアルゴリズムが必要です。最後に秘密。

4

1 に答える 1

6

これは、有名なメンタル ポーカーの問題です。１つの解決策は可換暗号化（すなわち、Ｅ１（Ｅ２（Ｍ））＝＝Ｅ２（Ｅ１（Ｍ）））を含む。

ウィキの記事から：

  1. Alice と Bob は、カードの特定の「デッキ」について同意します。実際には、これは、セットの各要素がカードを表すような一連の数字またはその他のデータに同意することを意味します。
  2. Alice は暗号化キー A を選び、これを使用してデックの各カードを暗号化します。
  3. アリスはカードをシャッフルします。
  4. アリスは、暗号化されシャッフルされたデックをボブに渡します。暗号化が行われると、Bob はどのカードがどれであるかを知ることができなくなります。
  5. ボブは暗号化キー B を選び、これを使用して、暗号化およびシャッフルされたデックの各カードを暗号化します。
  6. ボブはデックをシャッフルします。
  7. ボブは二重に暗号化され、シャッフルされたデックをアリスに返します。
  8. Alice は自分の鍵 A を使用して各カードを復号化します。ただし、Bob の暗号化はそのまま残されるため、どのカードがどれであるかを知ることはできません。
  9. Alice は各カード (A1、A2 など) に対して 1 つの暗号化キーを選択し、それらを個別に暗号化します。
  10. アリスはデックをボブに渡します。
  11. ボブは自分の鍵 B を使用して各カードを復号化します。ただし、アリスの個別の暗号化はそのまま残されるため、アリスはどのカードがどれであるかを知ることができません。
  12. ボブは各カード (B1、B2 など) に対して 1 つの暗号化キーを選択し、それらを個別に暗号化します。
  13. ボブはデックをアリスに返します。
  14. アリスは、プレイするすべての人のためにデッキを公開します。
    [...]
    このアルゴリズムは、任意の数のプレーヤーに対して拡張できます。

これにより、カードをシャッフルすることができ、どちらの側もチートすることができず、どちらの側も相手が何のカードを持っているかを知る必要がありません (最後の要件を削除して公正なシャッフルのみが必要な場合、問題ははるかに簡単になります)。

使用する暗号化は、既知の平文攻撃に対して安全でなければなりません。

于 2012-08-24T21:38:34.183 に答える