클로프리 순열(claw-free permutation)은 수학 및 컴퓨터 과학, 특히 암호학 분야에서 사용되는 개념으로, 두 개의 순열 함수 쌍이 특정한 성질을 만족할 때 이를 가리키는 용어이다.
수학 및 컴퓨터 과학, 암호학 분야에서 세 숫자 (x, y, z)의 집합은 다음 조건을 만족할 때 두 순열 f₀ 및 f₁의 클로(claw)라고 한다.
f₀(x) = f₁(y) = z
즉, 두 서로 다른 순열 함수가 동일한 출력값 z를 산출하는 입력값 x와 y가 존재하는 경우, 그 세 값의 조합을 클로라고 부른다. 이때 클로를 계산하기 위한 효율적인 알고리즘이 존재하지 않는 경우, 한 쌍의 순열 f₀ 및 f₁은 클로프리(claw-free)라고 한다.
이 용어는 Goldwasser, Micali 및 Rivest가 1984년 논문 "A Paradoxical Solution to the Signature Problem"에서 처음 소개하였다. 이후 더 완전한 저널 논문에서 그들은 한 쌍의 클로프리 트랩도어(trapdoor) 순열이 존재하면 적응형 선택 메시지 공격으로부터 안전한 디지털 서명 체계가 존재한다는 것을 증명하였다. 이 구성은 이후 단방향 트랩도어 순열로부터 디지털 서명을 구성하는 방식으로 대체되었다.
트랩도어 순열의 존재 자체가 클로프리 순열의 존재를 의미하지는 않는다. 그러나 인수분해가 어려울 경우 클로프리 순열이 존재하는 것으로 알려져 있다.
클로프리 순열(반드시 트랩도어일 필요는 없는)의 일반적인 개념은 Ivan Damgård의 박사논문 "The Application of Claw Free Functions in Cryptography"(Aarhus University, 1988)에서 추가로 연구되었으며, 그는 클로프리 순열로부터 충돌 방지 해시 함수를 구성하는 방법을 보여주었다. 클로프리(claw-freeness) 개념은 해시 함수의 충돌 저항 개념과 밀접한 관련이 있다. 차이점은 클로프리 순열은 그들 사이에 충돌을 일으키기 어려운 함수 쌍인 반면, 충돌 방지 해시 함수는 충돌을 찾기 어려운 단일 함수라는 점이다.
클로프리 순열 f₀과 f₁ 쌍이 주어지면 비트 커밋먼트(bit commitment)를 만드는 것은 간단하다. 비트 b를 커밋하기 위해 보낸 사람은 임의의 x를 선택하고 f_b(x)를 계산한다. f₀과 f₁ 모두 동일한 도메인(및 범위)을 공유하므로 비트 b는 통계적으로 수신자에게 숨겨진다. 커밋먼트를 개시하기 위해 발신자는 단순히 랜덤한 x를 수신자에게 보낸다. 송신자는 1-b에 대한 커밋먼트를 여는 것이 클로를 찾는 것과 정확히 동일하기 때문에 자신의 비트에 묶이게 된다. 충돌 방지 해시 함수의 구성과 마찬가지로 이 구성에서는 클로프리 기능에 트랩도어가 필요하지 않다.
주요 참고 문헌으로는 Goldwasser, Micali, Rivest의 "A digital signature scheme secure against adaptive chosen-message attacks"(SIAM J. Comput., 1988), Bellare와 Micali의 "How to sign given any trapdoor permutation"(Journal of the ACM, 1992), Dodis와 Reyzin의 "On the Power of Claw-Free Permutations"(2002) 등이 있다.
