6
$\begingroup$

I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) mappings and their application.

For three variables, the transformation matrix is given below:

enter image description here

I have posted this with some details and a description for reducing 3-SAT to checking the existence of specific term in an ordinary polynomial product on math.stackexchange (here). I have not got much feedback there. I was wondering if someone here could help.

If this is not the right forum to ask this sort of questions, or more details are needed, please let me know in comments.

EDIT: I found similarities to Zhegalkin polynomials and the $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ -1,1 \right \}$ representation described here with the difference that this is a $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ 0,1 \right \}$ representation.

$\endgroup$
9
$\begingroup$

Well done on your independent discovery.

This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc.

Ryan O'Donnell's notes on Analysis of Boolean functions available here which are now published as a book, Claude Carlet's chapters on Boolean functions here are easily accessible online.

Just use the order $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ which corresponds to lexicographic order over the integers, and apply the corresponding permutation to the columns as well.

In that order your matrix is simply the 3-fold Kronecker product $$H_2 \otimes H_2\otimes H_2$$of the basic 2 by 2 Hadamard matrix.

$$ H_2=\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right), $$

This paper considers efficient evaluation of Hadamard representation coefficients.

$\endgroup$
2
$\begingroup$

You are right about Zhegalkin polynomials, which are called Algebraic Normal Form (ANF) in the Boolean functions literature. Such representation is unique.

$$f(x) = \bigoplus_{u\in GF(2^n)} a_u x^u = \bigoplus_{u\in GF(2^n)} a_u x_1^{u_1} \ldots x_n^{u_n},$$

where $a_u \in GF(2)$ are coefficients of the monomials, $u$ is the binary mask defining the form of the monomial and $x=x_1,\ldots,x_n$ are the variables. $x^u$ is just a shorthand for bitwise powers.

The linear (over $GF(2)$) mapping which transforms the truth table of a Boolean function into the table of $2^n$ coefficients $a_u$ is called Möbius transform:

$$a_u = \bigoplus_{x \preceq u} f(x),$$

where $x \preceq u$ means that $x \& u = x$.

Möbius transform is also the inverse of itself.

It's matrix is the Kronecker "power" of this matrix:

$$\pmatrix{ 1 & 1 \\ 1 & 0 }^{(n)}$$

From this one can derive a simple recursive algorithm performing the Mobius transform in time $n2^n$.

Some methods of cryptanalysis are using ANF. They exploit low degrees of the ANFs in a cryptographic primitive. For example, if you can prove an upper-bound on the degree of a cipher, you know that for $u$ with high Hamming weight the coefficient $a_u = \bigoplus_{x \preceq u} f(x)$ is zero. So you get a property of $f$ which distinguishes it from random function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.