## In this issue

1. [2023/1719] MQ on my Mind: Post-Quantum Signatures from the ...
2. [2024/332] Leakage-Tolerant Circuits
3. [2024/724] zkSNARKs in the ROM with Unconditional UC-Security
4. [2024/725] Multi User Security of LightMAC and LightMAC_Plus
5. [2024/726] Challenger: Blockchain-based Massively Multiplayer ...
6. [2024/727] Let Attackers Program Ideal Models: Modularity and ...
7. [2024/728] Relativized Succinct Arguments in the ROM Do Not Exist
8. [2024/729] Covert Adaptive Adversary Model: A New Adversary ...
9. [2024/730] New Solutions to Delsarte's Dual Linear Programs
10. [2024/731] Tight Security of Double-Block Nonce-Based MACs
11. [2024/732] Compact Encryption based on Module-NTRU problems
12. [2024/733] Proxying is Enough: Security of Proxying in TLS ...
13. [2024/734] Proof of Stake and Activity: Rewarding On-Chain ...
14. [2024/735] Secure Multiparty Computation in the Presence of ...
15. [2024/736] Secret Sharing with Certified Deletion
16. [2024/737] Mutable Batch Arguments and Applications
17. [2024/738] Quantum Key-Revocable Dual-Regev Encryption, Revisited
18. [2024/739] BGJ15 Revisited: Sieving with Streamed Memory Access
19. [2024/740] Multi-Client Functional Encryption with Public ...
20. [2024/741] A Deniability Analysis of Signal's Initial ...
21. [2024/742] Efficient Universally-Verifiable Electronic Voting ...
22. [2024/743] Improved Conditional Cube Attacks on Ascon AEADs in ...
23. [2024/744] An NVMe-based Secure Computing Platform with FPGA- ...
24. [2024/745] $\mathsf{FRAST}$: TFHE-friendly Cipher Based on ...

## 2023/1719

* Title: MQ on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem
* Authors: Ryad Benadjila, Thibauld Feneuil, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2023/1719)
* [Download](https://eprint.iacr.org/2023/1719.pdf)

### Abstract

This paper presents MQ on my Mind (MQOM), a digital signature scheme based on the difficulty of solving multivariate systems of quadratic equations (MQ problem). MQOM has been submitted to the NIST call for additional post-quantum signature schemes. MQOM relies on the MPC-in-the-Head (MPCitH) paradigm to build a zero-knowledge proof of knowledge (ZK-PoK) for MQ which is then turned into a signature scheme through the Fiat-Shamir heuristic. The underlying MQ problem is non-structured in the sense that the system of quadratic equations defining an instance is drawn uniformly at random. This is one of the hardest and most studied problems from multivariate cryptography which hence constitutes a conservative choice to build candidate post-quantum cryptosystems. For the efficient application of the MPCitH paradigm, we design a specific MPC protocol to verify the solution of an MQ instance. Compared to other multivariate signature schemes based on non-structured MQ instances, MQOM achieves the shortest signatures (6.3-7.8 KB) while keeping very short public keys (few dozen of bytes). Other multivariate signature schemes are based on structured MQ problems (less conservative) which either have large public keys (e.g. UOV) or use recently proposed variants of these MQ problems (e.g. MAYO).

## 2024/332

* Title: Leakage-Tolerant Circuits
* Authors: Yuval Ishai, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/332)
* [Download](https://eprint.iacr.org/2024/332.pdf)

### Abstract

A leakage-resilient circuit for $f:\{0,1\}^n\to\{0,1\}^m$ is a randomized Boolean circuit $C$ mapping a randomized encoding of an input $x$ to an encoding of $y=f(x)$, such that applying any leakage function $L\in \cal L$ to the wires of $C$ reveals essentially nothing about $x$. A leakage-tolerant circuit achieves the stronger guarantee that even when $x$ and $y$ are not protected by any encoding, the output of $L$ can be simulated by applying some $L'\in \cal L$ to $x$ and $y$ alone. Thus, $C$ is as secure as an ideal hardware implementation of $f$ with respect to leakage from $\cal L$.

Leakage-resilient circuits were constructed for low-complexity classes $\cal L$, including (length-$t$ output) $\mathcal{AC}0$ functions, parities, and functions with bounded communication complexity. In contrast, leakage-tolerant circuits were only known for the simple case of probing leakage, where $L$ outputs the values of $t$ wires in $C$.

We initiate a systematic study of leakage-tolerant circuits for natural classes $\cal L$ of global leakage functions, obtaining the following main results.

$\textbf{Leakage-tolerant circuits for depth-1 leakage.}$ Every circuit $C_f$ for $f$ can be efficiently compiled into an $\cal L$-tolerant circuit $C$ for $f$, where $\cal L$ includes all leakage functions $L$ that output either $t$ parities or $t$ disjunctions (alternatively, conjunctions) of any number of wires or their negations. In the case of parities, our simulator runs in $2^{O(t)}$ time. We provide partial evidence that this may be inherent.

$\textbf{Application to stateful leakage-resilient circuits.}$ We present a general transformation from (stateless) leakage-tolerant circuits to stateful leakage-resilient circuits. Using this transformation, we obtain the first constructions of stateful $t$-leakage-resilient circuits that tolerate a continuous parity/disjunction/conjunction leakage in which the circuit size grows sub-quadratically with $t$. Interestingly, here we can obtain $\mathtt{poly}(t)$-time simulation even in the case of parities.

## 2024/724

* Title: zkSNARKs in the ROM with Unconditional UC-Security
* Authors: Alessandro Chiesa, Giacomo Fenzi
* [Permalink](https://eprint.iacr.org/2024/724)
* [Download](https://eprint.iacr.org/2024/724.pdf)

### Abstract

The universal composability (UC) framework is a “gold standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger protocols. Zero knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are a popular cryptographic primitive that are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not necessary, goal.
In this paper we prove that there exist zkSNARKs in the random oracle model (ROM) that unconditionally achieve UC-security. Here, “unconditionally” means that security holds against adversaries that make a bounded number of queries to the random oracle, but are otherwise computationally unbounded.
Prior work studying UC-security for zkSNARKs obtains transformations that rely on computational assumptions and, in many cases, lose most of the succinctness property of the zkSNARK. Moreover, these transformations make the resulting zkSNARK more expensive and complicated.
In contrast, we prove that widely used zkSNARKs in the ROM are UC-secure without modifications. We prove that the Micali construction, which is the canonical construction of a zkSNARK, is UC-secure. Moreover, we prove that the BCS construction, which many zkSNARKs deployed in practice are based on, is UC-secure. Our results confirm the intuition that these natural zkSNARKs do not need to be augmented to achieve UC-security, and give confidence that their use in larger real-world systems is secure.

## 2024/725

* Title: Multi User Security of LightMAC and LightMAC_Plus
* Authors: Nilanjan Datta, Shreya Dey, Avijit Dutta, Devdutto Kanungo
* [Permalink](https://eprint.iacr.org/2024/725)
* [Download](https://eprint.iacr.org/2024/725.pdf)

### Abstract

In FSE'16, Luykx et al. have proposed $\textsf{LightMAC}$ that provably achieves a query length independent PRF security bound. To be precise, the construction achieves security roughly in the order of $O(q^2/2^n)$, when instantiated with two independently keyed $n$-bit block ciphers and $q$ is the total number of queries made by the adversary. Subsequently, in ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the $\textsf{LightMAC}$ construction, dubbed as $\textsf{LightMAC_Plus}$, that is built on three independently keyed $n$-bit block ciphers and achieves $2n/3$-bits PRF security. Security analyses of these two constructions have been conducted in the single-user setting, where we assume that the adversary has the access to a single instance of the construction. In this paper, we investigate, for the first time, the security of the $\textsf{LightMAC}$ and the $\textsf{LightMAC_Plus}$ construction in the context of multi-user setting, where we assume that the adversary has access to more than one instances of the construction. In particular, we have shown that $\textsf{LightMAC}$ remains secure roughly up to $2^{n/2}$ construction queries and $2^k$ ideal-cipher queries in the ideal-cipher model and $\textsf{LightMAC_Plus}$ maintains security up to approximately $2^{2n/3}$ construction queries and $2^{2k/3}$ ideal-cipher queries in the ideal-cipher model, where $n$ denotes the block size and $k$ denotes the key size of the block cipher.

## 2024/726

* Title: Challenger: Blockchain-based Massively Multiplayer Online Game Architecture
* Authors: Boris Chan Yip Hon, Bilel Zaghdoudi, Maria Potop-Butucaru, Sébastien Tixeuil, Serge Fdida
* [Permalink](https://eprint.iacr.org/2024/726)
* [Download](https://eprint.iacr.org/2024/726.pdf)

### Abstract

We propose Challenger a peer-to-peer blockchain-based middleware architecture for narrative games, and discuss its resilience to cheating attacks. Our architecture orchestrates nine services in a fully decentralized manner where nodes are not aware of the entire composition of the system nor its size. All these components are orchestrated together to obtain (strong) resilience to cheaters.
The main contribution of the paper is to provide, for the first time, an architecture for narrative games agnostic of a particular blockchain that brings together several distinct research areas, namely distributed ledgers, peer-to-peer networks, multi-player-online games and resilience to attacks.