Characterizing Linear Structures of Boolean Functions from Arithmetic Walsh Transform

• ZHAO Qinglan

  School of Information Security Engineering, Shanghai Jiao Tong University School of Telecommunication and Information Engineering, Xi'an University of Post and Telecommunications

• ZHENG Dong

  School of Telecommunication and Information Engineering, Xi'an University of Post and Telecommunications

• LI Xiangxue

  Department of Computer Science and Technology, East China Normal University

• ZHANG Yinghui

  School of Telecommunication and Information Engineering, Xi'an University of Post and Telecommunications

• DONG Xiaoli

  School of Telecommunication and Information Engineering, Xi'an University of Post and Telecommunications

抄録

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).

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A (9), 1965-1972, 2017

  一般社団法人 電子情報通信学会

キーワード

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

詳細情報

• CRID: 1390282681288022400
• NII論文ID: 130006038254
• DOI: 10.1587/transfun.e100.a.1965
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E100.A/9/E100.A_1965/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可