## 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.