클로프리 순열

링크 편집
위키백과, 우리 모두의 백과사전.

수학 및 컴퓨터 과학, 암호 분야에서 세 숫자(x, y, z)의 집합은 다음과 같은 경우 두 순열 f0 및 f1의 클로(claw)라고 한다.

f0(x) = f1(y) = z.

클로를 계산하기 위한 효율적인 알고리즘이 없는 경우, 한 쌍의 순열 f0 및 f1은 클로프리(claw-free) 라고 한다.

클로프리(claw-free) 라는 용어는 Goldwasser, Micali 및 Rivest 가 1984년 논문 "A Paradoxical Solution to the Signature Problem"(나중에 더 완전한 저널 논문에서)에서 소개되었으며, 여기서 그들은 한 쌍의 클로프리 트랩도어(trapdoor) 순열로 인해 적응형 선택 메시지 공격으로부터 안전한 디지털서명 체계가 존재한다는 것 증명하였다.[1] 이 구성은 나중에 단방향 트랩도어 순열로부터 디지털 서명 구성으로 대체되었다.[2] 트랩도어 순열의 존재 자체가 클로프리 순열이 존재한다는 것을 의미하지는 않는다.[3] 그러나 인수분해가 어려울 경우 클로프리 순열(CFP)이 존재하는 것으로 나타났다.

클로프리 순열(꼭 트랩도어일 필요는 없음)의 일반적인 개념은 Ivan Damgård 의 박사논문 The Application of Claw Free Functions in Cryptography (Aarhus University, 1988)에서 추가로 연구되었으며, 여기서 그는 클로프리 순열로부터 충돌 방지 해시 함수를 구성하는 방법을 보여주었다. 클로프리(claw-freeness) 개념은 해시 함수의 충돌 저항 개념과 밀접한 관련이 있다. 차이점은 클로프리 순열은 그들 사이에 충돌을 일으키기 어려운 함수 쌍인 반면, 충돌 방지 해시 함수는 충돌을 찾기 어려운 단일 함수라는 것이다. 즉, 다음과 같은 고유한 값 x, y 쌍을 찾는 것이 어려운 경우, 함수 H 는 충돌 저항력이 있다.

H(x) = H(y).

해시 함수 문헌에서는 이를 일반적으로 해시 충돌이라고 한다. 충돌을 찾기 어려운 해시 함수를 충돌 저항이 있다고 한다.

비트 커밋먼트[편집]

클로프리 순열 f0과 f1 쌍이 주어지면, 비트 커밋먼트를 만드는 것은 간단한다. 비트 b 를 커밋하기 위해 보낸 사람은 임의의 x를 선택하고 fb(x)를 계산한다. f0 과 f1 모두 동일한 도메인(및 범위)을 공유하므로 비트 b는 통계적으로 수신자에게 숨겨진다. 커밋먼트를 개시하기 위해 발신자는 단순히 랜덤한 x를 수신자에게 보낸다. 송신자는 1 - b에 대한 커밋먼트를 여는 것은 클로를 찾는 것과 정확히 동일하기 때문에 자신의 비트에 묶이게 된다. 충돌 방지 해시 함수의 구성과 마찬가지로 이 구성에서는 클로프리 기능에 트랩도어가 필요하지 않는다.

참고자료[편집]

  1. ↑ Goldwasser, Shafi; Micali, Silvio; Rivest, Ronald L. (April 1988). “A digital signature scheme secure against adaptive chosen-message attacks”. 《SIAM J. Comput.》 17 (2): 281–308. doi:10.1137/0217017. 
  2. ↑ Bellare, Mihir; Micali, Silvio (1992). “How to sign given any trapdoor permutation”. 《Journal of the ACM》 39: 214–233. doi:10.1145/147508.147537. 
  3. ↑ Dodis, Yevgeniy; Reyzin, Leonid (2002). “On the Power of Claw-Free Permutations”: 55–73. 

추가 읽기[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=클로프리_순열&oldid=37042834"