Ideal-lattice pseudorandom functions

Definitions and mathematical statement

A pseudorandom-function family consists of an efficient randomized key generator and efficient evaluation algorithms $F_k:D_\lambda\to R_\lambda$, indexed by security parameter $\lambda$. For every probabilistic polynomial-time oracle distinguisher $A$, require \[ \left|\Pr[A^{F_k}(1^\lambda)=1]-\Pr[A^{\mathcal R}(1^\lambda)=1]\right| \] to be negligible in $\lambda$, where $k$ is generated honestly and $\mathcal R$ is a uniformly random function with the same finite domain and range. The oracle may be queried adaptively. This is the standard classical PRF interpretation; the source does not specify a quantum-query or other stronger model.

An ideal lattice is a lattice associated with an ideal of an algebraic-number ring under a specified coefficient or Minkowski embedding. "Ideal-lattice problems" can include different geometric worst-case approximation problems and average-case ring problems, whose parameters and reductions must be stated.

Construct an efficient PRF with a security proof based on the intended ideal-lattice hardness assumption. The excerpt does not specify a ring family, ideal problem, approximation factor, modulus/error distribution, security reduction, or concrete efficiency target. It does not demand key homomorphism or security based only on ideal-SVP; those are not added as requirements.

The summary reports ring/ideal-LWE-related PRF progress and cites Boneh--Lewi--Montgomery--Raghunathan (2013) for key-homomorphic work, while distinguishing direct ideal-SVP-only constructions as less standard. No exact theorem or reduction parameters are supplied. A ring-LWE security theorem and a direct worst-case ideal-SVP assumption must not be identified without their reductions. The 2006 request and later partial-progress assessment are retained as source reports pending current primary-literature review.

Short English statement

Build efficiently evaluable functions indistinguishable from random functions, with security based on a specified ideal-lattice problem. The source leaves the hardness parameters and reduction model open; later ring-LWE-based work is reported as progress, not as an identical direct ideal-SVP theorem.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800071$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attributed to Daniele Micciancio.
• IPAM, Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6240, PDF page 38: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied PDF/legacy-PPT visual audit accessed 2026-07-29; it reports 19 inspected surviving attachments.
• Boneh--Lewi--Montgomery--Raghunathan (2013), key-homomorphic PRF work cited by the summary, without full publication details or exact lattice assumptions.