Weightwise degree-d (WWdd) functions are Boolean functions that, on each set of fixed Hamming weight, coincide with a function of degree at most d. They generalize both symmetric functions and the Hidden Weight Bit Function (HWBF), which has been studied in cryptography for its favorable properties. In this work, we establish a general upper bound on the algebraic immunity of such functions, a key security parameter against algebraic attacks on stream ciphers like filtered Linear Feedback Shift Registers (LFSRs). We construct explicit low-degree annihilators for WWdd functions with small d, and show how to generalize these constructions. As an application, we prove that the algebraic immunity of the HWBF is upper bounded by \(3\sqrt{n}\) disproving a result from 2011 that claimed a lower bound of n/3. We then apply our technique to several generalizations of the HWBF proposed since 2021 for homomorphically friendly constructions and LFSR-based ciphers, refining or refuting results from six prior works.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

From at Least n/3 to at Most \(3\sqrt{n}\) : Correcting the Algebraic Immunity of the Hidden Weight Bit Function

  • Pierrick Méaux

摘要

Weightwise degree-d (WWdd) functions are Boolean functions that, on each set of fixed Hamming weight, coincide with a function of degree at most d. They generalize both symmetric functions and the Hidden Weight Bit Function (HWBF), which has been studied in cryptography for its favorable properties. In this work, we establish a general upper bound on the algebraic immunity of such functions, a key security parameter against algebraic attacks on stream ciphers like filtered Linear Feedback Shift Registers (LFSRs). We construct explicit low-degree annihilators for WWdd functions with small d, and show how to generalize these constructions. As an application, we prove that the algebraic immunity of the HWBF is upper bounded by \(3\sqrt{n}\) disproving a result from 2011 that claimed a lower bound of n/3. We then apply our technique to several generalizations of the HWBF proposed since 2021 for homomorphically friendly constructions and LFSR-based ciphers, refining or refuting results from six prior works.