We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduct...
Yan-Song Feng, Jia-Qi Liu, Heng-Yi Luo et al.· 0 citations
It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ an...
Yan-Song Feng, Hao Jiang, Guan-Cheng Li et al.· 1 citation· ⚡1
Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up...
Let $q$ range over primes congruent to $3$ modulo $4$. Let $\zeta_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(\zeta_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[\zeta_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-co...
The cyclic results answer Micciancio's questions of whether exact decision-CVP is-hard on cyclic lattices and on a fixed family of cyclic lattices, even when restricted to full-rank principal cyclic ideals.