3
$\begingroup$

Some weeks ago, I read an article about an interesting boolean function with some applications to cryptography. Then, I forgot about the article and now I cannot find it. Hence here I am asking if someone is familiar with this function and can give me some references. Thank you in advance.

Fix a positive integer $n$. The function boolean function $f$, taking a $n$bits words $\mathbf{x}$ as input and returning a single bit as output is defined by $$f(\mathbf{x}) = x_{w(\mathbf{x}) \!\!\!\mod\!\! n} ,$$ where $w(\mathbf{x})$ is the Hamming weight of $\mathbf{x}$ (number of bits equal to 1) and $\mathbf{x} = x_0 x_1 \dots x_{n-1}$ (with $x_i \in \{0,1\}$).

$\endgroup$
3
  • $\begingroup$ isn't the mod n useless in the definition of f? w(x) will always be in {0 ... n-1} anyway. $\endgroup$ Sep 24, 2020 at 16:01
  • $\begingroup$ @Geoffroy Couteau: the $\mod n$ is necessary to return $x_0$, rather than the undefined $x_n$, when each of the $n$ bits $x_i$ are $1$. An alternative is to define $x_n=1$ and then indeed $f(\mathbf{x})=x_{w(\mathbf{x})}$. Unfortunately that function does not ring any bell. Note: the function is balanced. It tends to return one of it's center bits. $\endgroup$
    – fgrieu
    Sep 24, 2020 at 19:31
  • $\begingroup$ Ah right, missed that, thanks (it does not ring any bell here either). $\endgroup$ Sep 24, 2020 at 20:11

1 Answer 1

3
$\begingroup$

It is the hidden weighted bit function. There is more than one paper related to cryptographic applications of this function, but the full definition may be found, for example, in Chapter 3 of this paper:

Cryptographic properties of the hidden weighted bit function

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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