[continued from previous message]

We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN)
assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (
CRYPTO 2024), together with exponentially-hard MQ.

The main technical ingredient of our construction is an extremely natural (but only in hindsight!) construction of correlation-intractable (CI) hash functions from MQ, for a NIZK-friendly sub-class of constant-degree polynomials that we call concatenated
constant-degree polynomials. Under exponential security, this hash function also satisfies the stronger notion of approximate CI for concatenated constant-degree polynomials. The NIZK construction then follows from a prior blueprint of Brakerski-Koppula-
Mour (CRYPTO 2020). In addition, we show how to construct (approximate) CI hashing for degree-$d$ functions from the (exponential) hardness of solving random degree-$d$ equations, a natural generalization of MQ. To realize NIZK with statistical zero-
knowledge, we design a lossy public-key encryption scheme with approximate linear decryption and inverse-polynomial decryption error from Dense-Sparse LPN. These constructions may be of independent interest.

Our work therefore gives a new way to leverage MQ with uniformly random equations, which has found little cryptographic applications to date. Indeed, most applications in the context of encryption and signature schemes make use of structured variants of
MQ, where the polynomials are not truly random but posses a hidden planted structure. We believe that the MQ assumption may plausibly find future use in the designing other advanced proof systems.



## 2024/1255

* Title: Compass: Encrypted Semantic Search with High Accuracy
* Authors: Jinhao Zhu, Liana Patel, Matei Zaharia, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2024/1255)
* [Download](https://eprint.iacr.org/2024/1255.pdf)

### Abstract

We introduce Compass, a semantic search system over encrypted data that offers high accuracy, comparable to state-of-the-art plaintext search algorithms while protecting data, queries and search results from a fully compromised server. Compass also
enables privacy-preserving RAG where both the RAG database and the query are protected. Compass's search index contributes a novel way to traverse the search graph in Hierarchical Navigable Small Worlds (HNSW), a top performing vector nearest neighbor
search, using Oblivious RAM, a cryptographic primitive with strong security guarantees. Our techniques, Directional Neighbor Filtering, Speculative Greedy Search and HNSW-tailored Path ORAM ensure that Compass achieves user-perceived latencies of few
seconds and is orders of magnitude faster than a baseline for encrypted embeddings search.



## 2024/1256

* Title: Concrete Analysis of Schnorr-type Signatures with Aborts
* Authors: Theo Fanuela Prabowo, Chik How Tan
* [Permalink](https://eprint.iacr.org/2024/1256)
* [Download](https://eprint.iacr.org/2024/1256.pdf)

### Abstract

Lyubashevsky’s signature can be viewed as a lattice-based adapation of the Schnorr signature, with the core difference being the use of aborts during signature generation process. Since the proposal of Lyubashevsky’s signature, a number of other
variants of Schnorr-type signatures with aborts have been proposed, both in lattice-based and code-based setting. In this paper, we examine the security of Schnorr-type signature schemes with aborts. We give a detailed analysis of when the expected value
of the signature is correlated to the secret key, and when it is not. Our analysis shows that even when abort condition is employed, it is crucial to set the parameters carefully in order to defend against statistical attack. In particular, we recommend
to set δ ≥ β (where δ, β are public parameters) as in this case we prove that the signature does not reveal any information about the secret key. On the other hand, if this condition is not satisfied, then some information about the secret key are
leaked, making the scheme susceptible to statistical attacks. For completeness, we also analyze the security of Schnorr-type signatures without aborts. In particular, we present a detailed key recovery attack via statistical method on the EagleSign
signature, which is one of the submission to the NIST call for Additional PQC Signature. Moreover, we give a formula for determining the number of required signatures to successfully launch the statistical attack.



## 2024/1257

* Title: Committing Wide Encryption Mode with Minimum Ciphertext Expansion
* Authors: Yusuke Naito, Yu Sasaki, Takeshi Sugawara
* [Permalink](https://eprint.iacr.org/2024/1257)
* [Download](https://eprint.iacr.org/2024/1257.pdf)

### Abstract

We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. WE is attracting much attention in the last few years, and its advantage includes RAE
security that provides robustness against wide range of misuses, combined with the encode-then-encipher (EtE) construction. Unfortunately, WE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4 attack (Chen et
al., ToSC 2023(4)). Improving CMT-4 security requires considerable ciphertext expansion, and the state-of-the-art scheme expands the ciphertext by s_rae + 2 s_cmt bits from an original message to achieve s_rae-bit RAE and s_cmt-bit CMT-4 security. Our
new WE mode FFF addresses the issue by achieving s_rae-bit RAE and s_cmt-bit CMT-4 security only with max{s_cmt, s_rae} bits of ciphertext expansion. Our design is based on the committing concealer proposed by Bellare et al., and its extension to WE (cf.
tag-based AE) while satisfying RAE security is the main technical innovation.



## 2024/1258

* Title: Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange
* Authors: Mihir Bellare, Doreen Riepel, Stefano Tessaro, Yizhao Zhang
* [Permalink](https://eprint.iacr.org/2024/1258)
* [Download](https://eprint.iacr.org/2024/1258.pdf)

### Abstract

In the multi-user with corruptions (muc) setting there are $n\geq 1$ users, and the goal is to prove that, even in the face of an adversary that adaptively corrupts users to expose their keys, un-corrupted users retain security. This can be considered
for many primitives including signatures and encryption. Proofs of muc security, while possible, generally suffer a factor n loss in tightness, which can be large. This paper gives new proofs where this factor is reduced to the number c of corruptions,
which in practice is much smaller than n. We refer to this as corruption-parametrized muc (cp-muc) security. We give a general result showing it for a class of games that we call local. We apply this to get cp-muc security for signature schemes (
including ones in standards and in TLS 1.3) and some forms of public-key and symmetric encryption. Then we give dedicated cp-muc security proofs for some important schemes whose underlying games are not local, including the Hashed ElGamal and Fujisaki-
Okamoto KEMs and authenticated key exchange. Finally, we give negative results to show optimality of our bounds.



## 2024/1259

* Title: Efficient (Non-)Membership Tree from Multicollision-Resistance with Applications to Zero-Knowledge Proofs
* Authors: Maksym Petkus
* [Permalink](https://eprint.iacr.org/2024/1259)
* [Download](https://eprint.iacr.org/2024/1259.pdf)

### Abstract

Many applications rely on accumulators and authenticated dictionaries, from timestamping certificate transparency and memory checking to blockchains and privacy-preserving decentralized electronic money, while Merkle tree and its variants are efficient
for arbitrary element membership proofs, non-membership proofs, i.e., universal accumulators, and key-based membership proofs may require trees up to 256 levels for 128 bits of security, assuming binary tree, which makes it inefficient in practice,
particularly in the context of zero-knowledge proofs.

Building on the hardness of multi-collision we introduce a novel (non-)membership, optionally key-value, accumulator with up to 2x smaller tree depth while preserving the same security level, as well as multiple application-specific versions with even
shallower trees, up to 6x smaller depth, that rely on the low-entropy source. Moreover, solving for special case of adversarial attacks we introduce key index variants which might be a stepping stone for an entropy-free accumulator.

Notably, unlike other constructions, this work, although may, doesn't depend on the dynamic depth of the tree which is simpler and more suitable for constant-size ZKP circuits, while ensuring a substantially smaller upper bound on depth.

Efficient in practice construction in the adversarial context, e.g. blockchain, where the tree manager doesn't need to be trusted, i.e., operations can be carried out by an untrusted party and verified by anyone, is the primary goal.
Example instantiations are considered, where special treatment is given to the application of representing serial numbers, aka nullifiers.
Nevertheless, the constructions are self-sufficient and can be used in other contexts, without blockchain and/or zero-knowledge proofs, including non-adversarial contexts.

Furthermore, our findings might be of independent interest for other use cases, such as hash tables, databases and other data structures.



## 2024/1260

* Title: zk-Promises: Making Zero-Knowledge Objects Accept the Call for Banning and Reputation
* Authors: Maurice Shih, Michael Rosenberg, Hari Kailad, Ian Miers
* [Permalink](https://eprint.iacr.org/2024/1260)
* [Download](https://eprint.iacr.org/2024/1260.pdf)

### Abstract

Privacy preserving systems often need to allow anonymity while requiring accountability. For anonymous clients, depending on application, this may mean banning/revoking their accounts, docking their reputation, or updating their state in some complex
access control scheme. Frequently, these operations happen asynchronously when some violation, e.g., a forum post, is found well after the offending action occurred. Malicious clients, naturally, wish to evade this asynchronous negative feedback.
Considering privacy-preserving analogues of modern access control and reputation schemes raises a more fundamental technical challenge with far broader applications: how do we allow multiple parties to interact with private state stored by an anonymous
client while ensuring state integrity and supporting oblivious updates?

We propose zk-promises, a framework which supports Turing-complete state machines with arbitrary asynchronous callbacks. In zk-promises, client state is stored in a zk-object. Updates to the zk-object, represented as a cryptographic commitment to the new,
modified object, require a zkSNARK that ensures integrity and atomicity while providing confidentiality. Clients can modify and prove their state by calling valid methods (e.g, to show they are authorized to post) and can give callbacks to third
parties (e.g., to later hold them accountable). Through careful protocol design, we ensure clients who advance their state-machine are forced to ingest callbacks that are called by a third party.

zk-promises allows us to build a privacy-preserving account model. State that would normally be stored on a trusted server can be privately outsourced to the client while preserving the server's ability to update the account. To demonstrate the
feasibility of our approach, we build an anonymous reputation system with better than state-of-the-art performance and features, supporting asynchronous reputation updates, banning, and reputation-dependent rate limiting to better protect against Sybil
attacks.



## 2024/1261

* Title: A Key-Recovery Attack on a Leaky Seasign Variant
* Authors: Shai Levin
* [Permalink](https://eprint.iacr.org/2024/1261)
* [Download](https://eprint.iacr.org/2024/1261.pdf)

### Abstract

We present a key-recovery attack on a variant of the Seasign signature scheme presented by [Kim24], which attempts to avoid rejection sampling by presampling vectors $\mathbf{f}$ such that the $\mathbf{f}-\mathbf{e}$ is contained in an acceptable bound,
where $\mathbf{e}$ is the secret key. We show that this choice leads to a bias of these vectors such that, in a small number of signatures, the secret key can either be completely recovered or its keyspace substantially reduced. In particular, on average,
given $20$ signatures, with parameter set II of their paper, the attack reduces the private key to 128 possibilities



## 2024/1262

* Title: Dilithium-Based Verifiable Timed Signature Scheme
* Authors: Erkan Uslu, Oğuz Yayla
* [Permalink](https://eprint.iacr.org/2024/1262)
* [Download](https://eprint.iacr.org/2024/1262.pdf)

### Abstract

Verifiable Timed Signatures (VTS) are cryptographic constructs that enable obtaining a signature at a specific time in the future and provide evidence that the signature is legitimate. This framework particularly finds utility in applications such as
payment channel networks, multiparty signing operations, or multiparty computation, especially within blockchain architectures. Currently, VTS schemes are based on signature algorithms such as BLS signature, Schnorr signature, and ECDSA. These signature
algorithms are considered insecure against quantum attacks due to the effect of Shor's Algorithm on the discrete logarithm problem. We present a new VTS scheme called VT-Dilithium based on CRYSTALS-Dilithium Digital Signature Algorithm that has been
selected as NIST's quantum-resistant digital signature standard and is considered secure against both classical and quantum attacks. Integrating Dilithium into the VTS scheme is more challenging problem due to its complex mathematical operations (i.e.
polynomial multiplications, rounding operations) and large module parameters such as polynomials, polynomial vectors, and matrices. This work aims to provide a comprehensive exposition of the VT-Dilithium scheme.



## 2024/1263

* Title: A Security Analysis of Two Classes of RSA-like Cryptosystems
* Authors: Paul Cotan, George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/1263)
* [Download](https://eprint.iacr.org/2024/1263.pdf)

### Abstract

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2002, Elkamchouchi, Elshenawy and Shaban introduced an RSA-like cryptosystem that uses the key equation $ed - k (p^2-1)(q^2-1) = 1$, instead of the classical RSA key equation $ed - k
(p-1)(q-1) = 1$. Another variant of RSA, presented in 2017 by Murru and Saettone, uses the key equation $ed - k (p^2+p+1)(q^2+q+1) = 1$.
Despite the authors' claims of enhanced security, both schemes remain vulnerable to adaptations of common RSA attacks. Let $n$ be an integer. This paper proposes two families of RSA-like encryption schemes: one employs the key equation $ed - k (p^n-1)
(q^n-1) = 1$ for $n > 0$, while the other uses $ed - k [(p^n-1)(q^n-1)]/[(p-1)(q-1)] = 1$ for $n > 1$. Note that we remove the conventional assumption of primes having equal bit sizes. In this scenario, we show that regardless of the choice of $n$,
continued fraction-based attacks can still recover the secret exponent. Additionally, this work fills a gap in the literature by establishing an equivalent of Wiener's attack when the primes do not have the same bit size.



## 2024/1264

* Title: Succinct Non-Subsequence Arguments
* Authors: San Ling, Khai Hanh Tang, Khu Vu, Huaxiong Wang, Yingfei Yan
* [Permalink](https://eprint.iacr.org/2024/1264)
* [Download](https://eprint.iacr.org/2024/1264.pdf)

### Abstract

Lookup arguments have recently attracted a lot of developments due to their applications in the constructions of succinct non-interactive arguments of knowledge (SNARKs). A closely related topic is subsequence arguments in which one can prove that string
$\mathbf{s}$ is a subsequence of another string $\mathbf{t}$, i.e., deleting some characters in $\mathbf{t}$ can achieve $\mathbf{s}$. A dual notion, namely, non-subsequence arguments, is to prove that $\mathbf{s}$ is not a subsequence of $\mathbf{t}$.
These problems have a lot of important applications in DNA sequence analysis, internet of things, blockchains, natural language processing, speech recognition, etc. However, despite their applications, they are not well-studied in cryptography,
especially succinct arguments for non-subsequences with efficient proving time and sublinear verification time.

In this work, we propose the first succinct non-subsequence argument. Our solution applies the sumcheck protocol and is instantiable by any multivariate polynomial commitment schemes (PCSs). We achieve an efficient prover whose running time is linear in
the size of sequences $\mathbf{s}$, $\mathbf{t}$ and their respective alphabet $\Sigma$. Our proof is succinct and the verifier time is sublinear assuming the employed PCS has succinct commitments and sublinear verification time. When instantiating with
Sona PCS (EUROCRYPT'24), we achieve proof size $\mathcal{O}(\log_2|\mathbf{s}| + \log_2|\mathbf{t}|+\log_2|\Sigma|)$, prover time $\mathcal{O}(|\mathbf{s}|+|\mathbf{t}|+|\Sigma|)$ and verifier time $\mathcal{O}(\sqrt{|\mathbf{s}|}+\sqrt{|\mathbf{t}|}+\
sqrt{|\Sigma|})$.

Extending our technique, we can achieve a batch subsequence argument for proving in batch $k$ interleaving subsequence and non-subsequence arguments without proof size suffering a linear blow-up in $k$.



## 2024/1265

* Title: Safe curves for elliptic-curve cryptography
* Authors: Daniel J. Bernstein, Tanja Lange
* [Permalink](https://eprint.iacr.org/2024/1265)
* [Download](https://eprint.iacr.org/2024/1265.pdf)

### Abstract

This paper surveys interactions between choices of elliptic curves and the security of elliptic-curve cryptography. Attacks considered include not just discrete-logarithm computations but also attacks exploiting common implementation pitfalls.



## 2024/1266

* Title: Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond
* Authors: D'or Banoun, Elette Boyle, Ran Cohen
* [Permalink](https://eprint.iacr.org/2024/1266)
* [Download](https://eprint.iacr.org/2024/1266.pdf)

### Abstract

Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the network topology from within a given class of graphs. Although broadcast is a privacy-free task, it is known that THB for
certain graph classes necessitates computational assumptions, even against "honest but curious" adversaries, and even given a single corrupted party. Recent works have tried to understand when THB can be obtained with information-theoretic (IT) security (
without cryptography or setup assumptions) as a function of properties of the corresponding graph class.

We revisit this question through a case study of the class of wheel graphs and their subgraphs. The $n$'th wheel graph is established by connecting $n$ nodes who form a cycle with another "center" node, thus providing a natural extension that captures
and enriches previously studied graph classes in the setting of IT-THB.

We present a series of new findings in this line.
We fully characterize feasibility of IT-THB for any class of subgraphs of the wheel, each possessing an embedded star (i.e., a well-defined center connected to all other nodes). Our characterization provides evidence that IT-THB feasibility may correlate
with a more fine-grained degree structure---as opposed to pure connectivity---of the corresponding graphs.
We provide positive results achieving perfect IT-THB for new graph classes, including ones where the number of nodes is unknown. Further, we provide the first feasibility of IT-THB on non-degenerate graph-classes with $t>1$ corruptions, for the class of
friendship graphs (Erdos, Renyi, Sos '66).

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