Technical Program

Paper Detail

Paper Title On (2n/3-1)-Resilient (n,2)-Functions
Paper IdentifierFR3.R9.2
Authors Denis S. Krotov, Sobolev Institute of Mathematics, Russia
Session Theoretical Cryptography
Location Pontoise, Level 5
Session Time Friday, 12 July, 14:30 - 16:10
Presentation Time Friday, 12 July, 14:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract A $\{00,01,10,11\}$-valued function on the vertices of the $n$-cube is called a $t$-resilient $(n,2)$-function if it has the same number of $00$s, $01$s, $10$s and $11$s among the vertices of every subcube of dimensional $t$. The Friedman and Fon-Der-Flaass bounds on the correlation immunity order say that such a function must satisfy $t\le 2n/3-1$; moreover, the $(2n/3-1)$-resilient $(n,2)$-functions correspond to the equitable partitions of the $n$-cube with the quotient matrix $[[0,r,r,r],[r,0,r,r],[r,r,0,r],[r,r,r,0]]$, $r=n/3$. We suggest constructions of such functions and corresponding partitions, showing connections with Latin hypercubes and binary $1$-perfect codes, characterizing the non-full-rank and the reducible functions from the considered class, and discussing the possibility to make a complete characterization of the class.