**Iterated Inhomogeneous Polynomials**

*Jiaxin Guan and Mark Zhandry*

**Abstract: **Let $p$ be a polynomial, and let $p^{(i)}(x)$ be the result of iterating the polynomial $i$ times, starting at an input $x$. The case where $p(x)$ is the homogeneous polynomial $x^2$ has been extensively studied in cryptography. Due to its associated group structure, iterating this polynomial gives rise to a number of interesting cryptographic applications such as time-lock puzzles and verifiable delay functions. On the other hand, the associated group structure leads to quantum attacks on the applications.

In this work, we consider whether inhomogeneous polynomials, such as $2x^2+3x+1$, can have useful cryptographic applications. We focus on the case of polynomials mod $2^n$, due to some useful mathematical properties. The natural group structure no longer exists, so the quantum attacks but also applications no longer immediately apply. We nevertheless show classical polynomial-time attacks on analogs of hard problems from the homogeneous setting. We conclude by proposing new computational assumptions relating to these inhomogeneous polynomials, with cryptographic applications.

**Category / Keywords: **foundations / foundations

**Date: **received 16 Oct 2021

**Contact author: **jiaxin at guan io, mzhandry at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20211018:061351 (All versions of this report)

**Short URL: **ia.cr/2021/1399

[ Cryptology ePrint archive ]