Full Text:   <1273>

CLC number: TP301.6

On-line Access: 

Received: 2004-05-10

Revision Accepted: 2005-02-11

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3484

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.5 P.358~364


On the construction of cryptographically strong Boolean functions with desirable trade-off

Author(s):  REN Kui, PARK Jaemin, KIM Kwangjo

Affiliation(s):  ECE Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA; more

Corresponding email(s):   kren@ece.wpi.edu, jaemin@icu.ac.kr, kkj@icu.ac.kr

Key Words:  Boolean functions, Bent sequences, Nonlinearity, GAC, PC, Balancedness

REN Kui, PARK Jaemin, KIM Kwangjo. On the construction of cryptographically strong Boolean functions with desirable trade-off[J]. Journal of Zhejiang University Science A, 2005, 6(5): 358~364.

@article{title="On the construction of cryptographically strong Boolean functions with desirable trade-off",
author="REN Kui, PARK Jaemin, KIM Kwangjo",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T On the construction of cryptographically strong Boolean functions with desirable trade-off
%A REN Kui
%A PARK Jaemin
%A KIM Kwangjo
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 5
%P 358~364
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A0358

T1 - On the construction of cryptographically strong Boolean functions with desirable trade-off
A1 - REN Kui
A1 - PARK Jaemin
A1 - KIM Kwangjo
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 5
SP - 358
EP - 364
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A0358

This paper proposes a practical algorithm for systematically generating strong boolean functions (f:GF(2)nGF(2)) with cryptographic meaning. This algorithm takes bent function as input and directly outputs the resulted Boolean function in terms of truth table sequence. This algorithm was used to develop two classes of balanced boolean functions, one of which has very good cryptographic properties: nl(f)=22k-1-2k+2k-2 (n=2k), with the sum-of-squares avalanche characteristic of f satisfying σf=24k+23k+2+23k+23k-2 and the absolute avalanche characteristic of Δf satisfying Δf=2k+1. This is the best result up to now compared to existing ones. Instead of bent sequences, starting from random boolean functions was also tested in the algorithm. Experimental results showed that starting from bent sequences is highly superior to starting from random boolean functions.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Clark, J.A., Jacob, J.L., Stepney, S., Maitra, S., Millan, W., 2002. Evolving Boolean Functions Satisfying Multiple Criteria. International Conference on Cryptology in India(INDOCRYPT 2002, LNCS 2551, Springer-Verlag, p.246-259.

[2] Dobbertin, H., 1995. Construction of Bent Functions and Balanced Boolean Functions with High Nonlinearity. Fast Software Encryption(FSE’94, LNCS 1008, Springer-Verlag, p.61-74.

[3] Hou, X.D., 1993. Further results on the covering radii of the Reed-Muller codes. Design, Codes and Cryptography, 3(2):167-177.

[4] Kim, K., 1991. Construction of DES-like S-boxes Based on Boolean Functions Satisfying the SAC. Advances in Cryptology(Proc. of Asiacrypt’91, Lecture Notes in Computer Science, Springer-Verlag, p.59-72.

[5] Meier, W., Staffelbach, O., 1989. Nonlinearity Criteria for Cryptographic Functions. Advances in Cryptology(EUROCRYPT’89, LNCS 434, Springer-Verlag, p.549-562.

[6] Millan, W., Clark, A.J., Dawson, E., 1997. Smart Hill Climbing Finds Better Boolean Functions. Workshop on Selected Areas in Cryptology 1997, Workshop Record, p.50-63.

[7] Millan, W., Clark, A.J., Dawson, E., 1998. Heuristic Design of Cryptographically Strong Balanced Boolean Functions. Advance in Cryptology(EUROCRYPT’98, LNCS 1403, Springer-Verlag, p.489-499.

[8] Millan, W., Clark, A., Dawson, E., 1999. Boolean Function Design Using Hill Climbing Methods. Australasian Conference on Information Security and Privacy(ACISP’99, LNCS 1587, Springer-Verlag, p.1-11.

[9] Patterson, N.J., Wiedemann, D.H., 1983. The covering radius of the (215,6) Reed-Muller code is at least 16276. IEEE Transactions on Information Theory, IT-29(3):354-356.

[10] Preneel, B., Van Leekwijck, W., Van Linden, L., Govaerts, R., Vandewalle, J., 1990. Propagation Characteristics of Boolean Functions. Advances in Cryptology(EUROCRYPT’90, LNCS 473, Springer-Verlag, p.161-173.

[11] Rothaus, S., 1976. On bent functions. Journal of Combinatorial Theory, Ser. A, 20:300-305.

[12] Son, J.J., Lim, J.I., Chee, S., Sung, S.H., 1998. Global avalanche characteristics and nonlinearity of balanced Boolean functions. Information Processing Letters, 65(3):139-144.

[13] Stanica, P., 2002. Nonlinearity, local and global avalanche characteristics of balanced Boolean functions. Discrete Mathematics, 248(1-3):181-193.

[14] Stanica, P., 2004. Boolean functions with five controllable cryptographic properties. Designs, Codes and Cryptography, 31:147-157.

[15] Stanica, P., Sung, S.H., 2001. Improving the nonlinearity of certain balanced Boolean functions with good local and global avalanche characteristics. Information Processing Letters, 79(4):167-172.

[16] Sung, S.H., Chee, S., Park, C., 1999. Global avalanche characteristics and propagation criterion of balanced Boolean functions. Information Processing Letters, 69(1):21-24.

[17] Webster, F., Tavares, S.E., 1985. On the Design of S-boxes. Advances in Cryptology(CRYPTO’85, LNCS 218, Springer-Verlag, p.523-534.

[18] Zhang, X., Zheng, Y.L., 1995. GAC–the criterion of global avalanche characteristics of cryptographic functions. Journal of Universal Computer Science, 1(5):316-333.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE