Provable security is an important area in modern cryptography. A cryptographic scheme is said to be provably secure if defeating it can be shown to be essentially as difficult as solving a well-known and supposedly difficult problem.
Recently, the conjugacy problem in braid groups has been turned out to be cryptographically useful.
In this thesis, we study based on the conjugacy problem two fundamental areas of provably secure cryptographic primitives: one-way functions and pseudorandom generators. The difficulty of inverting a one-way function induces a notion of hard-core predicate.
Our results are twofold. On the one hand, we view the conjugacy problem as a one-way function. To apply this problem to provably secure schemes, we describe formally the conjugacy problem as a collection of one-way functions in terms of the theory of computation. For this one-way function collection we present a hard-core predicate showing that it inherits the difficulty of solving the conjugacy problem.
On the other hand, we view the decisional Ko-Lee problem, a variant of the conjugacy problem, as a computationally infeasible problem. To apply this to provably secure schemes, we describe formally the decisional Ko-Lee assumption in terms of the theory of computation. From this, we construct two practical pseudorandom schemes: a pseudorandom generator and a pseudorandom synthesizer. And then we show that they are provably as secure as the decisional Ko-Lee assumption.
증명 가능한 안전성(provable security)은 현대 암호학에서 중요한 분야이다. 어떤 암호 시스템을 깨는 것이 매우 어렵다고 알려진 문제를 푸는 것과 같을 때, 이 암호 시스템은 안전성이 증명 가능하다고 한다.
최근, 땋임군(braid groups)에서의 공액 문제(conjugacy problem)가 암호에 유용하게 이용될 수 있음이 밝혀졌다.
본 논문에서는, 안전성이 공액 문제에 기반을 두고 증명가능한 암호 요소들인 일방향 함수와 유사난수 발생기(pseudorandom generator)를 공부한다. 일방향 함수를 역행시키는 어려움은 hard-core predicate라는 개념을 유도한다.
본 논문의 주요 결과는 다음 두 가지로 요약된다.
첫째, 공액 문제를 일방향 함수로 간주하고, 이 문제를 안전성이 증명 가능한 암호 시스템을 설계하는데 적용하기 위해 일방향 함수들의 집합(collection of one-way functions)을 구체적으로 정의한다. 이렇게 정의된 일방향 함수들의 집합에 대해서, 안전성이 증명 가능한 hard-core predicate을 제안하고, 이 hard-core predicate은 공액 문제의 일방향성을 그대로 간직함고 있음을 보인다.
둘째, 공액 문제의 변형인 결정적 Ko-Lee 문제(the decisional Ko-Lee assum- ption)가 다루기 힘든 문제라는 가정하에서, 이 문제를 안전성이 증명 가능한 암호 시스템을 설계하는데 적용하기 위해 computational indistinguishablility의 개념을 이용하여 구체적으로 다시 정의한다. 이로부터 실용적인 유사난수 발생기와 유사난수 합성기(pseudorandom sysnthesizer)를 설계하고, 이들이 결정적 Ko-Lee 가정 만큼 안전함을 증명한다.
