각 에이전트가 자신의 요소만 알 수 있도록 n개의 요소를 n개의 에이전트에 무작위로 할당합니다.

Question

문제

저는 카드를 섞고 플레이어에게 배포하는 앱을 개발 중입니다.도전으로서, 나는 신뢰할 수 있는 중개자가 필요하지 않은 방식으로 이 문제를 해결하려고 노력했습니다.

즉, 작업은 다음과 같은 분산 알고리즘을 찾는 것입니다.

• 고유하게 할당 $n$ 상담원 번호 $1..n$
• 각 에이전트는 자신의 할당 외에는 할당에 대해 아무것도 알 수 없습니다.
• 과제를 공개할 때 다른 플레이어가 과제를 확인할 수 있습니다.

우리는 또한 다른 에이전트의 할당을 아는 것이 각 에이전트의 장점이고 자신의 할당을 조기에 공개하는 것이 단점이라고 가정합니다.또한 에이전트는 다른 모든 에이전트에게 숨겨진 방식으로 서로 대화할 수 있다고 가정됩니다.

부분적인 해결책

제가 생각해낸 해결책은 적들이 협력하지 않는다는 가정 하에서만 작동합니다.

아이디어는 다음과 같은 세트를 만드는 것입니다. $n$ nonce를 지정하고 각 에이전트에 정확히 하나의 nonce를 할당합니다.그런 다음 세트는 합의된 순서에 따라 에이전트에서 에이전트로 전달되며 각 에이전트가 세트를 정확히 한 번 수신할 때까지 다른 모든 에이전트에게는 숨겨집니다.에이전트가 세트를 수신할 때마다 해당 nonce를 새 nonce로 교환하고 새 nonce를 기억한 다음 다른 사람에게 세트 수신을 확인합니다.이 전체 절차는 두 번 수행됩니다. 이 시점에서 모든 에이전트는 다른 모든 에이전트가 자신의 nonce를 교환한 후 적어도 한 번 세트를 수신하므로 nonce를 인식할 수 없고 따라서 다른 에이전트에 매핑할 수 없습니다.

마지막 에이전트가 세트를 두 번째로 받으면 이를 모든 사람과 공유하고 모든 에이전트는 자신의 nonce가 세트에 포함되어 있음을 다른 에이전트에게 확인합니다.그런 다음 에이전트는 합의된 무작위 시드를 기반으로 세트의 각 nonce에 숫자를 할당하여 필요한 고유 할당을 제공합니다.

소유권 확인을 허용하기 위해 에이전트는 nonce 대신 nonce의 해시 값을 세트에 넣고 확인이 필요한 경우에만 실제 nonce를 공개합니다.

---

이 솔루션의 문제점은 적들이 협업하도록 허용된 경우, 적들이 세트를 수신할 때마다 자신의 버전을 비교하고 변경 사항을 식별하며 잠재적으로 다른 에이전트에 속한 nonce를 파생하여 자신에게 할당된 번호를 알 수 있다는 것입니다. .

모든 아이디어에 감사드립니다!

Answer 1

이 문제는 다음과 같은 문제 집합의 일부입니다. 멘탈 포커.

있다 훌륭하고 작은 기사 Shamir, Rivest 및 Adleman이 이러한 알고리즘을 구현하는 방법에 대한 실용적인 방법을 설명합니다.

초록은 금이다:

부정직할 가능성이 있는 두 명의 플레이어가 카드를 사용하지 않고 공정한 포커 게임을 할 수 있습니까(예:전화로)?

이 문서에서는 다음과 같은 답변을 제공합니다.

1. 아니요.(엄격한 수학적 증명이 제공됩니다.)
2. 예.(정확하고 완전한 프로토콜이 제공됩니다.)

기본적으로 정보 이론적인 관점에서 보면 신뢰할 수 있는 제3자가 없으면 이러한 게임을 플레이하는 것이 불가능하지만 잘 알려진 역방향 암호화 기능을 사용하여 프로토콜을 설계하는 것은 가능합니다.

---

알고리즘은 다음과 같이 작동합니다.

당신이 가지고 있다고 가정 $n$ nonce(다음의 숫자 $1$ 에게 $n$).프로토콜의 각 참가자는 비밀 기능에 액세스할 수 있습니다. $e_i$ 그리고 $d_i$ 데이터를 암호화하고 해독하는 데 사용됩니다.이 함수는 나중에 분석할 몇 가지 속성을 충족해야 합니다.

첫 번째 참가자에게는 전체 nonce 세트가 제공됩니다.비밀 기능으로 각 nonce를 암호화합니다. $e_1$, 무작위로 섞은 후 결과 데이터를 두 번째 참가자에게 전달합니다.

두 번째 참가자도 동일한 작업을 수행하지만 이 경우에는 nonce가 없지만 암호화된 nonce의 무작위 순열이 있습니다.또한 자체 비밀 기능으로 각 요소를 암호화합니다. $e_2$ 그리고 데이터를 다시 섞으세요.

그런 다음 세 번째 참가자 등 모든 참가자가 비밀 기능을 사용하여 데이터를 섞고 암호화할 때까지 계속됩니다.

전반적인 설정 프로세스는 다음과 같습니다.

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

이 설정 후의 각 요소는 data 모든 비밀 기능으로 암호화된 nonce입니다. $e_i$ 어떤 참가자도 알 수 없는 무작위 순서로.

이 시점에서 각 참가자가 다른 참가자의 도움 없이 각 nonce를 추론하는 것은 불가능합니다.그리고 일부 악의적인 참가자가 순서에 편향을 시도하는 경우 독립적으로 참가자 중 한 명이 결과 순서에서 가능한 편견을 제거하기 위해 데이터를 완전히 무작위로 섞는 것으로 충분합니다.

참가자 $i$-th 위치에 nonce가 할당됩니다. $i$.이러한 Nonce를 복구하기 위해 참가자는 $i$ 참가자들에게 서로 묻는다. $j eq i$ 비밀 기능으로 값을 해독합니다. $d_j$ 차례로.마지막에는 참가자 $i$ Nonce는 자체 비밀 기능으로만 암호화됩니다. $e_i$ 그래서 그것은 그것을 사용하여 그것을 복구할 수 있습니다 $d_i$.

임시 복구 중 $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를 알게 되지만 다른 참가자는 이에 대해 아무것도 모릅니다.

현재 문제에 대해 이 값을 사용한 후 플레이어는 비밀 기능을 게시하여 실제로 그러한 nonce를 제어하고 있다고 주장할 수 있습니다. $e_i$ 그리고 $d_i$, 모든 사람이 로컬에서 모든 값을 계산하거나 값을 해독할 수 있도록 합니다. data[i] 첫 번째 단계 이후 두 번째 단계 전에 이 값을 게시한 다음 두 번째 단계의 입력으로 사용하여 완전히 해독합니다.

기능 $e_i$ 그리고 $d_i$ 다음과 같은 속성을 가져야 합니다:

1. $e_i(x)$ 메시지의 암호화된 버전입니다. $x$ 키 아래 $i$,
2. $d_i(e_i(x)) = x$ 모든 메시지에 대해 $x$ 그리고 열쇠 $i$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ 모든 메시지에 대해 $x$ 그리고 열쇠 $i$ 그리고 $j$,
4. 주어진 $x$ 그리고 $e_i(x)$ 암호 분석가가 파생하는 것은 계산상 불가능합니다. $i$, 모든 $x$ 그리고 $i$,
5. 어떤 메시지가 주어졌을 때 $x$ 그리고 $y$, 키를 찾는 것은 계산상 불가능합니다. $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 \equiv 1 \mod(P -1)$.그럼 참가자 $i$ 비밀 기능을 사용할 수 있습니다:

$$e_i(x) = x^{k_i} \mod(P)$$ $$d_i(y) = y^{q_i} \mod(P)$$

이 알고리즘에 대한 몇 가지 주의 사항:참가자는 공모가 다른 피어에 대한 임시 정보를 배우는 데 도움이 되는 방식으로 부정 행위를 할 수 없습니다(물론 그렇지 않은 경우). $n-1$ 참여자들이 공모하여 Nonce가 1개만 남게 됩니다.)그러나 악의적인 참가자는 참여하지 않음으로써 프로토콜을 공격할 수 있으며, 이는 nonce를 처리하는 동안 각 참가자에게 많은 작업이 필요하기 때문에 거래 프로세스를 효과적으로 지연시킬 수 있습니다.또한 횡설수설을 생성할 수도 있지만 이는 프로토콜을 확장하여 어떤 참가자가 범인인지 감지하고 해당 참가자에게 더 높은 수준의 처벌을 적용하는 것을 완화할 수 있습니다.

---

나는 포커 게임을 위해 이 알고리즘을 구현했습니다. NEAR 블록체인.녹슨 코드를 볼 수 있습니다. 여기.블록체인에는 신뢰할 수 있는 제3자가 없지만 모든 참가자가 이 프로토콜을 실행하는 메커니즘으로 사용할 수 있는 신뢰할 수 있는 컴퓨팅 환경이 있습니다.