In recent years, formal verification has emerged as a crucial method for assessing security against Side-Channel attacks of masked implementations, owing to its remarkable versatility and high degree of automation. However, formal verification still faces technical bottlenecks in balancing accuracy and efficiency, thereby limiting its scalability. Former efficient tools like maskVerif and CocoAlma are often inaccurate when verifying schemes utilizing properties of Boolean functions. Later,...

Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme,...

The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$. We prove the existence of decompositions using quadratic and linear power permutations for all permutations when...

The analysis of real-life incidents has revealed that state-level efforts are made to camouflage the intentional flaws in the mathematical layer of an S-Box to exploit the information-theoretic properties, i.e., Kuznyechik. To extract and investigate the common features in the backdoored S-Box(es), this research thoroughly examines them from the perspective of 24 cryptanalytic attack vectors available in the open literature. We have debunked the earlier claims by the backdoor engineers that...

Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the...

An important tool that has contributed to collision search on Keccak/SHA3 is the Target Difference Algorithm (TDA) and its inter- nal differential counterpart Target Internal Difference Algorithm (TIDA), which were introduced by Dinur et al. in separate works in FSE 2012 and 2013 respectively. These algorithms provide an ingenious way of extend- ing the differential trails by one round and exploiting the affine subspaces generated due to the low algebraic degree of the Keccak S-box....

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis side-channel attacks which was proposed by Nikova, Rechberger, and Rijmen in 2006. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no generic construction was ever presented. In this paper, we present the first universal threshold implementation with $t+2$ shares that...

The LowMC family of block ciphers was first proposed by Albrecht et al. in [ARS+15], specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3-bit S-box as the sole non-linear transformation in the algorithm. In contrast, both the linear layer and round key generation are achieved through multiplications of full rank matrices over GF(2). The cipher is instantiable using a diverse set of default configurations, some of...

Research on the design of masked cryptographic hardware circuits in the past has mostly focused on reducing area and randomness requirements. However, many embedded devices like smart cards and IoT nodes also need to meet certain performance criteria, which is why the latency of masked hardware circuits also represents an important metric for many practical applications. The root cause of latency in masked hardware circuits is the need for additional register stages that synchronize the...

With the enormous increase in portable cryptographic devices, physical attacks are becoming similarly popular. One of the most common physical attacks is Side-Channel Analysis (SCA), extremely dangerous due to its non-invasive nature. Threshold Implementations (TI) was proposed as the first countermeasure to provide provable security in masked hardware implementations. While most works on hardware masking are focused on optimizing the area requirements, with the newer and smaller...

In order to provide benefits in the areas of fully homomorphic encryption (FHE), multi-party computation (MPC), post-quantum signature schemes, or efficient masked implementations for side-channel resistance, reducing the number of multiplications has become a quite popular trend for the symmetric cryptographic primitive designs. With an aggressive design strategy exploiting the extremely simple and low-degree S-box and low number of rounds, Pyjamask, the fundamental block cipher of the AEAD...

Several efforts have been seen claiming the lightweight block ciphers as a necessarily suitable substitute in securing the Internet of Things. Currently, it has been able to envisage as a pervasive frame of reference almost all across the privacy preserving of smart and sensor-oriented appliances. Different approaches are likely to be inefficient, bringing desired degree of security considering the easiness and surely the process of simplicity but security. Strengthening the well-known...

Side-channel attacks are a serious problem in the implementation of cryptosystems. Masking is an effective countermeasure to this problem and it has been actively studied for implementations of block ciphers. An obstacle to efficient masked implementation is the complexity of an evaluation of multiplication, which is quadratic in the order of masking. A natural approach to this problem is to explore ways to reduce the number of multiplications required to compute an S-box. Algebraic...

Designing cryptographic permutations and block ciphers using a substitution-permutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios. For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that...

Given a vectorial function $F:\mathbb{F}_2^n \mapsto \mathbb{F}_2^m$, the indicator $1_{{\cal G}_F}$ of its graph ${\cal G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ allows to express the algebraic degree of $F$ in a simple way. Exploiting the formula, obtained in a previous paper, for the graph indicator of a composite function $G\circ F$, that involves only a sum of products of $1_{{\cal G}_F}$ and $1_{{\cal G}_G}$, we deduce bounds on the algebraic degree of $G\circ F$, whose efficiency comes...

The effort in reducing the area of AES implementations has largely been focused on Application-Specific Integrated Circuits (ASICs) in which a tower field construction leads to a small design of the AES S-box. In contrast, a naive implementation of the AES S-box has been the status-quo on Field-Programmable Gate Arrays (FPGAs). A similar discrepancy holds for masking schemes - a well-known side-channel analysis countermeasure - which are commonly optimized to achieve minimal area in ASICs....

S-boxes, typically the only nonlinear part of a block cipher, are the heart of symmetric cryptographic primitives. They significantly impact the cryptographic strength and the implementation characteristics of an algorithm. Due to their simplicity, quadratic vectorial Boolean functions are preferred when efficient implementations for a variety of applications are of concern. Many characteristics of a function stay invariant under affine equivalence. So far, all 6-bit Boolean functions, 3-...

In the present day, AES is one the most widely used and most secure Encryption Systems prevailing. So, naturally lots of research work is going on to mount a significant attack on AES. Many different forms of Linear and differential cryptanalysis have been performed on AES. Of late, an active area of research has been Algebraic Cryptanalysis of AES, where although fast progress is being made, there are still numerous scopes for research and improvement. One of the major reasons behind this...

Many lightweight block ciphers apply a very simple key schedule in which the round keys only differ by addition of a round-specific constant. Generally, there is not much theory on how to choose appropriate constants. In fact, several of those schemes were recently broken using invariant attacks, i.e., invariant subspace or nonlinear invariant attacks. This work analyzes the resistance of such ciphers against invariant attacks and reveals the precise mathematical properties that render...

S-boxes are important building blocks in block ciphers. For secure design one should not choose an S-box that has low degree. In this work we consider minimum degree of an S-box which is the minimum value of the degree of the nonzero component functions of the S-box. For an S-box $F : {F_2}^n \rightarrow {F_2}^m$, there are $2^m - 1$ nonzero component functions, we show that there is a better way to determine the minimum degree of an S-box which does not require to check all the $2^m - 1$...

Substitution box (S-box) is an important component of block ciphers for providing confusion into the cryptosystems. The functions used as S-boxes should have low differential uniformity, high nonlinearity and high algebraic degree. Due to the lack of knowledge on the existence of APN permutations over $\mathbb{F}_{2^{2k}}$, which have the lowest differential uniformity, when $k>3$, they are often constructed from differentially 4-uniform permutations. Up to now, many infinite families of...

Since they were first proposed as a countermeasure against differential power analysis (DPA) in 2006, threshold schemes have attracted a lot of attention from the community concentrating on cryptographic implementations. What makes threshold schemes so attractive from an academic point of view is that they come with an information-theoretic proof of resistance against a specific subset of side-channel attacks: first-order DPA. From an industrial point of view they are attractive as a careful...

The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009. In this paper, we apply methods intended to reverse-engineer S-Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over $GF(2^3)$. More precisely, we show that it is a particular case of a permutation structure we...

In 2015, Todo introduced a property of multisets of a finite field called the division property. It is then used by Todo in an attack against the S7 S-box of the MISTY1 cipher. This paper provides a complete mathematical analysis of the division property. The tool we use is the discrete Fourier transform. We relate the division property to the natural concept of the degree of a subset of a finite field. This indeed provides a characterization of multisets satisfying the division property. In...

Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the...

In this paper we propose an efficient technique to compute algebraic degree of an S-box (minimum of algebraic degrees of its component functions). Using our technique we have calculated algebraic degree of a $26\times 64$ S-box.

The incidence matrix between a set of monomials and a set of vectors in $\F_2$ has a great importance in the study of coding theory, cryptography, linear algebra, combinatorics. The rank of these matrices are very useful while computing algebraic immunity($\ai$) of Boolean functions in cryptography literature~\cite{MPC04,DGM04}. Moreover, these matrices are very sparse and well structured. Thus, for aesthetic reason finding the rank of these matrices is also very interesting in mathematics....