各エージェントが独自の要素のみを知っているように、n個のエージェントにランダムに割り当てます。

Question

問題

私はプレーヤーにトランプをシャッフルして配布するアプリに取り組んでいます。挑戦として、私は信頼できる仲介者を必要としない方法でこの問題を解決しようとしました。

他の用語では、タスクは

の分散アルゴリズムを見つけることです。

• 一意に $ n $ エージェント番号 $ 1..N $
• 各エージェントが割り当てについて何も知らないが、それ自身の
• 代入を明らかにするときは、他のプレーヤーが割り当て
を確認できるようにします。

私達はまた、他の人の課題が各エージェントにとって利点であり、それ自身の最先端の不利な点を明らかにすると仮定する。エージェントはまた、他のすべてのエージェントから隠されているように互いに話すことができると仮定されています。

部分溶液

私が敵対者が協力しないという仮定の下でのみ作品を思いついた解決策。

アイデアは、 $ n $ のセットを作成し、各エージェントを1つのnonceに割り当てることです。その後、セットは、各エージェントがセットを一度だけ受信されるまで、他のすべての順序で隠された、すべての順序でエージェントに渡されます。エージェントがセットを受信するたびに、Nonceを新しいものと交換し、新しいNonceを記憶し、そのセットの受信を他のユーザーに確認します。この時点で、この時点で、すべてのエージェントが少なくとも1回のエージェントがそれらのノンスを交換した後、すべてのエージェントが少なくとも一度セットを受信し、それを認識することが不可能である。

最後のエージェントが2回目の設定を受け取ると、それを全員と共有し、すべてのエージェントは自分のNonceがセットに含まれていることを他のエージェントに確認します。その後、エージェントは、ランダムなシードの合意に基づいてセット内の各NONCEに数値を割り当て、必要な固有の割り当てを与えます。

所有権検証を許可するために、ノンスの代わりに、エージェントはセットに非通信のハッシュ値を設定し、検証が必要な場合にのみ実際のNONCEを明らかにします。

---

この解決策の問題は、敵対者がコラボレーションを許可されている場合、敵対者がセットを受け取るたびに、それらのバージョンを比較し、変更を識別し、どのNonceが他のエージェントに属するかを派生させることができます。それらに割り当てられます。

すべてのアイデアが高く評価されています！

Answer 1

この問題は、 mental poker 。

優れた小品 Shamirそのようなアルゴリズムを実装する方法についての実用的な方法を説明する、リベストとアドレーマ。

要約は金です：

2人の不正なプレーヤーは、カードを使わずにポーカーの公正なゲームをプレイすることができますか？

この論文は以下の回答を提供します：

1. いいえ。 （厳格な数学的証明が供給されています。）
2. はい。（正しい＆完全なプロトコル。）

基本的に、情報理論的な観点から、このようなゲームをプレイすることは信頼できる第三者なしでは不可能ですが、暗号機能を逆にするためによく知られている難しさを使用してプロトコルを設計することが可能です。

---

アルゴリズムは以下のように機能します。

$ n $ が持っているとします（ $ 1 $ から $ n $ ）プロトコルの各参加者は、秘密関数 $ E_I $ 、 $ d_i $ を暗号化するために使用されます。データを復号化します。この関数はいくつかのプロパティを満たすべきです。

最初の参加者には、1組のノンスセットが与えられます。それはその秘密関数 $ e_1 $ を使って各nonceを暗号化し、それらをランダムにシャッフルし、結果のデータを2番目の参加者に渡します。

2人目の参加者は同じことをしますが、この場合はノンスがありませんが、暗号化されたノンスのランダムな置換を持ちません。各要素を独自の秘密関数="math-complete"> $ E_2 $ で暗号化し、データを再度シャッフルします。

その後、すべての参加者がシャッフルしてその秘密機能を持つデータを暗号化するまで、3番目の参加者など。

全体のセットアッププロセスは次のとおりです。

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

.

この設定の後、dataの各要素は、すべての秘密関数 $ E_I $ で暗号化されています。

他の参加者の助けを借りずに各参加者がそれぞれの無断を推定することは不可能であることに注意してください。そして、いくつかの悪意のある参加者が注文を偏っていることを試みる場合には、その結果、得られた順序で可能な可能なバイアスを除去するためにデータを完全にランダムにシャッフルすることが十分で十分です。

参加者 $ i $ -thには、 $ i $ のnonceが割り当てられています。このようなNOCEを回復するには、参加者 $ i $ を尋ねる $ j \ neq i $ を求めます。秘密関数 $ d_j $ の秘密の値。エンド参加者の $ i $ で、それ自身の秘密関数 $ e_i $ でのみ暗号化されています。 $ d_i $ を使用してそれを回復することができます。

nonceの回復 $ i $ ：

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

.

この手順の最後に、各参加者はそれ自身のNONCEを知っていますが、他の参加者はそれについて何も知らない。

現在の問題にこの値を使用した後、Playerは、Secrets関数 $ E_I $ と $ d_i $ であるため、すべての値はローカルにすべての値を計算することも、最初のステップの後に値data[i]を復号化したり、2番目のステップの前に、この値を入力としてこの値を使用したりすることができます。完全に復号化するための2番目のステップ。

関数 $ e_i $ と $ d_i $ には、次のプロパティがあります。

1. $ E_I（x）$ は、キー $ x $ の暗号化バージョンです。 SPAN CLASS="math-container"> $ i $ 、
2. $ d_i（e_i（x））= x $ すべてのメッセージの場合 $ x $ とkeys $ i $ 、
3. $ e_i（e_j（x））= e_j（e_j（x））$ すべてのメッセージの場合 $ x $ とkeys $ i $ と $ j $ 、
4. 与えられた $ x $ と $ e_i（x）$ それは、暗号狭石が計算的に不可能です。 $ i $ 、$ x $ 、および $ i $ 、<

/ li>

メッセージ $ x $ と $ Y $ 、keysを見つけるのは計算上不可能です。 SPAN CLASS="math-container"> $ i $ と $ j $ $ E_I（x ）= e_j（y）$ 。

論文に記載されているように、この仮定のほとんどは、暗号化機能を通勤する必要があることを通知するプロパティ3を除いて、どういうわけか一般的です。

それらはこれらのプロパティを満たす単純な暗号化方式を提案します。すべての参加者がいくつかの大きな素数 $ p $ で同意したとしましょう（プロトコルで固定されていれば大丈夫です）。そして、各参加者は常に乱数 $ k_i $ を選択して、 $ gcd（k_i、p - 1）= 1 $ < /スパン>。 $ q_i $ は、 $ k_i \ cdot q_i \ queiv 1 \ mod（p -1）$ < /スパン>。その後、参加者 $ i $ 秘密関数を使用できます。

$$ e_i（x）= x ^ {k_i} \ mod（p）$$ $$ d_i（y）= ^ {q_i} \ mod（p）$$

このアルゴリズムについての注意事項：参加者は、他のピアについてのノンスを学ぶことに衝突するような方法で騙すことはできません（もちろん $ n-1 $ < / SPAN>参加者は損なわれ、残りの1つだけです。しかし、悪意のある参加者は、各参加者からの多くの行動がノンスを扱っている間に多くの行動が必要とされるので、参加してプロトコルを攻撃することができ、対処プロセスを効果的に失効することができます。彼らはジブベリッシュを生産することもできますが、これはプロトコルを拡大することができ、どの参加者が犯人であり、そのような参加者がより高いレベルでこのような参加者を罰します。

---

私はこのアルゴリズムをPokerゲームに実装しました。> Lear BlockChain 。 une 。ブロックチェーンには信頼できる第三者がいませんが、参加者全員がこのプロトコルを実行するメカニズムとして使用できる信頼できるコンピューティング環境があります。