تقرير
Trace Monomial Boolean Functions with Large High-Order Nonlinearities
| العنوان: | Trace Monomial Boolean Functions with Large High-Order Nonlinearities |
|---|---|
| المؤلفون: | Gao, Jinjie, Kan, Haibin, Li, Yuan, Xu, Jiahua, Wang, Qichun |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Cryptography and Security, Computer Science - Computational Complexity, Mathematics - Rings and Algebras |
| الوصف: | Exhibiting an explicit Boolean function with a large high-order nonlinearity is an important problem in cryptography, coding theory, and computational complexity. We prove lower bounds on the second-order, third-order, and higher-order nonlinearities of some trace monomial Boolean functions. We prove lower bounds on the second-order nonlinearities of functions $\mathrm{tr}_n(x^7)$ and $\mathrm{tr}_n(x^{2^r+3})$ where $n=2r$. Among all trace monomials, our bounds match the best second-order nonlinearity lower bounds by \cite{Car08} and \cite{YT20} for odd and even $n$ respectively. We prove a lower bound on the third-order nonlinearity for functions $\mathrm{tr}_n(x^{15})$, which is the best third-order nonlinearity lower bound. For any $r$, we prove that the $r$-th order nonlinearity of $\mathrm{tr}_n(x^{2^{r+1}-1})$ is at least $2^{n-1}-2^{(1-2^{-r})n+\frac{r}{2^{r-1}}-1}- O(2^{\frac{n}{2}})$. For $r \ll \log_2 n$, this is the best lower bound among all explicit functions. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2309.11229 |
| رقم الأكسشن: | edsarx.2309.11229 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |