https://www.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
Special Colloquia Mathematical Analysis Models and Siumlations file Collège de France Pierre-Louis Lions
Special Colloquia Regularization by noise in nonlinear evolution equations file Dep. Math., Kyoto Univ. Yoshio Tsutsumi
Special Colloquia What is Weak KAM Theory? file ENS-Lyon Albert Fathi
Special Colloquia Regularity of solutions of Hamilton-Jacobi equation on a domain file ENS-Lyon Albert Fathi
Special Colloquia 허준이 교수 호암상 수상 기념 강연 (Lorentzian Polynomials) file Professor, Stanford University 허준이 교수
Special Colloquia Harmonic bundles and Toda lattices with opposite sign file RIMS, Kyoto Univ. Takuro Mochizuki
Special Colloquia Persistent Homology file Stanford University Gunnar E. Carlsson
Special Colloquia Structures on Persistence Barcodes and Generalized Persistence file Stanford University Gunnar E. Carlsson
Special Colloquia Topological Mapping of Point Cloud Data file Stanford University Gunnar E. Carlsson
Special Colloquia Queer Lie Superalgebras file Univ. of Texas, Arlington Dimitar Grantcharov
Special Colloquia Algebraic surfaces with minimal topological invariants file 고등과학원 금종해
Special Colloquia Combinatorics and Hodge theory file 미국 프린스턴대 교수, 한국 고등과학원 석학교수 허준이
Special Colloquia Contact topology and the three-body problem file 서울대학교 Otto van Koert
Special Colloquia A New Approach to Discrete Logarithm with Auxiliary Inputs file 서울대학교 천정희
Special Colloquia 최고과학기술인상수상 기념강연: On the wild world of 4-manifolds file 서울대학교 박종일
Special Colloquia Irreducible Plane Curve Singularities file 서울대학교 강정혁
Special Colloquia A wrapped Fukaya category of knot complement and hyperbolic knot file 포항공대 오용근
Board Pagination Prev 1 Next
/ 1