We proposed recently new signature schemes using the braid groups. Our schemes are based on a gap between the decision version and the computational version of the conjugacy problem in the braid groups. In order to construct our schemes, we need an algorithm for deciding whether any two braids are conjugate each other or not, which must be efficient and cryptographically secure.
In this thesis, we construct this algorithm, called the conjugacy decision algorithm.
In Chapter 1, we introduce the braid group and the digital signature scheme briefly.
In Chapter 2, we introduce invariants of a conjugacy class of a braid, which are used to construct this algorithm.
In Chapter 3, we describe the conjugacy problem and the braid signature scheme using it in brief.
In Chapter 4, we explain the efficiency and cryptographical security of this algorithm. Then we design the conjugacy decision algorithm and describe subalgorithms of it in concrete forms.
최근에 땋임군을 이용한 새로운 서명 기법들이 제안되었다. 이 서명 기법들은 공액 판별 문제와 공액 계산 문제의 차이에 기반한다. 이 서명 기법을 구현하기 위해서는 효율적이고 암호적으로 안전한 공액 판별 알고리즘이 필요하다.
본 논문에서는 이 알고리즘을 구현한다. 1장에서는 땋임군과 디지털 서명 기법에 대해 간단히 소개한다. 2장에서는 땋임의 공액류에 대한 불변량들을에 대해 알아본다. 3장에서는 공액 문제들과 이것들을 이용한 땋임 서명 기법에 대한 설명한다. 마지막으로 4장에서는 본 논문에서 구현될 알고리즘이 효율적이고 암호적으로 안전함을 설명하고 이 알고리즘의 구현에 필요한 서브알고리즘들을 구현하고 설명한다.
