all InfoSec news
Improved Hardness of BDD and SVP Under Gap-(S)ETH. (arXiv:2109.04025v2 [cs.CC] UPDATED)
Jan. 27, 2022, 2:20 a.m. | Huck Bennett, Chris Peikert, Yi Tang
cs.CR updates on arXiv.org arxiv.org
We show improved fine-grained hardness of two key lattice problems in the
$\ell_p$ norm: Bounded Distance Decoding to within an $\alpha$ factor of the
minimum distance ($\mathrm{BDD}_{p, \alpha}$) and the (decisional)
$\gamma$-approximate Shortest Vector Problem ($\mathrm{SVP}_{p,\gamma}$),
assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH).
Specifically, we show:
1. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for
$\mathrm{BDD}_{p, \alpha}$ for any constant $\alpha > \alpha_\mathsf{kn}$,
where $\alpha_\mathsf{kn} = 2^{-c_\mathsf{kn}} < 0.98491$ and $c_\mathsf{kn}$
is the …
More from arxiv.org / cs.CR updates on arXiv.org
Jobs in InfoSec / Cybersecurity
SOC 2 Manager, Audit and Certification
@ Deloitte | US and CA Multiple Locations
Information Security Engineers
@ D. E. Shaw Research | New York City
Information Security Manager & ISSO
@ Federal Reserve System | Minneapolis, MN
Forensic Lead
@ Arete | Hyderabad
Lead Security Risk Analyst (GRC)
@ Justworks, Inc. | New York City
Consultant Senior en Gestion de Crise Cyber et Continuité d’Activité H/F
@ Hifield | Sèvres, France