[continued from previous message]

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial heirarchy collapses. We realize this
possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P}^{\#\mathsf{P}}$ -- such as approximating the permanents of complex gaussian
matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as \any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true,
quantum cryptography can be based on the extremely mild assumption that $\mathsf{P}^{\#\mathsf{P}} \not\subseteq \mathsf{(io)BQP}/\mathsf{qpoly}$.
Our techniques uncover strong connections between the hardness of approximating the probabilities of outcomes of quantum processes, the existence of ``one-way'' state synthesis problems, and the existence of useful cryptographic primitives such as one-
way puzzles and quantum bit commitments. Specifically, we prove that the following hardness assumptions are equivalent under $\mathsf{BQP}$ reductions.
1. The hardness of approximating the probabilities of outcomes of certain efficiently sampleable distributions. That is, there exist quantumly efficiently sampleable distributions for which it is hard to approximate the probability assigned to a randomly
chosen string in the support of the distribution (upto inverse polynomial multiplicative error).
2. The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [
Khurana and Tomer, STOC'24].
3. The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (
challenges).
These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
Along the way, we also show that distributions that admit efficient quantum samplers but cannot be pseudo-deterministically efficiently sampled imply quantum commitments.



## 2024/1491

* Title: On the Anonymity of One Authentication and Key Agreement Scheme for Peer-to-Peer Cloud
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1491)
* [Download](https://eprint.iacr.org/2024/1491.pdf)

### Abstract

Peer-to-peer communication systems can provide many functions, including anonymized routing of network traffic, massive parallel computing environments, and distributed storage. Anonymity refers to the state of being completely nameless, with no attached
identifiers. Pseudonymity involves the use of a fictitious name that can be consistently linked to a particular user, though not necessarily to the real identity. Both provide a layer of privacy, shielding the user's true identity from public view. But
we find their significations are often misunderstood. In this note, we clarify the differences between anonymity and pseudonymity. We also find the Zhong et al.'s key agreement scheme [IEEE TCC, 2022, 10(3), 1592-1603] fails to keep anonymity, not as
claimed.



## 2024/1492

* Title: Multi-Designated Detector Watermarking for Language Models
* Authors: Zhengan Huang, Gongxian Zeng, Xin Mu, Yu Wang, Yue Yu
* [Permalink](https://eprint.iacr.org/2024/1492)
* [Download](https://eprint.iacr.org/2024/1492.pdf)

### Abstract

In this paper, we initiate the study of multi-designated detector watermarking (MDDW) for large language models (LLMs). This technique allows model providers to generate watermarked outputs from LLMs with two key properties: (i) only specific, possibly
multiple, designated detectors can identify the watermarks, and (ii) there is no perceptible degradation in the output quality for ordinary users. We formalize the security definitions for MDDW and present a framework for constructing MDDW for any LLM
using multi-designated verifier signatures (MDVS). Recognizing the significant economic value of LLM outputs, we introduce claimability as an optional security feature for MDDW, enabling model providers to assert ownership of LLM outputs within
designated-detector settings. To support claimable MDDW, we propose a generic transformation converting any MDVS to a claimable MDVS. Our implementation of the MDDW scheme highlights its advanced functionalities and flexibility over existing methods,
with satisfactory performance metrics.



## 2024/1493

* Title: Rate-1 Zero-Knowledge Proofs from One-Way Functions
* Authors: Noor Athamnah, Eden Florentz – Konopnicki, Ron D. Rothblum
* [Permalink](https://eprint.iacr.org/2024/1493)
* [Download](https://eprint.iacr.org/2024/1493.pdf)

### Abstract

We show that every NP relation that can be verified by a bounded-depth polynomial-sized circuit, or a bounded-space polynomial-time algorithm, has a computational zero-knowledge proof (with statistical soundness) with communication that is only
additively larger than the witness length. Our construction relies only on the minimal assumption that one-way functions exist.

In more detail, assuming one-way functions, we show that every NP relation that can be verified in NC has a zero-knowledge proof with communication $|w|+poly(\lambda,\log(|x|))$ and relations that can be verified in SC have a zero-knowledge proof
with communication $|w|+|x|^\epsilon \cdot poly(\lambda)$. Here $\epsilon>0$ is an arbitrarily small constant and \lambda denotes the security parameter. As an immediate corollary, we also get that any NP relation, with a size S verification circuit (
using unbounded fan-in XOR, AND and OR gates), has a zero-knowledge proof with communication $S+poly(\lambda,\log(S))$.

Our result improves on a recent result of Nassar and Rothblum (Crypto, 2022), which achieve length $(1+\epsilon) \cdot |w|+|x|^\epsilon \cdot poly(\lambda)$ for bounded-space computations, and is also considerably simpler. Building on a work of Hazay
et al. (TCC 2023), we also give a more complicated version of our result in which the parties only make a black-box use of the one-way function, but in this case we achieve only an inverse polynomial soundness error.



## 2024/1494

* Title: Concretely Efficient Private Set Union via Circuit-based PSI
* Authors: Gowri R Chandran, Thomas Schneider, Maximilian Stillger, Christian Weinert
* [Permalink](https://eprint.iacr.org/2024/1494)
* [Download](https://eprint.iacr.org/2024/1494.pdf)

### Abstract

Private set intersection (PSI) is a type of private set operation (PSO) for which concretely efficient linear-complexity protocols do exist.
However, the situation is currently less satisfactory for other relevant PSO problems such as private set union (PSU):
For PSU, the most promising protocols either rely entirely on computationally expensive public-key operations or suffer from substantial communication overhead.

In this work, we present the first PSU protocol that is mainly based on efficient symmetric-key primitives yet enjoys comparable communication as public-key-based alternatives.
Our core idea is to re-purpose state-of-the-art circuit-based PSI to realize a multi-query reverse private membership test (mq-RPMT), which is instrumental for building PSU.
We carefully analyze a privacy leakage issue resulting from the hashing paradigm commonly utilized in circuit-based PSI and show how to mitigate this via oblivious pseudorandom function (OPRF) and new shuffle sub-protocols.
Our protocol is modularly designed as a sequential execution of different building blocks that can be easily replaced by more efficient variants in the future, which will directly benefit the overall performance.

We implement our resulting PSU protocol, showing a run-time improvement of 10% over the state-of-the-art public-key-based protocol of Chen et al. (PKC'24) for input sets of size $2^{20}$.
Furthermore, we improve communication by $1.6\times$ over the state-of-the-art symmetric-key-based protocol of Zhang et al. (USENIX Sec'23).



## 2024/1495

* Title: Lattice-Based Vulnerabilities in Lee Metric Post-Quantum Cryptosystems * Authors: Anna-Lena Horlemann, Karan Khathuria, Marc Newman, Amin Sakzad, Carlos Vela Cabello
* [Permalink](https://eprint.iacr.org/2024/1495)
* [Download](https://eprint.iacr.org/2024/1495.pdf)

### Abstract

Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. Code-based and lattice-based cryptography are two promi- nent approaches, both heavily studied within the NIST
standardization project. Code-based cryptography—most prominently exemplified by the McEliece cryptosystem—is based on the hardness of decoding random linear error-correcting codes. Despite the McEliece cryptosystem having been unbroken for several
decades, it suffers from large key sizes, which has led to exploring variants using metrics than the Hamming metric, such as the Lee metric. This alternative metric may allow for smaller key sizes, but requires further analysis for potential
vulnerabilities to lattice- based attack techniques. In this paper, we consider a generic Lee met- ric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.



## 2024/1496

* Title: No Fish Is Too Big for Flash Boys! Frontrunning on DAG-based Blockchains
* Authors: Jianting Zhang, Aniket Kate
* [Permalink](https://eprint.iacr.org/2024/1496)
* [Download](https://eprint.iacr.org/2024/1496.pdf)

### Abstract

Frontrunning is rampant in blockchain ecosystems, yielding attackers profits that have already soared into several million. Most existing frontrunning attacks focus on manipulating transaction order (namely, prioritizing attackers' transactions before
victims' transactions) $\textit{within}$ a block. However, for the emerging directed acyclic graph (DAG)-based blockchains, these intra-block frontrunning attacks may not fully reveal the frontrunning vulnerabilities as they introduce block ordering
rules to order transactions belonging to distinct blocks.

This work performs the first in-depth analysis of frontrunning attacks toward DAG-based blockchains. We observe that the current block ordering rule is vulnerable to a novel $\textit{inter-block}$ frontrunning attack, which enables the attacker to
prioritize ordering its transactions before the victim transactions across blocks. We introduce three attacking strategies: $\textit{(i)}$ Fissure attack, where attackers render the victim transactions ordered later by disconnecting the victim's blocks. $
\textit{(ii)}$ Speculative attack, where attackers speculatively construct order-priority blocks. $\textit{(iii)}$ Sluggish attack, where attackers deliberately create low-round blocks assigned a higher ordering priority by the block ordering rule.

We implement our attacks on two open-source DAG-based blockchains, Bullshark and Tusk. We extensively evaluate our attacks in geo-distributed AWS and local environments by running up to $n=100$ nodes. Our experiments show remarkable attack effectiveness.
For instance, with the speculative attack, the attackers can achieve a $92.86\%$ attack success rate (ASR) on Bullshark and an $86.27\%$ ASR on Tusk. Using the fissure attack, the attackers can achieve a $94.81\%$ ASR on Bullshark and an $87.31\%$ ASR on
Tusk.

We also discuss potential countermeasures for the proposed attack, such as ordering blocks randomly and reordering transactions globally based on transaction fees. However, we find that they either compromise the performance of the system or make the
protocol more vulnerable to frontrunning using the existing frontrunning strategies.



## 2024/1497

* Title: Low-degree Security of the Planted Random Subgraph Problem
* Authors: Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
* [Permalink](https://eprint.iacr.org/2024/1497)
* [Download](https://eprint.iacr.org/2024/1497.pdf)

### Abstract

The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs $(H, G)$, where $G$ is an Erdos-Renyi random graph on $n$ vertices, and $H$ is
a random induced subgraph of $G$ on $k$ vertices.
Assuming the hardness of distinguishing these two distributions (with two leaked vertices), Abram et al. construct communication-efficient, computationally secure (1) 2-party private simultaneous messages (PSM) and (2) secret sharing for forbidden graph
structures.

We prove the low-degree hardness of detecting planted random subgraphs all the way up to $k\leq n^{1 - \Omega(1)}$. This improves over Abram et al.'s analysis for $k \leq n^{1/2 - \Omega(1)}$. The hardness extends to $r$-uniform hypergraphs for
constant $r$.

Our analysis is tight in the distinguisher's degree, its advantage, and in the number of leaked vertices. Extending the constructions of Abram et al, we apply the conjecture towards (1) communication-optimal multiparty PSM protocols for random functions
and (2) bit secret sharing with share size $(1 + \epsilon)\log n$ for any $\epsilon > 0$ in which arbitrary minimal coalitions of up to $r$ parties can reconstruct and secrecy holds against all unqualified subsets of up to $\ell = o(\epsilon \log n)^{1/(
r-1)}$ parties.



## 2024/1498

* Title: Practical Implementation of Pairing-Based zkSNARK in Bitcoin Script
* Authors: Federico Barbacovi, Enrique Larraia, Paul Germouty, Wei Zhang
* [Permalink](https://eprint.iacr.org/2024/1498)
* [Download](https://eprint.iacr.org/2024/1498.pdf)

### Abstract

Groth16 is a pairing-based zero-knowledge proof scheme that has a constant proof size and an efficient verification algorithm. Bitcoin Script is a stack-based low-level programming language that is used to lock and unlock bitcoins. In this paper, we
present a practical implementation of the Groth16 verifier in Bitcoin Script deployable on the mainnet of a Bitcoin blockchain called BSV. Our result paves the way for a framework of verifiable computation on Bitcoin: a Groth16 proof is generated for the
correctness of an off-chain computation and is verified in Bitcoin Script on-chain. This approach not only offers privacy but also scalability. Moreover, this approach enables smart contract capability on Bitcoin which was previously thought rather
limited if not non-existent.



## 2024/1499

* Title: Multi-Key Fully-Homomorphic Aggregate MAC for Arithmetic Circuits
* Authors: Suvasree Biswas, Arkady Yerukhimovich
* [Permalink](https://eprint.iacr.org/2024/1499)
* [Download](https://eprint.iacr.org/2024/1499.pdf)

### Abstract

Homomorphic message authenticators allow a user to perform computation on previously authenticated data producing a tag $\sigma$ that can be used to verify the authenticity of the computation. We extend this notion to consider a multi-party setting
where we wish to produce a tag that allows verifying (possibly different) computations on all party's data at once. Moreover, the size of this tag should not grow as a function of the number of parties or the complexity of the computations. We
construct the first aggregate homomorphic MAC scheme that achieves such aggregation of homomorphic tags. Moreover, the final aggregate tag consists of only a single group element.
Our construction supports aggregation of computations that can be expressed by bounded-depth arithmetic circuits and is secure in the random oracle model based on the hardness of the Computational Co-Diffie-Hellman problem over an asymmetric bilinear map.



## 2024/1500

* Title: Hard Quantum Extrapolations in Quantum Cryptography
* Authors: Luowen Qian, Justin Raizes, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1500)
* [Download](https://eprint.iacr.org/2024/1500.pdf)

### Abstract

Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and
only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical$\rightarrow$quantum extrapolation
task, where we ask to extrapolate the rest of a bipartite pure state given the first register measured in the computational basis. We then use it as a key component to establish new connections in quantum cryptography: (a) quantum commitments exist if
classical$\rightarrow$quantum extrapolation is hard; and (b) classical$\rightarrow$quantum extrapolation is hard if any of the following cryptographic primitives exists: quantum public-key cryptography (such as quantum money and signatures) with a
classical public key or 2-message quantum key distribution protocols.

For future work, we further generalize the extrapolation task and propose a fully quantum analogue. We observe that it is hard if quantum commitments exist, and it is easy for quantum polynomial space.



## 2024/1501

* Title: Exploring User Perceptions of Security Auditing in the Web3 Ecosystem * Authors: Molly Zhuangtong Huang, Rui Jiang, Tanusree Sharma, Kanye Ye Wang
* [Permalink](https://eprint.iacr.org/2024/1501)
* [Download](https://eprint.iacr.org/2024/1501.pdf)

### Abstract

In the rapidly evolving Web3 ecosystem, transparent auditing has emerged as a critical component for both applications and users. However, there is a significant gap in understanding how users perceive this new form of auditing and its implications for
Web3 security. Utilizing a mixed-methods approach that incorporates a case study, user interviews, and social media data analysis, our study leverages a risk perception model to comprehensively explore Web3 users' perceptions regarding information
accessibility, the role of auditing, and its influence on user behavior. Based on these extensive findings, we discuss how this open form of auditing is shaping the security of the Web3 ecosystem, identifying current challenges, and providing design
implications.



## 2024/1502

* Title: TopGear 2.0: Accelerated Authenticated Matrix Triple Generation with Scalable Prime Fields via Optimized HE Packing
* Authors: HyunHo Cha, Intak Hwang, Seonhong Min, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/1502)
* [Download](https://eprint.iacr.org/2024/1502.pdf)

### Abstract

The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries.
Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares, called authenticated triples, are generated.
However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are required.

In this work, we propose a new protocol for the SPDZ offline phase, TopGear 2.0, which improves upon the previous state-of-the-art construction, TopGear (Baum et al., SAC'19), and its variant for matrix triples (Chen et al., Asiacrypt'20).
Our protocol aims to achieve a speedup in matrix triple generation and support for larger prime fields, up to 4096 bits in size.
To achieve this, we employ a variant of the BFV scheme and a homomorphic matrix multiplication algorithm optimized for our purpose.

As a result, our protocol achieves about 3.6x speedup for generating scalar triples in a 1024-bit prime field and about 34x speedup for generating 128x128 matrix triples.
In addition, we reduce the size of evaluation keys from 27.4 GB to 0.22 GB and the communication cost for MAC key generation from 816 MB to 16.6 MB.



## 2024/1503

* Title: Scalable Mixnets from Mercurial Signatures on Randomizable Ciphertexts * Authors: Masayuki Abe, Masaya Nanri, Miyako Ohkubo, Octavio Perez Kempner, Daniel Slamanig, Mehdi Tibouchi
* [Permalink](https://eprint.iacr.org/2024/1503)
* [Download](https://eprint.iacr.org/2024/1503.pdf)

### Abstract

A mix network, or mixnet, is a cryptographic tool for anonymous routing, taking messages from multiple (identifiable) senders and delivering them in a randomly permuted order. Traditional mixnets employ encryption and proofs of correct shuffle to cut the
link between each sender and their input.

Hébant et al. (PKC '20) introduced a novel approach to scalable
mixnets based on linearly homomorphic signatures. Unfortunately, their security model is too weak to support voting applications. Building upon their work, we leverage recent advances in equivalence class signatures, replacing linearly homomorphic
signatures to obtain more efficient mixnets with security in a more robust model. More concretely, we introduce the notion of mercurial signatures on randomizable ciphertexts along with an efficient construction, which
we use to build a scalable mixnet protocol suitable for voting. We compare our approach to other (scalable) mixnet approaches, implement our protocols, and provide concrete performance benchmarks. Our findings show our mixnet significantly outperforms
existing alternatives in efficiency and scalability. Verifying the mixing process for 50k ciphertexts takes 135 seconds on a commodity laptop (without parallelization) when employing ten mixers.



## 2024/1504

* Title: Comments on "Privacy-Enhanced Federated Learning Against Poisoning Adversaries"
* Authors: Thomas Schneider, Ajith Suresh, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2024/1504)
* [Download](https://eprint.iacr.org/2024/1504.pdf)

### Abstract

In August 2021, Liu et al. (IEEE TIFS'21) proposed a privacy-enhanced framework named PEFL to efficiently detect poisoning behaviours in Federated Learning (FL) using homomorphic encryption. In this article, we show that PEFL does not preserve privacy.
In particular, we illustrate that PEFL reveals the entire gradient vector of all users in clear to one of the participating entities, thereby violating privacy. Furthermore, we clearly show that an immediate fix for this issue is still insufficient to
achieve privacy by pointing out multiple flaws in the proposed system.



## 2024/1505

* Title: FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE
* Authors: Jeongeun Park, Barry Van Leeuwen, Oliver Zajonc
* [Permalink](https://eprint.iacr.org/2024/1505)
* [Download](https://eprint.iacr.org/2024/1505.pdf)

### Abstract

Multi-key fully homomorphic encryption (MKFHE), a generalization of
fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi
key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of
the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE,
in particular reducing the computational complexity from quadratic to linear in the
number of keys.



## 2024/1506

* Title: Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis
* Authors: Daniele Micciancio, Mark Schultz-Wu
* [Permalink](https://eprint.iacr.org/2024/1506)
* [Download](https://eprint.iacr.org/2024/1506.pdf)

### Abstract

We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions,
and facilitating their use.
Specific contributions of this paper include:
(1) identifying the optimal adversaries achieving the highest possible MW advantage, showing that they are deterministic and have a very simple threshold structure;
(2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and
(3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments
and probability replacement theorems.
On the technical side, our results are obtained by introducing a new notion of "fuzzy" distinguisher (which we prove equivalent to the "aborting" distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam
metric, a standard quantity used in statistics.



## 2024/1507

* Title: Unbounded ABE for Circuits from LWE, Revisited
* Authors: Valerio Cini, Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2024/1507)
* [Download](https://eprint.iacr.org/2024/1507.pdf)

### Abstract

We introduce new lattice-based techniques for building ABE for circuits with unbounded attribute length based on the LWE assumption, improving upon the previous constructions of Brakerski and Vaikuntanathan (CRYPTO 16) and Goyal, Koppula, and Waters (
TCC 16). Our main result is a simple and more efficient unbounded ABE scheme for circuits where only the circuit depth is fixed at set-up; this is the first unbounded ABE scheme for circuits that rely only on black-box access to cryptographic and
lattice algorithms. The scheme achieves semi-adaptive security against unbounded collusions under the LWE assumption. The encryption time and ciphertext size are roughly $3 \times$ larger than the prior bounded ABE of Boneh et al. (EUROCRYPT 2014),
substantially improving upon the encryption times in prior works. As a secondary contribution, we present an analogous result for unbounded inner product predicate encryption that satisfies weak attribute-hiding.



## 2024/1508

* Title: Key Collisions on AES and Its Applications
* Authors: Kodai Taiyama, Kosei Sakamoto, Ryoma Ito, Kazuma Taka, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2024/1508)
* [Download](https://eprint.iacr.org/2024/1508.pdf)

### Abstract

In this paper, we explore a new type of key collisions called target-plaintext key collisions of AES, which emerge as an open problem in the key committing security and are directly converted into single-block collision attacks on Davies-Meyer (DM)
hashing mode. For this key collision, a ciphertext collision is uniquely observed when a specific plaintext is encrypted under two distinct keys. We introduce an efficient automatic search tool designed to find target-plaintext key collisions. This tool
exploits bit-wise behaviors of differential characteristics and dependencies among operations and internal variables of both data processing and key scheduling parts. This allows us to hierarchically perform rebound-type attacks to identify key
collisions. As a result, we demonstrate single-block collision attacks on 2/5/6-round AES-128/192/256-DM and semi-free-start collision attacks on 5/7/9-round AES-128/192/256-DM, respectively. To validate our attacks, we provide an example of fixed-target-
plaintext key collision/semi-free-start collisions on 9-round AES-256-DM. Furthermore, by exploiting a specific class of free-start collisions with our tool, we present two-block collision attacks on 3/9-round AES-128/256-DM, respectively.



## 2024/1509

* Title: DUPLEX: Scalable Zero-Knowledge Lookup Arguments over RSA Group
* Authors: Semin Han, Geonho Yoon, Hyunok Oh, Jihye Kim
* [Permalink](https://eprint.iacr.org/2024/1509)
* [Download](https://eprint.iacr.org/2024/1509.pdf)

### Abstract

Lookup arguments enable a prover to convince a verifier that a committed vector of lookup elements $\vec{f} \in \mathbb{F}^m$ is contained within a predefined table $T \in \mathbb{F}^N$. These arguments are particularly beneficial for enhancing the
performance of SNARKs in handling non-arithmetic operations, such as batched range checks or bitwise operations. While existing works have achieved efficient and succinct lookup arguments, challenges remain, particularly when dealing with large vectors
of lookup elements in privacy-sensitive applications.

In this paper, we introduce $\duplex$, a scalable zero-knowledge lookup argument scheme that offers significant improvements over previous approaches. Notably, we present the first lookup argument designed to operate over the RSA group. Our core
technique allows for the transformation of elements into prime numbers to ensure compatibility with the RSA group, all without imposing substantial computational costs on the prover. Given $m$ lookup elements, $\duplex$ achieves an asymptotic proving
time of $O(m \log m)$, with constant-sized proofs, constant-time verification, and a public parameter size independent of the table size $N$. Additionally, $\duplex$ ensures the privacy of lookup elements and is robust against dynamic table updates,
making it highly suitable for scalable verifiable computation in real-world applications.

We implemented and empirically evaluated $\duplex$, comparing it with the state-of-the-art zero-knowledge lookup argument Caulk [CCS'22]. Our experimental results demonstrate that $\duplex$ significantly outperforms Caulk in proving time for both single
and batched lookup arguments, while maintaining practical proof size and verification time.



## 2024/1510

* Title: Group Factorisation for Smaller Signatures from Cryptographic Group Actions
* Authors: Giuseppe D'Alconzo, Alessio Meneghetti, Edoardo Signorini
* [Permalink](https://eprint.iacr.org/2024/1510)
* [Download](https://eprint.iacr.org/2024/1510.pdf)

### Abstract

Cryptographic group actions have gained significant attention in recent years for their application on post-quantum Sigma protocols and digital signatures. In NIST's recent additional call for post-quantum signatures, three relevant proposals are based
on group actions: LESS, MEDS, and ALTEQ. This work explores signature optimisations leveraging a group's factorisation. We show that if the group admits a factorisation as a semidirect product of subgroups, the group action can be restricted on a
quotient space under the equivalence relation induced by the factorisation. If the relation is efficiently decidable, we show that it is possible to construct an equivalent Sigma protocol for a relationship that depends only on one of the subgroups.
Moreover, if a special class of representative of the quotient space is efficiently computable via a canonical form, the restricted action is effective and does not incur in security loss.
Finally, we apply these techniques to the group actions underlying LESS and MEDS, showing how they will affect the length of signatures and public keys.



## 2024/1511

* Title: Some Classes of Cubic Monomial Boolean Functions with Good Second-Order Nonlinearity
* Authors: RUCHI TELANG GODE
* [Permalink](https://eprint.iacr.org/2024/1511)
* [Download](https://eprint.iacr.org/2024/1511.pdf)

### Abstract


[continued in next message]

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