서지주요정보
(A) study of provably secure pseudo-random generator and hard-core predicate = 안전성이 증명 가능한 유사난수 생성기와 Hard-core Predicate에 관한 연구
서명 / 저자 (A) study of provably secure pseudo-random generator and hard-core predicate = 안전성이 증명 가능한 유사난수 생성기와 Hard-core Predicate에 관한 연구 / Eon-Kyung Lee.
저자명 Lee, Eon-Kyung ; 이언경
발행사항 [대전 : 한국과학기술원, 2001].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8012484

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 01011

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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 가정 만큼 안전함을 증명한다.

서지기타정보

서지기타정보
청구기호 {DMA 01011
형태사항 ii, 35 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이언경
지도교수의 영문표기 : Sang-Geun Hahn
지도교수의 한글표기 : 한상근
수록잡지명 : "Pseudorandomness from braid groups". Advances in cryptology-crypto 2001, (2001)
수록잡지명 : "A construction of the simplest super pseudorandom permutation generator". Computers and mathematics with applications, v.29, pp.19-25 (1995)
학위논문 학위논문(박사) - 한국과학기술원 : 수학전공,
서지주기 Reference : p. 32-34
주제 Cryptology
Braid group
One-way function
Hard-core predicate
Pseudorandom generator
암호학
땋임군
일방향 함수
가장 어려운 지시자
유사난수 생성기
QR CODE qr code