Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform

Qinglan ZHAO; Dong ZHENG; Xiangxue LI; Yinghui ZHANG; Xiaoli DONG

doi:10.1587/transfun.E100.A.1965

Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform

Qinglan ZHAO, Dong ZHENG, Xiangxue LI, Yinghui ZHANG, Xiaoli DONG

Full Text Views

0

Share
Cite this

Summary :

As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1ⁿ of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1ⁿ. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1965-1972

Publication Date: 2017/09/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E100.A.1965

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Authors

Qinglan ZHAO
  Shanghai Jiao Tong University,Xi'an University of Post and Telecommunications
Dong ZHENG
  Xi'an University of Post and Telecommunications
Xiangxue LI
  East China Normal University
Yinghui ZHANG
  Xi'an University of Post and Telecommunications
Xiaoli DONG
  Xi'an University of Post and Telecommunications

Keyword

Boolean functions, linear structure, arithmetic Walsh transform, Walsh-Hadamard transform

Cite this

Copy

Qinglan ZHAO, Dong ZHENG, Xiangxue LI, Yinghui ZHANG, Xiaoli DONG, "Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform" in IEICE TRANSACTIONS on Fundamentals, vol. E100-A, no. 9, pp. 1965-1972, September 2017, doi: 10.1587/transfun.E100.A.1965.
Abstract: As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1ⁿ of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1ⁿ. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1965/_p

Copy

@ARTICLE{e100-a_9_1965,
author={Qinglan ZHAO, Dong ZHENG, Xiangxue LI, Yinghui ZHANG, Xiaoli DONG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform},
year={2017},
volume={E100-A},
number={9},
pages={1965-1972},
abstract={As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1ⁿ of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1ⁿ. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).},
keywords={},
doi={10.1587/transfun.E100.A.1965},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1965
EP - 1972
AU - Qinglan ZHAO
AU - Dong ZHENG
AU - Xiangxue LI
AU - Yinghui ZHANG
AU - Xiaoli DONG
PY - 2017
DO - 10.1587/transfun.E100.A.1965
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1ⁿ of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1ⁿ. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).
ER -