Papers for

cryptographic algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Certificate complexity determined for all elementary symmetric Boolean functions

Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Abstract: Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Our previous work determined its certificate complexity when $d$ is odd and when $d$ is a power of $2$, while even degrees with at least two nonzero binary digits were left open. We solve that open question and determine $C(σ_{n,d})$ for every $1\le d\le n$.

Mon 14 SeptDiscrete Mathematics
The gist
This paper looks at special Boolean functions called elementary symmetric functions, which depend on how many input variables are set to true. Previously, the authors found how complex it is to verify these functions for some cases, but not all. Now they solve that problem, describing exactly how complex it is for every possible case. This helps complete the understanding of these functions’ verification difficulty.
Open → 2609.15678v1