Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
foundations
Contact author(s)
jiaxin @ guan io
mzhandry @ gmail com
History
2021-10-18: received
Short URL
https://ia.cr/2021/1399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1399,
      author = {Jiaxin Guan and Mark Zhandry},
      title = {Iterated Inhomogeneous Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1399},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1399}},
      url = {https://eprint.iacr.org/2021/1399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.