Braid군과 암호알고리듬

◎ 각각의 -braid 는 다음과 같은 유일한 형태를 가진다. (단, , 는 정수, 는 와 가 아닌 치환braid .) ◎ 양의 braid ⇒ 의 우정형: 단, 는 가 아닌 치환braid, : 의 길이(canonical length) ◎ ⇒ , ◎ ◎ . ◎ ⇒ 와 은 commute한다. ● 가정할 때의 우정형에 대하여 ◎: 길이가 이하인 양의 -braid ⇒ :길이가 이하인 양의 braid. ◎: 길이 이하인 양의 braid ⇒ :길이가 이하인 양의 braid. e.g. : 짝수, , =) ⇒ = = (의 center) =. ◎ , : 길이가 이하인 양의 braid들 ⇒ : 길이가 이하인 양의 braid. ◎ , , : 길이가 이하인 양의 braid들 ⇒는 길이가 이하인 양의 braid. ● Braid의 bit 표현 ◎ 일 때 자연수 에 대해 길이가 이하인 양의 -braid들은 bit로 유일하게 표현가능 : 과 사이의 임의의 일대일대응과 다음의 사상을 합성. 의 2진수 표현. ● 암호체계 BR(,) : 짝수 , : 자연수, , : 자연수 : one-way 함수 ◎ key : (). : 길이가 이하인 양의 -braid, : 길이가 인 양의 -braid, . (,) 는 공개키 : 비밀키 ◎ m 평문 ⇒ 길이가 인 양의 -braid 를 random하게 선택, (m) = m ◎ 암호문 (,e) ⇒ e= e 단, , 와 는 그것의 우정형 또는 그것의 bit표현이어야 한다. ● 우정형의 계산 ◎ ,: 치환braid ⇒ 가 치환braid ⇔ , ◎ 가 치환braid ⇔ ● 치환braid 에 대해서 의 우정형을 구하는 algorithm: 우정…
…