Download PDFOpen PDF in browserComplexity of Monomial Prediction in Cryptography and Machine LearningEasyChair Preprint 149728 pages•Date: September 21, 2024AbstractIn this paper, we focus on the monomial prediction problem in two settings: (1) Decide whether a particular monomial m is present in a composite function f:= f_r \circ f_{r1} \circ \hdots f_0, where f_i are quadratic boolean functions, (2) Decide whether a particular monomial m is present in a composite function f:= f_r \circ f_{r1} \circ \hdots f_0, where polynomials f_i are efficiently computable by Probabilistic Generating circuits over rationals. Probabilistic generating circuits (PGCs) are economical representations of multivariate probability generating polynomials (PGPs), which capture many tractable probabilistic models in machine learning. The first problem has a strong connection with the security of symmetrickey primitives. Dinur and Shamir proposed the cube attack for distinguishing a cryptographic primitive from a random function, which can be thought of as an efficient monomial prediction. In a general setting, over any large finite field or integers, monomial prediction is known to be NPhard. Here, we show that in the quadratic setting, the problem is \oplus Pcomplete. \oplus P is an interesting complexity class that is not known to contain NP, however, it is believed to contain computationally hard problems. On the other hand, we also present several new zerosum distinguishers for 5round Ascon, which is one of the ten finalists for NIST light weight cryptography standardization competition. We show that the second problem is #Pcomplete. It is known that PGCs have efficient inference, i.e. given a monomial, one can efficiently output (which signifies the probability) its coefficient in the polynomial computed by the circuit. However, a composition of such functions makes the inference hard. Composition of probabilistic models and their efficient inference play a crucial role in the semantic contextualization and framework of uncertainty theories in graphical modelling. Keyphrases: #Pcomplete, Ascon, Boolean function, \oplus Pcomplete, cube testers, monomial prediction, probabilistic generating circuits, zerosum distinguisher
