Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separatio...
Let $\kappa_p(n)$ denote the maximum kissing number of a lattice $\mathcal{L} \subset \mathbb{R}^n$. We prove that $\kappa_p(n) \geq 2^{\Omega(\sqrt{n})}$ for all $p\ge 1$ and that $\kappa_p(n) \geq \Omega(\alpha_p^n)$ for all $p>2$, where $\alpha_p>1$ is a constant depending only on $p$. In particular, our former resu...
Huck Bennett, Minki Hhan, Zi-Han Li et al.· 0 citations
It is shown that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs.
The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has re...
This work introduces an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models, and proves an optimal generic salting theorem for decision games.
Minki Hhan, Sunghyuk Jo, Qi-Peng Liu· arXiv.org· 0 citations
This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact...
The authors' algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples, and optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity.