# Mathematical Applications in Cryptography

Organizers:

- Francis N. Castro (Puerto Rico University)
- T. Aaron Gulliver (University of Victoria)
- Amr Youssef (Concordia University)

Schedule:

- Thursday, Jul 27 [Centre Mont Royal, Room Cartier I & II]
- 11:45 Sihem Mesnager (, University of Paris 8, Paris 13 and Telecom ParisTech), Recent advances on bent functions for symmetric cryptography
- 12:15 Claude Crépeau (McGill University), Relativistic Commitments and Zero-Knowledge Proofs
- 14:45 Francis N. Castro (Universidad de Puerto Rico Mayaguez), Diophantine Equations with Binomials Coefficents and Perturbations of Symmetric Boolean Functions
- 15:15 Dr. Valentin Suder (UVSQ), Two Notions of Differential Equivalence on Sboxes
- Friday, Jul 28 [Centre Mont Royal, Room Cartier I & II]
- 11:45 Daniel Panario (Carleton University), Ambiguity, deficiency and differential spectrum of low degree normalized permutation polynomials over finite fields
- 12:15 Jintai Ding (Cincinnati University), Post-Quantum Key Exchange from the LWE
- 14:15 Petr Lisonek (Simon Fraser University), Non-existence results for vectorial bent functions with Dillon-type exponents
- 14:45 Kenza Guenda (Victoria University), A Secure New Variant of the McEliece Cryptosystem

- Sihem Mesnager

, University of Paris 8, Paris 13 and Telecom ParisTechRecent advances on bent functions for symmetric cryptographyBoolean functions are important objects in discrete mathematics. They play a role in mathematics and in many domains of computer science. We will be mainly interested in their relationships with private-key cryptography. The talk is devoted to special families of Boolean functions which are viewed as important objects in combinatorics and the information theory framework (namely, cryptography and coding theory) : the so-called bent functions. Bent functions are maximally nonlinear Boolean functions. They are wonderful creatures introduced by O. Rothaus in the 1960's and initially studied by J. Dillon since 1974. For their own sake as interesting combinatorial objects, but also for their relations to coding theory (e.g. Reed-Muller codes, Kerdock codes, etc.), combinatorics (e.g. difference sets), design theory, sequence theory, and applications in cryptography (design of stream ciphers and of S-boxes for block ciphers), they have attracted a lot of research for four decades. We give a survey of the main results in bent functions and present new ones. - Claude Crépeau

McGill UniversityRelativistic Commitments and Zero-Knowledge ProofsWe present techniques for zero-knowledge proofs of NP statements using very few relativistic commitments, making it possible for two synchronized verifiers, far enough from each other, to test two synchronized provers, close enough to the verifiers, in such a way that * under the assumption that information cannot travel faster than the speed of light, only valid statements can be demonstrated by the provers (soundness) * the answers obtained by the verifiers are useless to convince an off-line third party of the validity of the statement (zero-knowledge). We achieve this by presenting a new interactive proof for NP languages that uses only 6 commitments at any point in the proof to be perfect zero-knowledge. Joint work with Lucas Stinchcombe and Nan Yang - Francis N. Castro

Universidad de Puerto Rico MayaguezDiophantine Equations with Binomials Coefficents and Perturbations of Symmetric Boolean FunctionsThis work presents a study of perturbations of symmetric Boolean functions. In particular, it establishes a connection between exponential sums of these perturbations and Diophantine equations of the form $$\sum_{l=0}^n \binom{n}{l} x_l,$$ where $x_l$ belongs to some fixed bounded subset $\Gamma$ of $\mathbb{Z}$. The concepts of trivially balanced symmetric Boolean function and sporadic balanced Boolean function are extended to this type of perturbations. An observation made by Canteaut and Videau for symmetric Boolean functions of fixed degree is extended. To be specific, it is proved that, excluding the trivial cases, balanced perturbations of fixed degree do not exist when the number of variables grows. Some sporadic balanced perturbations are presented. Finally, a beautiful but unexpected identity between perturbations of two very different symmetric Boolean functions is also included in this work. This is a joint work with Oscar Gonzalez and Luis Medina. - Dr. Valentin Suder

UVSQTwo Notions of Differential Equivalence on SboxesIn this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of \emph{DDT-equivalence} which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion, to what we call the \emph{$\gamma$-equivalence}, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions and provide an algorithm for computing the DDT-equivalence and the $\gamma$-equivalence classes for a given function. We study the sizes of these classes for some families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct. (Joint work with Christina Boura, Anne Canteaut and Jérémy Jean). - Daniel Panario

Carleton UniversityAmbiguity, deficiency and differential spectrum of low degree normalized permutation polynomials over finite fieldsLet $\mathbb{F}_q$ be the finite field of $q$ elements, $q$ a prime power. If $f: \mathbb{F}_q \to \mathbb{F}_q$ induces a bijection, $f$ is a*permutation polynomial*; if $f$ is monic, $f(0)=0$, and, when the degree $n$ of $f$ is not divisible by the characteristic of $\mathbb F_q$, the coefficient of $x^{n-1}$ is zero, $f$ is in*normalized*form. Normalized permutation polynomials are known exhaustively up to degree six. For $a \in \mathbb{F}_{q}^*$, the*difference map*of $f$ is defined as $\Delta_{f,a}(x) = f(x+a) - f(x)$. This map plays a central role in differential cryptanalisis. To resist linear and differential cryptanalysis, we want permutations functions $f$ such that $|\Delta_{f,a}^{-1}(b)|$ is low for all $a \in \mathbb{F}_{q}^*$ and $b \in \mathbb{F}_q$. We define $n_k(f)$ as the number of pairs $(a,b)$ such that $f(x+a)-f(x)=b$ has exactly $k$ solutions. The vector $[n_0(f),\ldots,n_q(f)]$ is the*spectrum*vector of the difference map of $f$. The*deficiency*of $f$ is $D(f) = n_0 (f)$; it measures how close the $\Delta_{f,a}$'s are to be surjective. The*(weighted) ambiguity*of $f$ is $A(f) = \sum_{0 \leq k \leq n } n_k (f) {k \choose 2}$; it measures how close the $\Delta_{f,a}$'s are to be injective. We give exact formulas for the differential spectrum, deficiency and ambiguity of all normalized permutation polynomials of degree up to six over finite fields. Joint work with Daniel Santana (Federal University of Santa Catarina, Brazil) and Qiang Wang (Carleton University, Canada) - Jintai Ding

Cincinnati UniversityPost-Quantum Key Exchange from the LWEIn this lecture, we present practical and provably secure (authenticated) key exchange protocol and password authenticated key exchange protocol, which are based on the learning with errors problems. These protocols areconceptually simple and have strong provable security properties. This type of new constructions were started in 2011-2012. These protocols are shown indeed practical. We will explain that all the existing LWE based key exchanges are variants of this fundamental design. In addition, we will explain some issues with key reuse and how to use the signal function invented for KE for authentication schemes. - Petr Lisonek

Simon Fraser UniversityNon-existence results for vectorial bent functions with Dillon-type exponentsVectorial bent functions with Dillon-type exponents have attracted attention because they are hyperbent whenever they are bent, and they achieve the highest possible algebraic degree among all bent functions on the same domain. We study monomial functions $f(x) = {\rm Tr}^{2m}_k(ax^{2^m-1})$ where $a\in{\mathbb F}_{2^{2m}}^*$ and ${\rm Tr}^{2m}_k$ denotes the trace from ${\mathbb F}_{2^{2m}}$ to ${\mathbb F}_{2^{k}}$. Muratovi\'{c}-Ribi\'{c}, Pasalic and Bajri\'{c} (IEEE Trans.\ Inform.\ Theory 2014) proved that $f$ is not bent when $k=m$. Lapierre and Lison\v{e}k (Proceedings ISIT 2016) proved that $f$ is not bent when $k=m/2$, $k\ge 2$. In the current work we further introduce new proof techniques and we prove that $f$ is not bent when $k=m/3$ where $k$ is odd, $k\ge 3$. Our techniques use results that relate the divisibility of the Kloosterman sum $K(a)$ by powers of $2$ and the coefficients of the characteristic polynomial of $a$ due to G\"olo\u{g}lu, Lison\v{e}k, McGuire and Moloney (IEEE Trans.\ Inform.\ Theory 2012). This is joint work with Luc Lapierre. - Kenza Guenda

Victoria UniversityA Secure New Variant of the McEliece CryptosystemIn this work joined with H. Mofek and T.A Gulliver we will be presenting a new version of the McEliece cryptosystem based on quasi-cyclic (QC) low density parity check (LDPC) codes and QC moderate density parity check (MDPC) codes. A modified self-shrinking generator is used to obtain random bits which are utilized in the cryptosystem. It is shown that this system is secure against the known attacks.