1. Introduction

Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다.

이렇듯, 현실에는 각자 자신에게 배정된 수 외의 정보를 알 수 없는 상태에서 derangement를 랜덤하게 생성해야 하는 (암호학적인 상황을 포함하여) 상황이 존재한다. 본 글에서는 카드를 이용하여 랜덤한 교란 순열을 생성하는 알고리즘에 대해 소개할 것이다.

2. Protocol 1: using $O(n^2)$ cards

먼저, 가장 심플한 $n^2$ 개의 카드를 사용하는 프로토콜을 알아보자.

1. 각 사람 마다 줄 빨간 1장, 검은 카드 $n-1$ 장을 준비한다.
2. $i$ 번째 사람은 위에서 부터 $i$ 번째 카드가 빨간 카드가 되도록 세팅된 카드 꾸러미 $p_i$를 가지게 된다.
3. 카드 더미들을 섞어서 나눠준다.
   • 즉, 무작위로 뽑은 $\pi \in S_n$ 에 대해 $i$ 번째 사람에게 $p_{\pi(i)}$ 번 째 카드 꾸러미가 주어진다.
4. 각 $i = 1, 2, 3 \cdots , n$ 에 대해 $i$ 번째 사람은 $p_{\pi(i)}$ 번째 카드를 공개한다.
5. 공개된 카드들 가운데 빨간 카드가 없는 경우에는 $\pi$ 가 derangement라는 뜻이므로, 더 이상 할 일이 없다. (이 때, $i$ 번째 참가자가 알고 있는 정보는 $\pi$가 derangement라는 것과 $i \mapsto \pi(i)$ 라는 것 뿐이다.)
6. 공개된 카드들 가운데 빨간 카드가 있는 경우에는, $\pi$ 에 fixed point가 있다는 뜻이므로, 위 과정들을 다시 반복한다.

이 경우에 프로토콜의 수행이 성공적인 결과를 낳을 확률은 $p = {D_n \over n!} \approx {1 \over e}$ 가 된다.

3. Protocol 2: using $O(n \log n)$ cards

섹션 2에서 살펴봤던 방법은 $\pi(i)$의 값을 나타내는데 $O(n)$ 의 공간을 사용했다. 이 섹션에서 살펴볼 방법은 $O(\log n)$ 만의 공간(카드)을 사용하게 된다.

여기에서는 하나의 비트를 표현하는데에 두 장의 카드를 사용하게 된다. 검은 카드 - 빨간 카드 순으로 놓이면 이것은 0을, 빨간 카드 - 검은 카드 순으로 놓으면 1을 의미하게 된다. 기본적으로는 섹션 2에서 소개한것과 비슷하지만, fixed point의 존재 여부를 확인하는 과정이 다르고, 다소 까다롭다.

일단, $\pi(i) - 1$ 의 이진전개는 $\pi(i) - 1 = a_{\log n}\cdots a_2 a_1$ 라 하고, $i - 1$의 이진 전개는 $b_{\log n}\cdots b_2 b_1$ 이라고 할 때, 우리가 판별하고자 하는 것을 비트 연산을 이용해 다음과 같이 적을 수 있다: $(a_1 \oplus \bar b_1) \land \cdots \land (a_{\log n} \oplus \bar b_{\log n})$

결국, 우리는 $\pi(i)$에 대해 추가적인 정보를 노출하지 않으면서 위 논리식의 값을 평가하면 되고, 이제 이를 위한 특별한 비트 연산 방식을 알아보자.

NEGATE

두 카드 $a, b$ 로 이루어진 비트를 negate 하기 위해서는 $b, a$ 순으로 순서를 바꿔주면 된다.

COPY

1. 카드를 놓는 자리 6개를 일렬로 만들고, 1, 2, 3, 4, 5, 6으로 번호를 붙이자.
2. 1, 2번 자리에는 복사하고 싶은 비트 $x$를 나타내는 카드 두 장을 놓는다.
3. 3, 4, 5, 6번 자리에는 차례로 검정, 빨강, 검정, 빨강 카드를 놓는다. (즉, 0 2개 놓음)
4. 1, 2, 3, 4, 5, 6번 자리에 있던 카드를 차례로 1, 4, 2, 5, 3, 6번 자리에 놓는다.
5. 카드의 왼쪽 절반과 오른쪽 절반을 각자 따로 순서를 섞는다.
6. 1, 2, 3, 4, 5 ,6번 자리에 있던 카드를 차례로 1, 3, 5, 2, 4, 6번 자리에 놓는다.
7. 그러면, 차례로 놓인 3개의 비트가 어떤 비트 $r$에 대해 각각 $x \oplus r$, $r$, $r$ 가 된다.
8. 맨 왼쪽 비트를 까보자.
   • 0인 경우, 오른쪽 두 개의 비트가 $x, x$ 가 된다.
   • 1인 경우, 오른쪽 두 개의 비트가 $\bar x, \bar x$ 가 된다.

AND

1. 카드를 놓는 자리 8개를 일렬로 만들고 1, 2, 3, 4, 5, 6, 7, 8 순으로 번호를 붙이자.
2. 왼쪽에서 부터 차례로 $a, 0, 0, b$ 를 나타내는 카드를 올리자. 우리가 구하고 싶은 것은 $a \land b$ 이다.
3. 1, 2, 3, 4, 5, 6, 7, 8번 자리에 있던 카드를 차례로 1, 5, 2, 6, 3, 4, 7, 8번 자리에 놓는다.
4. 카드의 왼쪽 절반과 오른쪽 절반을 각각 따로 순서를 섞는다.
5. 1, 2, 3, 4, 5, 6, 7, 8번 자리에 있던 카드를 1, 3, 5, 6, 2, 4, 7, 8번 자리에 놓는다.
6. 그러면, 왼쪽 두 비트는 차례로 $a\oplus r, r$ 가 된다. 오른쪽 두 비트는 $0, b$ 의 순서를 $r$번 뒤집은 상태가 된다.
7. 맨 왼쪽 비트를 까보자.
   • 0인 경우, $a = r$ 이 되므로, 왼쪽에서 두 번째 비트가 $a$, 세 번째 비트가 $a \land b$ 가 된다.
   • 1인 경우, $a \neq r$ 이 되므로, 왼쪽에서 두 번째 비트가 $\bar a$, 네 번째 비트가 $a \land b$ 가 된다.

Checking Fixed Point

위의 연산들을 이용하면 이제 논리식 $(a_1 \oplus \bar b_1) \land \cdots \land (a_{\log n} \oplus \bar b_{\log n})$ 의 값을 평가할 수 있게 되고, 결국 총 $O(n \log n)$ 장의 카드만 사용해서 Derangement를 생성할 수 있었다.

References

• [1] R. Ishikawa et al. Efficient Card-based Protocols for Generating a Hidden Random Permutation without Fixed Points (2015)