## In this issue

1. [2023/1719] MQ on my Mind: Post-Quantum Signatures from the ...
2. [2024/332] Leakage-Tolerant Circuits
3. [2024/724] zkSNARKs in the ROM with Unconditional UC-Security
4. [2024/725] Multi User Security of LightMAC and LightMAC_Plus
5. [2024/726] Challenger: Blockchain-based Massively Multiplayer ...
6. [2024/727] Let Attackers Program Ideal Models: Modularity and ...
7. [2024/728] Relativized Succinct Arguments in the ROM Do Not Exist
8. [2024/729] Covert Adaptive Adversary Model: A New Adversary ...
9. [2024/730] New Solutions to Delsarte's Dual Linear Programs
10. [2024/731] Tight Security of Double-Block Nonce-Based MACs
11. [2024/732] Compact Encryption based on Module-NTRU problems
12. [2024/733] Proxying is Enough: Security of Proxying in TLS ...
13. [2024/734] Proof of Stake and Activity: Rewarding On-Chain ...
14. [2024/735] Secure Multiparty Computation in the Presence of ...
15. [2024/736] Secret Sharing with Certified Deletion
16. [2024/737] Mutable Batch Arguments and Applications
17. [2024/738] Quantum Key-Revocable Dual-Regev Encryption, Revisited
18. [2024/739] BGJ15 Revisited: Sieving with Streamed Memory Access
19. [2024/740] Multi-Client Functional Encryption with Public ...
20. [2024/741] A Deniability Analysis of Signal's Initial ...
21. [2024/742] Efficient Universally-Verifiable Electronic Voting ...
22. [2024/743] Improved Conditional Cube Attacks on Ascon AEADs in ...
23. [2024/744] An NVMe-based Secure Computing Platform with FPGA- ...
24. [2024/745] $\mathsf{FRAST}$: TFHE-friendly Cipher Based on ...

## 2023/1719

* Title: MQ on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem
* Authors: Ryad Benadjila, Thibauld Feneuil, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2023/1719)
* [Download](https://eprint.iacr.org/2023/1719.pdf)

### Abstract

This paper presents MQ on my Mind (MQOM), a digital signature scheme based on the difficulty of solving multivariate systems of quadratic equations (MQ problem). MQOM has been submitted to the NIST call for additional post-quantum signature schemes. MQOM
relies on the MPC-in-the-Head (MPCitH) paradigm to build a zero-knowledge proof of knowledge (ZK-PoK) for MQ which is then turned into a signature scheme through the Fiat-Shamir heuristic. The underlying MQ problem is non-structured in the sense that the
system of quadratic equations defining an instance is drawn uniformly at random. This is one of the hardest and most studied problems from multivariate cryptography which hence constitutes a conservative choice to build candidate post-quantum
cryptosystems. For the efficient application of the MPCitH paradigm, we design a specific MPC protocol to verify the solution of an MQ instance. Compared to other multivariate signature schemes based on non-structured MQ instances, MQOM achieves the
shortest signatures (6.3-7.8 KB) while keeping very short public keys (few dozen of bytes). Other multivariate signature schemes are based on structured MQ problems (less conservative) which either have large public keys (e.g. UOV) or use recently
proposed variants of these MQ problems (e.g. MAYO).



## 2024/332

* Title: Leakage-Tolerant Circuits
* Authors: Yuval Ishai, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/332)
* [Download](https://eprint.iacr.org/2024/332.pdf)

### Abstract

A leakage-resilient circuit for $f:\{0,1\}^n\to\{0,1\}^m$ is a randomized Boolean circuit $C$ mapping a randomized encoding of an input $x$ to an encoding of $y=f(x)$, such that applying any leakage function $L\in \cal L$ to the wires of $C$ reveals
essentially nothing about $x$. A leakage-tolerant circuit achieves the stronger guarantee that even when $x$ and $y$ are not protected by any encoding, the output of $L$ can be simulated by applying some $L'\in \cal L$ to $x$ and $y$ alone. Thus, $C$ is
as secure as an ideal hardware implementation of $f$ with respect to leakage from $\cal L$.

Leakage-resilient circuits were constructed for low-complexity classes $\cal L$, including (length-$t$ output) $\mathcal{AC}0$ functions, parities, and functions with bounded communication complexity. In contrast, leakage-tolerant circuits were only
known for the simple case of probing leakage, where $L$ outputs the values of $t$ wires in $C$.

We initiate a systematic study of leakage-tolerant circuits for natural classes $\cal L$ of global leakage functions, obtaining the following main results.

$\textbf{Leakage-tolerant circuits for depth-1 leakage.}$ Every circuit $C_f$ for $f$ can be efficiently compiled into an $\cal L$-tolerant circuit $C$ for $f$, where $\cal L$ includes all leakage functions $L$ that output either $t$ parities or $t$
disjunctions (alternatively, conjunctions) of any number of wires or their negations. In the case of parities, our simulator runs in $2^{O(t)}$ time. We provide partial evidence that this may be inherent.

$\textbf{Application to stateful leakage-resilient circuits.}$ We present a general transformation from (stateless) leakage-tolerant circuits to stateful leakage-resilient circuits. Using this transformation, we obtain the first constructions of stateful
$t$-leakage-resilient circuits that tolerate a continuous parity/disjunction/conjunction leakage in which the circuit size grows sub-quadratically with $t$. Interestingly, here we can obtain $\mathtt{poly}(t)$-time simulation even in the case of parities.



## 2024/724

* Title: zkSNARKs in the ROM with Unconditional UC-Security
* Authors: Alessandro Chiesa, Giacomo Fenzi
* [Permalink](https://eprint.iacr.org/2024/724)
* [Download](https://eprint.iacr.org/2024/724.pdf)

### Abstract

The universal composability (UC) framework is a “gold standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger
protocols. Zero knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are a popular cryptographic primitive that are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not
necessary, goal.
In this paper we prove that there exist zkSNARKs in the random oracle model (ROM) that unconditionally achieve UC-security. Here, “unconditionally” means that security holds against adversaries that make a bounded number of queries to the random
oracle, but are otherwise computationally unbounded.
Prior work studying UC-security for zkSNARKs obtains transformations that rely on computational assumptions and, in many cases, lose most of the succinctness property of the zkSNARK. Moreover, these transformations make the resulting zkSNARK more
expensive and complicated.
In contrast, we prove that widely used zkSNARKs in the ROM are UC-secure without modifications. We prove that the Micali construction, which is the canonical construction of a zkSNARK, is UC-secure. Moreover, we prove that the BCS construction, which
many zkSNARKs deployed in practice are based on, is UC-secure. Our results confirm the intuition that these natural zkSNARKs do not need to be augmented to achieve UC-security, and give confidence that their use in larger real-world systems is secure.



## 2024/725

* Title: Multi User Security of LightMAC and LightMAC_Plus
* Authors: Nilanjan Datta, Shreya Dey, Avijit Dutta, Devdutto Kanungo
* [Permalink](https://eprint.iacr.org/2024/725)
* [Download](https://eprint.iacr.org/2024/725.pdf)

### Abstract

In FSE'16, Luykx et al. have proposed $\textsf{LightMAC}$ that provably achieves a query length independent PRF security bound. To be precise, the construction achieves security roughly in the order of $O(q^2/2^n)$, when instantiated with two
independently keyed $n$-bit block ciphers and $q$ is the total number of queries made by the adversary. Subsequently, in ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the $\textsf{LightMAC}$ construction, dubbed as $\textsf{LightMAC_
Plus}$, that is built on three independently keyed $n$-bit block ciphers and achieves $2n/3$-bits PRF security. Security analyses of these two constructions have been conducted in the single-user setting, where we assume that the adversary has the access
to a single instance of the construction. In this paper, we investigate, for the first time, the security of the $\textsf{LightMAC}$ and the $\textsf{LightMAC_Plus}$ construction in the context of multi-user setting, where we assume that the adversary
has access to more than one instances of the construction. In particular, we have shown that $\textsf{LightMAC}$ remains secure roughly up to $2^{n/2}$ construction queries and $2^k$ ideal-cipher queries in the ideal-cipher model and $\textsf{LightMAC_
Plus}$ maintains security up to approximately $2^{2n/3}$ construction queries and $2^{2k/3}$ ideal-cipher queries in the ideal-cipher model, where $n$ denotes the block size and $k$ denotes the key size of the block cipher.



## 2024/726

* Title: Challenger: Blockchain-based Massively Multiplayer Online Game Architecture
* Authors: Boris Chan Yip Hon, Bilel Zaghdoudi, Maria Potop-Butucaru, Sébastien Tixeuil, Serge Fdida
* [Permalink](https://eprint.iacr.org/2024/726)
* [Download](https://eprint.iacr.org/2024/726.pdf)

### Abstract

We propose Challenger a peer-to-peer blockchain-based middleware architecture for narrative games, and discuss its resilience to cheating attacks. Our architecture orchestrates nine services in a fully decentralized manner where nodes are not aware of
the entire composition of the system nor its size. All these components are orchestrated together to obtain (strong) resilience to cheaters.
The main contribution of the paper is to provide, for the first time, an architecture for narrative games agnostic of a particular blockchain that brings together several distinct research areas, namely distributed ledgers, peer-to-peer networks, multi-
player-online games and resilience to attacks.



## 2024/727

* Title: Let Attackers Program Ideal Models: Modularity and Composability for Adaptive Compromise
* Authors: Joseph Jaeger
* [Permalink](https://eprint.iacr.org/2024/727)
* [Download](https://eprint.iacr.org/2024/727.pdf)

### Abstract

We show that the adaptive compromise security definitions of Jaeger and Tyagi (Crypto '20) cannot be applied in several natural use-cases. These include proving multi-user security from single-user security, the security of the cascade PRF, and the
security of schemes sharing the same ideal primitive. We provide new variants of the definitions and show that they resolve these issues with composition. Extending these definitions to the asymmetric settings, we establish the security of the modular
KEM/DEM and Fujisaki-Okamoto approaches to public key encryption in the full adaptive compromise setting. This allows instantiations which are more efficient and standard than prior constructions.



## 2024/728

* Title: Relativized Succinct Arguments in the ROM Do Not Exist
* Authors: Annalisa Barbara, Alessandro Chiesa, Ziyi Guan
* [Permalink](https://eprint.iacr.org/2024/728)
* [Download](https://eprint.iacr.org/2024/728.pdf)

### Abstract

A relativized succinct argument in the random oracle model (ROM) is a succinct argument in the ROM that can prove/verify the correctness of computations that involve queries to the random oracle. We prove that relativized succinct arguments in the ROM do
not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical).

This impossibility puts on a formal footing the commonly-held belief that succinct arguments require non-relativizing techniques. Moreover, our results stand in sharp contrast with other oracle models, for which a recent line of work has constructed
relativized succinct non-interactive arguments (SNARGs). Indeed, relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable
cryptographic assumptions. Our results rule out this approach for IVC and PCD in the ROM.



## 2024/729

* Title: Covert Adaptive Adversary Model: A New Adversary Model for Multiparty Computation
* Authors: Isheeta Nargis, Anwar Hasan
* [Permalink](https://eprint.iacr.org/2024/729)
* [Download](https://eprint.iacr.org/2024/729.pdf)

### Abstract

In covert adversary model, the corrupted parties can behave in any possible way like active adversaries, but any party that attempts to cheat is guaranteed to get caught by the honest parties with a minimum fixed probability. That probability is called
the deterrence factor of covert adversary model. Security-wise, covert adversary is stronger than passive adversary and weaker than active adversary. It is more realistic than passive adversary model. Protocols for covert adversaries are significantly
more efficient than protocols for active adversaries. Covert adversary model is defined only for static corruption. Adaptive adversary model is more realistic than static adversaries. In this article, we define a new adversary model, the covert adaptive
adversary model, by generalizing the definition of covert adversary model for the more realistic adaptive corruption. We prove security relations between the new covert adaptive adversary model with existing adversary models like passive adaptive
adversary model, active adaptive
adversary model and covert static adversary model. We prove the sequential composition theorem for the new adversary model which is necessary to allow modular design of protocols for this new adversary model.



## 2024/730

* Title: New Solutions to Delsarte's Dual Linear Programs
* Authors: André Chailloux, Thomas Debris-Alazard
* [Permalink](https://eprint.iacr.org/2024/730)
* [Download](https://eprint.iacr.org/2024/730.pdf)

### Abstract

Understanding the maximum size of a code with a given minimum distance is a major question in computer science and discrete mathematics. The most fruitful approach for finding asymptotic bounds on such codes is by using Delsarte's theory of association
schemes. With this approach, Delsarte constructs a linear program such that its maximum value is an upper bound on the maximum size of a code with a given minimum distance. Bounding this value can be done by finding solutions to the corresponding dual
linear program. Delsarte's theory is very general and goes way beyond binary codes.
In this work, we provide universal bounds in the framework of association schemes that generalize the Hamming bound and the Elias-Bassalygo bound, which can be applied to any association scheme constructed from a distance function. These bounds are
obtained by constructing new solutions to Delsarte's dual linear program. We instantiate these results and we recover known bounds for $q$-ary codes and for constant-weight binary codes but which didn't come from the linear program method. Our other
contribution is to recover, for essentially any $Q$-polynomial scheme, MRRW-type solutions to Delsarte's dual linear program which are inspired by the Laplacian approach of Friedman and Tillich instead of using the Christoffel-Darboux formulas. We show
in particular how the second linear programming bound can be interpreted in this framework.



## 2024/731

* Title: Tight Security of Double-Block Nonce-Based MACs
* Authors: Wonseok Choi, Jooyoung Lee, Yeongmin Lee
* [Permalink](https://eprint.iacr.org/2024/731)
* [Download](https://eprint.iacr.org/2024/731.pdf)

### Abstract

In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}
}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $
F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool,
namely extended Mirror theory based on two independent permutations to a wide range of $\xi_{\max}$ including inequalities. Furthermore, we give a generic semi-black-box reduction from single-user security bound in the standard model to multi-user
security bound in the ideal cipher model, yielding significantly better bounds than the naive hybrid argument. This reduction is applicable to all MAC construction we considered in this paper and even can be more generalized.
We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.



## 2024/732

* Title: Compact Encryption based on Module-NTRU problems
* Authors: Shi Bai, Hansraj Jangir, Hao Lin, Tran Ngo, Weiqiang Wen, Jinwei Zheng
* [Permalink](https://eprint.iacr.org/2024/732)
* [Download](https://eprint.iacr.org/2024/732.pdf)

### Abstract

The Module-NTRU problem, introduced by Cheon, Kim,
Kim, Son (IACR ePrint 2019/1468), and Chuengsatiansup, Prest, Stehlé,
Wallet, Xagawa (ASIACCS ’20), generalizes the versatile NTRU assump-
tion. One of its main advantages lies in its ability to offer greater flexibil- ity on parameters, such as the underlying ring dimension. In this work,
we present several lattice-based encryption schemes, which are IND-CPA
(or OW-CPA) secure in the standard model based on the Module-NTRU
and Module-LWE problems. Leveraging the Fujisaki-Okamoto transfor-
mations, one can obtain IND-CCA secure key encapsulation schemes.
Our first encryption scheme is based on the Module-NTRU assumption,
which uses the determinant of the secret matrix over the underlying ring
for the decryption. Our second scheme is analogue to the Module-LWE
encryption scheme, but uses only a matrix as the public key, based on a vectorial variant of the Module-NTRU problem. In the end, we conduct comprehensive analysis of known attacks and propose concrete parame-
ters for the instantiations. In particular, our ciphertext size is about 614 (resp. 1228) bytes for NIST Level 1 (resp. Level 5) security and small decryption failure, placing it on par with the most recent schemes such as
the one proposed by Zhang, Feng and Yan (ASIACRYPT ’23). We also
present several competitive parameters for NIST Level 3, which has a ci- phertext size of 921 bytes. Moreover, our schemes do not require specific
codes for plaintext encoding and decoding.



## 2024/733

* Title: Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
* Authors: Zhongtang Luo, Yanxue Jia, Yaobin Shen, Aniket Kate
* [Permalink](https://eprint.iacr.org/2024/733)
* [Download](https://eprint.iacr.org/2024/733.pdf)

### Abstract

TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and
reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client (prover), and the
oracle (verifier) node; however, the key practical requirement for TLS oracles to ensure that data provenance process remains transparent to the TLS server. Recent TLS oracle protocols such as DECO enforce the communication pattern of server-client-
verifier and utilize a novel three-party handshake process during TLS to ensure data integrity against potential tempering by the client. However, this approach comes with a significant performance penalty on the client/prover and the verifier and raises
the question if it is possible to improve the performance by putting the verifier (as a proxy) between the server and the client such that the correct TLS transcript is always available to the verifier.

This work offers both positive and negative answers to this oracle proxy question: We first formalize the oracle proxy notion that allows the verifier to directly proxy client-server TLS communication, without entering a three-party handshake or
interfering with the connection in any way. We then show that for common TLS-based higher-level protocols such as HTTPS, data integrity to the verifier proxy is ensured by the variable padding built into the HTTP protocol semantics. On the other hand, if
a TLS-based protocol comes without variable padding, we demonstrate that data integrity cannot be guaranteed. In this context, we then study the case where the TLS response is pre-determined and cannot be tampered with during the connection. We propose
the concept of context unforgeability and show allows overcoming the impossibility. We further show that ChaCha20-Poly1305 satisfies the concept while AES-GCM does not under the standard model.



## 2024/734

* Title: Proof of Stake and Activity: Rewarding On-Chain Activity Through Consensus
* Authors: Aram Jivanyan, Karen Terjanian
* [Permalink](https://eprint.iacr.org/2024/734)
* [Download](https://eprint.iacr.org/2024/734.pdf)

### Abstract

We are introducing a novel consensus protocol for
blockchain, called Proof of Stake and Activity (PoSA) which can
augment the traditional Proof of Stake methods by integrating
a unique Proof of Activity system. PoSA offers a compelling
economic model that promotes decentralization by rewarding
validators based on their staked capital and also the business
value they contribute to the chain. This protocol has been
implemented already into a fully-fledged blockchain platform
called Bahamut (www.bahamut.io) which boasts hundreds of thousands of active users already.



## 2024/735

* Title: Secure Multiparty Computation in the Presence of Covert Adaptive Adversaries
* Authors: Isheeta Nargis, Anwar Hasan
* [Permalink](https://eprint.iacr.org/2024/735)
* [Download](https://eprint.iacr.org/2024/735.pdf)

### Abstract

We design a new MPC protocol for arithmetic circuits secure against erasure-free covert adaptive adversaries with deterrence 1/2. The new MPC protocol has the same asymptotic communication cost, the number of PKE operations and the number of
exponentiation operations as the most efficient MPC protocol for arithmetic circuits secure against covert static adversaries. That means, the new MPC protocol improves security from covert static security to covert adaptive adversary almost for free.
For MPC problems where the number of parties n is much larger than the number of multiplication gates M, the new MPC protocol asymptotically improves communication complexity over the most efficient MPC protocol for arithmetic circuits secure against
erasure-free active adaptive adversaries.



## 2024/736

* Title: Secret Sharing with Certified Deletion
* Authors: James Bartusek, Justin Raizes
* [Permalink](https://eprint.iacr.org/2024/736)
* [Download](https://eprint.iacr.org/2024/736.pdf)

### Abstract

Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its
security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption.
We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical)
secret $s$ is split into quantum shares that can be destroyed in a manner verifiable by the dealer.
We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about $s$, even if
the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of $s$ against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of
corrupted shares minus deleted shares remains unauthorized.
Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive
certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical
ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation
can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.



## 2024/737

* Title: Mutable Batch Arguments and Applications
* Authors: Rishab Goyal
* [Permalink](https://eprint.iacr.org/2024/737)
* [Download](https://eprint.iacr.org/2024/737.pdf)

### Abstract

Non-interactive batch arguments (BARGs) let a prover compute a single proof $\pi$ proving validity of a `batch' of $k$ $\mathbf{NP}$ statements $x_1, \ldots, x_{k}$. The two central features of BARGs are succinctness and soundness. Succinctness states
that proof size, $|\pi|$ does not grow with $k$; while soundness states a polytime cheating prover cannot create an accepting proof for any invalid batch of statements.

In this work, we put forth a new concept of mutability for batch arguments, called mutable batch arguments. Our goal is to re-envision how we think about and use BARGs. Traditionally, a BARG proof string $\pi$ is an immutable encoding of $k$ $\mathbf{NP}$
witness $\omega_1, \ldots, \omega_{k}$. In a mutable BARG system, each proof string $\pi$ is a mutable encoding of original witnesses. Thus, a mutable BARG captures and enables computations over a batch proof $\pi$. We also study new privacy notions for
mutable BARGs, guaranteeing that a mutated proof hides all non-trivial information. Such mutable BARGs are a naturally good fit for many privacy sensitive applications.

Our main contributions can be summarized as introducing the general concept of mutable BARGs, identifying new non-trivial classes of feasible mutations over BARGs, designing new constructions for mutable BARGs satisfying mutation privacy for these
classes from standard cryptographic assumptions, and developing applications of mutable BARGs to advanced signatures such as homomorphic signatures, redactable signatures, and aggregate signatures. Our results improve state-of-the-art known for many such
signature systems either in terms of functionality, efficiency, security, or versatility (in terms of cryptographic assumptions).



## 2024/738

* Title: Quantum Key-Revocable Dual-Regev Encryption, Revisited
* Authors: Prabhanjan Ananth, Zihan Hu, Zikuan Huang
* [Permalink](https://eprint.iacr.org/2024/738)
* [Download](https://eprint.iacr.org/2024/738.pdf)

### Abstract

Quantum information can be used to achieve novel cryptographic primitives that are impossible to achieve classically. A recent work by Ananth, Poremba, Vaikuntanathan (TCC 2023) focuses on equipping the dual-Regev encryption scheme, introduced by Gentry,
Peikert, Vaikuntanathan (STOC 2008), with key revocation capabilities using quantum information. They further showed that the key-revocable dual-Regev scheme implies the existence of fully homomorphic encryption and pseudorandom functions, with both of
them also equipped with key revocation capabilities. Unfortunately, they were only able to prove the security of their schemes based on new conjectures and left open the problem of basing the security of key revocable dual-Regev encryption on well-
studied assumptions.

In this work, we resolve this open problem. Assuming polynomial hardness of learning with errors (over sub-exponential modulus), we show that key-revocable dual-Regev encryption is secure. As a consequence, for the first time, we achieve the following
results:
1. Key-revocable public-key encryption and key-revocable fully-homomorphic encryption satisfying classical revocation security and based on polynomial hardness of learning with errors. Prior works either did not achieve classical revocation or were based
on sub-exponential hardness of learning with errors.
2. Key-revocable pseudorandom functions satisfying classical revocation from the polynomial hardness of learning with errors. Prior works relied upon unproven conjectures.



## 2024/739

* Title: BGJ15 Revisited: Sieving with Streamed Memory Access
* Authors: Ziyu Zhao, Jintai Ding, Bo-Yin Yang
* [Permalink](https://eprint.iacr.org/2024/739)
* [Download](https://eprint.iacr.org/2024/739.pdf)

### Abstract

The focus of this paper is to tackle the issue of memory access within sieving algorithms for lattice problems. We have conducted an in-depth analysis of an optimized BGJ sieve (Becker-Gama-Joux 2015), and our findings suggest that its inherent structure
is significantly more memory-efficient compared to the asymptotically fastest BDGL sieve (Becker-Ducas-Gama-Laarhoven 2016). Specifically, it necessitates merely $2^{0.2075n + o(n)}$ streamed (non-random) main memory accesses for the execution of an $n$-
dimensional sieving. We also provide evidence that the time complexity of this refined BGJ sieve could potentially be $2^{0.292n + o(n)}$, or at least something remarkably close to it. Actually, it outperforms the BDGL sieve in all dimensions that are
practically achievable. We hope that this study will contribute to the resolution of the ongoing debate regarding the measurement of RAM access overhead in large-scale, sieving-based lattice attacks.

The concept above is also supported by our implementation. Actually, we provide a highly efficient, both in terms of time and memory, CPU-based implementation of the refined BGJ sieve within an optimized sieving framework. This implementation results in
approximately 40% savings in RAM usage and is at least $2^{4.5}$ times more efficient in terms of gate count compared to the previous 4-GPU implementation (Ducas-Stevens-Woerden 2021). Notably, we have successfully solved the 183-dimensional SVP
Darmstadt Challenge in 30 days using a 112-core server and approximately 0.87TB of RAM. The majority of previous sieving-based SVP computations relied on the HK3-sieve (Herold-Kirshanova 2017), hence this implementation could offer further insights into
the behavior of these asymptotically faster sieving algorithms when applied to large-scale problems. Moreover, our refined cost estimation of SVP based on this implementation suggests that some of the NIST PQC candidates, such as Falcon-512, are unlikely
to achieve NIST's security requirements.



## 2024/740

* Title: Multi-Client Functional Encryption with Public Inputs and Strong Security
* Authors: Ky Nguyen, Duong Hieu Phan, David Pointcheval
* [Permalink](https://eprint.iacr.org/2024/740)
* [Download](https://eprint.iacr.org/2024/740.pdf)

### Abstract


[continued in next message]

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