info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[digest] 2022 Week 42
13 views
Skip to first unread message
IACR ePrint Archive
Oct 23, 2022, 3:21:27 PM10/23/22
to
## In this issue
1. [2022/1340] Understanding the Duplex and Its Security
2. [2022/1397] Synchronous Perfectly Secure Message Transmission ...
3. [2022/1398] MILP-aided Cryptanalysis of the FUTURE Block Cipher
4. [2022/1399] Low-latency implementation of the GIFT cipher on ...
5. [2022/1400] EdMSM: Multi-Scalar-Multiplication for recursive ...
6. [2022/1401] Improved Constant-weight PIR with an Extension for ...
7. [2022/1402] Sorting Attacks Resilient Authentication Protocol ...
8. [2022/1403] On the Dual Attack of LWE Schemes in the Presence ...
9. [2022/1404] Reducing an LWE Instance by Modular Hints and its ...
10. [2022/1405] Subverting Deniability
11. [2022/1406] Leveling Dilithium against Leakage: Revisited ...
12. [2022/1407] Threshold Linear Secret Sharing to the Rescue of ...
13. [2022/1408] Improved Biometrics-Authenticated Key Exchange
14. [2022/1409] SNARGs and PPAD Hardness from the Decisional ...
15. [2022/1410] Breaking and Protecting the Crystal: Side-Channel ...
16. [2022/1411] Cryptographic Administration for Secure Group Messaging
17. [2022/1412] Boolean Polynomial Evaluation for the Masses
## 2022/1340
* Title: Understanding the Duplex and Its Security
* Authors: Bart Mennink
* [Permalink](https://eprint.iacr.org/2022/1340)
* [Download](https://eprint.iacr.org/2022/1340.pdf)
### Abstract
At SAC 2011, Bertoni et al. introduced the keyed duplex construction as a tool to build permutation based authenticated encryption schemes. The construction was generalized to full-state absorption by Mennink et al. (ASIACRYPT 2015). Daemen et al. (ASIACRYPT 2017) generalized it further to cover much more use cases, and proved security of this general construction, and Dobraunig and Mennink (ASIACRYPT 2019) derived a leakage resilience security bound for this construction. Due to its generality, the full-state keyed duplex construction that we know today has plethora applications, but the flip side of the coin is that the general construction is hard to grasp and the corresponding security bounds are very complex. Consequently, the state-of-the-art results on the full-state keyed duplex construction are not used to the fullest. In this work, we revisit the history of the duplex construction, give a comprehensive discussion of its possibilities and limitations, and demonstrate how the two security bounds (of Daemen et al. and Dobraunig and Mennink) can be interpreted in particular applications of the duplex.
## 2022/1397
* Title: Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees
* Authors: Giovanni Deligios, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2022/1397)
* [Download](https://eprint.iacr.org/2022/1397.pdf)
### Abstract
Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary.
\emph{Perfectly-secure} SMT protocols in synchronous and asynchronous networks are resilient up to $\ell/2$ and $\ell/3$ corruptions respectively. In this work, we ask whether it is possible to achieve a perfect SMT protocol that simultaneously tolerates $t_s < \ell/2$ corruptions when the network is synchronous, and $t_a < \ell/3$ when the network is asynchronous.
We completely resolve this question by showing that perfect SMT is possible if and only if $2t_a + t_s < \ell$. In addition, we provide a concretely round-efficient solution for the (slightly worse) trade-off $t_a + 2t_s < \ell$.
As a direct application of our results, following the recent work by Appan, Chandramouli, and Choudhury [PODC'22], we obtain an $n$-party perfectly-secure synchronous multi-party computation protocol with asynchronous fallback over any network with connectivity $\ell$, as long as $t_a + 3t_s <n$ and $2t_a + t_s < \ell$.
## 2022/1398
* Title: MILP-aided Cryptanalysis of the FUTURE Block Cipher
* Authors: Murat Burhan İlter, Ali Aydin Selcuk
* [Permalink](https://eprint.iacr.org/2022/1398)
* [Download](https://eprint.iacr.org/2022/1398.pdf)
### Abstract
FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions.
In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model. Through the MILP analysis, we were able to find differential and linear distinguishers for up to 5 rounds of FUTURE, extending the known distinguishers of the cipher by one round.
## 2022/1399
* Title: Low-latency implementation of the GIFT cipher on RISC-V architectures
* Authors: Gheorghe Pojoga, Kostas Papagiannopoulos
* [Permalink](https://eprint.iacr.org/2022/1399)
* [Download](https://eprint.iacr.org/2022/1399.pdf)
### Abstract
Lightweight cryptography is a viable solution for constrained computational environments that require a secure communication channel. To standardize lightweight primitives, NIST has published a call for algorithms that address needs like compactness, low-latency, low-power/energy, etc. Among the candidates, the GIFT family of block ciphers was utilized in various NIST candidates due to its high-security margin and small gate footprint. As a result of their hardware-oriented design, software implementations of GIFT require additional optimization techniques such as bitslicing and fixslicing to achieve optimal performance. Even though the performance of these methods has been assessed for several ISA families such as x86 and ARM, there is currently a lack of data with regards to their acceleration capabilities for RISC-V. Since this ISA is an important element of the growing open-hardware movement, our goal is to address this knowledge gap. Therefore, we have developed several assembly implementations for both GIFT-64 and GIFT-128, using the RV32I ISA, and performed a quantitative assessment of their performance using a physical board i.e., Hifive1 Rev B. Our study has shown that by using bitslicing the number of clock cycles can be reduced by 69.33% for GIFT-64 and 71.38% for GIFT-128, compared to a naive assembly implementation, while fixslicing decreases the number of clock cycles by 85.7% (GIFT-64) and 81.28% (GIFT-128). Nonetheless, the preferred technique is fixslicing with key pre-computation, which can achieve a reduction of 88.69% (GIFT-64) and 95.05% (GIFT-128), while maintaining relatively low memory requirements of 938 bytes (GIFT-64) and 1388 bytes (GIFT-128), respectively.
## 2022/1400
* Title: EdMSM: Multi-Scalar-Multiplication for recursive SNARKs and more
* Authors: Youssef EL Housni, Gautam Botrel
* [Permalink](https://eprint.iacr.org/2022/1400)
* [Download](https://eprint.iacr.org/2022/1400.pdf)
### Abstract
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. This is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions.
Accelerating the MSM over these curves on mobile devices is critical for deployment of recursive proof systems on mobile applications. This work is implemented in Go and uses hand-written arm64 assembly for accelerating the finite field arithmetic (bigint). This work was implemented as part of a submission to the ZPrize competition in the open division “Accelerating MSM on Mobile” (https://www.zprize.io/). We achieved a 78% speedup over the ZPrize baseline implementation in Rust.
## 2022/1401
* Title: Improved Constant-weight PIR with an Extension for Multi-query
* Authors: Jian Liu, Jingyu Li, Di Wu, Kui Ren
* [Permalink](https://eprint.iacr.org/2022/1401)
* [Download](https://eprint.iacr.org/2022/1401.pdf)
### Abstract
Homomorphic equality operator is essential for many secure computation tasks such as private information retrieval (PIR). However, the folklore homomorphic equality operator is typically considered to be impractical as its multiplicative depth depends on the input bit-length. In Usenix SEC '22, Mahdavi-Kerschbaum propose a homomorphic equality operator with a constant multiplicative depth, based on constant-weight code. On that basis, they propose constant-weight PIR (CwPIR for short); compared with other PIR protocols, CwPIR is more friendly to databases with large payloads and can support keyword query almost for free. Unfortunately, CwPIR cannot support databases with a large number of elements, which limits its real-world impact.
In this paper, we propose a homomorphic constant-weight equality operator that supports batch processing, hence it can perform thousands of equality checks with a much smaller amortized cost. Based on this improved homomorphic equality operator, we propose a novel PIR protocol named PIRANA, which inherits all advantages of CwPIR with a significant improvement in supporting more elements. We further extend PIRANA to support multi-query. To the best of our knowledge, PIRANA is the first multi-query PIR that can save both computation and communication. Our experimental results show that our single-query PIRANA is upto 30.8× faster than CwPIR; our multi-query PIRANA saves upto 163.9× communication over the state-of-the-art multi-query PIR (with a similar computational cost).
## 2022/1402
* Title: Sorting Attacks Resilient Authentication Protocol for CMOS Image Sensor Based PUF
* Authors: Chandan Kumar, Mahendra Rathor, Urbi Chatterjee
* [Permalink](https://eprint.iacr.org/2022/1402)
* [Download](https://eprint.iacr.org/2022/1402.pdf)
### Abstract
Physically Unclonable Functions (PUFs) have emerged as a viable and cost-effective method for device authentication and key generation. Recently, CMOS image sensors have been exploited as PUF for hardware fingerprinting in mobile devices. As CMOS image sensors are readily available in modern devices such as smartphones, laptops etc., it eliminates the need for additional hardware for implementing a PUF structure. In ISIC2014, an authentication protocol has been proposed to generate PUF signatures using a CMOS image sensor by leveraging the fixed pattern noise (FPN) of certain pixel values. This makes the PUF candidate an interesting target for adversarial attacks. In this work, we testify that a simple sorting attack and a win-rate (WR) based sorting attack can be launched in this architecture to predict the PUF response for given a challenge. We also propose a modified authentication protocol as a countermeasure to make it resilient against simple sorting and WR sorting attacks. The proposed work reduces the accuracy of prediction due to simple sorting attack and WR sorting attack by approximately 14% compared to the existing approach.
## 2022/1403
* Title: On the Dual Attack of LWE Schemes in the Presence of Hints
* Authors: Han Wu, Xiaoyun Wang, Guangwu Xu
* [Permalink](https://eprint.iacr.org/2022/1403)
* [Download](https://eprint.iacr.org/2022/1403.pdf)
### Abstract
Combining theoretical-based traditional attack method with practical-based side-channel attack method provides more accurate security estimations for post-quantum cryptosystems. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes.
This paper develops a general Fourier analytic framework to work with the dual attack in the presence of hints. Distinguishers that depend on specific geometric properties related to hints are established. The Fourier transform of discretized multivariate conditional Gaussian distribution on $\mathbb{Z}_q^d$ is carefully computed and estimated, some geometric characteristics of the resulting distinguisher are explored and a new model of dual attack is proposed. In our framework, an adversary performs the BKZ algorithm directly in a projected lattice to find short projection components, and then recovers them by MLLL algorithm to make a distinction. This method relies on a reasonable assumption and is backed up by naturally formed mathematical arguments. The improvements and the assumption are validated by experiments. For examples, for a Kyber768 instance, with 200 hints, the blocksize can be reduced by at least 188 and the time complexity can be reduced by a factor of greater than $2^{55}$. After adding 300 hints to a FireSaber instance, even in the worst case, the blocksize drops from 819 to 542, and the cost drops from $2^{255.61}$ to $2^{174.72}$.
## 2022/1404
* Title: Reducing an LWE Instance by Modular Hints and its Applications to Primal Attack, Dual Attack and BKW Attack
* Authors: Han Wu, Xiaoyun Wang, Guangwu Xu
* [Permalink](https://eprint.iacr.org/2022/1404)
* [Download](https://eprint.iacr.org/2022/1404.pdf)
### Abstract
An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.
## 2022/1405
* Title: Subverting Deniability
* Authors: Marcel Armour, Elizabeth A. Quaglia
* [Permalink](https://eprint.iacr.org/2022/1405)
* [Download](https://eprint.iacr.org/2022/1405.pdf)
### Abstract
Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message.
DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines security from the point of view of the adversary while remaining undetected by users. ASAs have been considered against a number of primitives including digital signatures, symmetric encryption and pseudo-random generators. However, public-key encryption has presented a less fruitful target, as the sender's only secrets are plaintexts and ASA techniques generally do not provide sufficient bandwidth to leak these.
In this work, we show that subversion attacks against deniable encryption schemes present an attractive opportunity for an adversary. We note that whilst the notion is widely accepted, there are as yet no practical deniable PKE schemes; we demonstrate the feasibility of ASAs targeting deniable encryption using a representative scheme as a proof of concept. We also provide a formal model and discuss how to mitigate ASAs targeting deniable PKE schemes. Our results strengthen the security model for deniable encryption and highlight the necessity of considering subversion in the design of practical schemes.
## 2022/1406
* Title: Leveling Dilithium against Leakage: Revisited Sensitivity Analysis and Improved Implementations
* Authors: Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Markus Schönauer, Tobias Schneider, François-Xavier Standaert, Christine van Vredendaal
* [Permalink](https://eprint.iacr.org/2022/1406)
* [Download](https://eprint.iacr.org/2022/1406.pdf)
### Abstract
CRYSTALS-Dilithium has been selected by the NIST as the new standard for
post-quantum digital signatures. In this work, we revisit the side-channel
countermeasures of Dilithium in three directions. First, we improve its
sensitivity analysis by classifying intermediate computations according their
physical security requirements. This allows us to identify which parts of
Dilithium must be protected against Differential Power Analysis (DPA), which
parts must be protected against Simple Power Analysis (SPA) and which parts can
leak in an unbounded manner. Second, we provide improved gadgets dedicated to
Dilithium, taking advantage of recent advances in masking conversion
algorithms. Third, we combine these contributions with standard shuffling
techniques in order to design so-called leveled implementations that offer an
improved security vs. performance trade-off compared to the state-of-the-art.
Our benchmarking results additionally put forward that the randomized version
of Dilithium can lead to significantly more efficient implementations (than its
deterministic version) when side-channel attacks are a concern.
## 2022/1407
* Title: Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head
* Authors: Thibauld Feneuil, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2022/1407)
* [Download](https://eprint.iacr.org/2022/1407.pdf)
### Abstract
The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations proposed so far rely on additive secret sharing.
In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general MPC protocol model capturing most of the existing MPCitH schemes, we show that our approach improves the soundness of the underlying proof system from $1/N$ down to $1/\binom{N}{\ell}$, where $N$ is the number of parties and $\ell$ is the threshold of the sharing scheme. While very general, our technique is limited to a number of parties $N \leq |\mathbb{F}|$, where $\mathbb{F}$ is the field underlying the statement, because of the MDS conjecture.
Applying our approach with a low-threshold LSSS also boosts the performance of the proof system by making the MPC emulation cost independent of $N$ for both the prover and the verifier. The gain is particularly significant for the verification time which becomes logarithmic in $N$ (while the prover still has to generate and commit the $N$ input shares). We further generalize and improve our framework: we show how homomorphic commitments can get rid of the linear complexity of the prover, we generalize our result to any quasi-threshold LSSS, and we describe an efficient batching technique relying on Shamir's secret sharing.
We finally apply our techniques to specific use-cases. We first propose a variant of the recent SDitH signature scheme achieving new interesting trade-offs. In particular, for a signature size of 10 KB, we obtain a verification time lower than $0.5$ ms, which is competitive with SPHINCS+, while achieving much faster signing. We further apply our batching technique to two different contexts: batched SDitH proofs and batched proofs for general arithmetic circuits based on the Limbo proof system. In both cases, we obtain an amortized proof size lower than $1/10$ of the baseline scheme when batching a few dozen statements, while the amortized performances are also significantly improved.
## 2022/1408
* Title: Improved Biometrics-Authenticated Key Exchange
* Authors: Pia Bauspieß, Tjerand Silde, Alexandre Tullot, Anamaria Costache, Christian Rathgeb, Jascha Kolberg, Christoph Busch
* [Permalink](https://eprint.iacr.org/2022/1408)
* [Download](https://eprint.iacr.org/2022/1408.pdf)
### Abstract
Biometric data are uniquely suited for connecting individuals to their digital identities. Deriving cryptographic key exchange from successful biometric authentication therefore gives an additional layer of trust compared to password-authenticated key exchange. However, biometric data differ from passwords in two crucial points: firstly, they are sensitive personal data that need to be protected on a long-term basis. Secondly, efficient feature extraction and comparison components resulting in high intra-subject tolerance and low inter-subject distinguishability, documented with good biometric performance, need to be applied in order to prevent zero-effort impersonation attacks.
In this work, we present a protocol for secure and efficient biometrics-authenticated key exchange that fulfils the above requirements of biometric information protection compliant with ISO/IEC 24745. The protocol is based on established fuzzy vault schemes and validated with good recognition performance. We build our protocol from established primitives for password-authenticated key exchange using oblivious pseudo-random functions. Our protocol is independent of the biometric modality and can be instantiated both based on the security of discrete logarithms and lattices.
We provide an open-source implementation of our protocol instantiated with elliptic curves and a state-of-the art unlinkable fingerprint fuzzy vault scheme that is practical with transaction times of less than one second from the image capture to the completed key exchange.
## 2022/1409
* Title: SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
* Authors: Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2022/1409)
* [Download](https://eprint.iacr.org/2022/1409.pdf)
### Abstract
We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman assumption. Our SNARG is also unambiguous: for every (true) statement $x$, it is computationally hard to find any accepting proof for $x$ other than the proof produced by the prescribed prover strategy.
We obtain our result by showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system. Our new technical contributions are (1) giving a $TC^0$ circuit family for finding roots of cubic polynomials over a special family of characteristic $2$ fields (Healy-Viola, STACS '06) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC '90) only involve degree $3$ polynomials over said fields.
Along the way, since we can instantiate Fiat-Shamir for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) computationally hard problems in the complexity class $\mathsf{PPAD}$, assuming the sub-exponential hardness of DDH. Previous $\mathsf{PPAD}$ hardness results all required either bilinear maps or the learning with errors assumption.
## 2022/1410
* Title: Breaking and Protecting the Crystal: Side-Channel Analysis of Dilithium in Hardware
* Authors: Hauke Steffen, Georg Land, Lucie Kogelheide, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2022/1410)
* [Download](https://eprint.iacr.org/2022/1410.pdf)
### Abstract
The lattice-based CRYSTALS-Dilithium signature schemes has been selected for standardization by the NIST. As part of the selection process, a large number of implementations for platforms like x86, ARM Cortex-M4, or - on the hardware side - Xilinx Artix-7 have been presented and discussed by experts. Moreover, the software implementations have been subject to side-channel analysis with several attacks being published.
Until now, however, an analysis of Dilithium hardware implementations and their peculiarities have not taken place. With this work, we aim to fill this gap, presenting an analysis of vulnerable operations and practically showing a successful profiled SPA and a CPA on a recent hardware implementation by Beckwith et al. Our SPA attack requires 700000 profiling traces and targets the first NTT stage. After profiling, we can find pairs of coefficients with 1101 traces. The CPA attack finds secret coefficients with as low as 66000 traces. Our attack emphasizes that noise-generation in hardware is not sufficient as mitigation measure for SCA. As a consequence, we present countermeasures and show that they effectively prevent both attacks.
## 2022/1411
* Title: Cryptographic Administration for Secure Group Messaging
* Authors: David Balbás, Daniel Collins, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2022/1411)
* [Download](https://eprint.iacr.org/2022/1411.pdf)
### Abstract
Many real-world group messaging systems delegate group administration to the application level, failing to provide formal guarantees related to group membership.
Taking a cryptographic approach to group administration can prevent both implementation and protocol design pitfalls that result in a loss of confidentiality and consistency for group members.
In this work, we introduce a cryptographic framework for the design of group messaging protocols that offer strong security guarantees for group membership.
To this end, we extend the continuous group key agreement (CGKA) paradigm used in the ongoing IETF MLS group messaging standardisation process and introduce the administrated CGKA (A-CGKA) primitive.
Our primitive natively enables a subset of group members, the group admins, to control the addition and removal of parties and to update their own keying material in a secure manner.
We embed A-CGKA with a novel correctness notion which provides guarantees for group evolution and consistency, and a security model that prevents even corrupted (non-admin) members from forging messages that add new users to a group.
Moreover, we present two efficient and modular constructions of group administrators that are correct and secure with respect to our definitions.
Finally, we propose, implement, and benchmark an efficient extension of MLS that integrates cryptographic administrators.
Our constructions admit little overhead over running a CGKA and can be extended to support advanced admin functionalities.
## 2022/1412
* Title: Boolean Polynomial Evaluation for the Masses
* Authors: Charles Bouillaguet
* [Permalink](https://eprint.iacr.org/2022/1412)
* [Download](https://eprint.iacr.org/2022/1412.pdf)
### Abstract
This article gives improved algorithms to evaluate a multivariate Boolean
polynomial over all the possible values of its input variables. Such a
procedure is often used in cryptographic attacks against symmetric schemes.
More precisely, we provide improved and simplified versions of the
Fast Exhaustive Search algorithm presented at CHES'10 and of the
space-efficient Moebius transform given by Dinur at EUROCRYPT'21.
The new algorithms require $\mathcal{O}(d 2^n)$ operations with a degree-$d$
polynomial and operate in-place.
We provide the full C code of a complete implementation under
the form of a ``user-friendly'' library called BeanPolE, which we hope
could be helpful to other cryptographers. This paper actually contains
all the code, which is quite short.
1. [2022/1340] Understanding the Duplex and Its Security
2. [2022/1397] Synchronous Perfectly Secure Message Transmission ...
3. [2022/1398] MILP-aided Cryptanalysis of the FUTURE Block Cipher
4. [2022/1399] Low-latency implementation of the GIFT cipher on ...
5. [2022/1400] EdMSM: Multi-Scalar-Multiplication for recursive ...
6. [2022/1401] Improved Constant-weight PIR with an Extension for ...
7. [2022/1402] Sorting Attacks Resilient Authentication Protocol ...
8. [2022/1403] On the Dual Attack of LWE Schemes in the Presence ...
9. [2022/1404] Reducing an LWE Instance by Modular Hints and its ...
10. [2022/1405] Subverting Deniability
11. [2022/1406] Leveling Dilithium against Leakage: Revisited ...
12. [2022/1407] Threshold Linear Secret Sharing to the Rescue of ...
13. [2022/1408] Improved Biometrics-Authenticated Key Exchange
14. [2022/1409] SNARGs and PPAD Hardness from the Decisional ...
15. [2022/1410] Breaking and Protecting the Crystal: Side-Channel ...
16. [2022/1411] Cryptographic Administration for Secure Group Messaging
17. [2022/1412] Boolean Polynomial Evaluation for the Masses
## 2022/1340
* Title: Understanding the Duplex and Its Security
* Authors: Bart Mennink
* [Permalink](https://eprint.iacr.org/2022/1340)
* [Download](https://eprint.iacr.org/2022/1340.pdf)
### Abstract
At SAC 2011, Bertoni et al. introduced the keyed duplex construction as a tool to build permutation based authenticated encryption schemes. The construction was generalized to full-state absorption by Mennink et al. (ASIACRYPT 2015). Daemen et al. (ASIACRYPT 2017) generalized it further to cover much more use cases, and proved security of this general construction, and Dobraunig and Mennink (ASIACRYPT 2019) derived a leakage resilience security bound for this construction. Due to its generality, the full-state keyed duplex construction that we know today has plethora applications, but the flip side of the coin is that the general construction is hard to grasp and the corresponding security bounds are very complex. Consequently, the state-of-the-art results on the full-state keyed duplex construction are not used to the fullest. In this work, we revisit the history of the duplex construction, give a comprehensive discussion of its possibilities and limitations, and demonstrate how the two security bounds (of Daemen et al. and Dobraunig and Mennink) can be interpreted in particular applications of the duplex.
## 2022/1397
* Title: Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees
* Authors: Giovanni Deligios, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2022/1397)
* [Download](https://eprint.iacr.org/2022/1397.pdf)
### Abstract
Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary.
\emph{Perfectly-secure} SMT protocols in synchronous and asynchronous networks are resilient up to $\ell/2$ and $\ell/3$ corruptions respectively. In this work, we ask whether it is possible to achieve a perfect SMT protocol that simultaneously tolerates $t_s < \ell/2$ corruptions when the network is synchronous, and $t_a < \ell/3$ when the network is asynchronous.
We completely resolve this question by showing that perfect SMT is possible if and only if $2t_a + t_s < \ell$. In addition, we provide a concretely round-efficient solution for the (slightly worse) trade-off $t_a + 2t_s < \ell$.
As a direct application of our results, following the recent work by Appan, Chandramouli, and Choudhury [PODC'22], we obtain an $n$-party perfectly-secure synchronous multi-party computation protocol with asynchronous fallback over any network with connectivity $\ell$, as long as $t_a + 3t_s <n$ and $2t_a + t_s < \ell$.
## 2022/1398
* Title: MILP-aided Cryptanalysis of the FUTURE Block Cipher
* Authors: Murat Burhan İlter, Ali Aydin Selcuk
* [Permalink](https://eprint.iacr.org/2022/1398)
* [Download](https://eprint.iacr.org/2022/1398.pdf)
### Abstract
FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions.
In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model. Through the MILP analysis, we were able to find differential and linear distinguishers for up to 5 rounds of FUTURE, extending the known distinguishers of the cipher by one round.
## 2022/1399
* Title: Low-latency implementation of the GIFT cipher on RISC-V architectures
* Authors: Gheorghe Pojoga, Kostas Papagiannopoulos
* [Permalink](https://eprint.iacr.org/2022/1399)
* [Download](https://eprint.iacr.org/2022/1399.pdf)
### Abstract
Lightweight cryptography is a viable solution for constrained computational environments that require a secure communication channel. To standardize lightweight primitives, NIST has published a call for algorithms that address needs like compactness, low-latency, low-power/energy, etc. Among the candidates, the GIFT family of block ciphers was utilized in various NIST candidates due to its high-security margin and small gate footprint. As a result of their hardware-oriented design, software implementations of GIFT require additional optimization techniques such as bitslicing and fixslicing to achieve optimal performance. Even though the performance of these methods has been assessed for several ISA families such as x86 and ARM, there is currently a lack of data with regards to their acceleration capabilities for RISC-V. Since this ISA is an important element of the growing open-hardware movement, our goal is to address this knowledge gap. Therefore, we have developed several assembly implementations for both GIFT-64 and GIFT-128, using the RV32I ISA, and performed a quantitative assessment of their performance using a physical board i.e., Hifive1 Rev B. Our study has shown that by using bitslicing the number of clock cycles can be reduced by 69.33% for GIFT-64 and 71.38% for GIFT-128, compared to a naive assembly implementation, while fixslicing decreases the number of clock cycles by 85.7% (GIFT-64) and 81.28% (GIFT-128). Nonetheless, the preferred technique is fixslicing with key pre-computation, which can achieve a reduction of 88.69% (GIFT-64) and 95.05% (GIFT-128), while maintaining relatively low memory requirements of 938 bytes (GIFT-64) and 1388 bytes (GIFT-128), respectively.
## 2022/1400
* Title: EdMSM: Multi-Scalar-Multiplication for recursive SNARKs and more
* Authors: Youssef EL Housni, Gautam Botrel
* [Permalink](https://eprint.iacr.org/2022/1400)
* [Download](https://eprint.iacr.org/2022/1400.pdf)
### Abstract
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. This is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions.
Accelerating the MSM over these curves on mobile devices is critical for deployment of recursive proof systems on mobile applications. This work is implemented in Go and uses hand-written arm64 assembly for accelerating the finite field arithmetic (bigint). This work was implemented as part of a submission to the ZPrize competition in the open division “Accelerating MSM on Mobile” (https://www.zprize.io/). We achieved a 78% speedup over the ZPrize baseline implementation in Rust.
## 2022/1401
* Title: Improved Constant-weight PIR with an Extension for Multi-query
* Authors: Jian Liu, Jingyu Li, Di Wu, Kui Ren
* [Permalink](https://eprint.iacr.org/2022/1401)
* [Download](https://eprint.iacr.org/2022/1401.pdf)
### Abstract
Homomorphic equality operator is essential for many secure computation tasks such as private information retrieval (PIR). However, the folklore homomorphic equality operator is typically considered to be impractical as its multiplicative depth depends on the input bit-length. In Usenix SEC '22, Mahdavi-Kerschbaum propose a homomorphic equality operator with a constant multiplicative depth, based on constant-weight code. On that basis, they propose constant-weight PIR (CwPIR for short); compared with other PIR protocols, CwPIR is more friendly to databases with large payloads and can support keyword query almost for free. Unfortunately, CwPIR cannot support databases with a large number of elements, which limits its real-world impact.
In this paper, we propose a homomorphic constant-weight equality operator that supports batch processing, hence it can perform thousands of equality checks with a much smaller amortized cost. Based on this improved homomorphic equality operator, we propose a novel PIR protocol named PIRANA, which inherits all advantages of CwPIR with a significant improvement in supporting more elements. We further extend PIRANA to support multi-query. To the best of our knowledge, PIRANA is the first multi-query PIR that can save both computation and communication. Our experimental results show that our single-query PIRANA is upto 30.8× faster than CwPIR; our multi-query PIRANA saves upto 163.9× communication over the state-of-the-art multi-query PIR (with a similar computational cost).
## 2022/1402
* Title: Sorting Attacks Resilient Authentication Protocol for CMOS Image Sensor Based PUF
* Authors: Chandan Kumar, Mahendra Rathor, Urbi Chatterjee
* [Permalink](https://eprint.iacr.org/2022/1402)
* [Download](https://eprint.iacr.org/2022/1402.pdf)
### Abstract
Physically Unclonable Functions (PUFs) have emerged as a viable and cost-effective method for device authentication and key generation. Recently, CMOS image sensors have been exploited as PUF for hardware fingerprinting in mobile devices. As CMOS image sensors are readily available in modern devices such as smartphones, laptops etc., it eliminates the need for additional hardware for implementing a PUF structure. In ISIC2014, an authentication protocol has been proposed to generate PUF signatures using a CMOS image sensor by leveraging the fixed pattern noise (FPN) of certain pixel values. This makes the PUF candidate an interesting target for adversarial attacks. In this work, we testify that a simple sorting attack and a win-rate (WR) based sorting attack can be launched in this architecture to predict the PUF response for given a challenge. We also propose a modified authentication protocol as a countermeasure to make it resilient against simple sorting and WR sorting attacks. The proposed work reduces the accuracy of prediction due to simple sorting attack and WR sorting attack by approximately 14% compared to the existing approach.
## 2022/1403
* Title: On the Dual Attack of LWE Schemes in the Presence of Hints
* Authors: Han Wu, Xiaoyun Wang, Guangwu Xu
* [Permalink](https://eprint.iacr.org/2022/1403)
* [Download](https://eprint.iacr.org/2022/1403.pdf)
### Abstract
Combining theoretical-based traditional attack method with practical-based side-channel attack method provides more accurate security estimations for post-quantum cryptosystems. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes.
This paper develops a general Fourier analytic framework to work with the dual attack in the presence of hints. Distinguishers that depend on specific geometric properties related to hints are established. The Fourier transform of discretized multivariate conditional Gaussian distribution on $\mathbb{Z}_q^d$ is carefully computed and estimated, some geometric characteristics of the resulting distinguisher are explored and a new model of dual attack is proposed. In our framework, an adversary performs the BKZ algorithm directly in a projected lattice to find short projection components, and then recovers them by MLLL algorithm to make a distinction. This method relies on a reasonable assumption and is backed up by naturally formed mathematical arguments. The improvements and the assumption are validated by experiments. For examples, for a Kyber768 instance, with 200 hints, the blocksize can be reduced by at least 188 and the time complexity can be reduced by a factor of greater than $2^{55}$. After adding 300 hints to a FireSaber instance, even in the worst case, the blocksize drops from 819 to 542, and the cost drops from $2^{255.61}$ to $2^{174.72}$.
## 2022/1404
* Title: Reducing an LWE Instance by Modular Hints and its Applications to Primal Attack, Dual Attack and BKW Attack
* Authors: Han Wu, Xiaoyun Wang, Guangwu Xu
* [Permalink](https://eprint.iacr.org/2022/1404)
* [Download](https://eprint.iacr.org/2022/1404.pdf)
### Abstract
An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.
## 2022/1405
* Title: Subverting Deniability
* Authors: Marcel Armour, Elizabeth A. Quaglia
* [Permalink](https://eprint.iacr.org/2022/1405)
* [Download](https://eprint.iacr.org/2022/1405.pdf)
### Abstract
Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message.
DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines security from the point of view of the adversary while remaining undetected by users. ASAs have been considered against a number of primitives including digital signatures, symmetric encryption and pseudo-random generators. However, public-key encryption has presented a less fruitful target, as the sender's only secrets are plaintexts and ASA techniques generally do not provide sufficient bandwidth to leak these.
In this work, we show that subversion attacks against deniable encryption schemes present an attractive opportunity for an adversary. We note that whilst the notion is widely accepted, there are as yet no practical deniable PKE schemes; we demonstrate the feasibility of ASAs targeting deniable encryption using a representative scheme as a proof of concept. We also provide a formal model and discuss how to mitigate ASAs targeting deniable PKE schemes. Our results strengthen the security model for deniable encryption and highlight the necessity of considering subversion in the design of practical schemes.
## 2022/1406
* Title: Leveling Dilithium against Leakage: Revisited Sensitivity Analysis and Improved Implementations
* Authors: Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Markus Schönauer, Tobias Schneider, François-Xavier Standaert, Christine van Vredendaal
* [Permalink](https://eprint.iacr.org/2022/1406)
* [Download](https://eprint.iacr.org/2022/1406.pdf)
### Abstract
CRYSTALS-Dilithium has been selected by the NIST as the new standard for
post-quantum digital signatures. In this work, we revisit the side-channel
countermeasures of Dilithium in three directions. First, we improve its
sensitivity analysis by classifying intermediate computations according their
physical security requirements. This allows us to identify which parts of
Dilithium must be protected against Differential Power Analysis (DPA), which
parts must be protected against Simple Power Analysis (SPA) and which parts can
leak in an unbounded manner. Second, we provide improved gadgets dedicated to
Dilithium, taking advantage of recent advances in masking conversion
algorithms. Third, we combine these contributions with standard shuffling
techniques in order to design so-called leveled implementations that offer an
improved security vs. performance trade-off compared to the state-of-the-art.
Our benchmarking results additionally put forward that the randomized version
of Dilithium can lead to significantly more efficient implementations (than its
deterministic version) when side-channel attacks are a concern.
## 2022/1407
* Title: Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head
* Authors: Thibauld Feneuil, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2022/1407)
* [Download](https://eprint.iacr.org/2022/1407.pdf)
### Abstract
The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations proposed so far rely on additive secret sharing.
In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general MPC protocol model capturing most of the existing MPCitH schemes, we show that our approach improves the soundness of the underlying proof system from $1/N$ down to $1/\binom{N}{\ell}$, where $N$ is the number of parties and $\ell$ is the threshold of the sharing scheme. While very general, our technique is limited to a number of parties $N \leq |\mathbb{F}|$, where $\mathbb{F}$ is the field underlying the statement, because of the MDS conjecture.
Applying our approach with a low-threshold LSSS also boosts the performance of the proof system by making the MPC emulation cost independent of $N$ for both the prover and the verifier. The gain is particularly significant for the verification time which becomes logarithmic in $N$ (while the prover still has to generate and commit the $N$ input shares). We further generalize and improve our framework: we show how homomorphic commitments can get rid of the linear complexity of the prover, we generalize our result to any quasi-threshold LSSS, and we describe an efficient batching technique relying on Shamir's secret sharing.
We finally apply our techniques to specific use-cases. We first propose a variant of the recent SDitH signature scheme achieving new interesting trade-offs. In particular, for a signature size of 10 KB, we obtain a verification time lower than $0.5$ ms, which is competitive with SPHINCS+, while achieving much faster signing. We further apply our batching technique to two different contexts: batched SDitH proofs and batched proofs for general arithmetic circuits based on the Limbo proof system. In both cases, we obtain an amortized proof size lower than $1/10$ of the baseline scheme when batching a few dozen statements, while the amortized performances are also significantly improved.
## 2022/1408
* Title: Improved Biometrics-Authenticated Key Exchange
* Authors: Pia Bauspieß, Tjerand Silde, Alexandre Tullot, Anamaria Costache, Christian Rathgeb, Jascha Kolberg, Christoph Busch
* [Permalink](https://eprint.iacr.org/2022/1408)
* [Download](https://eprint.iacr.org/2022/1408.pdf)
### Abstract
Biometric data are uniquely suited for connecting individuals to their digital identities. Deriving cryptographic key exchange from successful biometric authentication therefore gives an additional layer of trust compared to password-authenticated key exchange. However, biometric data differ from passwords in two crucial points: firstly, they are sensitive personal data that need to be protected on a long-term basis. Secondly, efficient feature extraction and comparison components resulting in high intra-subject tolerance and low inter-subject distinguishability, documented with good biometric performance, need to be applied in order to prevent zero-effort impersonation attacks.
In this work, we present a protocol for secure and efficient biometrics-authenticated key exchange that fulfils the above requirements of biometric information protection compliant with ISO/IEC 24745. The protocol is based on established fuzzy vault schemes and validated with good recognition performance. We build our protocol from established primitives for password-authenticated key exchange using oblivious pseudo-random functions. Our protocol is independent of the biometric modality and can be instantiated both based on the security of discrete logarithms and lattices.
We provide an open-source implementation of our protocol instantiated with elliptic curves and a state-of-the art unlinkable fingerprint fuzzy vault scheme that is practical with transaction times of less than one second from the image capture to the completed key exchange.
## 2022/1409
* Title: SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
* Authors: Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2022/1409)
* [Download](https://eprint.iacr.org/2022/1409.pdf)
### Abstract
We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman assumption. Our SNARG is also unambiguous: for every (true) statement $x$, it is computationally hard to find any accepting proof for $x$ other than the proof produced by the prescribed prover strategy.
We obtain our result by showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system. Our new technical contributions are (1) giving a $TC^0$ circuit family for finding roots of cubic polynomials over a special family of characteristic $2$ fields (Healy-Viola, STACS '06) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC '90) only involve degree $3$ polynomials over said fields.
Along the way, since we can instantiate Fiat-Shamir for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) computationally hard problems in the complexity class $\mathsf{PPAD}$, assuming the sub-exponential hardness of DDH. Previous $\mathsf{PPAD}$ hardness results all required either bilinear maps or the learning with errors assumption.
## 2022/1410
* Title: Breaking and Protecting the Crystal: Side-Channel Analysis of Dilithium in Hardware
* Authors: Hauke Steffen, Georg Land, Lucie Kogelheide, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2022/1410)
* [Download](https://eprint.iacr.org/2022/1410.pdf)
### Abstract
The lattice-based CRYSTALS-Dilithium signature schemes has been selected for standardization by the NIST. As part of the selection process, a large number of implementations for platforms like x86, ARM Cortex-M4, or - on the hardware side - Xilinx Artix-7 have been presented and discussed by experts. Moreover, the software implementations have been subject to side-channel analysis with several attacks being published.
Until now, however, an analysis of Dilithium hardware implementations and their peculiarities have not taken place. With this work, we aim to fill this gap, presenting an analysis of vulnerable operations and practically showing a successful profiled SPA and a CPA on a recent hardware implementation by Beckwith et al. Our SPA attack requires 700000 profiling traces and targets the first NTT stage. After profiling, we can find pairs of coefficients with 1101 traces. The CPA attack finds secret coefficients with as low as 66000 traces. Our attack emphasizes that noise-generation in hardware is not sufficient as mitigation measure for SCA. As a consequence, we present countermeasures and show that they effectively prevent both attacks.
## 2022/1411
* Title: Cryptographic Administration for Secure Group Messaging
* Authors: David Balbás, Daniel Collins, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2022/1411)
* [Download](https://eprint.iacr.org/2022/1411.pdf)
### Abstract
Many real-world group messaging systems delegate group administration to the application level, failing to provide formal guarantees related to group membership.
Taking a cryptographic approach to group administration can prevent both implementation and protocol design pitfalls that result in a loss of confidentiality and consistency for group members.
In this work, we introduce a cryptographic framework for the design of group messaging protocols that offer strong security guarantees for group membership.
To this end, we extend the continuous group key agreement (CGKA) paradigm used in the ongoing IETF MLS group messaging standardisation process and introduce the administrated CGKA (A-CGKA) primitive.
Our primitive natively enables a subset of group members, the group admins, to control the addition and removal of parties and to update their own keying material in a secure manner.
We embed A-CGKA with a novel correctness notion which provides guarantees for group evolution and consistency, and a security model that prevents even corrupted (non-admin) members from forging messages that add new users to a group.
Moreover, we present two efficient and modular constructions of group administrators that are correct and secure with respect to our definitions.
Finally, we propose, implement, and benchmark an efficient extension of MLS that integrates cryptographic administrators.
Our constructions admit little overhead over running a CGKA and can be extended to support advanced admin functionalities.
## 2022/1412
* Title: Boolean Polynomial Evaluation for the Masses
* Authors: Charles Bouillaguet
* [Permalink](https://eprint.iacr.org/2022/1412)
* [Download](https://eprint.iacr.org/2022/1412.pdf)
### Abstract
This article gives improved algorithms to evaluate a multivariate Boolean
polynomial over all the possible values of its input variables. Such a
procedure is often used in cryptographic attacks against symmetric schemes.
More precisely, we provide improved and simplified versions of the
Fast Exhaustive Search algorithm presented at CHES'10 and of the
space-efficient Moebius transform given by Dinur at EUROCRYPT'21.
The new algorithms require $\mathcal{O}(d 2^n)$ operations with a degree-$d$
polynomial and operate in-place.
We provide the full C code of a complete implementation under
the form of a ``user-friendly'' library called BeanPolE, which we hope
could be helpful to other cryptographers. This paper actually contains
all the code, which is quite short.
0 new messages