Effective and Efficient Masking with Low Noise Using Small-Mersenne-Prime Ciphers

in Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques Lyon, France, April 23-27, 2023, Proceedings, Part IV (2023)

Embedded devices used in security applications are natural targets for physical attacks. Thus, enhancing their side-channel resistance is an important research challenge. A standard solution for this ... [more ▼]

Embedded devices used in security applications are natural targets for physical attacks. Thus, enhancing their side-channel resistance is an important research challenge. A standard solution for this purpose is the use of Boolean masking schemes, as they are well adapted to current block ciphers with efficient bitslice representations. Boolean masking guarantees that the security of an implementation grows exponentially in the number of shares under the assumption that leakages are sufficiently noisy (and independent). Unfortunately, it has been shown that this noise assumption is hardly met on low-end devices. In this paper, we therefore investigate techniques to mask cryptographic algorithms in such a way that their resistance can survive an almost complete lack of noise. Building on seed theoretical results of Dziembowski et al., we put forward that arithmetic encodings in prime fields can reach this goal. We first exhibit the gains that such encodings lead to thanks to a simulated information theoretic analysis of their leakage (with up to six shares). We then provide figures showing that on platforms where optimized arithmetic adders and multipliers are readily available (i.e., most MCUs and FPGAs), performing masked operations in small to medium Mersenne-prime fields as opposed to binary extension fields will not lead to notable implementation overheads. We compile these observations into a new AES-like block cipher, called AES-prime, which is well-suited to illustrate the remarkable advantages of masking in prime fields. We also confirm the practical relevance of our findings by evaluating concrete software (ARM Cortex-M3) and hardware (Xilinx Spartan-6) implementations. Our experimental results show that security gains over Boolean masking (and, more generally, binary encodings) can reach orders of magnitude despite the same amount of information being leaked per share. [less ▲]

Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices

in Applied Cryptography and Network Security - 21st International Conference ACNS 2023, Kyoto, Japan, June 19-22, 2023, Proceedings, Part I (2023)

We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured ... [more ▼]

We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length). Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from nonadaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation. On the whole, we get better security bounds, shorter signatures and faster algorithms. [less ▲]

On the weightwise nonlinearity of weightwise perfectly balanced functions

in Discrete Applied Mathematics (2022), 322

In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this ... [more ▼]

In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this criterion can take over WPB functions, deriving theoretic bounds, and exhibiting the first values. We emphasize the link between this minimum and weightwise affine functions, and we prove that for n≥8 no n-variable WPB function can have this property. Then, we focus on the distribution and the maximum of this criterion over the set of WPB functions. We provide theoretic bounds on the latter and algorithms to either compute or estimate the former, together with the results of our experimental studies for n up to 8. Finally, we present two new constructions of WPB functions obtained by modifying the support of linear functions for each set of fixed Hamming weight. This provides a large corpus of WPB function with proven weightwise nonlinearity, and we compare the weightwise nonlinearity of these constructions to the average value, and to the parameters of former constructions in 8 and 16 variables. [less ▲]

Towards Globally Optimized Hybrid Homomorphic Encryption - Featuring the Elisabeth Stream Cipher

in Towards Globally Optimized Hybrid Homomorphic Encryption - Featuring the Elisabeth Stream Cipher (2022)

Hybrid Homomorphic Encryption (HHE) reduces the amount of computation client-side and bandwidth usage in a Fully Homomorphic Encryption (FHE) framework. HHE requires the usage of specific symmetric ... [more ▼]

Hybrid Homomorphic Encryption (HHE) reduces the amount of computation client-side and bandwidth usage in a Fully Homomorphic Encryption (FHE) framework. HHE requires the usage of specific symmetric schemes that can be evaluated homomorphically efficiently. In this paper, we introduce the paradigm of Group Filter Permutator (GFP) as a generalization of the Improved Filter Permutator paradigm introduced by Méaux et al. From this paradigm, we specify Elisabeth, a family of stream cipher and give an instance: Elisabeth. After asserting the security of this scheme, we provide a Rust implementation of it and ensure its performance is comparable to state-of-the-art HHE. The true strength of Elisabeth lies in the available operations server-side: while the best HHE applications were limited to a few multiplications server-side, we used data sent through Elisabeth to homomorphically evaluate a neural network inference. Finally, we discuss the improvement and loss between the HHE and the FHE framework and give ideas to build more efficient schemes from the Elisabeth family. [less ▲]

Homomorphic encryption for privacy-friendly augmented democracy

in 2022 IEEE 21st Mediterranean Electrotechnical Conference (MELECON) (2022)

A Complete Study of Two Classes of Boolean Functions: Direct Sums of Monomials and Threshold Functions

in IEEE Transactions on Information Theory (2022), 68(5), 3404--3425

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also ... [more ▼]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [less ▲]

$\mathcal{S}_0$-equivalent classes, a new direction to find better weightwise perfectly balanced functions, and more

E-print/Working paper (n.d.)