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\}$).

Improve this question
$\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$
    – Geoffroy Couteau
    Commented 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 ♦
    Commented Sep 24, 2020 at 19:31
  • $\begingroup$ Ah right, missed that, thanks (it does not ring any bell here either). $\endgroup$
    – Geoffroy Couteau
    Commented Sep 24, 2020 at 20:11

1 Answer 1

Reset to default
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

Improve this answer
$\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.