## In this issue

1. [2024/2061] Programming Equation Systems of Arithmetization- ...
2. [2024/2062] Two Halves Make a Whole: How to Reconcile Soundness ...
3. [2024/2063] The Number of the Beast: Reducing Additions in Fast ...
4. [2024/2064] (Deep) Learning about Elliptic Curve Cryptography
5. [2024/2065] Partial Exposure Attacks Against a Family of RSA- ...
6. [2024/2066] COCO: Coconuts and Oblivious Computations for ...
7. [2024/2067] Bypassing the characteristic bound in logUp
8. [2024/2068] Weightwise Almost Perfectly Balanced Functions, ...
9. [2024/2069] One Solves All: Exploring ChatGPT's Capabilities ...
10. [2024/2070] Sneaking up the Ranks: Partial Key Exposure Attacks ...
11. [2024/2071] Perfectly Secure Fluid MPC with Abort and Linear ...
12. [2024/2072] Advancements in Distributed RSA Key Generation: ...
13. [2024/2073] Succinct Partial Garbling from Groups and Applications
14. [2024/2074] EQSIGN: Practical Digital Signatures from the Non- ...
15. [2024/2075] Tightly-Secure Blind Signatures in Pairing-Free Groups
16. [2024/2076] Blind Signatures from Proofs of Inequality
17. [2024/2077] Report on evaluation of KpqC Round-2 candidates
18. [2024/2078] Strongly Secure Universal Thresholdizer
19. [2024/2079] Solving AES-SAT Using Side-Channel Hints: A ...
20. [2024/2080] Improved Lattice-Based Attack on Mersenne Low ...
21. [2024/2081] Generalized Cryptanalysis of Cubic Pell RSA
22. [2024/2082] ClusterGuard: Secure Clustered Aggregation for ...
23. [2024/2083] Fully Hybrid TLSv1.3 in WolfSSL on Cortex-M4
24. [2024/2084] Zero Knowledge Memory-Checking Techniques for ...
25. [2024/2085] Definition of End-to-end Encryption
26. [2024/2086] How To Think About End-To-End Encryption and AI: ...

## 2024/2061

* Title: Programming Equation Systems of Arithmetization-Oriented Primitives with Constraints
* Authors: Mengyu Chang, Kexin Qiao, Junjie Cheng, Changhai Ou, Liehuang Zhu
* [Permalink](https://eprint.iacr.org/2024/2061)
* [Download](https://eprint.iacr.org/2024/2061.pdf)

### Abstract

Arithmetization-Oriented (AO) cryptographic algorithms operate on large finite fields. The most threatening attack on such designs is the Gröbner basis attack, which solves the equation system encoded from the cryptanalysis problem. However, encoding a
primitive as a system of equations is not unique, and finding the optimal one with low solving complexity is a challenge. This paper introduces an automatic tool that converts the CICO problem into a Mixed-Integer Quadratic Constraint Programming (MIQCP)
model, using integer variables and constraints to track degree propagation and determine variable introduction points. The optimal MIQCP solution provides the lowest solving complexity. We build models for Griffin, Anemoi, and Ciminion permutations to
cover modules comprehensively. Experiments show reduced Gröbner basis attack complexity, lower than designers’ bounds for small numbers of rounds, e.g. up to 8 rounds for Griffin.This tool can be used for security evaluation against Gröbner basis
attack in new designs.



## 2024/2062

* Title: Two Halves Make a Whole: How to Reconcile Soundness and Robustness in Watermarking for Large Language Models
* Authors: Lei Fan, Chenhao Tang, Weicheng Yang, Hong-Sheng Zhou
* [Permalink](https://eprint.iacr.org/2024/2062)
* [Download](https://eprint.iacr.org/2024/2062.pdf)

### Abstract

Watermarking techniques have been used to safeguard AI-generated content. In this paper, we study publicly detectable watermarking schemes (Fairoze et al.), and have several research findings.

First, we observe that two important security properties, robustness and soundness, may conflict with each other. We then formally investigate these two properties in the presence of an arguably more realistic adversary that we called editing-adversary,
and we can prove an impossibility result that, the robustness and soundness properties cannot be achieved via a publicly-detectable single watermarking scheme.

Second, we demonstrate our main result: we for the first time introduce the new concept of publicly- detectable dual watermarking scheme, for AI-generated content. We provide a novel construction by using two publicly-detectable watermarking schemes;
each of the two watermarking schemes can achieve “half” of the two required properties: one can achieve robustness, and the other can achieve soundness. Eventually, we can combine the two halves into a whole, and achieve the robustness and soundness
properties at the same time. Our construction has been implemented and evaluated.



## 2024/2063

* Title: The Number of the Beast: Reducing Additions in Fast Matrix Multiplication Algorithms for Dimensions up to 666
* Authors: Erik Mårtensson, Paul Stankovski Wagner
* [Permalink](https://eprint.iacr.org/2024/2063)
* [Download](https://eprint.iacr.org/2024/2063.pdf)

### Abstract

While a naive algorithm for multiplying two 2 × 2 matrices requires
eight multiplications and four additions, Strassen showed how to compute the same matrix product using seven multiplications and 18 additions. Winograd reduced the number of additions to 15, which was assumed to be optimal. However, by introducing a
change of basis, Karstadt and Schwartz showed how to lower the number of additions to 12, which they further showed to be optimal within this generalized Karstadt-Schwartz (KS) framework. Since the cost of the change of basis is smaller than one addition
(per each recursive level), it is disregarded in this cost metric.

In this work we present improved methods for classical optimization of the number of additions in Strassen-type matrix multiplication schemes, but for larger matrix sizes, and without including any change of basis.

We find specific examples where our methods beat the best instances found within the KS framework, the most impressive one being Laderman’s algorithm for multiplying 3 × 3 matrices, which we reduce from the naive 98 additions to 62, compared to 74 in
the KS framework. We indicate that our approach performs better compared to previous work within the KS framework, as the matrix dimensions increase.

We additionally apply our algorithms to another reference set of algorithms due to Moosbauer and Kauers for which we do not have results in the KS framework as a comparison. For parameters (n, m, k), when multiplying an (n × m) matrix with an (m × k)
matrix, the schoolbook algorithm uses nk(m − 1) additions. Using the reference set of algorithms we find that our algorithm leads to an optimized number of additions of roughly cnk(m − 1), where c is a small constant which is independent of the
dimensions.

We further provide concrete and practical implementations of our methods that are very efficient for dimensions including (and surpassing) the 666 limit, i.e. (n, m, k) = (6, 6, 6), in our reference set of fast multiplication algorithms.



## 2024/2064

* Title: (Deep) Learning about Elliptic Curve Cryptography
* Authors: Diana Maimut, Alexandru Cristian Matei, George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/2064)
* [Download](https://eprint.iacr.org/2024/2064.pdf)

### Abstract

Motivated by the interest in elliptic curves both from a theoretical (algebraic geometry) and applied (cryptography) perspective, we conduct a preliminary study on the underlying mathematical structure of these mathematical structures.
Hence, this paper mainly focuses on investigating artificial intelligence techniques to enhance the efficiency of Schoof's algorithm for point counting across various elliptic curve distributions, achieving varying levels of success.



## 2024/2065

* Title: Partial Exposure Attacks Against a Family of RSA-like Cryptosystems
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/2065)
* [Download](https://eprint.iacr.org/2024/2065.pdf)

### Abstract

An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy, and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order $n \geq 1$. In this generalized framework, the key equation is $
ed - k (p^n-1)(q^n-1) = 1$, where $p$ and $q$ are prime numbers. Note that, the classical RSA, and the Elkamchouchi \emph{et al.} key equations are special cases, namely $n=1$ and $n=2$. In addition to introducing this generic family, Cotan and Teș
eleanu describe a continued fractions attack capable of recovering the secret key $d$ if $d < N^{0.25n}$. This bound was later improved by Teșeleanu using a lattice based method. In this paper, we explore other lattice attacks that could lead to
factoring the modulus $N = pq$. Namely, we propose a series of partial exposure attacks that can aid an adversary in breaking this family of cryptosystems if certain conditions hold.



## 2024/2066

* Title: COCO: Coconuts and Oblivious Computations for Orthogonal Authentication
* Authors: Yamya Reiki
* [Permalink](https://eprint.iacr.org/2024/2066)
* [Download](https://eprint.iacr.org/2024/2066.pdf)

### Abstract

Authentication often bridges real-world individuals and their virtual public identities, like usernames, user IDs and e-mails, exposing vulnerabilities that threaten user privacy. This research introduces COCO (Coconuts and Oblivious Computations for
Orthogonal Authentication), a framework that segregates roles among Verifiers, Authenticators, and Clients to achieve privacy-preserving authentication.

COCO eliminates the need for Authenticators to directly access virtual public identifiers or real-world identifiers for authentication. Instead, the framework leverages Oblivious Pseudorandom Functions (OPRFs) and an extended Coconut Credential Scheme to
ensure privacy by introducing separate unlinkable orthogonal authentication identifiers and a full-consensus mechanism to perform zero-knowledge authentications whose proof-s are unlinkable across multiple sessions. Authentication process becomes self-
contained, preventing definitive reverse tracing of virtual public identifiers to real-world identifiers.



## 2024/2067

* Title: Bypassing the characteristic bound in logUp
* Authors: Liam Eagen, Ulrich Haböck
* [Permalink](https://eprint.iacr.org/2024/2067)
* [Download](https://eprint.iacr.org/2024/2067.pdf)

### Abstract

In this informal note, we describe how to bypass the characteristic bound in logUp [eprint 2022/1530] by abstracting the notion of (pole) multiplicity. The method applies as well to the GKR-variant from Papini and Haböck [eprint 2023/1284], and it
moreover unlocks fractional decomposition lookups over binary fields.



## 2024/2068

* Title: Weightwise Almost Perfectly Balanced Functions, Construction From A Permutation Group Action View
* Authors: Deepak Kumar Dalai, Krishna Mallick, Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2024/2068)
* [Download](https://eprint.iacr.org/2024/2068.pdf)

### Abstract

The construction of Boolean functions with good cryptographic properties over subsets of vectors with fixed Hamming weight is significant for lightweight stream ciphers like FLIP. In this article, we propose a general method to construct a class of
Weightwise Almost Perfectly Balanced (WAPB) Boolean functions using the action of a cyclic permutation group on $\mathbb{F}_2^n$. This class generalizes the Weightwise Perfectly Balanced (WPB) $2^m$-variable Boolean function construction by Liu and
Mesnager to any $n$. We show how to bound the nonlinearity and weightwise nonlinearities of functions from this construction. Additionally, we explore two significant permutation groups, $\langle \psi \rangle$ and $\langle \sigma \rangle$, where $\psi$
is a binary-cycle permutation and $\sigma$ is a rotation. We theoretically analyze the cryptographic properties of the WAPB functions derived from these permutations and experimentally evaluate their nonlinearity parameters for $n$ between 4 and 10.



## 2024/2069

* Title: One Solves All: Exploring ChatGPT's Capabilities for Fully Automated Simple Power Analysis on Cryptosystems
* Authors: Wenquan Zhou, An Wang, Yaoling Ding, Congming Wei, Jingqi Zhang, Liehuang Zhu
* [Permalink](https://eprint.iacr.org/2024/2069)
* [Download](https://eprint.iacr.org/2024/2069.pdf)

### Abstract

Side-channel analysis is a powerful technique to extract secret data from cryptographic devices. However, this task heavily relies on experts and specialized tools, particularly in the case of simple power analysis (SPA). Meanwhile, ChatGPT, a leading
example of large language models, has attracted great attention and been widely applied for assisting users with complex tasks. Despite this, ChatGPT’s capabilities for fully automated SPA, where prompts and traces are input only once, have yet to be
systematically explored and improved. In this paper, we introduce a novel prompt template with three expert strategies and conduct a large-scale evaluation of ChatGPT’s capabilities for SPA. We establish a dataset comprising seven sets of real power
traces from various implementations of public-key cryptosystems, including RSA, ECC, and Kyber, as well as eighteen sets of simulated power traces that illustrate typical SPA leakage patterns. The results indicate that ChatGPT fails to be directly used
for SPA. However, by applying the expert strategies, we successfully recovered the private keys for all twenty-five traces, which demonstrate that non-experts can use ChatGPT with our expert strategies to perform fully automated SPA.



## 2024/2070

* Title: Sneaking up the Ranks: Partial Key Exposure Attacks on Rank-Based Schemes
* Authors: Giuseppe D'Alconzo, Andre Esser, Andrea Gangemi, Carlo Sanna
* [Permalink](https://eprint.iacr.org/2024/2070)
* [Download](https://eprint.iacr.org/2024/2070.pdf)

### Abstract

A partial key exposure attack is a key recovery attack where an adversary obtains a priori partial knowledge of the secret key, e.g., through side-channel leakage. While for a long time post-quantum cryptosystems, unlike RSA, have been believed to be
resistant to such attacks, recent results by Esser, May, Verbel, and Wen (CRYPTO ’22), and by Kirshanova and May (SCN ’22), have refuted this belief.

In this work, we focus on partial key exposure attacks in the context of rank-metric-based schemes, particularly targeting the RYDE, MIRA, and MiRitH digital signatures schemes, which are active candidates in the NIST post-quantum cryptography
standardization process. We demonstrate that, similar to the RSA case, the secret key in RYDE can be recovered from a constant fraction of its bits. Specifically, for NIST category I parameters, our attacks remain efficient even when less than 25% of the
key material is leaked. Interestingly, our attacks lead to a natural improvement of the best generic attack on RYDE without partial knowledge, reducing security levels by up to 9 bits. For MIRA and MiRitH our attacks remain efficient as long as roughly
57%-60% of the secret key material is leaked.

Additionally, we initiate the study of partial exposure of the witness in constructions following the popular MPCitH (MPC-in-the-Head) paradigm. We show a generic reduction from recovering RYDE and MIRA’s witness to the MinRank problem, which again
leads to efficient key recovery from constant fractions of the secret witness in both cases.



## 2024/2071

* Title: Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity
* Authors: Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2024/2071)
* [Download](https://eprint.iacr.org/2024/2071.pdf)

### Abstract

The \emph{Fluid} multiparty computation (MPC) model, introduced in (Choudhuri \emph{et al.} CRYPTO 2021), addresses dynamic scenarios where participants can join or leave computations between rounds. Communication complexity initially stood at $\Omega(n^
2)$ elements per gate, where $n$ is the number of parties in a committee online at a time. This held for both statistical security (honest majority) and computational security (dishonest majority) in (Choudhuri \emph{et al.}~CRYPTO'21) and (Rachuri and
Scholl, CRYPTO'22), respectively. The work of Bienstock \emph{et al.}~CRYPTO'23) improved communication to $O(n)$ elements per gate. However, it's important to note that the perfectly secure setting with one-third corruptions per committee has only
recently been addressed in the work of (David \emph{et al.}~CRYPTO'23). Notably, their contribution marked a significant advancement in the Fluid MPC literature by introducing guaranteed output delivery. However, this achievement comes at the cost of
prohibitively expensive communication, which scales to $\Omega(n^9)$ elements per gate.

In this work, we study the realm of perfectly secure Fluid MPC under one-third active corruptions. Our primary focus lies in proposing efficient protocols that embrace the concept of security with abort. Towards this, we design a protocol for perfectly
secure Fluid MPC that requires only \emph{linear} communication of $O(n)$ elements per gate, matching the communication of the non-Fluid setting. Our results show that, as in the case of computational and statistical security, perfect security with abort
for Fluid MPC comes "for free (asymptotically linear in $n$) with respect to traditional non-Fluid MPC, marking a substantial leap forward in large scale dynamic computations, such as Fluid MPC.



## 2024/2072

* Title: Advancements in Distributed RSA Key Generation: Enhanced Biprimality Tests
* Authors: ChihYun Chuang, IHung Hsu, TingFang Lee
* [Permalink](https://eprint.iacr.org/2024/2072)
* [Download](https://eprint.iacr.org/2024/2072.pdf)

### Abstract

RSA is widely used in modern cryptographic practice, with certain RSA-based protocols relying on the secrecy of $p$ and $q$. A common approach is to use secure multiparty computation to address the privacy concerns of
$p$ and $q$.
Specifically constrained to distributed RSA modulus generation protocols, the biprimality test for Blum integers $N=pq$, where $p\equiv q\equiv 3 \mod 4$ are two primes, proposed by Boneh and Franklin in $2001$ is the most commonly used. Over the past $
20 $ years, the worst-case acceptance rate of this test has been consistently assumed to be $1/2$ under the condition $\gcd(pq,p+q-1)=1$.
In this paper, we show that for the Boneh-Franklin test, its acceptance probability is at most $1/4$ rather than $1/2$,
except in the case where $p = q = 3$. At the same time, $1/4$ is also the tightest upper bound. Enhance the effectiveness of applying the Boneh-Franklin test in this result: achieving the same soundness for the RSA modulus requires only half the number
of iterations commonly recognized.
Furthermore, we propose two types of Lucas biprimality tests. In the worst case, one of proposed tests acceptance rate is at most $1/4 + 1.25/(p_{\min} -3)$, where $p_{\min}$ is the smallest prime factors of $N$. However, simulation study suggests that
this test is generally more efficient than the Boneh-Franklin test for detecting when $N$ is not an RSA modulus.
The second type of Lucas test, though less efficient, can be applied to arbitrary RSA moduli $p$ and $q$. Nevertheless, if the soundness error for generating an RSA modulus is set at approximately $2^{-80}$, it leaks at most $46$ quadratic symbol values,
regardless of the public key length. We also design corresponding protocols for both tests and validate their resilience against semi-honest adversaries, which can be applied to most known distributed RSA modulus generation protocols. After thoroughly
analyzing and comparing well-known protocols, including the variant Miller-Rabin test used by Burkhardt et al. (CCS 2023), the Boneh-Franklin test, and our proposed Lucas-type tests, our proposed Lucas test is also highly competitive in verifying whether
$N$ is an RSA modulus.



## 2024/2073

* Title: Succinct Partial Garbling from Groups and Applications
* Authors: Yuval Ishai, Hanjun Li, Huijia Lin
* [Permalink](https://eprint.iacr.org/2024/2073)
* [Download](https://eprint.iacr.org/2024/2073.pdf)

### Abstract

A garbling scheme transforms a program (e.g., circuit) $C$ into a garbled program $\hat{C}$, along with a pair of short keys $(k_{i,0},k_{i,1})$ for each input bit $x_i$, such that $(C,\hat{C}, \{k_{i,x_i}\})$ can be used to recover the output $z = C(x)$
while revealing nothing else about the input $x$. This can be naturally generalized to partial garbling, where part of the input is public, and a computation $z = C(x, y)$ is decomposed into a public part $C_{\text{pub}}(x)$, depending only on the public
input $x$, and a private part $z = C_{\text{priv}}(C_{\text{pub}}(x), y)$ that also involves a private input $y$.

A key challenge in garbling is to achieve succinctness, where the size of the garbled program may grow only with the security parameter and (possibly) the output length, but not with the size of $C$. Prior work achieved this strong notion of succinctness
using heavy tools such as indistinguishability obfuscation (iO) or a combination of fully homomorphic encryption and attribute-based encryption.

In this work, we introduce new succinct garbling schemes based on variants of standard group-based assumptions. Our approach, being different from prior methods, offers a promising pathway towards practical succinct garbling. Specifically, we construct:
- A succinct partial garbling scheme for general circuits, where the garbled circuit size scales linearly with the private computation $|C_{\text{priv}}|$ and is independent of the public computation $|C_{\text{pub}}|$. This implies fully succinct
conditional disclosure of secrets (CDS) protocols for circuits.
- Succinct (fully hiding) garbling schemes for simple types of programs, including truth tables, bounded-length branching programs (capturing decision trees and DFAs as special cases) and degree-2 polynomials, where the garbled program size is
independent of the program size. This implies succinct private simultaneous messages (PSM) protocols for the same programs.

Our succinct partial garbling scheme can be based on a circular-security variant of the power-DDH assumption, which holds in the generic group model, or alternatively on the key-dependent message security of the Damgård-Jurik encryption. For bounded-
depth circuits or the aforementioned simple programs, we avoid circular-security assumptions entirely.

At the heart of our technical approach is a new computational flavor of algebraic homomorphic MAC (aHMAC), for which we obtain group-based constructions building on techniques from the literature on homomorphic secret sharing. Beyond succinct garbling,
we demonstrate the utility of aHMAC by constructing constrained pseudorandom functions (CPRFs) for general constraint circuits from group-based assumptions. Previous CPRF constructions were limited to $\mathsf{NC}^1$ circuits or alternatively relied on
lattices or iO.



## 2024/2074

* Title: EQSIGN: Practical Digital Signatures from the Non-Abelian Hidden Subgroup Problem and Information Theoretic Equivocation
* Authors: Samuel Lavery
* [Permalink](https://eprint.iacr.org/2024/2074)
* [Download](https://eprint.iacr.org/2024/2074.pdf)

### Abstract

We present a novel digital signature scheme grounded in non-commutative cryptography and implemented over a bilinear matrix group platform. At the core of our design is a unique equivocation function that obfuscates intermediate elements, effectively
concealing outputs and minimizing observable information leakage. To the best of our knowledge, this is the first digital signature scheme to combine information-theoretic security with computational hardness, relying on a challenging instance of the Non-
Abelian Hidden Subgroup Problem (NAHSP) and strengthened by practical guarantees. This dual-layered security approach ensures robustness against both classical and quantum adversaries while maintaining communication overheads competitive with RSA. Our
work represents a significant advancement toward efficient, quantum-resilient digital signatures for real-world applications. This paper is an early pre-release intended to invite collaboration and feedback. The work is presented for research purposes
only and is not intended for use in production systems.



## 2024/2075

* Title: Tightly-Secure Blind Signatures in Pairing-Free Groups
* Authors: Nicholas Brandt, Dennis Hofheinz, Michael Klooß, Michael Reichle
* [Permalink](https://eprint.iacr.org/2024/2075)
* [Download](https://eprint.iacr.org/2024/2075.pdf)

### Abstract

We construct the first blind signature scheme that achieves all of the following properties simultaneously:
- it is tightly secure under a standard (i.e., non-interactive,
non-\(q\)-type) computational assumption,
- it does not require pairings,
- it does not rely on generic, non-black-box techniques (like generic NIZK proofs).
The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 \(\mathbb{Z}_p\)-elements.

Our scheme starts from a pairing-based non-blind signature scheme (Abe et al., JoC 2023), and uses recent techniques of Chairattana-Apirom, Tessaro, and Zhu (CRYPTO 2024) to replace the pairings used in this scheme with non-interactive zero-knowledge
proofs in the random oracle model. This conversion is not generic or straightforward (also because the mentioned previous works have converted only significantly simpler signature schemes), and we are required to improve upon and innovate existing
techniques in several places.

As an interesting side note, and unlike previous works, our techniques only require a non-programmable random oracle, and our signature scheme achieves predicate blindness (which means that the user can prove statements about the signed message during
the signing process).



## 2024/2076

* Title: Blind Signatures from Proofs of Inequality
* Authors: Michael Klooß, Michael Reichle
* [Permalink](https://eprint.iacr.org/2024/2076)
* [Download](https://eprint.iacr.org/2024/2076.pdf)

### Abstract

Blind signatures are an important primitive for privacy-preserving technologies. To date, highly efficient pairing-free constructions rely on the random oracle model, and additionally, a strong assumption, such as interactive assumptions or the algebraic
group model.

In contrast, for signatures we know many efficient constructions that rely on the random oracle model and standard assumptions. In this work, we develop techniques to close this gap. Compared to the most efficient pairing-free AGM-based blind signature
by Crites et. al. (Crypto 2023), our construction has a relative overhead of only a factor $3\times$ and $2\times$ in terms of communication and signature size, and it is provable in the random oracle model under the DDH assumption. With one additional
move and $\mathbb{Z}_p$ element, we also achieve one-more strong unforgeability.

Our construction is inspired by the recent works by Chairattana-Apirom, Tessaro, and Zhu (Crypto 2024) and Klooß, Reichle, and Wagner (Asiacrypt 2024), and we develop a tailored technique to circumvent the sources of inefficiency in their constructions.
Concretely, we achieve signature and communication size of $192$ B and $608$ B, respectively.



## 2024/2077

* Title: Report on evaluation of KpqC Round-2 candidates
* Authors: Daniel J. Bernstein, Jolijn Cottaar, Emanuele Di Giandomenico, Kathrin Hövelmanns, Andreas Hülsing, Mikhail Kudinov, Tanja Lange, Mairon Mahzoun, Matthias Meijers, Alex Pellegrini, Alberto Ravagnani, Silvia Ritsch, Sven Schäge, Tianxin Tang,
Monika Trimoska, Marc Vorstermans, Fiona Johanna Weber
* [Permalink](https://eprint.iacr.org/2024/2077)
* [Download](https://eprint.iacr.org/2024/2077.pdf)

### Abstract

This report covers our analysis (security, proofs, efficiency) of the Round-2 candidates to the Korean post-quantum competiton KpqC. Signature systems covered in the report are AIMer, HAETAE, MQ-Sign, and NCC-Sign; KEMs covered are NTRU+, Paloma, REDOG,
and SMAUG-T.



## 2024/2078

* Title: Strongly Secure Universal Thresholdizer
* Authors: Ehsan Ebrahimi, Anshu Yadav
* [Permalink](https://eprint.iacr.org/2024/2078)
* [Download](https://eprint.iacr.org/2024/2078.pdf)

### Abstract

A universal thresholdizer (UT), constructed from a threshold fully homomorphic encryption by Boneh et. al
, Crypto 2018, is a general framework for universally thresholdizing many cryptographic schemes. However,
their framework is insufficient to construct strongly secure threshold schemes, such as threshold signatures
and threshold public-key encryption, etc.
In this paper, we strengthen the security definition for a universal thresholdizer and propose a scheme
which satisfies our stronger security notion. Our UT scheme is an improvement of Boneh et. al ’s construction
at the level of threshold fully homomorphic encryption using a key homomorphic pseudorandom function.
We apply our strongly secure UT scheme to construct strongly secure threshold signatures and threshold
public-key encryption.



## 2024/2079

* Title: Solving AES-SAT Using Side-Channel Hints: A Practical Assessment
* Authors: Elena Dubrova
* [Permalink](https://eprint.iacr.org/2024/2079)
* [Download](https://eprint.iacr.org/2024/2079.pdf)

### Abstract

Side-channel attacks exploit information leaked through non-primary channels, such as power consumption, electromagnetic emissions, or timing, to extract sensitive data from cryptographic devices. Over the past three decades, side-channel analysis has
evolved into a mature research field with well-established methodologies for analyzing standard cryptographic algorithms like the Advanced Encryption Standard (AES). However, the integration of side-channel analysis with formal methods remains relatively
unexplored. In this paper, we present a hybrid attack on AES that combines side-channel analysis with SAT. We model AES as a SAT problem and leverage hints of the input and output values of the S-boxes, extracted via profiled deep learning-based power
analysis, to solve it. Experimental results on an ATXmega128D4 MCU implementation of AES-128 demonstrate that the SAT-assisted approach consistently recovers the full encryption key from a single trace, captured from devices different from those used for
profiling, within one hour. In contrast, without SAT assistance, the success rate remains below 80% after 26 hours of key enumeration.



## 2024/2080

* Title: Improved Lattice-Based Attack on Mersenne Low Hamming Ratio Search Problem
* Authors: Mengce Zheng, Wei Yan
* [Permalink](https://eprint.iacr.org/2024/2080)
* [Download](https://eprint.iacr.org/2024/2080.pdf)

### Abstract

This paper investigates the Mersenne number-based $\mathsf{AJPS}$ cryptosystem, with a particular focus on its associated hard problem. Specifically, we aim to enhance the existing lattice-based attack on the Mersenne low Hamming ratio search problem.
Unlike the previous approach of directly employing lattice reduction algorithm, we apply the lattice-based method to solving polynomial equations derived from the above problem. We extend the search range for vulnerabilities in weak keys and increase the
success probability of key recovery attack. To validate the efficacy and accuracy of our proposed improvements, we conduct numerical computer experiments. These experiments serve as a concrete validation of the practicality and effectiveness of our
improved attack.



## 2024/2081

* Title: Generalized Cryptanalysis of Cubic Pell RSA
* Authors: Hao Kang, Mengce Zheng
* [Permalink](https://eprint.iacr.org/2024/2081)
* [Download](https://eprint.iacr.org/2024/2081.pdf)

### Abstract


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)