[continued from previous message]

* Title: Proof of Time: A Method for Verifiable Temporal Commitments Without Timestamp Disclosure
* Authors: Alexander John Lee
* [Permalink](https://eprint.iacr.org/2024/1963)
* [Download](https://eprint.iacr.org/2024/1963.pdf)

### Abstract

This paper introduces a cryptographic method that enables users to prove that an event occurred in the past and that a specified amount of time has since elapsed, without disclosing the exact timestamp of the event. The method leverages zero-knowledge
proofs and an on-chain Incremental Merkle Tree to store hash commitments. By utilizing the Poseidon hash function and implementing zero-knowledge circuits in Noir, this approach ensures both the integrity and confidentiality of temporal information.



## 2024/1964

* Title: Lova: Lattice-Based Folding Scheme from Unstructured Lattices
* Authors: Giacomo Fenzi, Christian Knabenhans, Ngoc Khanh Nguyen, Duc Tu Pham * [Permalink](https://eprint.iacr.org/2024/1964)
* [Download](https://eprint.iacr.org/2024/1964.pdf)

### Abstract

Folding schemes (Kothapalli et al., CRYPTO 2022) are a conceptually simple, yet powerful cryptographic primitive that can be used as a building block to realise incrementally verifiable computation (IVC) with low recursive overhead without general-
purpose non-interactive succinct arguments of knowledge (SNARK).
Most folding schemes known rely on the hardness of the discrete logarithm problem, and thus are both not quantum-resistant and operate over large prime fields. Existing post-quantum folding schemes (Boneh, Chen, ePrint 2024/257) based on lattice
assumptions instead are secure under structured lattice assumptions, such as the Module Short Integer Solution Assumption (MSIS), which also binds them to relatively complex arithmetic.
In contrast, we construct Lova, the first folding scheme whose security relies on the (unstructured) SIS assumption. We provide a Rust implementation of Lova, which makes only use of arithmetic in hardware-friendly power-of-two moduli. Crucially, this
avoids the need of implementing and performing any finite field arithmetic. At the core of our results lies a new exact Euclidean norm proof which might be of independent interest.



## 2024/1965

* Title: Onion Franking: Abuse Reports for Mix-Based Private Messaging
* Authors: Matthew Gregoire, Margaret Pierce, Saba Eskandarian
* [Permalink](https://eprint.iacr.org/2024/1965)
* [Download](https://eprint.iacr.org/2024/1965.pdf)

### Abstract

The fast-paced development and deployment of private messaging applications demands mechanisms to protect against the concomitant potential for abuse. While widely used end-to-end encrypted (E2EE) messaging systems have deployed mechanisms for users to
verifiably report abusive messages without compromising the privacy of unreported messages, abuse reporting schemes for systems that additionally protect message metadata are still in their infancy. Existing solutions either focus on a relatively small
portion of the design space or incur much higher communication and computation costs than their E2EE brethren.

This paper introduces new abuse reporting mechanisms that work for any private messaging system based on onion encryption. This includes low-latency systems that employ heuristic or opportunistic mixing of user traffic, as well as schemes based on
mixnets. Along the way, we show that design decisions and abstractions that are well-suited to the E2EE setting may actually impede security and performance improvements in the metadata-hiding setting. We also explore stronger threat models for abuse
reporting and moderation not explored in prior work, showing where prior work falls short and how to strengthen both our scheme and others' -- including deployed E2EE messaging platforms -- to achieve higher levels of security.

We implement a prototype of our scheme and find that it outperforms the best known solutions in this setting by well over an order of magnitude for each step of the message delivery and reporting process, with overheads almost matching those of message
franking techniques used by E2EE encrypted messaging apps today.



## 2024/1966

* Title: Efficient Succinct Zero-Knowledge Arguments in the CL Framework
* Authors: Agathe Beaugrand, Guilhem Castagnos, Fabien Laguillaumie
* [Permalink](https://eprint.iacr.org/2024/1966)
* [Download](https://eprint.iacr.org/2024/1966.pdf)

### Abstract

The CL cryptosystem, introduced by Castagnos and Laguillaumie in 2015, is a linearly homomorphic encryption scheme that has seen numerous developments and applications in recent years, particularly in the field of secure multiparty computation. Designing
efficient zero-knowledge proofs for the CL framework is critical, especially for achieving adaptive security for such multiparty protocols. This is a challenging task due to the particularities of class groups of quadratic fields used to instantiate the
groups of unknown order required in the CL framework.

In this work, we provide efficient proofs and arguments for statements involving a large number of ciphertexts. We propose a new batched proof for correctness of CL ciphertexts and new succinct arguments for correctness of a shuffle of these ciphertexts.
Previous efficient proofs of shuffle for linearly homomorphic encryption were designed for Elgamal “in the exponent” which has only a limited homomorphic property. In the line of a recent work by Braun, Damgard and Orlandi (CRYPTO 2023), all the new
proofs and arguments provide partial extractability, a property that we formally introduce here. Thanks to this notion, we show that bulletproof techniques, which are in general implemented with groups of known prime order, can be applied in the CL
framework despite the use of unknown order groups, giving non interactive arguments of logarithmic sizes.

To prove the practicability of our approach we have implemented these protocols with the BICYCL library, showing that computation and communication costs are competitive. We also illustrate that the partial extractability of our proofs provide enough
guarantees for complex applications by presenting a bipartite private set intersection sum protocol which achieves security against malicious adversaries using CL encryption, removing limitations of a solution proposed by Miao et al. (CRYPTO 2020).



## 2024/1967

* Title: Analysis of REDOG: The Pad Thai Attack
* Authors: Alex Pellegrini, Marc Vorstermans
* [Permalink](https://eprint.iacr.org/2024/1967)
* [Download](https://eprint.iacr.org/2024/1967.pdf)

### Abstract

This paper introduces the Pad Thai message recovery attack
on REDOG, a rank-metric code-based encryption scheme selected for the
second round of evaluation in the Korean Post-Quantum Cryptography
(KPQC) competition. The attack exploits the low rank weight of a portion of the ciphertext to construct multiple systems of linear equations,
one of which is noise-free and can be solved to recover the secret message.
The Pad Thai attack significantly undermines the security of REDOG,
revealing that its provided security is much lower than originally claimed.



## 2024/1968

* Title: SoK: Pseudorandom Generation for Masked Cryptographic Implementation
* Authors: Rei Ueno, Naofumi Homma, Akiko Inoue, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2024/1968)
* [Download](https://eprint.iacr.org/2024/1968.pdf)

### Abstract

This paper investigates pseudorandom generation in the context of masked cryptographic implementation. Although masking and pseudorandom generators (PRGs) have been distinctly studied for a long time, little literature studies how the randomness in the
masked implementation should be generated. The lack of analysis on mask-bits generators makes the practical security of masked cryptographic implementation unclear, and practitioners (e.g., designer, implementer, and evaluator) may be confused about how
to realize it. This paper provides a novel viewpoint and comprehensive analyses by developing new three models, which correspond to respective practical scenarios of leakage assessment, quantitative evaluation of side-channel security (e.g., success rate)
, and practical deployment. We reveal what properties are required for each scenario. In particular, we support a long-held belief/folklore with a proof: for the output of PRG for masking, cryptographic security (i.e., randomness and unpredictability) is
sufficient but not necessary, but only a statistical uniformity is necessary. In addition, we thoroughly investigate the SCA security of PRGs in the wild in the masking context. We conclude this paper with some recommendations for practitioners, with a
proposal of leakage-resilient method of comparative performance.



## 2024/1969

* Title: SoK: Security of the Ascon Modes
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/1969)
* [Download](https://eprint.iacr.org/2024/1969.pdf)

### Abstract

The Ascon authenticated encryption scheme and hash function of Dobraunig et al (Journal of Cryptology 2021) were recently selected as winner of the NIST lightweight cryptography competition. The mode underlying Ascon authenticated encryption (Ascon-AE)
resembles ideas of SpongeWrap, but not quite, and various works have investigated the generic security of Ascon-AE, all covering different attack scenarios and with different bounds. This work systemizes knowledge on the mode security of Ascon-AE, and
fills gaps where needed. We consider six mainstream security models, all in the multi-user setting: (i) nonce-respecting security, reflecting on the existing bounds of Chakraborty et al (ASIACRYPT 2023, ACISP 2024) and Lefevre and Mennink (SAC 2024), (ii)
nonce-misuse resistance, observing a non-fixable flaw in the proof of Chakraborty et al (ACISP 2024), (iii) nonce-misuse resilience, delivering missing security analysis, (iv) leakage resilience, delivering a new security analysis that supersedes the
informal proof sketch (though in a different model) of Guo et al (ToSC 2020), (v) state-recovery security, expanding on the analysis of Lefevre and Mennink, and (vi) release of unverified plaintext, also delivering missing security analysis. We also
match all bounds with tight attacks. As a bonus, we systemize the knowledge on Ascon-Hash and Ascon-PRF (but there are no technical novelties here).



## 2024/1970

* Title: Scribe: Low-memory SNARKs via Read-Write Streaming
* Authors: Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Karan Newatia, Steve Wang
* [Permalink](https://eprint.iacr.org/2024/1970)
* [Download](https://eprint.iacr.org/2024/1970.pdf)

### Abstract

Succinct non-interactive arguments of knowledge (SNARKs) enable a prover to produce a short and efficiently verifiable proof of the validity of an arbitrary NP statement. Recent constructions of efficient SNARKs have led to interest in using them for a
wide range of applications, but unfortunately, deployment of SNARKs in these applications faces a key bottleneck: SNARK provers require a prohibitive amount of time and memory to generate proofs for even moderately large statements. While there has been
progress in reducing prover time, prover memory remains an issue.

In this work, we describe Scribe, a new low-memory SNARK that can efficiently prove large statements even on cheap consumer devices such as smartphones by leveraging a plentiful, but heretofore unutilized, resource: disk storage. In more detail, instead
of storing its (large) intermediate state in RAM, Scribe's prover instead stores it on disk. To ensure that accesses to state are efficient, we design Scribe's prover in a *read-write streaming* model of computation that allows the prover to read and
modify its state only in a streaming manner.

We implement and evaluate Scribe's prover, and show that, on commodity hardware, it can easily scale to circuits of size $2^{28}$ gates while using only 2GB of memory and incurring only minimal proving latency overhead (10-35%) compared to a state-of-the-
art memory-intensive baseline (HyperPlonk [EUROCRYPT 2023]) that requires much more memory. Our implementation minimizes overhead by leveraging the streaming access pattern to enable several systems optimizations that together mask I/O costs.



## 2024/1971

* Title: Further Connections Between Isogenies of Supersingular Curves and Bruhat-Tits Trees
* Authors: Steven Galbraith, Valerie Gilchrist, Shai Levin, Ari Markowitz
* [Permalink](https://eprint.iacr.org/2024/1971)
* [Download](https://eprint.iacr.org/2024/1971.pdf)

### Abstract

We further explore the explicit connections between supersingular curve isogenies and Bruhat-Tits trees. By identifying a supersingular elliptic curve $E$ over $\mathbb{F}_p$ as the root of the tree, and a basis for the Tate module $T_\ell(E)$; our main
result is that given a vertex $M$ of the Bruhat-Tits tree one can write down a generator of the ideal $I \subseteq \text{End}(E)$ directly, using simple linear algebra, that defines an isogeny corresponding to the path in the Bruhat-Tits tree from the
root to the vertex $M$. In contrast to previous methods to go from a vertex in the Bruhat-Tits tree to an ideal, once a basis for the Tate module is set up and an explicit map $\Phi : \text{End}(E) \otimes_{\mathbb{Z}_\ell} \to M_2( \mathbb{Z}_\ell )$ is
constructed, our method does not require any computations involving elliptic curves, isogenies, or discrete logs. This idea leads to simplifications and potential speedups to algorithms for converting between isogenies and ideals.



## 2024/1972

* Title: RoK, Paper, SISsors – Toolkit for Lattice-based Succinct Arguments
* Authors: Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, Michał Osadnik
* [Permalink](https://eprint.iacr.org/2024/1972)
* [Download](https://eprint.iacr.org/2024/1972.pdf)

### Abstract

Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as $f(\vec{s}) = \vec{t} \bmod q$ and $\|\vec{s}\|\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the
witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques
often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments:

(i) We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds.
(ii) We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits
polynomial-size subtractive sets.
(iii) We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathbb{Z}$-inner-products as $\mathcal{R}$-inner-products for some
structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a square-free odd part.
(iv) We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth
conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations.

Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that $\vec{s}$ satisfying $f(\vec{s}) = \vec{t} \bmod q$ has binary coefficients, without soundness gap and with polynomial-size modulus $q$.

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