Abstract
For each non-constant q in the set of n-variable Boolean functions, the q-transform of a Boolean function f is related to the Hamming distances from f to the functions obtainable from q by nonsingular linear change of basis. Klapper conjectured that no Boolean function exists with its q-transform coefficients equal to \(\pm \, 2^{n/2}\) (such function is called q-bent) when q is non-affine balanced. In our early work, we only gave partial results to confirm this conjecture for small n. Here we prove thoroughly that the conjecture is true for all n by investigating the nonexistence of the partial difference sets in abelian groups with special parameters. We also introduce a new family of functions called \((\delta ,q)\)-bent functions, which give a measurement of q-bentness.
This is a preview of subscription content, access via your institution.
Notes
- 1.
If an \(h\in {\mathcal {B}}_n\), we say that the rank of h is the least positive integer r such that for some \(B\in GL_n\) the function \(h_B\) depends only on r variables.
- 2.
- 3.
In this case, we use \(4\mu + 2^{n/2+1}\) in place of \(4\mu - 2^{n/2+1}\).
References
- 1.
Carlet C.: Boolean functions for cryptography and error correcting codes. In: Crama Y., Hammer P. (eds.) Boolean Methods and Models, pp. 257–397. Cambridge University Press, Cambridge (2010). http://www.math.univ-paris13.fr/~carlet/pubs.html.
- 2.
Cusick T., Stănică P.: Cryptographic Boolean Functions and Applications. Academic Press, Amsterdam (2009).
- 3.
Ding C.: Codes from Difference Sets. World Scientific, Singapore (2015).
- 4.
Ding C., Pott A., Wang Q.: Constructions of almost difference sets from finite fields. Des. Codes Cryptogr. 72(3), 581–592 (2014).
- 5.
Gu T., Chen Z., Klapper A.: Correlation immune functions with respect to the \(q\)-transform. Cryptogr. Commun. (2017). https://doi.org/10.1007/s12095-017-0267-0.
- 6.
Klapper A.: A new transform related to distance from a Boolean function. IEEE Trans. Inf. Theory 62(5), 2798–2812 (2016).
- 7.
Klapper A., Chen Z.: On the nonexistence of \(q\)-bent Boolean functions. IEEE Trans. Inf. Theory 64(4), 2953–2961 (2018).
- 8.
Lidl R., Niederreiter H.: Finite Fields, 2nd edn. Cambridge University Press, Cambridge (1997).
- 9.
Ma S.L.: Partial difference sets. Discret. Math. 52, 75–89 (1984).
- 10.
Ma S.L.: A survey of partial difference sets. Des. Codes Cryptogr. 4(3), 221–261 (1994).
- 11.
Ma S.L.: Some necessary conditions on the parameters of partial difference sets. J. Stat. Plan. Inference 62, 47–56 (1997).
- 12.
Rothaus O.S.: On “bent” functions. J. Comb. Theory A 20, 300–305 (1976).
Acknowledgements
The authors wish to thank Prof. Cunsheng Ding for some suggestions on the theory of difference sets. Thanks also go to the anonymous referees and the editor for their time and useful comments. The work was partially supported by the National Natural Science Foundation of China under grant No. 61772292 and by the Provincial Natural Science Foundation of Fujian under Grant No. 2018J01425. A. Klapper was partially supported by the National Science Foundation under Grant No. CNS-1420227. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
Author information
Affiliations
Corresponding author
Additional information
Communicated by C. Carlet.
Appendix: Example 1 re-visited
Appendix: Example 1 re-visited
In this appendix we give a proof for Example 1.
We write \(\mathrm {supp}(f)=\{\alpha _i : 1\le i\le 6\}\) with
We check that \(\alpha _1+\alpha _2+\alpha _3=0000\) and \(\alpha _4+\alpha _5+\alpha _6=0000.\) However, in the set \(\mathrm {supp}(q)\), we only have \(1100+1010+0110=0000\) and among vectors left there are no three vectors such that they are linearly dependent. Similar result holds in the set \(V_4\setminus (\mathrm {supp}(q)\cup \{0000\})\). This means that there are no \(A\in GL_4\) such that \(\mathrm {supp}(f_A)\subseteq \mathrm {supp}(q)\) or \(\mathrm {supp}(f_A)\subseteq V_4\setminus (\mathrm {supp}(q)\cup \{0000\})\). In other words, we always have
and
for all \(A\in GL_4\). Hence we get
from which we derive \(W_q(f)(A)\in \{0,\pm \, 4, \pm \,8\}\) for all \(A\in GL_4\). \(\square \)
Rights and permissions
About this article
Cite this article
Chen, Z., Gu, T. & Klapper, A. On the q-bentness of Boolean functions. Des. Codes Cryptogr. 87, 163–171 (2019). https://doi.org/10.1007/s10623-018-0494-1
Received:
Revised:
Accepted:
Published:
Issue Date:
Keywords
- Boolean function
- Walsh–Hadamard transform
- Bent function
- q-transform
- q-bent function
- Partial difference set
Mathematics Subject Classification
- 94A60
- 06E30
- 05B10