Cryptanalysis by Algebraic Relations

Abstract

Algebraic relations are a high-degree generalization of linear relationships. Given an algebraic relation it is possible to predict the outcome of single components of a polynomial equation system or refute points that do not lie in the image of a polynomial map. This work investigates the application of algebraic relations to cryptanalysis, presenting novel insights and algorithms. As a first result, we will show a simple theorem that guarantees the existence of algebraic relations of sublinear degree for overdetermined polynomial equation systems. Equipped with algebraic relations of small degree, we will then show lower bounds for primitives of two cryptographic areas: Pseudorandom Generators. A pseudorandom generator (PRG) is a deterministic function that stretches a random bit string to a longer bit string, which is supposed to be indistinguishable from uniform randomness. While efficiently computable PRGs do exist, PRGs of low complexity are of special interest, as they are in high demand to construct advanced cryptosystems. However, as we will see, PRGs that are evaluated by polynomials of constant degree or locality admit algebraic relations of low degree. This opens an algebraic attack surface, which yields new attack algorithms of subexponential runtime on lightweight PRGs. In particular, in the setting of polynomial or local PRGs of small polynomial stretch, our algorithms asymptotically surpass all other currently known attack algorithms. Our insights for algebraic PRGs extend to the popular class of Macaulay matrix-based solving algorithms for polynomial equation systems. We will give the first proof that the overdetermined multivariate quadratic polynomial problem can be solved in the average case over small fields by computing Macaulay matrices up to some sublinear degree. Functional Encryption. A functional encryption (FE) scheme allows fine-grained access to encrypted data. More specifically, in an FE scheme a master secret key-holder can issue special functional keys that only admit the decryption of evaluations of specific functions on the data of ciphertexts. Since it is known that compact FE implies indistinguishability obfuscation (Bitansky-Vaikuntanatha FOCS 2015, Ananth-Jain CRYPTO 2015), investigating the feasibility of FE schemes is of large interest in cryptographic research. While FE schemes for linear functions do exist from a plethora of assumptions, it is an open problem to construct lattice-based FE schemes for richer functionalities. This is counterintuitive, as lattice-based hardness assumptions, e.g. learning with errors (Regev STOC 2005), imply strong cryptographic primitives, including fully homomorphic encryption (Brakerski-Vaikuntanathan FOCS 2011). In this work, we will attempt to explain why strong assumptions like learning with errors cannot imply richer FE schemes. Concretely, we will use algebraic relations to prove two lower bounds: if no bit-decomposition is used, we can completely rule out the feasibility of lattice-based function-hiding FE. Further, we can rule out the existence of lattice-based compact FE schemes for strict parameter choices.