2015 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2015. Please put the report number in the subject. 
Goto Thread: PreviousNext
Goto: Forum ListMessage ListNew TopicSearchLog In
2015/313: Quantum attacks against the short PIP problem are not polynomial time
Posted by: biasse (IP Logged)
Date: 07 May 2015 20:21

The preprint 2015/313 "Recovering Short Generators of Principal Ideals in Cyclotomic Rings" by Cramer-Ducas-Peikert-Regev claims that its main result implies a quantum polynomial time key-recovery attack against cryptographic constructions relying on the hardness of finding a short generator of a principal ideal in a cyclotomic field (ex: multilinear maps or Smart-Vercauteren scheme).

This statement is not true, and it should be amended.

It is based on two references to justify the existence of a quantum polynomial time algorithm to solve the Principal Ideal Problem (PIP).

First, an online draft "SOLILOQUY: a cautionary tale" from Campbel, Grove and Shepherd [CGS14]. This work in progress has been publicly released as it was when the corresponding research program at CESG was interrupted. According to its authors, the polynomial run time of the attack is an overstatement that cannot be supported (This has been stated at the Heilbronn Quantum Algorithms Meeting 2015 and at the ICERM workshop on lattices and cybersecurity 2015). Moreover, it is unclear that the approach chosen in [CGS14] could ever lead to a polynomial run time for at least two fundamental reasons explained in this forum post :

Then, the authors of 2015/313 refer to ongoing research by Fang Song and myself. This work in progress (which adopts a totally different approach than that of [CGS14]) has never been shared with the authors and has never been publicly released. We have no timeline for its submission, and although it is promissing, it is clearly too soon to refer to it with the level of confidence chosen by the authors of this preprint ("known algorithm for the PIP"). We have already shared our concerns about this citation with the authors of 2015/313, but no change has been made so far. It is clearly "work in progress", and Fang Song and myself do not refer to it as an actual result.

Edited 2 time(s). Last edit at 10-Jun-2015 13:58 by biasse.

Please log in for posting a message. Only registered users may post in this forum.