Cryptology ePrint Archive: Report 2021/1399

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:

[ Cryptology ePrint archive ]