MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/368まで

_ 気になった論文１：Breaking pairing-based cryptosystems using $\eta_T$ pairing over $GF(3^{97})$（Takuya Hayashi and Takeshi Shimoyama and Naoyuki Shinohara and Tsuyoshi Takagi, IACR ePrint 2012/345）

There are many useful cryptographic schemes, such as ID-based encryption, short signature, keyword searchable encryption, attribute-based encryption, functional encryption, that use a bilinear pairing. It is important to estimate the security of such pairing-based cryptosystems in cryptography. The most essential number-theoretic problem in pairing-based cryptosystems is the discrete logarithm problem (DLP) because pairing-based cryptosystems are no longer secure once the underlining DLP is broken. One efficient bilinear pairing is the $\eta_T$ pairing defined over a supersingular elliptic curve $E$ on the finite field $GF(3^n)$ for a positive integer $n$. The embedding degree of the $\eta_T$ pairing is $6$; thus, we can reduce the DLP over $E$ on $GF(3^n)$ to that over the finite field $GF(3^{6n})$. In this paper, for breaking the $\eta_T$ pairing over $GF(3^n)$, we discuss solving the DLP over $GF(3^{6n})$ by using the function field sieve (FFS), which is the asymptotically fastest algorithm for solving a DLP over finite fields of small characteristics. We chose the extension degree $n=97$ because it has been intensively used in benchmarking tests for the implementation of the $\eta_T$ pairing, and the order (923-bit) of $GF(3^{6\cdot 97})$ is substantially larger than the previous world record (676-bit) of solving the DLP by using the FFS. We implemented the FFS for the medium prime case (JL06-FFS), and propose several improvements of the FFS, for example, the lattice sieve for JL06-FFS and the filtering adjusted to the Galois action. Finally, we succeeded in solving the DLP over $GF(3^{6\cdot 97})$. The entire computational time of our improved FFS requires about 148.2 days using 252 CPU cores. Our computational results contribute to the secure use of pairing-based cryptosystems with the $\eta_T$ pairing.

先日大きな話題になった離散対数問題の解析に関する論文。一部報道によってこの研究成果の意味が誤解されている節が見られるので簡単に補足しておくと、この結果は「ペアリングベース暗号」という比較的新しい暗号の構成法について、ある特定のパラメータを選ぶと期待されていたほど強い暗号にならないことを明らかにしたものである*1。決して、「全てのペアリングベース暗号が安全でないことがわかった」などという大それた主張をしているわけではないので注意していただきたい。

_ 気になった論文２：Another look at non-uniformity（Neal Koblitz and Alfred Menezes, IACR ePrint 2012/359）

We argue that it is unnatural and undesirable to use the non-uniform model of complexity for practice-oriented security reductions in cryptography.

まだちゃんと読んでいないのだけど、私自身の研究の興味とも関連がありそうなのでちゃんと読むべきかもしれない。