Date | Dec 13, 2017 |
---|---|

Speaker | Mehdi Tibouchi |

Dept. | NTT Secure Platform Laboratories |

Room | 129-104 |

Time | 15:30-19:30 |

At CCS 2017, Espitau et al. described a side-channel attack against the

rejection sampling step in BLISS signatures, and mentioned that the

attack could be greatly improved and simplified for *uncompressed* BLISS

signatures, as one could target the part of rejection sampling depending

linearly on the secret key, as opposed to quadratically. In actual,

compressed BLISS signatures, though, one only gets noisy linear relations

on the secret, so key recovery amounts to solving a high-dimensional

LWE-type problem. As a result, Espitau et al. dimissed this approach as

infeasible.

However, the LWE problem that arises in this way does not involve any

modular reduction: it is defined over Z. With that motivation in mind, we

study the hardness of LWE over the integers, and find that the problem

(with polynomial size errors) can heuristically always be solved given

sufficiently many samples. We also present provable results in that

direction, and show that we can in fact mount the side-channel attack on

BLISS, against 100% of secret keys (as opposed to ~7% in the CCS paper).

This is joint work with J. Bootle (University College London).

rejection sampling step in BLISS signatures, and mentioned that the

attack could be greatly improved and simplified for *uncompressed* BLISS

signatures, as one could target the part of rejection sampling depending

linearly on the secret key, as opposed to quadratically. In actual,

compressed BLISS signatures, though, one only gets noisy linear relations

on the secret, so key recovery amounts to solving a high-dimensional

LWE-type problem. As a result, Espitau et al. dimissed this approach as

infeasible.

However, the LWE problem that arises in this way does not involve any

modular reduction: it is defined over Z. With that motivation in mind, we

study the hardness of LWE over the integers, and find that the problem

(with polynomial size errors) can heuristically always be solved given

sufficiently many samples. We also present provable results in that

direction, and show that we can in fact mount the side-channel attack on

BLISS, against 100% of secret keys (as opposed to ~7% in the CCS paper).

This is joint work with J. Bootle (University College London).

TEL 02-880-5857,6530,6531 / FAX 02-887-4694