http://web.math.snu.ac.kr/board/files/attach/images/701/ff97c54e6e21a4ae39315f9a12b27314.png
Extra Form
Lecturer 천정희
Dept. 서울대학교
date Feb 19, 2013
Let  be a cyclic group with generator . The discrete logarithm problem with auxiliary inputs (DLPwAI) is asked to find  with auxiliary inputs ,…, . In Eurocrypt 2006, an algorithm is proposed to solve DLPwAI in  when . In this paper, we reduce the DLPwAI to the problems to find polynomials with small value sets or to find efficiently.
In this talk, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials.
More precisely, with a polynomial  of degree over , the proposed algorithm shows the complexity  group operations to recover with , where  denotes the number of pairs  such that . As an example using the Dickson polynomial, we reveal  group operations when .
Atachment
Attachment '1'
List of Articles
Category Subject Dept. Lecturer
Math Colloquia <정년퇴임 기념강연> The Elements of Euclid file 서울대/광주과학기술원 김홍종
Math Colloquia Gaussian free field and conformal field theory file 서울대학교 강남규
Math Colloquia 학부생을 위한 강연: Introduction to partial differential equations file 서울대학교 변순식
Math Colloquia 곡선의 정의란 무엇인가? file 서울대학교 김영훈
Math Colloquia Fano manifolds of Calabi-Yau Type file 서울대학교 Atanas Iliev
Math Colloquia 젊은과학자상 수상기념강연: From particle to kinetic and hydrodynamic descriptions to flocking and synchronization file 서울대학교 하승열
Math Colloquia 정년퇴임 기념강연회: 숙제 file 서울대학교 지동표
Math Colloquia Noncommutative Geometry. Quantum Space-Time and Diffeomorphism Invariant Geometry file 서울대학교 Raphael Ponge
Math Colloquia 학부생을 위한 ε 강연회: Sir Isaac Newton and scientific computing file 서울대학교 신동우
Special Colloquia A New Approach to Discrete Logarithm with Auxiliary Inputs file 서울대학교 천정희
Math Colloquia 정년퇴임 기념강연: Volume Conjecture file 서울대학교 김혁
Special Colloquia Irreducible Plane Curve Singularities file 서울대학교 강정혁
Math Colloquia Subgroups of Mapping Class Groups file 서울대학교 김상현
Math Colloquia Randomness of prime numbers file 서울대학교 임선희
Math Colloquia Non-commutative Lp-spaces and analysis on quantum spaces file 서울대학교 이훈희
Math Colloquia 학부생을 위한 ε 강연회: Mathematics from the theory of entanglement file 서울대학교 계승혁
Math Colloquia Brownian motion and energy minimizing measure in negative curvature file 서울대학교 임선희
Math Colloquia Combinatorial Laplacians on Acyclic Complexes file 서울대학교 국웅
Special Colloquia Contact topology and the three-body problem file 서울대학교 Otto van Koert
Math Colloquia Fefferman's program and Green functions in conformal geometry file 서울대학교 Raphaël Ponge
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Next
/ 15