Complexity of Monomial Prediction in Cryptography and Machine Learning

EasyChair Preprint 14972

Abstract

In 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_{r-1} \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_{r-1} \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 symmetric-key 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 NP-hard. Here, we show that in the quadratic setting, the problem is \oplus P-complete. \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 zero-sum distinguishers for 5-round Ascon, which is one of the ten finalists for NIST light weight cryptography standardization competition.

We show that the second problem is #P-complete. 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: #P-complete, Ascon, Boolean function, \oplus P-complete, cube testers, monomial prediction, probabilistic generating circuits, zero-sum distinguisher

@booklet{EasyChair:14972,
  author    = {Pranjal Dutta and Mahesh Rajasree and Santanu Sarkar},
  title     = {Complexity of Monomial Prediction in Cryptography and Machine Learning},
  howpublished = {EasyChair Preprint 14972},
  year      = {EasyChair, 2024}}