Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions

Xian Mo Zhang; Yuliang Zheng; H. Imai

doi:10.1109/ISIT.1998.709044

Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions

Xian Mo Zhang, Yuliang Zheng, H. Imai

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

Abstract

This paper studies nonlinear characteristics of (Boolean) functions which are important in cryptography. The main contributions of this paper are: (1) we show that the restriction of a function on a coset has significant influence on cryptographic properties of the function, (2) we identify relationships between the nonlinearity of a function and the distribution of terms in the polynomial representation of the function, (3) we prove that cycles of odd length in the terms, as well as quadratic terms, in a function play an important role in determining the nonlinearity of the function. Results in this paper will contribute to the study of new cryptanalytic attacks on encryption algorithms, and counter-measures against such attacks.

Original language	English
Title of host publication	Proceedings - 1998 IEEE International Symposium on Information Theory, ISIT 1998
Pages	439
Number of pages	1
DOIs	https://doi.org/10.1109/ISIT.1998.709044
Publication status	Published - 1998
Event	1998 IEEE International Symposium on Information Theory, ISIT - 1998 - Cambridge, United States Duration: 16 Aug 1998 → 21 Aug 1998

Other

Other	1998 IEEE International Symposium on Information Theory, ISIT - 1998
Country/Territory	United States
City	Cambridge
Period	16/08/98 → 21/08/98

Access to Document

10.1109/ISIT.1998.709044

Cite this

@inproceedings{77c7cfdd9c824d7db958453e1d506752,

title = "Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions",

abstract = "This paper studies nonlinear characteristics of (Boolean) functions which are important in cryptography. The main contributions of this paper are: (1) we show that the restriction of a function on a coset has significant influence on cryptographic properties of the function, (2) we identify relationships between the nonlinearity of a function and the distribution of terms in the polynomial representation of the function, (3) we prove that cycles of odd length in the terms, as well as quadratic terms, in a function play an important role in determining the nonlinearity of the function. Results in this paper will contribute to the study of new cryptanalytic attacks on encryption algorithms, and counter-measures against such attacks.",

author = "Zhang, \{Xian Mo\} and Yuliang Zheng and H. Imai",

year = "1998",

doi = "10.1109/ISIT.1998.709044",

language = "English",

isbn = "0780350006",

pages = "439",

booktitle = "Proceedings - 1998 IEEE International Symposium on Information Theory, ISIT 1998",

note = "1998 IEEE International Symposium on Information Theory, ISIT - 1998 ; Conference date: 16-08-1998 Through 21-08-1998",

}

Zhang, XM, Zheng, Y & Imai, H 1998, Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions. in Proceedings - 1998 IEEE International Symposium on Information Theory, ISIT 1998., 709044, pp. 439, 1998 IEEE International Symposium on Information Theory, ISIT - 1998, Cambridge, Massachusetts, United States, 16/08/98. https://doi.org/10.1109/ISIT.1998.709044

TY - GEN

T1 - Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions

AU - Zhang, Xian Mo

AU - Zheng, Yuliang

AU - Imai, H.

PY - 1998

Y1 - 1998

N2 - This paper studies nonlinear characteristics of (Boolean) functions which are important in cryptography. The main contributions of this paper are: (1) we show that the restriction of a function on a coset has significant influence on cryptographic properties of the function, (2) we identify relationships between the nonlinearity of a function and the distribution of terms in the polynomial representation of the function, (3) we prove that cycles of odd length in the terms, as well as quadratic terms, in a function play an important role in determining the nonlinearity of the function. Results in this paper will contribute to the study of new cryptanalytic attacks on encryption algorithms, and counter-measures against such attacks.

AB - This paper studies nonlinear characteristics of (Boolean) functions which are important in cryptography. The main contributions of this paper are: (1) we show that the restriction of a function on a coset has significant influence on cryptographic properties of the function, (2) we identify relationships between the nonlinearity of a function and the distribution of terms in the polynomial representation of the function, (3) we prove that cycles of odd length in the terms, as well as quadratic terms, in a function play an important role in determining the nonlinearity of the function. Results in this paper will contribute to the study of new cryptanalytic attacks on encryption algorithms, and counter-measures against such attacks.

UR - https://www.scopus.com/pages/publications/84890382805

U2 - 10.1109/ISIT.1998.709044

DO - 10.1109/ISIT.1998.709044

M3 - Conference proceeding contribution

AN - SCOPUS:84890382805

SN - 0780350006

SN - 9780780350007

SP - 439

BT - Proceedings - 1998 IEEE International Symposium on Information Theory, ISIT 1998

T2 - 1998 IEEE International Symposium on Information Theory, ISIT - 1998

Y2 - 16 August 1998 through 21 August 1998

ER -

Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this