서지주요정보
On the bit security of the weak Diffie-Hellman problem = Weak Diffie-Hellman 문제의 비트 안전성
서명 / 저자 On the bit security of the weak Diffie-Hellman problem = Weak Diffie-Hellman 문제의 비트 안전성 / Dong-Young Roh.
발행사항 [대전 : 한국과학기술원, 2011].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8022202

소장위치/청구기호

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

DMA 11002

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

Boneh and Venkatesan proposed a problem called the \textit{hidden number problem} and they gave a polynomial time algorithm to solve it. And they showed that one can compute $g^{xy}$ from $g^{x}$ and $g^{y}$ if one has an oracle which computes roughly $\sqrt{\log p}$ most significant bits of $g^{xy}$ from given $g^{x}$ and $g^{y}$ in $ \mathbb F_{p}$ by using an algorithm for solving the hidden number problem. Later, Shparlinski showed that one can compute $g^{x^{2}}$ if one can compute roughly $\sqrt{\log p}$ most significant bits of $g^{x^{2}}$ from given $g^{x}$. In this paper we extend these results by using some improvements on the hidden number problem and the bound of exponential sums. We show that for given $g, g^{\alpha}, \ldots, g^{\alpha^{l}} \in \mathbb F_{\it p}^{*}$, computing about $\sqrt{\log p}$ most significant bits of $g^{\frac{1}{\alpha}}$ is as hard as computing $g^{\frac{1}{\alpha}}$ itself, provided that the multiplicative order of $g$ is prime and not too small. Furthermore, we show that we can do it when $g$ has even much smaller multiplicative order in some special cases.

Boneh와 Venkatesan이 숨겨진 수 문제라 불리는 문제를 제안하였고 이를 풀 수 있는 다항식 시간 알고리즘을 만들었다. 그리고 그들은 $g^{x}$와 $g^{y}$가 주어졌을 때 $g^{xy}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산해주는 오라클이 있다면 숨겨진 수 문제를 푸는 알고리즘을 이용하여 $g^{xy}$를 계산할 수 있다는 것을 보였다. 그 후, Shparlinski는 $g^{x}$가 주어졌을 때 $g^{x^2}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산해주는 오라클이 있다면 $g^{xy}$를 계산할 수 있다는 것을 보였다. 이 논문에서 우리는 숨겨진 수 문제와 지수합의 경계에 대한 향상된 결과를 가지고 이 결과들을 확장하였다. 우리는 $g$의 곱의 위수가 소수이고 너무 작지만 않다면 $g, g^{\alpha}, \ldots, g^{\alpha^l} \in \mathbb F_{p}^{*}$가 주어졌을 때, $g^ {\frac{1}{\alpha}}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산하는 것은 $g^{\frac{1} {\alpha}}$ 자체를 계산하는 것 만큼 어렵다는 것을 보였다. 뿐만 아니라 우리는 특별한 경우에는 $g$가 훨씬 더 작은 곱의 위수를 가지더라도 같은 결론을 얻을 수 있다는 것을 보였다.

서지기타정보

서지기타정보
청구기호 {DMA 11002
형태사항 iii, 25 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 노동영
지도교수의 영문표기 : Sang-Geun Hahn
지도교수의 한글표기 : 한상근
수록잡지명 : "On the bit security of the weak Diffie-Hellman problem". Information Processing Letters, v.110 no.18-19, pp.799-802(2010)
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 23-25
주제 Cryptography
Hidden number problem
Weak Diffie-Hellman problem
암호학
숨겨진 수 문제
Weak Diffie-Hellman 문제
QR CODE qr code