(A) study of provably secure pseudo-random generator and hard-core predicate = 안전성이 증명 가능한 유사난수 생성기와 Hard-core Predicate에 관한 연구

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.
Advisors
Hahn, Sang-Geunresearcher한상근researcher
Publisher
한국과학기술원
Issue Date
2001
Identifier
169520/325007 / 000975823
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 수학전공, 2001.8, [ ii, 35 p. ]

Keywords

Hard-core predicate; One-way function; Braid group; Cryptology; Pseudorandom generator; 유사난수 생성기; 가장 어려운 지시자; 일방향 함수; 땋임군; 암호학

URI
http://hdl.handle.net/10203/41838
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=169520&flag=t
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 152
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0