Fast Algebraic Immunity of $2^m+2$ & $2^m+3$ variables Majority Function

Yindong Chen; Fei Guo; Liu Zhang

Paper 2019/286 Original: eprint.iacr.org/2019/286 ↗

Fast Algebraic Immunity of $2^m+2$ & $2^m+3$ variables Majority Function

Yindong Chen

Fei Guo

Liu Zhang

Abstract

Boolean functions used in some cryptosystems of stream ciphers should satisfy various criteria simultaneously to resist some known attacks. The fast algebraic attack (FAA) is feasible if one can find a nonzero function $g$ of low algebraic degree and a function $h$ of algebraic degree significantly lower than $n$ such that $f\cdot g=h$. Then one new cryptographic property fast algebraic immunity was proposed, which measures the ability of Boolean functions to resist FAAs. It is a great challenge to determine the exact values of the fast algebraic immunity of an infinite class of Boolean functions with optimal algebraic immunity. In this letter, we explore the exact fast algebraic immunity of two subclasses of the majority function.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2019-03-19: last updated; 2019-03-19: published
Short URL: https://ia.cr/2019/286
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2019/286,
      author = {Yindong Chen and Fei Guo and Liu Zhang},
      title = {Fast Algebraic Immunity of $2^m+2$ & $2^m+3$ variables Majority Function},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/286},
      year = {2019},
      url = {https://eprint.iacr.org/2019/286}
}