PIP in 2^(n^(1/2 + o(1))) in some cyclotomics

[Jean-François Biasse]

Dear colleagues,

Sorry for the last post, there was an embarrassing typo :(

I would like to inform you that I recently updated a March 2015 online draft where I had claimed a PIP algorithm in 2^(n^(1/2 + o(1))) for some cyclotomics. https://arxiv.org/abs/1503.03107v5

The updated versions since Sept 30th  feature these additions:

a) Reduction from PIP in K to PIP in K^+ . It seems to be folklore, but O. Regev pointed out to me in October 2015 that some of the details were unclear.

b) Optimized relation search around cyclotomic units.

c) Optimized q-descent strategy.

d) PIP in time 2^(n^b) for b < 1/2 (with precomputation on K) . There are a whole range of possible complexities. For examples a precomputation of time 2^(n^{2/3}) allows us to solve any instance of the PIP in time 2^(n^{4/9 + o(1)}). Besides being an attack against schemes relying on the short-PIP, this can also be used to solve gamma-SVP for gamma in e^{Õ(n^(1/2))} when combined with the methods of Cramer Ducas and Wesolowski https://eprint.iacr.org/2016/885 under unproved heuristics on the number of generators of the class group. With that precomputation (and under these heuristics), our method solves gamma-SVP in better complexity than BKZ.

Regards,
Jean-François