암호학자의 저녁식사 문제

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

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

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

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

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

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

세 암호학자가 저녁식사를 했는데 웨이터가 누군가가 이미 계산했다고 말했다. 셋 중 한 명, 혹은 NSA 둘 중 하나가 계산한 것으로 보이는 상황에서, 세 명은 몰래 계산한 누군가의 선의를 존중해서 그것이 누구인지는 밝히지 않으려 하나 NSA가 계산했는지 아닌지는 궁금했다고 한다. 그 방법은?

— 유닼 (@udaqueness) October 4, 2018

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