\documentclass[11pt]{article}
\setcounter{secnumdepth}{3}
\usepackage{makeidx}
\usepackage{mathrsfs,amsmath,amssymb,url,color,enumerate}
\usepackage{url}
%\usepackage{caption}
%\usepackage{subcaption}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\JJ}{\mathbb{J}}

\newcommand{\Fk}{{\mathbb F}_{2^k}}  
\newcommand{\F}{{\mathbb F}_{2^n}}
\newcommand{\FB}{{\mathbb F}_2}

\newcommand{\B}{{\cal B}}
\newcommand{\LL}{{\cal L}}
\newcommand{\V}{{\cal V}}
\newcommand{\G}{{\cal G}}
\newcommand{\I}{{\cal I}}
\newcommand{\W}{{\cal W}}
\newcommand{\Sp}{{\cal S}}

\newcommand{\J}{\mathcal{J}}
\newcommand{\NL}{\mathcal{NL}}
\def\cB{{\mathcal B}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\cM{{\mathcal M}}
\def\MM{{\mathcal M}}

\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\Aut}{\hbox{{\rm Aut}}}
\newcommand{\diag}{\mathrm{diag}}

\newtheorem{theorem}{Izrek}[section]
\newtheorem{theo}{Izrek}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{example}{Example}[section]
\newtheorem{ex}{Example}[section]
\newtheorem{op}{Open Problem}
\newtheorem{constr}{Construction}

\newcommand{\EQ}{\begin{equation}}
\newcommand{\EN}{\end{equation}}

\newenvironment{proof}{\begin{trivlist}\item[]{\em Proof. }}%
{\samepage\hfill$\square$\end{trivlist}}

\newcounter{case}
\newenvironment{case}[1][\unskip]{\refstepcounter{case}\sc
\medskip \noindent Case \thecase\ #1.\ }{\unskip\upshape}
\renewcommand{\thecase}{\arabic{case}}

\makeindex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{O ukrivljenih funkcijah, ki ležijo izven Maiorana-McFarland razreda}
\author{Nastja~Cepak\footnote{Univerza na Primorskem,
		FAMNIT \& IAM, Koper, Slovenija, email:{nastja.cepak@famnit.upr.si}}}

\date{}
\maketitle
\begin{abstract}

Teoretični temelji moderne kriptografije in informacijske teorije v splošnem so bili postavljeni leta $1948$ s prebojnim člankom Clauda Shannona ``A Mathematical Theory of Communication''. Da bi zadovoljila današnjim potrebam, mora kriptografija zagotoviti štiri osnovne storitve: zaupnost, integriteto podatkov, avtentikacijo in ne-odklonskost. Kriptografske sheme tem zahtevam uspejo zadostiti s sodelovanjem strokovnjakov z mnogih področij, med drugim s sodelovanjem matematikov. Eno od naših področij raziskovanja se osredotoča na Boolove funkcije, torej na funkcije, ki preslikajo niz enic in ničel v ali enico, ali ničlo. Takšne funkcije morajo glede na področje, kjer so uporabljene, zadostiti številnim pogojem. Eden od njih je lastnost nelinearnost. Boolove funkcije z maksimalno nelinearnostjo imenujemo ukrivljene funkcije. Do sedaj nam je uspelo opisati le malo splošnih družin takšnih funkcij, želimo pa doseči njihovo klasifikacijo. Zaradi tega je pomembno, da uspemo razviti pokazatelje, ki nam čim hitreje povedo, če je novo definirana ukrivljena funkcija zaobjeta v že poznanih definicijah, ali ne. 



\end{abstract}
{\bf Ključne besede:} kriptografija, Boolove funkcije, nelinearnost, ukrivljene funkcije, Maiorana-McFarland.\newline
{\bf MSC 2010}: 05A05, 06E30, 11T55, 94C10

\section{Uvod in opis problema}
V 60. letih prejšnjega stoletja so se kriptografi v različnih državah ukvarjali s problemom optimizacije izbire Boolovih funkcij za namene boljše varnosti informacij. Ena od optimiziranih lastnosti je bila \textit{nelinearnost}. Boolove funkcije, ki ležijo na največji možni razdalji od množice vseh afinih funkcij se imenujejo \textit{ukrivljene funkcije} (\textit{bent functions}). Ta razred Boolovih funkcij so prvi odkrili raziskovalci Združenih držav Amerike in Sovjetske zveze v sklopu ločenih vzporednih tajnih raziskovalnih projektov. Danes se obravnava Oscarja Rothausa kot prvega raziskovalca, ki je svetu javno predstavil ukrivljene funkcije. Prvič je opisal ukrivljene funkcije v klasificiranem članku leta $1966$, ki je šele čez deset let postal dostopen širši javnosti \cite{RO76}.

V naslednjih desetletjih raziskovanja ukrivljenih funkcij so se pokazala mnoga področja njihove uporabe. V teoriji kodiranja je, na primer, pokazano, da je iskanje premera pokritja Reed-Muller-jeve kode ekvivalentno iskanju Boolove funkcij z najvišjo nelinearnostjo \cite{Reed, Reed2}. Ukrivljene funkcije se uporabljajo tudi za konstrukcijo znanih Kerdockovih kod \cite{Kerdock1, Kerdock2}. Uporabljajo se tudi za načrtovanje zaporedij, ki se jih uporablja v sklopu določenih telekomunikacijskih tehnik, ki uporabljajo CDMA metodo (Code Division Multiple Access).

Na področju ukrivljenih funkcij ostajajo številna odprta vprašanja. Kar se tiče njihovega načrtovanja in klasifikacije, so poznane določene primarne konstrukcije, obstajajo pa tudi številne sekundarne konstrukcije, ki iz že znanih ukrivljenih funkcij konstruirajo nove. Zainteresiran bralec si lahko pogleda tudi lep pregled ukrivljenih funkcij, ki sta ga napisala Carlet in Mesnager \cite{CarlMes2016}.

Glavni problem sekundarnih konstrukcij je, da je novo konstruirane ukrivljene funkcije težko klasificirati. Natančneje, lahko se zgodi, da nekatere sekundarne konstrukcije generirajo funkcije, ki pripadajo kateremu od že poznanih primarnih razredov. V tem primeru je pomembna samo njihova eksplicitna reprezentacija. Dokazovati, da funkcije ležijo izven popolnih primarnih razredov je težka naloga. V tem članku so opisani rezultati (ne)vsebovanosti v popolnem razredu Maiorana-McFarland.

\section{Definicije}

Naj $\FF_2$ označuje binarno polje in naj bo $n$-dimenzionalni vektorski prostor nad poljem $\FF_2$ označen z $\FF_2^n = \{\textbf{x}  = (x_1, \ldots, x_n) : x_i \in \FF_2, \mbox{ za  } i = 1,  \ldots, n \}$. 
Razširitev Galoisovega polja dimenzije $n$ nad poljem $\FF_2$ označimo z $\FF_{2^n}$. Če odstranimo element $0$; označimo to z $\FF_{2^n}^*$.
Funkcija, ki slika iz prostora $\FF_2^n$ v prostor $\FF_2$ (oziroma, ekvivalentno, iz polja $\FF_{2^n}$ v polje $\FF_2$)
imenujemo {\em Boolova funkcija} v $n$ spremenljivkah. Množico vseh Boolovih funkcij v $n$ spremenljivkah označimo z 
$\mathcal{ B}_{n}$.

Walsheva transformacija funkcije
$f\in\mathcal{ B}_{n}$ v točki $ x \in \mathbb{F}_{2}^n$ je definirana kot
$$W_f(x) = \sum_{y \in \mathbb{F}_{2}^n}(-1)^{f(y)
+ x \cdot y},$$
kjer $``\cdot"$ označuje klasični notranji produkt dveh vektorjev.

Naj bo $n$ sodo število. Za funkcijo $f \in \mathcal{B}_n$ rečemo, da je\textit{ ukrivljena}, če in samo če
$W_f(x) \in \{2^{\frac{n}{2}}, -2^{\frac{n}{2}}\}$, za vse $x \in \mathbb{F}_{2}^n$, kar predstavlja največje možne vrednosti Walshevega spektra.

Maiorana-McFarland razred $\cal M$ je množica vseh Boolovih funkcij z $m$ spremenljivkami ($m=2n$) oblike
$f(x,y)=x \cdot \pi(y)+ g(y), \mbox{ za vse elemente } x, y\in\FF_2^n$, kjer je $\pi$ permutacija prostora $\FF_2^n$ in je $g$ poljubna Boolova funkcija nad prostorom $\FF_2^n$. Če razredu dodamo še vse funkcije, ki so afino ekvivalentne Maiorana-McFalrnad funkcijam, dobljeno množico označujemo z $\mathcal{M}^{\#}$.

Iz tega razreda je Carlet v \cite{CC93} razvil dva nova razreda ukrivljenih funkcij. Prvi je razred  $\cC$, ki vsebuje vse funkcije oblike $f(x,y) = x\cdot\pi(y)+ 1_{L^{\perp}}(x)$
kjer je $L$ poljubni linearni podprostor prostora $\FF_2^n$ in $\pi$ poljubna takšna permutacija prostora $\FF_2^n$, da je
$\pi^{-1}(a + L)$ afin podprostor za vse elemente $a\in \FF_2^n$.
Poleg tega z $L^{\perp}$ označimo prostor, orthogonalen prostoru $L$, in z  $1_{L^{\perp}}$ označimo indikatorsko Boolovo funkcijo, ki elemente, ki so vsebovani v prostoru $L^{\perp}$, slika v $1$ in vse ostale v $0$.
Pravimo, da permutacija $\pi^{-1}$ in podprostor $L$  zadostita lastnosti $(C)$.

Drugi razred je imenovan $\cD$ razred in je podobno definiran:
$f(x, y)=x\cdot\pi(y) + 1_{E_1}(x) 1_{E_2}(y),$
kjer je $\pi$ permutacija prostora $\FF_2^{n}$ in sta $E_1,E_2$ takšna linearna podprostora prostora $\FF_2^n$, da $\pi(E_2)=E_1^{\perp}$. Permutacija $\pi$ in podprostora $E_1$, $E_2$  zadostita lastnosti $(D)$.

Za še nekaj preostalih definicij, kot sta definicija linearne strukture in podrazreda $\cD_0$, napotimo bralca k \cite{AfterM}.

\section{Rezultati}

Prvi pomemben rezultat na področju dokazovanja vključenosti oziroma iz\-klju\-če\-nosti iz razreda Maiorana-McFarland je bil objavljen leta 2017 v \cite{RothEnes2016}, kjer je bila uporabljena posebna oblika Rothaus-ove konstrukcije za načr\-to\-vanje ukrivljene funkcije, ki je dokazljivo izven razreda $\MM$. Delo se je nadaljevalo v \cite{IET2020}.

Sledila je serija člankov, ki se je osredotočila na preplet med razredi $\cC, \cD$ in $\MM$. Prvi velik rezultat na tem področju je bil v svoji končni obliki objavljen v \cite{AfterM}.

\begin{theorem}[\cite{AfterM}]\label{the}
Naj bo $m=2n >6$ sodo celo število in naj bo $f(x,y)= x \cdot \pi(y)+ 1_{E_1}(x)1_{E_2}(y)$, kjer je $f$ ukrivljena funkcija v razredu $\cD$.
Če elementi $(\pi,E_1,E_2)$ zadostijo pogojem
\begin{enumerate}
  \item[1)]   $\dim( E_1)\geq 2$ in $\dim( E_2)\geq 2$;
  \item[2)]   $u \cdot \pi$  nima neničelnih linearnih struktur za vse elemente $u\in \FF_2^{n*}$;
  \item[3)]   $\deg(\pi)\leq n-\dim(E_2 )$,
\end{enumerate}
potem je $f$ ukrivljena funkcija v razredu $\cD$, ki leži izven razreda $\mathcal{M}^{\#}$.
\end{theorem}

V istem članku je bil podoben rezultat dosežen tudi za razreda $\cC$ in $\cD_0$. V sledečih izrekih so podobni rezultati dobljeni glede na zaostrovanje začetnih zahtev parametrov funkcije. Sledili so rezultati iz članka \cite{LinStructures}, ki se je ukvarjal s tem, kako sploh zadovoljiti strogim pogojem, ki jih zahteva izrek \ref{the}. Dokazano je, da pri določeni izberi podprostorov zahtevani pogoji sploh ne morejo biti zadovoljeni, predložene pa so tudi eksplicitne konstrukcije neskončni družin funkcij, ki pogojem uspejo zadostiti.

Članek \cite{AmarVecMM} je definiral nov superrazred, ki vsebuje tudi $\MM$ razred, ter proučeval, kako to vpliva na zahtevane pogoje za izključevanje funkcij. Skupaj s člankom \cite{EnZa} se osredotoča na vključenost vektorskih ukrivljenih funkcij iz $\MM$ razreda in posploši številne prej objavljene rezultate. Uvede tudi pojem šibke vključenosti/izključenosti iz razreda.

Za nadaljnjo branje svetujemo tudi \cite{AmarNewMethod}, \cite{PaAmar}, \cite{Kudin}.

\begin{thebibliography}{10}

\bibitem{AmarVecMM} A.~Bapi\'c, E.~Pasalic,
{\em Constructions of (vectorial) bent functions outside the completed Maiorana-McFarland class},
Discrete Applied Mathematics, 314, pp. 197-212, (2022).

\bibitem{AmarNewMethod} A.~Bapi\'c, E.~Pasalic,
{\em A new method for secondary constructions of vectorial bent functions},
Design, Codes and Cryptography, 89, pp. 2463-2475, (2021).

\bibitem{PaAmar}
{\sc E. Pasalic, A. Bapi\`{c},  F. Zhang, S. Kudin, Y. Wei.}
\newblock Explicit infinite families of bent functions outside the completed Maiorana–McFarland class.
\newblock {\em Designs, Codes and Cryptography}, 2023.

\bibitem{CC93}
C.~Carlet
\newblock Two New Classes of Bent Functions
\newblock Eurocrypt '93, LNCS.  vol. 765 (1994), pp. 77--101.

\bibitem{CarlMes2016}
C.~Carlet, and S.~Mesnager,
\newblock Four decades of research on bent functions,
\newblock \textit{Designs,  Codes and Cryptography}, vol. 78 (1) (2016), pp. 5--50.

\bibitem{Kerdock1}
P.~Delsarte,
\newblock An algebraic approach to the association schemes of coding theory,
\newblock PhD thesis, 1973.

\bibitem{Reed}
S.~Kavut, S.~Maitra, M.D.~Yucel,
\newblock Search for Boolean functions with excellent profiles in the rotation symmetric class,
\newblock \textit{IEEE Trans Inform Theory} 53.5 (2007), pp. 1743--1751.

\bibitem{Kudin}
{\sc S. Kudin, E. Pasalic}
\newblock A complete characterization of $\cD_0 \cap \cM^\#$ and a general framework for specifying bent functions in $\cC$ outside $\cM^\#$
\newblock {\em Designs, Codes and Cryptography} volume 90 (2022), pp. 1783–-1796.

\bibitem{LinStructures}
{\sc S. Kudin, E. Pasalic, N. Cepak, F. Zhang.}
\newblock Permutations without linear structures inducing bent functions outside the completed Maiorana-McFarland class.
\newblock {\em Cryptography and Communications}, vol. 14, pp. 101–-116, 2022.

 \bibitem{IET2020}
S. Liu, F. Zhang, E. Pasalic, S. Xia, Z. Zhuo.
{\em Further study on constructing bent functions outside the completed Maiorana-McFarland class}. 
\newblock IET Inf. Secur. 14(6): 654-660 (2020)

\bibitem{Reed2}
S.~Maitra, P.~Sarkar,
\newblock Maximum nonlinearity of symmetric Boolean functions on odd number of variables.
\newblock \textit{IEEE Trans Inform Theory} 48(9) 2002, pp. 2626--30.

\bibitem{EnZa}
{\sc E. Pasalic, F. Zhang, S. Kudin, Y. Wei.}
\newblock Vectorial bent functions weakly/strongly outside the completed Maiorana–McFarland class.
\newblock {\em Discrete Applied Mathematics}, vol. 294, pp 138--151, 2021.

\bibitem{RO76}
O.~S.~Rothaus,
\newblock On Bent Functions,
\newblock \textit{J. Combinatorial Theory, Ser. A}, vol.  20 (1976), pp. 300--305.

\bibitem{Kerdock2}
V.~M.~Sidelnikov,
\newblock On extremal polynomials used to estimate the size of codes,
\newblock \textit{Probl. Inform. Transm}, 16 (1980), pp. 174--186.

\bibitem{AfterM}
F.~Zhang, N.~Cepak, E.~Pasalic, Y.~Wei
\newblock Further analysis	of bent functions from $\cC$ and $\cD$ which are provably outside or inside $\cM^\#$,
\newblock Discrete Applied Mathematics, 285 (2020), pp. 458--472.

\bibitem{RothEnes2016}
{\sc F. Zhang, E. Pasalic, Y. Wei, N. Cepak.}
\newblock Constructing bent functions outside the Maiorana-McFarland class using a general form of Rothaus.
\newblock {\em  IEEE Transactions on Information Theory}, vol. 63, no. 8, pp. 5336 -- 5349, 2017.


\end{thebibliography}
\end{document}