## In this issue

1. [2023/1401] On the Multi-User Security of LWE-based NIKE
2. [2024/1800] Privacy-Preserving Multi-Party Search via ...
3. [2024/1801] Investigation of the Optimal Linear Characteristics ...
4. [2024/1802] ColliderScript: Covenants in Bitcoin via 160-bit ...
5. [2024/1803] Siniel: Distributed Privacy-Preserving zkSNARK
6. [2024/1804] Quantum Chosen-Cipher Attack on Camellia
7. [2024/1805] Smoothing Parameter and Shortest Vector Problem on ...
8. [2024/1806] Encrypted RAM Delegation: Applications to Rate-1 ...
9. [2024/1807] An Unstoppable Ideal Functionality for Signatures ...
10. [2024/1808] Breaking BASS
11. [2024/1809] Foundations of Adaptor Signatures
12. [2024/1810] Linear Proximity Gap for Reed-Solomon Codes within ...
13. [2024/1811] Pseudorandom Function-like States from Common Haar ...
14. [2024/1812] Batching Adaptively-Sound SNARGs for NP
15. [2024/1813] Revisiting Leakage-Resilient MACs and Succinctly- ...
16. [2024/1814] SophOMR: Improved Oblivious Message Retrieval from ...
17. [2024/1815] Succinct Randomized Encodings from Non-compact ...
18. [2024/1816] Attacking Automotive RKE Security: How Smart are ...
19. [2024/1817] Improved ML-DSA Hardware Implementation With First ...
20. [2024/1818] SoK: On the Physical Security of UOV-based ...
21. [2024/1819] VCVio: A Formally Verified Forking Lemma and Fiat- ...
22. [2024/1820] On the Power of Oblivious State Preparation
23. [2024/1821] SCIF: Privacy-Preserving Statistics Collection with ...
24. [2024/1822] Anonymous Public-Key Quantum Money and Quantum Voting
25. [2024/1823] A Composability Treatment of Bitcoin's Transaction ...
26. [2024/1824] Constructing Dembowski–Ostrom permutation ...
27. [2024/1825] BrakingBase - a linear prover, poly-logarithmic ...
28. [2024/1826] Cloning Games, Black Holes and Cryptography
29. [2024/1827] OPTIMSM: FPGA hardware accelerator for Zero- ...
30. [2024/1828] Classic McEliece Hardware Implementation with ...
31. [2024/1829] Compiled Nonlocal Games from any Trapdoor Claw-Free ...
32. [2024/1830] A Tight Analysis of GHOST Consistency
33. [2024/1831] Fast Two-party Threshold ECDSA with Proactive Security
34. [2024/1832] How to Delete Without a Trace: Certified ...
35. [2024/1833] Private Neural Network Training with Packed Secret ...
36. [2024/1834] Scutum: Temporal Verification for Cross-Rollup ...
37. [2024/1835] Hybrid Zero-Knowledge from Garbled Circuits
38. [2024/1836] Symmetric Encryption on a Quantum Computer
39. [2024/1837] A Query Reconstruction Attack on the Chase-Shen ...
40. [2024/1838] Pushing the QAM method for finding APN functions ...
41. [2024/1839] Cryptographically Secure Digital Consent
42. [2024/1840] Ideal Pseudorandom Codes
43. [2024/1841] Verifying Jolt zkVM Lookup Semantics
44. [2024/1842] Zero-Knowledge Location Privacy via Accurate ...
45. [2024/1843] Khatam: Reducing the Communication Complexity of ...
46. [2024/1844] KLaPoTi: An asymptotically efficient isogeny group ...
47. [2024/1845] Single-Server Client Preprocessing PIR with Tight ...
48. [2024/1846] The LaZer Library: Lattice-Based Zero Knowledge and ...
49. [2024/1847] Notions of Quantum Reductions and Impossibility of ...
50. [2024/1848] Non-Interactive Zero-Knowledge Proofs with ...

## 2023/1401

* Title: On the Multi-User Security of LWE-based NIKE
* Authors: Roman Langrehr
* [Permalink](https://eprint.iacr.org/2023/1401)
* [Download](https://eprint.iacr.org/2023/1401.pdf)

### Abstract

Non-interactive key exchange (NIKE) schemes like the Diffie-Hellman key exchange are a widespread building block in several cryptographic protocols. Since the Diffie-Hellman key exchange is not post-quantum secure, it is important to investigate post-
quantum alternatives.

We analyze the security of the LWE-based NIKE by Ding et al. (ePrint 2012) and Peikert (PQCrypt 2014) in a multi-user setting where the same public key is used to generate shared keys with multiple other users. The Diffie-Hellman key exchange achieves
this security notion. The mentioned LWE-based NIKE scheme comes with an inherent correctness error (Guo et al., PKC 2020), and this has significant implications for the multi-user security, necessitating a closer examination.

Single-user security generically implies multi-user security when all users generate their keys honestly for NIKE schemes with negligible correctness error. However, the LWE-based NIKE requires a super-polynomial modulus to achieve a negligible
correctness error, which makes the scheme less efficient. We show that
- generically, single-user security does not imply multi-user security when the correctness error is non-negligible, but despite this
- the LWE-based NIKE with polynomial modulus is multi-user secure for honest users when the number of users is fixed in advance. This result takes advantage of the leakage-resilience properties of LWE.

We then turn to a stronger model of multi-user security that allows adversarially generated public keys. For this model, we consider a variant of the LWE-based NIKE where each public key is equipped with a NIZKPoK of the secret key. Adding NIZKPoKs is a
standard technique for this stronger model and Hesse et al. (Crypto 2018) showed that this is sufficient to achieve security in the stronger multi-user security model for perfectly correct NIKEs (which the LWE-based NIKE is not). We show that
- for certain parameters that include all parameters with polynomial modulus, the LWE-based NIKE can be efficiently attacked with adversarially generated public keys, despite the use of NIZKPoKs, but
- for suitable parameters (that require a super-polynomial modulus), this security notion is achieved by the LWE-based NIKE with NIZKPoKs.
This stronger security notion has been previously achieved for LWE-based NIKE only in the QROM, while all our results are in the standard model.



## 2024/1800

* Title: Privacy-Preserving Multi-Party Search via Homomorphic Encryption with Constant Multiplicative Depth
* Authors: Mihail-Iulian Pleşa, Ruxandra F. Olimid
* [Permalink](https://eprint.iacr.org/2024/1800)
* [Download](https://eprint.iacr.org/2024/1800.pdf)

### Abstract

We propose a privacy-preserving multiparty search protocol
using threshold-level homomorphic encryption, which we prove correct
and secure to honest but curious adversaries. Unlike existing approaches,
our protocol maintains a constant circuit depth. This feature enhances
its suitability for practical applications involving dynamic underlying databases.



## 2024/1801

* Title: Investigation of the Optimal Linear Characteristics of BAKSHEESH (Full Version)
* Authors: Yuxuan Peng, Jinpeng Liu, Ling Sun
* [Permalink](https://eprint.iacr.org/2024/1801)
* [Download](https://eprint.iacr.org/2024/1801.pdf)

### Abstract

This paper aims to provide a more comprehensive understanding of the optimal linear characteristics of BAKSHEESH. Initially, an explicit formula for the absolute correlation of the $R$-round optimal linear characteristic of BAKSHEESH is proposed when $R \
geqslant 12$. By examining the linear characteristics of BAKSHEESH with three active S-boxes per round, we derive some properties of the three active S-boxes in each round. Furthermore, we demonstrate that there is only one 1-round iterative linear
characteristic with three active S-boxes. Since the 1-round linear characteristic is unique, it must be included in any $R$-round ($R \geqslant 12$) linear characteristics of BAKSHEESH with three active S-boxes per round. Finally, we confirm that
BAKSHEESH's total number of $R$-round optimal linear characteristics is $3072$ for $R \geqslant 12$. All of these characteristics are generated by employing the 1-round iterative linear characteristic.



## 2024/1802

* Title: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions
* Authors: Ethan Heilman, Victor I. Kolobov, Avihu M. Levy, Andrew Poelstra
* [Permalink](https://eprint.iacr.org/2024/1802)
* [Download](https://eprint.iacr.org/2024/1802.pdf)

### Abstract

We introduce a method for enforcing covenants on Bitcoin outputs without requiring any changes to Bitcoin by designing a hash collision based equivalence check which bridges Bitcoin's limited Big Script to Bitcoin's Small Script. This allows us evaluate
the signature of the spending transaction (available only to Big Script) in Small Script. As Small Script enables arbitrary computations, we can introspect into the spending transaction and enforce covenants on it.

Our approach leverages finding collisions in the $160$-bit hash functions: SHA-1 and RIPEMD-160. By the birthday bound this should cost $\sim2^{80}$ work. Each spend of our covenant costs $\sim2^{86}$ hash queries and $\sim2^{56}$ bytes of space. For
security, we rely on an assumption regarding the hardness of finding a $3$-way collision (with short inputs) in $160$-bit hash functions, arguing that if the assumption holds, breaking covenant enforcement requires $\sim2^{110}$ hash queries. To put this
in perspective, the work to spend our covenant is $\sim33$ hours of the Bitcoin mining network, whereas breaking our covenant requires $\sim 450,000$ years of the Bitcoin mining network.
We believe there are multiple directions of future work that can significantly improve these numbers.

Evaluating covenants and our equivalence check requires performing many operations in Small Script, which must take no more than $4$ megabytes in total size, as Bitcoin does not allow transactions greater than $4$ megabytes. We only provide rough
estimates of the transaction size because, as of this writing, no Small Script implementations of the hash functions required, SHA-1 and RIPEMD-160, have been written.



## 2024/1803

* Title: Siniel: Distributed Privacy-Preserving zkSNARK
* Authors: Yunbo Yang, Yuejia Cheng, Kailun Wang, Xiaoguo Li, Jianfei Sun, Jiachen Shen, Xiaolei Dong, Zhenfu Cao, Guomin Yang, Robert H. Deng
* [Permalink](https://eprint.iacr.org/2024/1803)
* [Download](https://eprint.iacr.org/2024/1803.pdf)

### Abstract

Zero-knowledge Succinct Non-interactive Argument of Knowledge (zkSNARK) is a powerful cryptographic primitive, in which a prover convinces a verifier that a given statement is true without leaking any additional information. However, existing zkSNARKs
suffer from high computation overhead in the proof generation. This limits the applications of zkSNARKs, such as private payments, private smart contracts, and anonymous credentials. Private delegation has become a prominent way to accelerate proof
generation.

In this work, we propose Siniel, an efficient private delegation framework for zkSNARKs constructed from polynomial interactive oracle proof (PIOP) and polynomial commitment scheme (PCS). Our protocol allows a computationally limited prover (a.k.a.
delegator) to delegate its expensive prover computation to several workers without leaking any information about the private witness. Most importantly, compared with the recent work EOS (USENIX'23), the state-of-the-art zkSNARK prover delegation
framework, a prover in Siniel needs not to engage in the MPC protocol after sending its shares of private witness. This means that a Siniel prover can outsource the entire computation to the workers.

We compare Siniel with EOS and show significant performance advantages of the former. The experimental results show that, under low bandwidth conditions (10MBps), Siniel saves about 16% time for delegators than that of EOS, whereas under high bandwidth
conditions (1000MBps), Siniel saves about 80% than EOS.



## 2024/1804

* Title: Quantum Chosen-Cipher Attack on Camellia
* Authors: Yanjun Li, Qi Wang, DingYun Huang, Jian Liu, Huiqin Xie
* [Permalink](https://eprint.iacr.org/2024/1804)
* [Download](https://eprint.iacr.org/2024/1804.pdf)

### Abstract

The Feistel structure represents a fundamental architectural component within the domain of symmetric cryptographic algorithms, with a substantial body of research conducted within the context of classical computing environments. Nevertheless, research
into specific symmetric cryptographic algorithms utilizing the Feistel structure is relatively scarce in quantum computing environments. This paper builds upon a novel 4-round distinguisher proposed by Ito et al. for the Feistel structure under the
quantum chosen-ciphertext attack (qCCA) setting. It introduces a 5-round distinguisher for Camellia. The efficacy of the distinguisher has been empirically validated. Furthermore, this paper combines Grover's algorithm with Simon's algorithm, utilizing
an analysis of Camellia's key scheduling characteristics to construct a 9-round key recovery attack on Camellia algorithm. The time complexity for acquiring the correct key bits is $2^{61.5}$, and it requires 531 quantum bits. This represents the
inaugural chosen-ciphertext attack on Camellia under the Q2 model.



## 2024/1805

* Title: Smoothing Parameter and Shortest Vector Problem on Random Lattices
* Authors: Amaury Pouly, Yixin Shen
* [Permalink](https://eprint.iacr.org/2024/1805)
* [Download](https://eprint.iacr.org/2024/1805.pdf)

### Abstract

Lattice problems have many applications in various domains of computer science. There is currently a gap in the understanding of these problems with respect to their worst-case complexity and their average-case behaviour.
For instance, the Shortest Vector problem (SVP) on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ \cite{ADRS15}.
However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ \cite{BeckerDGL16}
to assess the security of lattice-based cryptography schemes. Those heuristic algorithms are experimentally verified
for lattices used in cryptography, which are usually random in some way.

In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developped by Siegel, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that
applies to almost all random lattices. This allows us to obtain a $2^{n/2+o(n)}$ time algorithm for an approximation version of the SVP on random lattices with a small constant approximation factor.



## 2024/1806

* Title: Encrypted RAM Delegation: Applications to Rate-1 Extractable Arguments, Homomorphic NIZKs, MPC, and more
* Authors: Abtin Afshar, Jiaqi Cheng, Rishab Goyal, Aayush Yadav, Saikumar Yadugiri
* [Permalink](https://eprint.iacr.org/2024/1806)
* [Download](https://eprint.iacr.org/2024/1806.pdf)

### Abstract

In this paper we introduce the notion of encrypted RAM delegation. In an encrypted RAM delegation scheme, the prover creates a succinct proof for a group of two input strings $x_\mathsf{pb}$ and $x_\mathsf{pr}$, where $x_\mathsf{pb}$ corresponds to a
large \emph{public} input and $x_\mathsf{pr}$ is a \emph{private} input. A verifier can check correctness of computation of $\mathcal{M}$ on $(x_\mathsf{pb}, x_\mathsf{pr})$, given only the proof $\pi$ and $x_\mathsf{pb}$.

We design encrypted RAM delegation schemes from a variety of standard assumptions such as DDH, or LWE, or $k$-linear. We prove strong knowledge soundness guarantee for our scheme as well as a special input hiding property to ensure that $\pi$ does not
leak anything about $x_\mathsf{pr}$.

We follow this by describing multiple applications of encrypted RAM delegation. First, we show how to design a rate-1 non-interactive zero-knowledge (NIZK) argument system with a straight-line extractor. Despite over 30+ years of research, the only known
construction in the literature for rate-1 NIZKs from standard assumptions relied on fully homomorphic encryption. Thus, we provide the first rate-1 NIZK scheme based purely on DDH or $k$-linear assumptions.

Next, we also design fully-homomorphic NIZKs from encrypted RAM delegation. The only prior solution crucially relied on algebraic properties of pairing-based NIZKs, thus was only known from the decision linear assumption. We provide the first fully-
homomorphic NIZK system from LWE (thus post-quantum security) and from DDH-hard groups.

We also provide a communication-complexity-preserving compiler for a wide class of semi-malicious multiparty computation (MPC) protocols to obtain fully malicious MPC protocols. This gives the first such compiler for a wide class of MPC protocols as any
comparable compiler provided in prior works relied on strong non-falsifiable assumptions such as zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). Moreover, we also show many other applications to composable zero-knowledge batch
arguments, succinct delegation of committed programs, and fully context-hiding multi-key multi-hop homomorphic signatures.



## 2024/1807

* Title: An Unstoppable Ideal Functionality for Signatures and a Modular Analysis of the Dolev-Strong Broadcast
* Authors: Ran Cohen, Jack Doerner, Eysa Lee, Anna Lysyanskaya, Lawrence Roy
* [Permalink](https://eprint.iacr.org/2024/1807)
* [Download](https://eprint.iacr.org/2024/1807.pdf)

### Abstract

Many foundational results in the literature of consensus follow the Dolev-Yao model (FOCS '81), which treats digital signatures as ideal objects with perfect correctness and unforgeability. However, no work has yet formalized an ideal signature scheme
that is both suitable for this methodology and possible to instantiate, or a composition theorem that ensures security when instantiating it cryptographically.

The Universal Composition (UC) framework would ensure composition if we could specify an ideal functionality for signatures and prove it UC-realizable. Unfortunately, all signature functionalities heretofore proposed are problematic when used to
construct higher-level protocols: either the functionality internally computes a computationally secure signature, and therefore higher-level protocols must rely upon computational assumptions, or else the functionality introduces a new attack surface
that does not exist when the functionality is realized. As a consequence, no consensus protocol has ever been analyzed in a modular way using existing ideal signature functionalities.

We propose a new unstoppable ideal functionality for signatures that is UC-realized exactly by the set of standard EUF-CMA signature schemes that are consistent and linear time. No adversary can prevent honest parties from obtaining perfectly ideal
signature services from our functionality. We showcase its usefulness by presenting the first modular analysis of the Dolev-Strong broadcast protocol (SICOMP '83) in the UC framework. Our result can be interpreted as a step toward a sound realization of
the Dolev-Yao methodology.



## 2024/1808

* Title: Breaking BASS
* Authors: Simon-Philipp Merz, Kenneth G. Paterson, Àlex Rodríguez García
* [Permalink](https://eprint.iacr.org/2024/1808)
* [Download](https://eprint.iacr.org/2024/1808.pdf)

### Abstract

We provide several attacks on the BASS signature scheme introduced by Grigoriev, Ilmer, Ovchinnikov and Shpilrain in 2023. We lay out a trivial forgery attack which generates signatures passing the scheme's probabilistic signature verification with high
probability. Generating these forgeries is faster than generating signatures honestly. Moreover, we describe a key-only attack which allows us to recover an equivalent private key from a signer's public key. The time complexity of this recovery is
asymptotically the same as that of signing messages.



## 2024/1809

* Title: Foundations of Adaptor Signatures
* Authors: Paul Gerhart, Dominique Schröder, Pratik Soni, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2024/1809)
* [Download](https://eprint.iacr.org/2024/1809.pdf)

### Abstract

Adaptor signatures extend the functionality of regular signatures through the computation of pre-signatures on messages for statements of NP relations. Pre-signatures are publicly verifiable; they simultaneously hide and commit to a signature of an
underlying signature scheme on that message. Anybody possessing a corresponding witness for the statement can adapt the pre-signature to obtain the "regular" signature. Adaptor signatures have found numerous applications for conditional payments in
blockchain systems, like payment channels (CCS'20, CCS'21), private coin mixing (CCS'22, SP'23), and oracle-based payments (NDSS'23).

In our work, we revisit the state of the security of adaptor signatures and their constructions. In particular, our two main contributions are:

- Security Gaps and Definitions: We review the widely-used security model of adaptor signatures due to Aumayr et al. (ASIACRYPT'21) and identify gaps in their definitions that render known protocols for private coin-mixing and oracle-based payments
insecure. We give simple counterexamples of adaptor signatures that are secure w.r.t. their definitions but result in insecure instantiations of these protocols. To fill these gaps, we identify a minimal set of modular definitions that align with these
practical applications.

- Secure Constructions: Despite their popularity, all known constructions are (1) derived from identification schemes via the Fiat-Shamir transform in the random oracle model or (2) require modifications to the underlying signature verification algorithm,
thus making the construction useless in the setting of cryptocurrencies. More concerningly, all known constructions were proven secure w.r.t. the insufficient definitions of Aumayr et al., leaving us with no provably secure adaptor signature scheme to
use in applications.

Firstly, in this work, we salvage all current applications by proving the security of the widely-used Schnorr adaptor signatures under our proposed definitions. We then provide several new constructions, including presenting the first adaptor
signature schemes for Camenisch-Lysyanskaya (CL), Boneh-Boyen-Shacham (BBS+), and Waters signatures, all of which are proven secure in the standard model. Our new constructions rely on a new abstraction of digital signatures, called dichotomic signatures,
which covers the essential properties we need to build adaptor signatures. Proving the security of all constructions (including identification-based schemes) relies on a novel non-black-box proof technique. Both our digital signature abstraction and the
proof technique could be of independent interest to the community.



## 2024/1810

* Title: Linear Proximity Gap for Reed-Solomon Codes within the 1.5 Johnson Bound
* Authors: Yiwen Gao, Haibin Kan, Yuan Li
* [Permalink](https://eprint.iacr.org/2024/1810)
* [Download](https://eprint.iacr.org/2024/1810.pdf)

### Abstract

We establish a linear proximity gap for Reed-Solomon (RS) codes within the one-and-a-half Johnson bound. Specifically, we investigate the proximity gap for RS codes, revealing that any affine subspace is either entirely $\delta$-close to an RS code or
nearly all its members are $\delta$-far from it. When $\delta$ is within the one-and-a-half Johnson bound, we prove an upper bound on the number of members (in the affine subspace) that are $\delta$-close to the RS code for the latter case. Our bound is
linear in the length of codewords. In comparison, Ben-Sasson, Carmon, Ishai, Kopparty and Saraf [FOCS 2020] prove a linear bound when $\delta$ is within the unique decoding bound and a quadratic bound when $\delta$ is within the Johnson bound. Note that
when the rate of the RS code is smaller than 0.23, the one-and-a-half Johnson bound is larger than the unique decoding bound.

Proximity gaps for Reed-Solomon (RS) codes have implications in various RS code-based protocols. In many cases, a stronger property than individual distance—known as correlated agreement—is required, i.e., functions in the affine subspace are not
only $\delta$-close to an RS code, but also agree on the same evaluation domain. Our results support this stronger property.



## 2024/1811

* Title: Pseudorandom Function-like States from Common Haar Unitary
* Authors: Minki Hhan, Shogo Yamada
* [Permalink](https://eprint.iacr.org/2024/1811)
* [Download](https://eprint.iacr.org/2024/1811.pdf)

### Abstract

Recent active studies have demonstrated that cryptography without one-way functions (OWFs) could be possible in the quantum world. Many fundamental primitives that are natural quantum analogs of OWFs or pseudorandom generators (PRGs) have been introduced,
and their mutual relations and applications have been studied. Among them, pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, and Yuen, Crypto 2022] are one of the most important primitives. PRFSGs are a natural quantum analogue of
pseudorandom functions (PRFs), and imply many applications such as IND-CPA secret-key encryption (SKE) and EUF-CMA message authentication code (MAC). However, only known constructions of (many-query-secure) PRFSGs are ones from OWFs or pseudorandom
unitaries (PRUs).
In this paper, we construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model which is introduced in [Chen and Movassagh, Quantum]. The invertible QHRO model is an idealized model where any party can
access a public single Haar random unitary and its inverse, which can be considered as a quantum analog of the random oracle model. Our PRFSG constructions resemble the classical Even-Mansour encryption based on a single permutation, and are secure
against any unbounded polynomial number of queries to the oracle and construction. To our knowledge, this is the first application in the invertible QHRO model without any assumption or conjecture. The previous best construction in the idealized model is
PRFSGs secure up to o(λ/ log λ) queries in the common Haar state model [Ananth, Gulati, and Lin, TCC 2024].
We develop new techniques on Haar random unitaries to prove the selective and adaptive security of our PRFSGs. For selective security, we introduce a new formula, which we call the Haar twirl approximation formula. For adaptive security, we show the
unitary reprogramming lemma and the unitary resampling lemma. These have their own interest, and may have many further applications. In particular, by using the approximation formula, we give an alternative proof of the non-adaptive security of the PFC
ensemble [Metger, Poremba, Sinha, and Yuen, FOCS 2024] as an additional result. Finally, we prove that our construction is not PRUs or quantum-accessible non-adaptive PRFSGs by presenting quantum polynomial time attacks. Our attack is based on generalizing the hidden subgroup problem where the relevant function outputs quantum
states.



## 2024/1812

* Title: Batching Adaptively-Sound SNARGs for NP
* Authors: Lalita Devadas, Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1812)
* [Download](https://eprint.iacr.org/2024/1812.pdf)

### Abstract

A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement $x$ is true with a proof whose size is sublinear in the length of the traditional NP witness. Moreover, a SNARG is adaptively sound if the
adversary can choose the statement it wants to prove after seeing the scheme parameters. Very recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-
exponentially-secure indistinguishability obfuscation, sub-exponentially-secure one-way functions, and polynomial hardness of discrete log).

We consider the batch setting where the prover wants to prove a collection of $T$ statements $x_1, \ldots, x_T$ and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of instances $T$. In this
setting, existing constructions either require the size of the public parameters to scale linearly with $T$ (and thus, can only support an a priori bounded number of instances), or only provide non-adaptive soundness, or have proof size that scales
linearly with the size of a single NP witness. In this work, we give two approaches for batching adaptively-sound SNARGs for NP, and in particular, show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we
can obtain an adaptively-sound SNARG for batch NP where the size of the proof is $\mathsf{poly}(\lambda)$ and the size of the CRS is $\mathsf{poly}(\lambda + |C|)$, where $\lambda$ is a security parameter and $|C|$ is the size of the circuit that
computes the associated NP relation.

Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the
chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) to obtain a SNARG for batch NP.



## 2024/1813

* Title: Revisiting Leakage-Resilient MACs and Succinctly-Committing AEAD: More Applications of Pseudo-Random Injections
* Authors: Mustafa Khairallah
* [Permalink](https://eprint.iacr.org/2024/1813)
* [Download](https://eprint.iacr.org/2024/1813.pdf)

### Abstract

Pseudo-Random Injections (PRIs) have had several applications in symmetric-key cryptography, such as in the idealization of Authenticated Encryption with Associated Data (AEAD) schemes, building robust AEAD, and, recently, in converting a committing AEAD
scheme into a succinctly committing AEAD scheme. In Crypto 2024, Bellare and Hoang showed that if an AEAD scheme is already committing, it can be transformed into a succinctly committed scheme by encrypting part of the plaintext using a PRI. In this
paper, we revisit the applications of PRIs in building Message Authentication Codes (MACs) and AEAD schemes.

First, we look at some of the properties and definitions PRIs, such as collision resistance and unforgeability when used as a MAC with small plaintext space, under different leakage models. Next, we show how they can be combined with collision-resistant
hash functions to build a MAC for long plaintexts, offering flexible security depending on how the PRI and equality check are implemented. If both the PRI and equality check are leak-free, the MAC provides almost optimal security, but the security
only degrades a little if the equality check is only leakage-resilient (rather than leak-free). If the equality check has unbounded leakage, the security drops to a baseline security, rather than being completely insecure. Next, we show how to use PRIs
to build a succinctly committing online AEAD scheme dubbed as scoAE from scratch that achieves succinct CMT4 security, privacy, and Ciphertext Integrity with Misuse and Leakage (CIML2) security. Last but not least, we show how to build a succinct nonce
Misuse-Resistant (MRAE) AEAD scheme, dubbed as scMRAE. The construction combines the SIV paradigm with PRI-based encryption (e.g. the Encode-then-Encipher (EtE) framework).



## 2024/1814

* Title: SophOMR: Improved Oblivious Message Retrieval from SIMD-Aware Homomorphic Compression
* Authors: Keewoo Lee, Yongdong Yeo
* [Permalink](https://eprint.iacr.org/2024/1814)
* [Download](https://eprint.iacr.org/2024/1814.pdf)

### Abstract

Privacy-preserving blockchains and private messaging services that ensure receiver-privacy face a significant UX challenge: each client must scan every payload posted on the public bulletin board individually to avoid missing messages intended for them.
Oblivious Message Retrieval (OMR) addresses this issue by securely outsourcing this expensive scanning process to a service provider using Homomorphic Encryption (HE).


[continued in next message]

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