Paper 2025/1590

The AIIP Problem: Toward a Post-Quantum Hardness Assumption from Affine Iterated Inversion over Finite Fields

Abstract

We introduce the Affine Iterated Inversion Problem (AIIP), a new candidate hard problem for post-quantum cryptography, based on inverting iterated polynomial maps over finite fields. Given a polynomial f ∈ Fq[x] of degree d ≥ 2, an iteration parameter n, and a target y ∈ Fq, AIIP requires finding an input x such that f(n)(x) = y, where f(n) denotes the n-fold composi tion of f. We establish the computational hardness of AIIP through two independent analytical frameworks: first, by establishing a formal connection to the Discrete Logarithm Problem in the Jacobian of hyperelliptic curves of exponentially large genus; second, via a polynomial time reduction to solving structured systems of multivariate quadratic (MQ) equations. The f irst construction provides number-theoretic evidence for hardness by embedding an AIIP in stance into the arithmetic of a high-genus curve, while the second reduction proves worst-case hardness relative to the NP-hard MQ problem. For the quadratic case f(x) = x2 + α, we show that the induced MQ system is heuristically indistinguishable from a random system, and we formalize a sufficient condition for its pseudorandomness under a standard cryptographic assumption. We provide a detailed security analysis against classical and quantum attacks, derive concrete parameters for standard security levels, and discuss the potential of AIIP as a foundation for digital signatures and public-key encryption. This dual hardness foundation, rooted in both algebraic geometry and multivariate algebra, positions AIIP as a versatile and promising primitive for post-quantum cryptography.

Note: This work represents the first installment in a series providing a solution at the cryptographic primitive level to the CRO Trilemma formalized in [https://eprint.iacr.org/2025/1348]. It introduces a new foundational primitive (AIIP) as the first component of the CASH (Chaotic Affine Secure Hash) family, whose dual security (algebraic and geometric) enables the construction of quantum-resistant cryptographic schemes that resolve the CRO Trilemma at the primitive level. While ZK-NR [https://eprint.iacr.org/2025/1138, 1422, 1529] implements a solution to the CRO Trilemma at the protocol level, the CASH family, initiated by AIIP, lays the groundwork at the primitive level. This protocol/primitive duality enables a modular and compositional approach to structurally resolve the formal incompatibility between confidentiality, reliability, and legal opposability. This submission is theoretical and foundational. It establishes the security foundations necessary for building future contextual and explainable cryptographic primitives aligned with the constraints of the CRO Trilemma.