[continued from previous message]

As a corollary, we provide a folding scheme for any relation R for which there is a reduction of knowledge (RoK) from $\mathcal{R}$ to one or more instance-witness pairs in the zero-check relation. Such RoKs appear implicitly in prior lookup arguments (e.
g., Lasso) and high-performance zkVMs for RISC-V (e.g., Jolt). We formalize these RoKs for several relations including indexed lookups, grand products, and CCS (which generalizes Plonkish, AIR, and R1CS). These are simple and constant round RoKs that
leverage interaction to perform randomized checks on committed witness elements. Instead of proving these resulting zero-check instances as is done in prior proof systems such as Jolt, NeutronNova provides the more efficient option of continual folding
of zero-check instances into a single running instance.



## 2024/1607

* Title: Tighter Proofs for PKE-to-KEM Transformation in the Quantum Random Oracle Model
* Authors: Jinrong Chen, Yi Wang, Rongmao Chen, Xinyi Huang, Wei Peng
* [Permalink](https://eprint.iacr.org/2024/1607)
* [Download](https://eprint.iacr.org/2024/1607.pdf)

### Abstract

In this work, we provide new, tighter proofs for the $T_{RH}$-transformation by Jiang et al. (ASIACRYPT 2023), which converts OW-CPA secure PKEs into KEMs with IND-1CCA security, a variant of typical IND-CCA security where only a single decapsulation
query is allowed. Such KEMs are efficient and have been shown sufficient for real-world applications by Huguenin-Dumittan and Vaudenay at EUROCRYPT 2022. We reprove Jiang et al.'s $T_{RH}$-transformation in both the random oracle model (ROM) and the
quantum random oracle model (QROM), for the case where the underlying PKE is rigid deterministic. In both ROM and QROM models, our reductions achieve security loss factors of $\mathcal{O}(1)$, significantly improving Jiang et al.'s results which have
security loss factors of $\mathcal{O}(q)$ in the ROM and $\mathcal{O}(q^2)$ in the QROM respectively. Notably, central to our tight QROM reduction is a new tool called ''reprogram-after-measure'', which overcomes the reduction loss posed by oracle
reprogramming in QROM proofs. This technique may be of independent interest and useful for achieving tight QROM proofs for other post-quantum cryptographic schemes. We remark that our results also improve the reduction tightness of the $T_{H}$-
transformation (which also converts PKEs to KEMs) by Huguenin-Dumittan and Vaudenay (EUROCRYPT 2022), as Jiang et al. provided a tight reduction from $T_H$-transformation to $T_{RH}$-transformation (ASIACRYPT 2023).



## 2024/1608

* Title: Mild Asymmetric Message Franking: Illegal-Messages-Only and Retrospective Content Moderation
* Authors: Zhengan Huang, Junzuo Lai, Gongxian Zeng, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1608)
* [Download](https://eprint.iacr.org/2024/1608.pdf)

### Abstract

Many messaging platforms have integrated end-to-end (E2E) encryption into their services. This widespread adoption of E2E encryption has triggered a technical tension between user privacy and illegal content moderation. The existing solutions either
support only unframeability or deniability, or they are prone to abuse (the moderator can perform content moderation for all messages, whether illegal or not), or they lack mechanisms for retrospective content moderation.

To address the above issues, we introduce a new primitive called \emph{mild asymmetric message franking} (MAMF) to establish illegal-messages-only and retrospective content moderation for messaging systems, supporting unframeability and deniability
simultaneously. We provide a framework to construct MAMF, leveraging two new building blocks, which might be of independent interest.



## 2024/1609

* Title: Blaze: Fast SNARKs from Interleaved RAA Codes
* Authors: Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D. Rothblum, Hadas Zeilberger
* [Permalink](https://eprint.iacr.org/2024/1609)
* [Download](https://eprint.iacr.org/2024/1609.pdf)

### Abstract

In this work we construct a new and highly efficient multilinear polynomial commitment scheme (MLPCS) over binary fields, which we call \emph{Blaze}. Polynomial commitment schemes allow a server to commit to a large polynomial and later decommit to
its evaluations. Such schemes have emerged as a key component in recent efficient SNARK constructions.

Blaze has an extremely efficient prover, both asymptotically and concretely. The commitment is dominated by $8n$ field additions (i.e., XORs) and one Merkle tree computation. The evaluation proof generation is dominated by $6n$ additions and $5n$
multiplications over the field. The verifier runs in time $O_\lambda(\log^2(n))$. Concretely, for sufficiently large message sizes, the prover is faster than all prior schemes except for Brakedown (Golovnev et al., Crypto 2023), but offers significantly
smaller proofs than the latter.

The scheme is obtained by combining two ingredients:

1. Building on the code-switching technique (Ron-Zewi and Rothblum, JACM 2024), we show how to compose any error-correcting code together with an interactive oracle proof of proximity (IOPP) underlying existing MLPCS constructions, into a new MLPCS. The
new MLPCS inherits its proving time from the code's encoding time, and its verification complexity from the underlying MLPCS. The composition is distinctive in that it is done purely on the information-theoretic side.

2. We apply the above methodology using an extremely efficient error-correcting code known as the Repeat-Accumulate-Accumulate (RAA) code. We give new asymptotic and concrete bounds, which demonstrate that (for sufficiently large message sizes) this code
has a better encoding time vs. distance tradeoff than previous linear-time encodable codes that were considered in the literature.



## 2024/1610

* Title: Secret Sharing with Snitching
* Authors: Stefan Dziembowski, Sebastian Faust, Tomasz Lizurej, Marcin Mielniczuk
* [Permalink](https://eprint.iacr.org/2024/1610)
* [Download](https://eprint.iacr.org/2024/1610.pdf)

### Abstract

We address the problem of detecting and punishing shareholder collusion in secret-sharing schemes. We do it in the recently proposed cryptographic model called individual cryptography (Dziembowski, Faust, and Lizurej, Crypto 2023), which assumes that
there exist tasks that can be efficiently computed by a single machine but distributing this computation across multiple (mutually distrustful devices) is infeasible.

Within this model, we introduce a novel primitive called secret sharing with snitching (SSS), in which each attempt to illegally reconstruct the shared secret $S$ results in a proof that can be used to prove such misbehavior (and, e.g., financially
penalize the cheater on a blockchain). This holds in a very strong sense, even if the shareholders attempt not to reconstruct the entire secret~$S$ but only learn some partial information about it. Our notion also captures the attacks performed using
multiparty computation protocols (MPCs), i.e., those where the malicious shareholders use MPCs to compute partial information on $S$. The main idea of SSS is that any illegal reconstruction can be proven and punished, which suffices to discourage illegal
secret reconstruction. Hence, our SSS scheme effectively prevents shareholders' collusion. We provide a basic definition of threshold ($t$-out-of-$n$) SSS. We then show how to construct it for $t = n$, and later, we use this construction to build an SSS
scheme for an arbitrary $t$.

In order to prove the security of our construction, we introduce a generalization of the random oracle model (Bellare, Rogaway, CCS 1993), which allows modelling hash evaluations made inside MPC.



## 2024/1611

* Title: Rhombus: Fast Homomorphic Matrix-Vector Multiplication for Secure Two-Party Inference
* Authors: Jiaxing He, Kang Yang, Guofeng Tang, Zhangjie Huang, Li Lin, Changzheng Wei, Ying Yan, Wei Wang
* [Permalink](https://eprint.iacr.org/2024/1611)
* [Download](https://eprint.iacr.org/2024/1611.pdf)

### Abstract

We present $\textit{Rhombus}$, a new secure matrix-vector multiplication (MVM) protocol in the semi-honest two-party setting, which is able to be seamlessly integrated into existing privacy-preserving machine learning (PPML) frameworks and serve as the
basis of secure computation in linear layers.
$\textit{Rhombus}$ adopts RLWE-based homomorphic encryption (HE) with coefficient encoding, which allows messages to be chosen from not only a field $\mathbb{F}_p$ but also a ring $\mathbb{Z}_{2^\ell}$, where the latter supports faster computation in non-
linear layers. To achieve better efficiency, we develop an input-output packing technique that reduces the communication cost incurred by HE with coefficient encoding by about $21\times$, and propose a split-point picking technique that reduces the
number of rotations to that sublinear in the matrix dimension. Compared to the recent protocol $\textit{HELiKs}$ by Balla and Koushanfar (CCS'23), our implementation demonstrates that $\textit{Rhombus}$ improves the whole performance of an MVM protocol
by a factor of $7.4\times \sim 8\times$, and improves the end-to-end performance of secure two-party inference of ResNet50 by a factor of $4.6\times \sim 18\times$.



## 2024/1612

* Title: On Wagner's k-Tree Algorithm Over Integers
* Authors: Haoxing Lin, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/1612)
* [Download](https://eprint.iacr.org/2024/1612.pdf)

### Abstract

The $k$-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case $k$-SUM problem that has found widespread use in cryptanalysis. Its input consists of $k$ lists, each containing $n$ integers from a range of size $m$. Wagner's original
heuristic analysis suggested that this algorithm succeeds with constant probability if $n \approx m^{1/(\log{k}+1)}$, and that in this case it runs in time $O(kn)$. Subsequent rigorous analysis of the algorithm [Lyubashevsky 05, Shallue 08, Joux-Kippen-
Loss 24] has shown that it succeeds with high probability if the input list sizes are significantly larger than this.

We present a broader rigorous analysis of the $k$-Tree algorithm, showing upper and lower bounds on its success probability and complexity for any size of the input lists. Our results confirm Wagner's heuristic conclusions, and also give meaningful
bounds for a wide range of list sizes that are not covered by existing analyses. We present analytical bounds that are asymptotically tight, as well as an efficient algorithm that computes (provably correct) bounds for a wide range of concrete parameter
settings. We also do the same for the $k$-Tree algorithm over $\mathbb{Z}_m$. Finally, we present experimental evaluation of the tightness of our results.



## 2024/1613

* Title: Efficient Maliciously Secure Oblivious Exponentiations
* Authors: Carsten Baum, Jens Berlips, Walther Chen, Ivan Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin
Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1613)
* [Download](https://eprint.iacr.org/2024/1613.pdf)

### Abstract

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither
learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman
assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance.

Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor $o(1)
$ as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments.

Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does
not rely on the OEP but nevertheless only has overhead $o(1)$ over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against
malicious attackers.



## 2024/1614

* Title: Related-Key Cryptanalysis of FUTURE
* Authors: Amit Jana, Smita Das, Ayantika Chatterjee, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1614)
* [Download](https://eprint.iacr.org/2024/1614.pdf)

### Abstract

In Africacrypt 2022, Gupta \etal introduced a 64-bit lightweight \mds matrix-based \spn-like block cipher designed to encrypt data in a single clock cycle with minimal implementation cost, particularly when unrolled. While various attack models were
discussed, the security of the cipher in the related-key setting was not addressed. In this work, we bridge this gap by conducting a security analysis of the cipher under related-key attacks using \milp(Mixed Integer Linear Programming)-based techniques.
Our model enables a related-key distinguishing attack on 8 rounds of FUTURE, requiring $2^{64}$ plaintexts, $2^{63}$ \xor operations, and negligible memory. Additionally, we present a 10-round boomerang distinguisher with a probability of $2^{-45}$,
leading to a distinguishing attack with $2^{46}$ plaintexts, $2^{46}$ \xor operations, and negligible memory. This result demonstrates a full break of the cipher’s 64-bit security in the related-key setting.



## 2024/1615

* Title: LeOPaRd: Towards Practical Post-Quantum Oblivious PRFs via Interactive Lattice Problems
* Authors: Muhammed F. Esgin, Ron Steinfeld, Erkan Tairi, Jie Xu
* [Permalink](https://eprint.iacr.org/2024/1615)
* [Download](https://eprint.iacr.org/2024/1615.pdf)

### Abstract

In this work, we introduce a more efficient post-quantum oblivious PRF (OPRF) design, called LeOPaRd. Our proposal is round-optimal and supports verifiability and partial obliviousness, all of which are important for practical applications. The main
technical novelty of our work is a new method for computing samples of MLWE (module learning with errors) in a two-party setting. To do this, we introduce a new family of interactive lattice problems, called interactive MLWE and rounding with re-use (
iMLWER-RU). We rigorously study the hardness of iMLWER-RU and reduce it (under some natural idealized setting) to a more standard MLWE-like problem where the adversary is additionally given access to a randomized MLWE PRF oracle. We believe iMLWER-RU can
be of independent interest for other interactive protocols.

LeOPaRd exploits this new iMLWER-RU assumption to realize a lattice-based OPRF design without relying on heavy machinery such as noise flooding and fully homomorphic encryption used in earlier works. LeOPaRd can feature around 136 KB total communication,
compared to 300+ KB in earlier works. We also identify gaps in some existing constructions and models, and propose appropriate fixes.



## 2024/1616

* Title: End-to-End Encrypted Cloud Storage in the Wild: A Broken Ecosystem
* Authors: Jonas Hofmann, Kien Tuong Truong
* [Permalink](https://eprint.iacr.org/2024/1616)
* [Download](https://eprint.iacr.org/2024/1616.pdf)

### Abstract

End-to-end encrypted cloud storage offers a way for individuals and organisations to delegate their storage needs to a third-party, while keeping control of their data using cryptographic techniques.
We conduct a cryptographic analysis of various products in the ecosystem, showing that many providers fail to provide an adequate level of security. In particular, we provide an in-depth analysis of five end-to-end encrypted cloud storage systems, namely
Sync, pCloud, Icedrive, Seafile, and Tresorit, in the setting of a malicious server. These companies cumulatively have over 22 million users and are major providers in the field. We unveil severe cryptographic vulnerabilities in four of them. Our attacks
invalidate the marketing claims made by the providers of these systems, showing that a malicious server can, in some cases, inject files in the encrypted storage of users, tamper with file data, and even gain direct access to the content of the files.
Many of our attacks affect multiple providers in the same way, revealing common failure patterns in independent cryptographic designs.
We conclude by discussing the significance of these patterns beyond the security of the specific providers.



## 2024/1617

* Title: Algebraic Equipage for Learning with Errors in Cyclic Division Algebras
* Authors: Cong Ling, Andrew Mendelsohn
* [Permalink](https://eprint.iacr.org/2024/1617)
* [Download](https://eprint.iacr.org/2024/1617.pdf)

### Abstract

In Noncommutative Ring Learning With Errors From Cyclic Algebras, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE', was developed, and security reductions similar to those known for the ring and module case were
given, as well as a Regev-style encryption scheme. In this work, we make a number of improvements to that work: namely, we describe methods to increase the number of cryptographically useful division algebras, demonstrate the hardness of CLWE from ideal
lattices obtained from non-maximal orders, and study Learning with Rounding in cyclic division algebras.



## 2024/1618

* Title: Shaking up authenticated encryption
* Authors: Joan Daemen, Seth Hoffert, Silvia Mella, Gilles Van Assche, Ronny Van Keer
* [Permalink](https://eprint.iacr.org/2024/1618)
* [Download](https://eprint.iacr.org/2024/1618.pdf)

### Abstract

Authenticated encryption (AE) is a cryptographic mechanism that allows communicating parties to protect the confidentiality and integrity of messages exchanged over a public channel, provided they share a secret key. In this work, we present new AE
schemes leveraging the SHA-3 standard functions SHAKE128 and SHAKE256, offering 128 and 256 bits of security strength, respectively, and their “Turbo” counterparts. They support session-based communication, where a ciphertext authenticates the
sequence of messages since the start of the session. The chaining in the session allows decryption in segments, avoiding the need to buffer the entire deciphered cryptogram between decryption and validation. And, thanks to the collision resistance of (
Turbo)SHAKE, they provide so-called CMT-4 committing security, meaning that they provide strong guarantees that a ciphertext uniquely binds to the key, plaintext and associated data. The AE schemes we propose have the unique combination of advantages
that 1) their security is based on the security claim of SHAKE, that has received a large amount of public scrutiny, that 2) they make use of the standard KECCAK-p permutation that not only receives more and more dedicated hardware support, but also
allows
competitive software-only implementations thanks to the TurboSHAKE instances, and that 3) they do not suffer from a 64-bit birthday bound like most AES-based schemes.



## 2024/1619

* Title: Structure-Preserving Compressing Primitives: Vector Commitments, Accumulators and Applications
* Authors: Stephan Krenn, Omid Mir, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2024/1619)
* [Download](https://eprint.iacr.org/2024/1619.pdf)

### Abstract

Compressing primitives such as accumulators and vector commitments, allow to rep- resent large data sets with some compact, ideally constant-sized value. Moreover, they support operations like proving membership or non-membership with minimal, ideally
also constant- sized, storage and communication overhead. In recent years, these primitives have found nu- merous practical applications, with many constructions based on various hardness assumptions. So far, however, it has been elusive to construct
these primitives in a strictly structure-preserving setting, i.e., in a bilinear group in a way that messages, commitments and openings are all ele- ments of the two source groups. Interestingly, backed by existing impossibility results, not even
conventional commitments with such constraints are known in this setting.

In this paper we investigate whether strictly structure-preserving compressing primitives can be realized. We close this gap by presenting the first strictly structure-preserving commitment that is shrinking (and in particular constant-size). We
circumvent existing impossibility results by employing a more structured message space, i.e., a variant of the Diffie-Hellman message space. Our main results are constructions of structure-preserving vector commitments (SPVC) as well as accumulators. We
first discuss generic constructions and then present concrete con- structions under the Diffie-Hellman Exponent assumption. To demonstrate the usefulness of our constructions, we present various applications. Most notable, we present the first entirely
prac- tical constant-size ring signature scheme in bilinear groups (i.e., the discrete logarithm setting). Concretely, using the popular BLS12-381 pairing-friendly curve, our ring signatures achieve a size of roughly 6500 bits.



## 2024/1620

* Title: Really Complex Codes with Application to STARKs
* Authors: Yuval Domb
* [Permalink](https://eprint.iacr.org/2024/1620)
* [Download](https://eprint.iacr.org/2024/1620.pdf)

### Abstract

Reed-Solomon (RS) codes [RS60], representing evaluations of univariate polynomials over distinct domains, are foundational in error correction and cryptographic protocols. Traditional RS codes leverage the Fourier domain for efficient encoding and
decoding via Fast Fourier Transforms (FFT). However, in fields such as the Reals and some finite prime fields, limited root-of-unity orders restrict these methods. Recent research, particularly in the context of modern STARKs [BSBHR18b], has explored the
Complex Fourier domain for constructing Real-valued RS codes, introducing novel transforms such as the Discrete Circle-Curve Transform (DCCT) for Real-to-Real transformations [HLP24]. Despite their efficiency, these transforms face limitations with high
radix techniques and potentially other legacy know-hows. In this paper, we propose a construction of Real-valued RS codes utilizing the Discrete Fourier Transform (DFT) over the Complex domain. This approach leverages well-established algebraic and
Fourier properties to achieve efficiency comparable to DCCT, while retaining compatibility with legacy techniques and optimizations.



## 2024/1621

* Title: PAKE Combiners and Efficient Post-Quantum Instantiations
* Authors: Julia Hesse, Michael Rosenberg
* [Permalink](https://eprint.iacr.org/2024/1621)
* [Download](https://eprint.iacr.org/2024/1621.pdf)

### Abstract

Much work has been done recently on developing password-authenticated key exchange (PAKE) mechanisms with post-quantum security. However, modern guidance recommends the use of hybrid schemes—schemes which rely on the combined hardness of a post-quantum
assumption, e.g., learning with Errors (LWE), and a more traditional assumption, e.g., decisional Diffie-Hellman. To date, there is no known hybrid PAKE construction, let alone a general method for achieving such.

In this paper, we present two efficient PAKE combiners—algorithms that take two PAKEs satisfying mild assumptions, and output a third PAKE with combined security properties—and prove these combiners secure in the Universal Composability (UC) model.
Our sequential combiner, instantiated with efficient existing PAKEs such as CPace (built on Diffie-Hellman-type assumptions) and CHIC[ML-KEM] (built on the Module LWE assumption), yields the first known hybrid PAKE.



## 2024/1622

* Title: A New Approach Towards Encrypted Data Sharing and Computation: Enhancing Efficiency Beyond MPC and Multi-Key FHE
* Authors: Anil Kumar Pradhan
* [Permalink](https://eprint.iacr.org/2024/1622)
* [Download](https://eprint.iacr.org/2024/1622.pdf)

### Abstract

In this paper, we introduce a novel approach to Multi-Key Fully Homomorphic Encryption (MK-FHE) that enhances both efficiency and security beyond the capabilities of traditional MK-FHE and MultiParty Computation (MPC) systems. Our method generates a
unified key structure, enabling constant ciphertext size and constant execution time for encrypted computations, regardless of the number of participants involved. This approach addresses critical limitations such as ciphertext size expansion, noise
accumulation, and the complexity of relinearization, which typically hinder scalability in multi-user environments. We also propose a new decryption method that simplifies decryption to a single information exchange, in contrast to traditional multi-key
FHE systems that require information to be passed between all parties sequentially.

Additionally, it significantly enhances the scalability of MK-FHE systems, allowing seamless integration of additional participants without introducing performance overhead. Through theoretical analysis and practical implementation, we demonstrate the
superiority of our approach in large-scale, collaborative encrypted computation scenarios, paving the way for more robust and efficient secure data processing frameworks. Further more, unlike the threshold based FHE schemes, the proposed system doesn’t
require a centralised trusted third party to split and distribute the individual secret keys, instead each participant independently generates their own secret key, ensuring both security and decentralization.



## 2024/1623

* Title: General Functional Bootstrapping using CKKS
* Authors: Andreea Alexandru, Andrey Kim, Yuriy Polyakov
* [Permalink](https://eprint.iacr.org/2024/1623)
* [Download](https://eprint.iacr.org/2024/1623.pdf)

### Abstract

The Ducas-Micciancio (DM/FHEW) and Chilotti-Gama-Georgieva-Izabachène (CGGI/TFHE) cryptosystems provide a general privacy-preserving computation capability. These fully homomorphic encryption (FHE) cryptosystems can evaluate an arbitrary function
expressed as a general look-up table (LUT) via the method of functional bootstrapping (also known as programmable bootstrapping). The main limitation of DM/CGGI functional bootstrapping is its efficiency because this procedure has to bootstrap every
encrypted number separately. A different bootstrapping approach, based on the Cheon-Kim-Kim-Song (CKKS) FHE scheme, can achieve much smaller amortized time due to its ability to bootstrap many thousands of numbers at once. However, CKKS does not
currently provide a functional bootstrapping capability that can evaluate a general LUT. An open research question is whether such capability can be efficiently constructed. We give a positive answer to this question by proposing and implementing a
general functional bootstrapping method based on CKKS-style bootstrapping. We devise a theoretical toolkit for evaluating an arbitrary function using the theory of trigonometric Hermite interpolations, which provides control over noise reduction during
functional bootstrapping. Our experimental results for 8-bit LUT evaluation show that the proposed method achieves the amortized time of 0.75 milliseconds, which is three orders of magnitude faster than the DM/CGGI approach and 6.6x faster than (a more
restrictive) amortized functional bootstrapping method based on the Brakerski/Fan-Vercauteren (BFV) FHE scheme.



## 2024/1624

* Title: Double-Matrix: Complete Diffusion in a Single Round with (small) MDS Matrices
* Authors: Jorge Nakahara Jr
* [Permalink](https://eprint.iacr.org/2024/1624)
* [Download](https://eprint.iacr.org/2024/1624.pdf)

### Abstract

This paper describes a simple idea to improve (text) diffusion in block ciphers that use MDS codes but that take more than
a single round to achieve full (text) diffusion. The Rijndael cipher family is used as an example since it comprises ciphers
with different state sizes.
A drawback of the new approach is the additional computational cost, but it is competitive compared to large MDS matrices
used in the Khazad and Kuznyechik ciphers.



## 2024/1625

* Title: On the Tight Security of the Double Ratchet
* Authors: Daniel Collins, Doreen Riepel, Si An Oliver Tran
* [Permalink](https://eprint.iacr.org/2024/1625)
* [Download](https://eprint.iacr.org/2024/1625.pdf)

### Abstract

The Signal Protocol is a two-party secure messaging protocol used in applications such as Signal, WhatsApp, Google Messages and Facebook Messenger and is used by billions daily. It consists of two core components, one of which is the Double Ratchet
protocol that has been the subject of a line of work that aims to understand and formalise exactly what security it provides. Existing models capture strong guarantees including resilience to state exposure in both forward security (protecting past
secrets) and post-compromise security (restoring security), adaptive state corruptions, message injections and out-of-order message delivery. Due to this complexity, prior work has failed to provide security guarantees that do not degrade in the number
of interactions, even in the single-session setting.

Given the ubiquity of the Double Ratchet in practice, we explore tight security bounds for the Double Ratchet in the multi-session setting. To this end, we revisit the modelling of Alwen, Coretti and Dodis (EUROCRYPT 2019) who decompose the protocol into
modular, abstract components, notably continuous key agreement (CKA) and forward-secure AEAD (FS-AEAD). To enable a tight security proof, we propose a CKA security model that provides one-way security under key checking attacks. We show that multi-
session security of the Double Ratchet can be tightly reduced to the multi-session security of CKA and FS-AEAD, capturing the same strong security guarantees as Alwen et al.

Our result improves upon the bounds of Alwen et al. in the random oracle model. Even so, we are unable to provide a completely tight proof for the Double Ratchet based on standard Diffie-Hellman assumptions, and we conjecture it is not possible. We thus
go a step further and analyse CKA based on key encapsulation mechanisms (KEMs). In contrast to previous works, our new analysis allows for tight constructions based on the DDH and post-quantum assumptions.



## 2024/1626

* Title: Faster Proofs and VRFs from Isogenies
* Authors: Shai Levin, Robi Pedersen
* [Permalink](https://eprint.iacr.org/2024/1626)
* [Download](https://eprint.iacr.org/2024/1626.pdf)

### Abstract


[continued in next message]

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