skytreeTokyo Crypto Day

Welcome to Tokyo Crypto-Park

Home / About

Cherry Blossom

 Related Events

Charles River Crypto Day
Bay Area Crypto Day
Paris Crypto Day
London Crypto Day

 Timeline: Past

 Upcoming Talks

Join us for the first Tokyo Crypto Day on Friday, June 2.


June 2nd, 2017


Musashino R&D Center
Convention Hall C (2nd floor)
3-9-11 Midori-cho,Musashino-shi,Tokyo


13:00 - 14:00 Fuyuki Kitagawa
TBA (On Functional Encryption)
14:00 - 14:30 Break
14:30 - 15:30 Atsushi Takayasu
Small CRT-Exponent RSA Revisited
15:30 - 16:00 Break
16:00 - 17:00 Keita Emura
Privacy-Preserving Aggregation of Time-Series Data
with Public Verifiability from Simple Assumptions


Title: TBA (On functional encryption)
Fuyuki Kitagawa (Tokyo Tech)

Abstract: TBA

Small CRT-Exponent RSA Revisited
Atsushi Takayasu (The University of Tokyo)

Since May (Crypto'02) revealed the vulnerability of the small CRT-exponent RSA using Coppersmith's lattice-based method, several papers have studied the problem and two major improvements have been made. Bleichenbacher and May (PKC'06) proposed an attack for small $d_q$ when the prime factor $p$ is significantly smaller than the other prime factor $q$; the attack works for $p< N^{0.468}$. Jochemsz and May (Crypto'07) proposed an attack for small $d_p$ and $d_q$ where the prime factors $p$ and $q$ are balanced; the attack works for $d_p , d_q < N^{0.073}$. Even after a decade has passed since their proposals, the above two attacks are still considered to be the state-of-the-art, and no improvements have been made thus far. A novel technique seems to be required for further improvements since the attacks have been studied with all the applicable techniques for Coppersmith's methods proposed by Durfee-Nguyen (Asiacrypt'00), Jochemsz-May (Asiacrypt'06), and Herrmann-May (Asiacrypt'09, PKC'10). In this paper, we propose two improved attacks on the small CRT-exponent RSA: a small $d_q$ attack for $p < N^{0.5}$ (an improvement of Bleichenbacher-May's) and a small $d_p$ and $d_q$ attack for $d_p , d_q < N^{0.091}$ (an improvement of Jochemsz-May's). We use Coppersmith's lattice-based method to solve modular equations and obtain the improvements from a novel lattice construction by exploiting useful algebraic structures of the CRT-RSA key generation. We explicitly show proofs of our attacks and verify the validities by computer experiments. In addition to the two main attacks, we propose small $d_q$ attacks on several variants of RSA.

Joint Work with Yao Lu and Liqiang Peng

Privacy-Preserving Aggregation of Time-Series Data with Public Verifiability from Simple Assumptions
Keita Emura (NICT)

Aggregator oblivious encryption was proposed by Shi et al. (NDSS 2011), where an aggregator can compute an aggregated sum of data and is unable to learn anything else (aggregator obliviousness). Since the aggregator does not learn individual data that may reveal users' habits and behaviors, several applications, such as privacy-preserving smart metering, have been considered. In this talk, we introduce our aggregator oblivious encryption schemes with public verifiability where the aggregator is required to generate a proof of an aggregated sum and anyone can verify whether the aggregated sum has been correctly computed by the aggregator. Though Leontiadis et al. (CANS 2015) considered the verifiability, their scheme requires an interactive complexity assumption to provide the unforgeability of the proof. Our schemes are proven to be unforgeable under a static and simple assumption (a variant of the Computational Diffie-Hellman assumption). Moreover, our schemes inherit the tightness of the reduction of the Benhamouda et al. scheme (ACM TISSEC 2016) for proving aggregator obliviousness. This tight reduction allows us to employ elliptic curves of a smaller order and leads to efficient implementation.


Contact Info.

tokyo dot cryptoday at gmail dot com