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'
  1. 03Sep
    by 김수현
    in Special Colloquia

    What is Weak KAM Theory?

  2. 03Sep
    by 김수현
    in Special Colloquia

    Regularity of solutions of Hamilton-Jacobi equation on a domain

  3. 07Nov
    by Editor
    in Special Colloquia

    Queer Lie Superalgebras

  4. 27Mar
    by 김수현
    in Special Colloquia

    Persistent Homology

  5. 27Mar
    by 김수현
    in Special Colloquia

    Structures on Persistence Barcodes and Generalized Persistence

  6. 27Mar
    by 김수현
    in Special Colloquia

    Topological Mapping of Point Cloud Data

  7. 07Nov
    by Editor
    in Special Colloquia

    Contact topology and the three-body problem

  8. 07Nov
    by Editor
    in Special Colloquia

    Mathematical Analysis Models and Siumlations

  9. 07Nov
    by Editor
    in Special Colloquia

    Harmonic bundles and Toda lattices with opposite sign

  10. 07Nov
    by Editor
    in Special Colloquia

    Regularization by noise in nonlinear evolution equations

  11. 28Nov
    by Editor
    in Special Colloquia

    Irreducible Plane Curve Singularities

  12. 17Oct
    by 김수현
    in Special Colloquia

    Algebraic surfaces with minimal topological invariants

  13. 07Nov
    by Editor
    in Special Colloquia

    최고과학기술인상수상 기념강연: On the wild world of 4-manifolds

  14. 17Oct
    by 김수현
    in Special Colloquia

    A wrapped Fukaya category of knot complement and hyperbolic knot

  15. 07Nov
    by Editor
    in Special Colloquia

    A New Approach to Discrete Logarithm with Auxiliary Inputs

  16. 29Jul
    by 김수현
    in Special Colloquia

    Combinatorics and Hodge theory

  17. 26May
    by Manager
    in Special Colloquia

    허준이 교수 호암상 수상 기념 강연 (Lorentzian Polynomials)

Board Pagination Prev 1 Next
/ 1