## Abstract

This paper studies the properties and constructions of nonlinear functions, which are a core component of cryptographic primitives including data encryption algorithms and one-way hash functions. A main contrilMtion of this paper is to reveal the relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function.In particular, we prove that (i) if f, a Boolean function on V_{n}, satisfies the propagation criterion with respect to all but a subset R of vectors in V_{n}, then the nonlinearity of f satisfies N_{f} ≥ 2 ^{n-1}-2^{1/2(n+t)-1}, where t is the rank of R, and (ii) When |R| > 2, the nonzero vectors in R are linearly dependent. Furthermore we show that (iii) if |R|= 2 then n must be odd, the nonlinearity of f satisfies N_{f} = 2^{n-1} - 2^{1/2(n-l)}, and the nonzero vector in R must be a linear structure of f.(iv) there exists no function on V_{n} such that |R| = 3.(v) if |R| = 4 then n must be even, the nonlinearityof f satisfies N_{f} = 2^{n-1}-2^{1/2n}, and the nonzero vectors in R must be linear structures of f.(vi) if |R|=5 then n must be odd, the nonlinearity of f is N_{f}=2^{n-1}-2^{1/2(n-l)}, the four nonzero vectors in R, denoted by β_{l},β_{2},β_{3}and β_{4} are related by the equation β_{l} ⊕β_{2} ⊕ β_{3} ⊕ β_{4}= 0, and none of the four vectors is a linear structure of f. (vii) there exists no function on V_{n} such that |R| = 6. We also discuss the structures of functions with |R| = 2, 4, 5. In particular we show that these functions have close relationships with bent functions, and can be easily constructed from the latter.

Original language | English |
---|---|

Title of host publication | Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings |

Publisher | Springer, Springer Nature |

Pages | 119-132 |

Number of pages | 14 |

Volume | 917 |

ISBN (Print) | 9783540593393 |

Publication status | Published - 1995 |

Event | 4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994 - Wollongong, Australia Duration: 28 Nov 1994 → 1 Dec 1994 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 917 |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994 |
---|---|

Country/Territory | Australia |

City | Wollongong |

Period | 28/11/94 → 1/12/94 |