암호학자의 저녁식사 문제

세 암호학자가 저녁식사를 마친 후 계산을 하려고 하는데, 웨이터가 이미 누군가가 계산을 마쳤다고 말했다. 셋 중 한 명, 혹은 NSA가 계산한 것으로 보이는 상황에서, 세 명은 전자의 경우라면 몰래 계산한 누군가의 선의를 존중해서 그것이 누구인지는 밝히고 싶지는 않지만, 적어도 전자인지 후자인지(즉 NSA가 계산을 해줬는지)는 궁금했다고 한다. NSA가 계산을 대신 해줬는지 여부를 알 수 있는 방법은?

[1]에 등장한 문제이다. 이하 풀이.

스포일러 방지를 위한 버퍼링으로 얼마 전에 배송온 사슴뿔 고양이 모리스 피규어를 감상해주십시오 (자랑)

세 사람을 1,2,3라 하고, (1,2), (2,3), (3,1) 각 쌍마다 동전을 던져서, 각자 알게 된 두 동전의 결과가 일치하는지(둘 다 앞면이거나 둘 다 뒷면이거나) 여부를 말하도록 한다. 단, 계산한 사람은 그 반대로 말하도록 한다. 이렇게 해서 불일치했다고 말한 사람 수가 짝수면 NSA가 계산해준 것이고 홀수면 셋 중 한 명이 계산한 것이 된다.

그 이유. 두 사람 i,j 사이에 던진 동전이 앞면이면 0, 뒷면이면 1인 값 x_{i,j}를 두고 사람 i가 계산하지 않으면 0, 계산하면 1인 값 y_i를 두면, \mathbb{Z}/2\mathbb{Z}에서 1은 x_{1,2}+x_{1,3}+y_1을, 2는 x_{1,2}+x_{2,3}+y_2를, 3는 x_{1,3}+x_{2,3}+y_3을 계산한 후 0이면 일치한다고, 1이면 불일치한다고 말하는 셈이 된다. 따라서 불일치한 사람 수의 기우성은 이 값들의 합과 같은데 그 합이 곧 y_1+y_2+y_3이 되므로 NSA가 계산하면 0, 아니면 1이 되는 것이다.

또한 이 방법은 셋 중 한 명이 계산한 경우여도 누가 계산했는지 알 수 없게 된다. 계산하지 않은 사람 i의 입장에선 나머지 둘 사이에서 던진 동전의 결과(i는 모른다)에 따라 둘 중 누가 계산했는지가 달라지기 때문에 알 수 없게 되는 것.

트윗 타래를 정리. (2018/10/04)

References

[1] D. Chaum, “The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability” J. Cryptology, 1(1), 1988, pp. 65-75. https://users.ece.cmu.edu/~adrian/731-sp04/readings/dcnets.html

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중