PKC 2012

PKC 2012 was held at the Darmstadium in Darmstadt, Germany during May 21-23, 2012. There were approximately 200 people in attendance. A total of 41 papers were accepted from 188 submissions, that corresponds to a record number of the history of PKC (ref. “preface” in proceedings).

Among the 41 papers, a few papers deal with elliptic curves: Ramanna, Chatterjee and Sarkar in [2] propose a variant of Waters IBE scheme in the setting of asymmetric pairings. In [3], Stefanov Shi and Song propose a privacy-preserving set intersection protocol with enforced privacy policies utilizing bilinear groups and pairings. Some other crypto schemes and protocols exploit bilinear maps, whose instantiation can be found in elliptic curves. However, elliptic curves themselves appear explicitly only in one paper [1].

Sakemi, Hanaoka, Izu, Takenaka and Yasuda [1] presented implementation results of Cheon’s algorithm (from [4]) about the discrete logarithm with auxiliary input (DLPwAI). This problem asks to find an integer a when given the group elements g, g^a, …, g^{a^d} where g is of order p. Such computational problems can arise in pairing-based cryptography. The authors of [1] take an elliptic curve over a 160 bit prime field whose order p is a 160 bit prime satisfying that p-1 is divisible by an 84 bit prime d. In [4], the attack complexity is estimated by O(sqrt(p-1)/d) exponentiations, which is about 2^38 field operations. By implementing this with some speeding-up techniques, they succeeded in solving this problem in 1314 core days with 256 MByte memory.  It is worth noting that the attack only uses the values g, g^a and g^{a^d} and so does not require reading or storing the 2^84 elements g^{a^i} for 2 <= i < d.

[1] Yumi Sakemi, Goichiro Hanaoka, Tetsuya Izu, Masahiko Takenaka, and Masaya Yasuda, “Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve,” pp.595-608, PKC 2012.

[2] Somindu C. Ramanna, Sanjit Chatterjee, and Palash Sarkar, “Variants of Waters’ Dual System Primitives Using Asymmetric Pairings (Extended Abstract),” pp. 298-315, PKC 2012.

[3] Emil Stefanov, Elaine Shi, and Dawn Song, “Policy-Enhanced Private Set Intersection: Sharing Information While Enforcing Privacy Policies,” pp. 413-430, PKC 2012.

[4] Jung Hee Cheon, “Discrete Logarithm Problems with Auxiliary Inputs,” Journal of Cryptology, Vol. 23, No. 3, pp.457-476, 2010.

 — Taechan Kim and Jung Hee Cheon (Seoul National University)

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s