Welcome to the resource topic for 2021/1399
Title:
Iterated Inhomogeneous Polynomials
Authors: Jiaxin Guan, 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.
ePrint: https://eprint.iacr.org/2021/1399
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .