컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0578 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
Fixed argument pairing inversion on elliptic curves |
| 저자(Author(s)) |
Sungwook Kim1, Jung-Hee Cheon1 ISaC and Dept. of Mathematical Sciences, Seoul National University 1 |
| 초록본문(Abstract) | Let $E$ be an elliptic curve over a finite field ${\mathbb F}_q$ with a power of prime $q$, $r$ a prime dividing $\#E({\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r | \Phi_k(p)$, called embedding degree. Then a bilinear map $t: E({\mathbb F}_q)[r] \times E({\mathbb F}_{q^k})/rE({\mathbb F}_{q^k}) \rightarrow {\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. And the Ate pairing and other variants are obtained by reducing the domain for each argument and raising it to some power. we consider the Fixed Argument Pairing Inversion (FAPI) problem for the Tate pairing and its variants. In 2012, considering FAPI for the Ate$_i$ pairing, Kanayama and Okamoto formulated the Exponentiation Inversion (EI) problem. However the definition gives a somewhat vague description of the hardness of EI. We point out that the described EI can be easily solved, and hence clarify the description so that the problem does contain the actual hardness connection with the prescribed domain for given pairings. Next we show that inverting the Ate pairing (including other variants of the Tate pairing) defined on the smaller domain is neither easier nor harder than inverting the Tate pairing defined on the lager domain. This is interesting because it is commonly believed that the structure of the Ate pairing is so simple and good (that is, the Miller length is short, the solution domain is small and has an algebraic structure induced from the Frobenius map) that there would be a chance for attackers to find further approach to solve FAPI for the Ate pairing, differently from the Tate pairing. |
| 분류기호 (MSC number(s)) |
11T71 |
| 키워드(Keyword(s)) | pairing inverision, fixed argument pairing inversion, exponentiation inversion, Tate pairing, Ate pairing |
| 강연 형태 (Language of Session (Talk)) |
English |