palash...@gmail.com
unread,Mar 11, 2022, 10:08:50 AM3/11/22Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Sign in to report message
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to pqc-forum, Neal Koblitz, Subhabrata Samajder, Subhadip Singha, Palash Sarkar
We have posted a paper with the above title to Eprint with the following link.
The abstract of the paper is as follows.
------------------------------------------------------------------
A seminal 2013 paper by Lyubashevsky, Peikert, and Regev
proposed basing post-quantum cryptography on ideal lattices and
supported this proposal by giving
a polynomial-time security reduction from the approximate
Shortest Independent Vectors Problem (SIVP) to the Decision
Learning With Errors (DLWE)
problem in ideal lattices. We
give a concrete analysis of this multi-step reduction.
We find that the tightness gap in the reduction is so great
as to vitiate any meaningful security guarantee,
and we find reasons to doubt the feasibility in the
foreseeable future of the quantum part of the reduction.
In addition, when we make the reduction concrete it
appears that the approximation factor in the SIVP problem is
far larger than expected, a circumstance that causes
the corresponding approximate-SIVP problem most likely
not to be hard for proposed cryptosystem parameters. We also
discuss implications for systems such as
Kyber and SABER that are based on module-DLWE.
------------------------------------------------------------------
We welcome feedback on the paper.
Thanks and regards,
Neal Koblitz
Subhabrata Samajder
Palash Sarkar
Subhadip Singha