[digest] 2023 Week 24

[IACR ePrint Archive]

## In this issue

1. [2023/271] Swoosh: Practical Lattice-Based Non-Interactive Key ...
2. [2023/868] Breaking the Chains of Rationality: Understanding ...
3. [2023/877] Public-Key Encryption with Quantum Keys
4. [2023/878] Introducing two Low-Latency Cipher Families: Sonic ...
5. [2023/890] Efficient Evaluation of Frequency Test for ...
6. [2023/891] When is Slower Block Propagation More Profitable ...
7. [2023/892] Suboptimality in DeFi
8. [2023/893] Short paper: Diversity Methods for Laser Fault ...
9. [2023/894] Differentially Private Selection from Secure ...
10. [2023/895] ModHE: Modular Homomorphic Encryption Using Module ...
11. [2023/896] Improved Gadgets for the High-Order Masking of ...
12. [2023/897] On the Impossibility of Algebraic NIZK In Pairing- ...
13. [2023/898] Leaking-cascades: an optimized construction for KEM ...
14. [2023/899] Practical Schnorr Threshold Signatures Without the ...
15. [2023/900] What If Alice Wants Her Story Told?
16. [2023/901] Secure Multiparty Computation with Free Branching
17. [2023/902] SublonK: Sublinear Prover PlonK
18. [2023/903] Near-Optimal Oblivious Key-Value Stores for ...
19. [2023/904] Pseudorandom Strings from Pseudorandom Quantum States
20. [2023/905] $\mathsf{zkSaaS}$: Zero-Knowledge SNARKs as a Service
21. [2023/906] Optimal Broadcast Encryption and CP-ABE from ...
22. [2023/907] Efficient Zero Knowledge for Regular Language
23. [2023/908] A Hardware-Software Co-Design for the Discrete ...
24. [2023/909] Efficient 3PC for Binary Circuits with Application ...
25. [2023/910] Amortized Functional Bootstrapping in less than ...
26. [2023/911] General Results of Linear Approximations over ...
27. [2023/912] Randomness of random in Cisco ASA
28. [2023/913] Hidden Stream Ciphers and TMTO Attacks on TLS 1.3, ...
29. [2023/914] Limits in the Provable Security of ECDSA Signatures
30. [2023/915] Attribute-based Single Sign-On: Secure, Private, ...
31. [2023/916] Unlinkability and Interoperability in Account-Based ...
32. [2023/917] Zeromorph: Zero-Knowledge Multilinear-Evaluation ...
33. [2023/918] Invertible Bloom Lookup Tables with Less Memory and ...
34. [2023/919] Threshold Private Set Intersection with Better ...
35. [2023/920] Beware Your Standard Cells! On Their Role in Static ...
36. [2023/921] Efficient Card-Based Millionaires' Protocols via ...
37. [2023/922] mR$_{\text{LWE}}$-CP-ABE a revocable CP-ABE for ...
38. [2023/923] Video-Based Cryptanalysis: Extracting Cryptographic ...
39. [2023/924] Generalized Initialization of the Duplex Construction
40. [2023/925] Homomorphic Indistinguishability Obfuscation and ...
41. [2023/926] Analysis of the security of the PSSI problem and ...
42. [2023/927] Collision Entropy Estimation in a One-Line Formula
43. [2023/928] Restricting vectorial functions to affine spaces ...
44. [2023/929] The tweakable block cipher family QARMAv2
45. [2023/930] Lattice-Based Succinct Arguments for NP with ...
46. [2023/931] Compact Identity Based Encryption Based on n^{th} - ...
47. [2023/932] On the (Im)possibility of Time-Lock Puzzles in the ...
48. [2023/933] Concrete NTRU Security and Advances in Practical ...

## 2023/271

* Title: Swoosh: Practical Lattice-Based Non-Interactive Key Exchange
* Authors: Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, Peter Schwabe
* [Permalink](https://eprint.iacr.org/2023/271)
* [Download](https://eprint.iacr.org/2023/271.pdf)

### Abstract

The advent of quantum computers has sparked significant interest in post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all existing viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange~(NIKE) is theoretically possible, it has been considered too inefficient for real-life applications.

In this work, we challenge this folklore belief and provide the first evidence against it. We construct a practical lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively-secure one. To substantiate our efficiency claim, we provide an optimised implementation of our construction in Rust and Jasmin. Our implementation demonstrates the scheme's applicability to real-world scenarios, yielding public keys of approximately $220$\,KBs. Moreover, the computation of shared keys takes fewer than $12$ million cycles on an Intel Skylake CPU, offering a post-quantum security level exceeding $120$ bits.



## 2023/868

* Title: Breaking the Chains of Rationality: Understanding the Limitations to and Obtaining Order Policy Enforcement
* Authors: Sarisht Wadhwa, Luca Zanolini, Francesco D'Amato, Aditya Asgaonkar, Fan Zhang, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2023/868)
* [Download](https://eprint.iacr.org/2023/868.pdf)

### Abstract

Order manipulation attacks such as frontrunning and sandwiching have become an increasing concern in blockchain applications such as DeFi. To protect from such attacks, several recent works have designed order policy enforcement (OPE) protocols to order transactions fairly in a data-independent fashion. However, while the manipulation attacks are motivated by monetary profits, the defenses assume honesty among a significantly large set of participants. In existing protocols, if all participants are rational, they may be incentivized to collude and circumvent the order policy without incurring any penalty.

This work makes two key contributions. First, we explore whether the need for the honesty assumption is fundamental. Indeed, we show that it is impossible to design OPE protocols under some requirements when all parties are rational. Second, we explore the tradeoffs needed to circumvent the impossibility result. In the process, we propose a novel concept of rationally binding transactions that allows us to construct AnimaguSwap(A key design in AnimaguSwap is that user orders may transform to a different direction---like the fictional creatures Animagi in Harry Potter---in order to achieve the desired game theoretic properties) , the first content-oblivious Automated Market Makers (AMM) that is secure under rationality.



## 2023/877

* Title: Public-Key Encryption with Quantum Keys
* Authors: Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, Michael Walter
* [Permalink](https://eprint.iacr.org/2023/877)
* [Download](https://eprint.iacr.org/2023/877.pdf)

### Abstract

In the framework of Impagliazzo's five worlds, a distinction is often made
between two worlds, one where public-key encryption exists (Cryptomania),
and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can change when quantum information is taken into account. Recent work has shown that quantum variants of oblivious transfer and multi-party computation, both primitives that are classically in Cryptomania, can be constructed from one-way functions, placing them in the realm of quantum MiniCrypt (the so-called MiniQCrypt).
This naturally raises the following question: Is it possible to construct a quantum variant of public-key encryption, which is at the heart of Cryptomania, from one-way functions or potentially weaker assumptions? In this work, we initiate the formal study of the notion of quantum public-key encryption (qPKE), i.e., public-key encryption where keys are allowed to be quantum states. We propose new definitions of security and several constructions of qPKE based on the existence of one-way functions (OWF), or even weaker assumptions, such as pseudorandom function-like states (PRFS) and pseudorandom function-like states with proof of destruction (PRFSPD). Finally, to give a tight characterization of this primitive, we show that computational assumptions are necessary to build quantum public-key encryption. That is, we give a self-contained proof that no quantum public-key encryption scheme can provide information-theoretic security.



## 2023/878

* Title: Introducing two Low-Latency Cipher Families: Sonic and SuperSonic
* Authors: Yanis Belkheyar, Joan Daemen, Christoph Dobraunig, Santosh Ghosh, Shahram Rasoolzadeh
* [Permalink](https://eprint.iacr.org/2023/878)
* [Download](https://eprint.iacr.org/2023/878.pdf)

### Abstract

For many latency-critical operations in computer systems, like memory reads/writes, adding encryption can have a big impact on the performance. Hence, the existence of cryptographic primitives with good security properties and minimal latency is a key element in the wide-spread implementation of such security measures. In this paper, we introduce two new families of low-latency permutations/block ciphers called Sonic and SuperSonic, inspired by the Simon block ciphers.



## 2023/890

* Title: Efficient Evaluation of Frequency Test for Overlapping Vectors Statistic
* Authors: Krzysztof MAŃK
* [Permalink](https://eprint.iacr.org/2023/890)
* [Download](https://eprint.iacr.org/2023/890.pdf)

### Abstract

Randomness testing is one of the essential and easiest tools for evaluating cryptographic primitives. The faster we can test, the greater volume of data that can be tested. Thus a more detailed analysis is possible.
This paper presents a range of observations made for a well-known frequency test for overlapping vectors in binary sequence testing. We have obtained precise chi-square statistic computed in $O \left(dt 2^{dt} \right)$ instead of $O\left( 2^{2dt}\right)$ time, without precomputed tables.



## 2023/891

* Title: When is Slower Block Propagation More Profitable for Large Miners?
* Authors: Zhichun Lu, Ren Zhang
* [Permalink](https://eprint.iacr.org/2023/891)
* [Download](https://eprint.iacr.org/2023/891.pdf)

### Abstract

For years, Bitcoin miners put little effort into adopting several widely-acclaimed block acceleration techniques, which, as some argued, would secure their revenues. Their indifference inspires a theory that slower block propagation is beneficial for some miners. In this study, we analyze and confirm this counterintuitive theory. Specifically, by modeling inadvertent slower blocks, we show that a mining coalition that controls more than a third of the total mining power can earn unfair revenue by propagating blocks slower to outsiders. Afterward, we explore the strategies of an attacker that consciously exploits this phenomenon. The results indicate that an attacker with 45% of the total mining power can earn 58% of the total revenue. This attack is alarming as it is equally fundamental but more stealthy than the well-known selfish mining attack. At last, we discuss its detection and defense mechanisms.



## 2023/892

* Title: Suboptimality in DeFi
* Authors: Aviv Yaish, Maya Dotan, Kaihua Qin, Aviv Zohar, Arthur Gervais
* [Permalink](https://eprint.iacr.org/2023/892)
* [Download](https://eprint.iacr.org/2023/892.pdf)

### Abstract

The Decentralized Finance (DeFi) ecosystem has proven to be immensely popular in facilitating financial operations such as lending and exchanging assets, with Ethereum-based platforms holding a combined amount of more than 30 billion USD. The public availability of these platforms' code together with real-time data on all user interactions and platform liquidity has given rise to sophisticated automatic tools that recognize profit opportunities on behalf of users and seize them.

In this work, we formalize three core DeFi primitives which together are responsible for a daily volume of over 100 million USD in Ethereum-based platforms alone: (1) lending and borrowing funds, (2) liquidation of insolvent loans, and (3) using flash-swaps to close arbitrage opportunities between cryptocurrency exchanges. The profit which can be made from each primitive is then cast as an optimization problem that can be readily solved.

We use our formalization to analyze several case studies for each primitive, showing that popular platforms and tools which promise to automatically optimize profits for users, actually fall short. In specific instances, the profits can be increased by more than 100%, with highest amount of ``missed'' revenue by a single suboptimal action equal to 428.14 ETH, or roughly 517K USD.

Finally, we show that many missed opportunities to make a profit do not go unnoticed by other users. Indeed, suboptimal transactions are sometimes immediately followed by ``trailing'' back-running transactions which extract additional profits using similar actions. By analyzing a subset of such events, we uncover that some users who frequently create such trailing transactions are heavily tied to specific miners, meaning that all of their transactions appear only in blocks mined by one miner in particular. As some of the backrun non-optimal transactions are private, we hypothesize that the users who create them are, in fact, miners (or users collaborating with miners) who use inside information known only to them to make a profit, thus gaining an unfair advantage.



## 2023/893

* Title: Short paper: Diversity Methods for Laser Fault Injection to Improve Location Coverage
* Authors: Marina Krček, Thomas Ordas, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2023/893)
* [Download](https://eprint.iacr.org/2023/893.pdf)

### Abstract

In the first step of fault injection attacks, it is necessary to perform fault injections for target characterization to improve the chances of finding vulnerabilities that can be exploited in the second step. The second step is the attack, where the vulnerabilities are used to break the security. This work considers the parameter search on the laser fault injection parameters. While this work can also be adjusted to find exploitable faults, the objective here is to find as many faults as possible on the target device. The goal comes from a security evaluation perspective to perform a successful target characterization. Previous works propose several methods, such as the memetic algorithm or hyperparameter tuning techniques. However, we notice a problem concerning the convergence of such methods to one specific target region, which is beneficial for an attack where one parameter combination could be enough. Indeed, these search algorithms lead to many observed vulnerabilities, but most seem to come from the same area on the target, which could mean some crucial vulnerabilities are missed.
In this work, we propose considering the location coverage of the algorithms and offer two methods promoting diversity in tested parameter combinations to increase it while still finding many faults.We compare the grid memetic algorithm and evolution strategies to the performance of the memetic algorithm and random search. Our results show a benefit from introducing diversity to increase location coverage, but the overall number of vulnerabilities is decreased compared to the memetic algorithm. However, the number of unique locations with vulnerabilities is similar between the three evolutionary algorithms, with evolution strategies providing the most distant locations.



## 2023/894

* Title: Differentially Private Selection from Secure Distributed Computing
* Authors: Ivan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, Rasmus Pagh
* [Permalink](https://eprint.iacr.org/2023/894)
* [Download](https://eprint.iacr.org/2023/894.pdf)

### Abstract

Given a collection of vectors $\mathbf{x}^{(1)},\dots,\mathbf{x}^{(n)} \in \{0,1\}^d$, the selection problem asks to report the index of an "approximately largest" entry in $\mathbf{x}=\sum_{j=1}^n \mathbf{x}^{(j)}$. Selection abstracts a host of problems; in machine learning it can be used for hyperparameter tuning, feature selection, or to model empirical risk minimization. We study selection under differential privacy, where a released index guarantees privacy for individual vectors. Though selection can be solved with an excellent utility guarantee in the central model of differential privacy, the distributed setting where no single entity is trusted to aggregate the data lacks solutions. Specifically, strong privacy guarantees with high utility are offered in high trust settings, but not in low trust settings. For example, in the popular shuffle model of distributed differential privacy, there are strong lower bounds suggesting that the utility of the central model cannot be obtained. In this paper we design a protocol for differentially private selection in a trust setting similar to the shuffle model - with the crucial difference that our protocol tolerates corrupted servers while maintaining privacy. Our protocol uses techniques from secure multi-party computation (MPC) to implement a protocol that: (i) has utility on par with the best mechanisms in the central model, (ii) scales to large, distributed collections of high-dimensional vectors, and (iii) uses $k\geq 3$ servers that collaborate to compute the result, where the differential privacy guarantee holds assuming an honest majority. Since general-purpose MPC techniques are not sufficiently scalable, we propose a novel application of integer secret sharing, and evaluate the utility and efficiency of our protocol both theoretically and empirically. Our protocol is the first to demonstrate that large-scale differentially private selection is possible in a distributed setting.



## 2023/895

* Title: ModHE: Modular Homomorphic Encryption Using Module Lattices: Potentials and Limitations
* Authors: Anisha Mukherjee, Aikata Aikata, Ahmet Can Mert, Yongwoo Lee, Sunmin Kwon, Maxim Deryabin, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2023/895)
* [Download](https://eprint.iacr.org/2023/895.pdf)

### Abstract

The promising field of homomorphic encryption enables functions to be evaluated on encrypted data and produce results that mimic the same computations done on plaintexts. It, therefore, comes as no surprise that many ventures at constructing homomorphic encryption schemes have come into the limelight in recent years. Most popular are those that rely on the hard lattice problem, called the Ring Learning with Errors problem (RLWE). One major limitation of these homomorphic encryption schemes is that in order to securely increase the maximum multiplicative depth, they need to increase the polynomial-size thereby also increasing the complexity of the design. We aim to bridge this gap by proposing a homomorphic encryption (HE) scheme based on the Module Learning with Errors problem (MLWE), ModHE that allows us to break the big computations into smaller ones. Given the popularity of module lattice-based post-quantum schemes, it is an evidently interesting research
endeavor to also formulate module lattice-based homomorphic encryption schemes.

While our proposed scheme is general, as a case study, we port the well-known RLWE-based CKKS scheme to the MLWE setting. The module version of the scheme completely stops the polynomial-size blowups when aiming for a greater circuit depth. Additionally, it presents greater opportunities for designing flexible, reusable, and parallelizable hardware architecture. A hardware implementation is provided to support our claims. We also acknowledge that as we try to decrease the complexity of computations, the amount of computations (such as relinearizations) increases. We hope that the potential and limitations of using such a hardware-friendly scheme will spark further research.



## 2023/896

* Title: Improved Gadgets for the High-Order Masking of Dilithium
* Authors: Jean-Sébastien Coron, François Gérard, Matthias Trannoy, Rina Zeitoun
* [Permalink](https://eprint.iacr.org/2023/896)
* [Download](https://eprint.iacr.org/2023/896.pdf)

### Abstract

We present novel and improved high-order masking gadgets for Dilithium, a post-quantum signature scheme that has been standardized by the National Institute of Standards and Technologies (NIST). Our proposed gadgets include the ShiftMod gadget, which is used for efficient arithmetic shifts and serves as a component in other masking gadgets. Additionally, we propose a new algorithm for Boolean-to-arithmetic masking conversion of a $\mu$-bit integer $x$ modulo any integer $q$, with a complexity that is independent of both $\mu$ and $q$. This algorithm is used in Dilithium to mask the generation of the random variable $y$ modulo $q$. Moreover, we describe improved techniques for masking the Decompose function in Dilithium. Our new gadgets are proven to be secure in the $t$-probing model.

We demonstrate the effectiveness of our countermeasures by presenting a complete high-order masked implementation of Dilithium that utilizes the improved gadgets described above. We provide practical results obtained from a C implementation and compare the performance improvements provided by our new gadgets with those of previous work.



## 2023/897

* Title: On the Impossibility of Algebraic NIZK In Pairing-Free Groups
* Authors: Emanuele Giunta
* [Permalink](https://eprint.iacr.org/2023/897)
* [Download](https://eprint.iacr.org/2023/897.pdf)

### Abstract

Non-Interactive Zero-Knowledge proofs (NIZK) allow a prover to convince a verifier that a statement is true by sending only one message and without conveying any other information.
In the CRS model, many instantiations have been proposed from group-theoretic assumptions.
On the one hand, some of these constructions use the group structure in a black-box way but rely on pairings, an example being the celebrated Groth-Sahai proof system.
On the other hand, a recent line of research realized NIZKs from sub-exponential DDH in pairing-free groups using Correlation Intractable Hash functions, but at the price of making non black-box usage of the group.

As of today no construction is known to simultaneously reduce its security to pairing-free group problems and to use the underlying group in a black-box way.

This is indeed not a coincidence:
in this paper, we prove that for a large class of NIZK either a pairing-free group is used non black-box by relying on element representation, or security reduces to external hardness assumptions.
More specifically our impossibility applies to two incomparable cases.
The first one covers Arguments of Knowledge (AoK) which proves that a preimage under a given one way function is known.
The second one covers NIZK (not necessarily AoK) for hard subset problems, which captures relations such as DDH, Decision-Linear and Matrix-DDH.



## 2023/898

* Title: Leaking-cascades: an optimized construction for KEM hybridization
* Authors: Céline Chevalier, Guirec Lebrun, Ange Martinelli
* [Permalink](https://eprint.iacr.org/2023/898)
* [Download](https://eprint.iacr.org/2023/898.pdf)

### Abstract

Hybrid post-quantum cryptography is a cautious approach that aims to guard against the threat posed by the quantum computer, through the simultaneous use of Post- Quantum (PQ) and classical (i.e. pre-quantum) cryptosystems, in case the post-quantum schemes used would turn out to be insecure.

Regarding the hybridization of Key Encapsulation Mechanisms (KEMs), most recent studies focus on how to safely combine the symmetric keys output by a parallel execution of classical and post-quantum KEMs. As simple as this architecture is, it however appears not to be the most efficient, computationally speaking as well as regarding the bandwidth of the exchanges.

Hence, we propose a new method to hybridize several KEMs more effectively, by combining the underlying Public Key Encryption schemes (PKEs) in an innovative variant of the cas- cade composition that we call "leaking-cascade". We prove that this architecture constitutes an IND-CPA-secure robust combiner for the encryption schemes, which permits to create an IND-CCA2 KEM upon the generated hybrid PKE. The leaking-cascade is at least as computationally effective as the commonly used parallel combination, and has a bandwidth gain - when it comes to the ciphertext produced - that may exceed 13 % compared to the latter.



## 2023/899

* Title: Practical Schnorr Threshold Signatures Without the Algebraic Group Model
* Authors: Hien Chu, Paul Gerhart, Tim Ruffing, Dominique Schröder
* [Permalink](https://eprint.iacr.org/2023/899)
* [Download](https://eprint.iacr.org/2023/899.pdf)

### Abstract

Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which is currently undergoing standardization in the IETF and whose security was recently analyzed at CRYPTO'22.

We continue this line of research by focusing on FROST's unforgeability combined with a practical distributed key generation (DKG) algorithm. Existing proofs of this setup either use non-standard heuristics, idealized group models like the AGM, or idealized key generation. Moreover, existing proofs do not consider all practical relevant optimizations that have been proposed. We close this gap between theory and practice by presenting the Schnorr threshold signature scheme Olaf, which combines the most efficient known FROST variant FROST3 with a variant of Pedersen's DKG protocol (as commonly used for FROST), and prove its unforgeability. Our proof relies on the AOMDL assumption (a weaker and falsifiable variant of the OMDL assumption) and, like proofs of regular Schnorr signatures, on the random oracle model.



## 2023/900

* Title: What If Alice Wants Her Story Told?
* Authors: Anindya Bhandari, Allison Bishop
* [Permalink](https://eprint.iacr.org/2023/900)
* [Download](https://eprint.iacr.org/2023/900.pdf)

### Abstract

In this paper, we pose the problem of defining technical privacy guarantees for anonymizing stories. This is a challenge that arises in practice in contexts like journalism and memoir writing, and can be crucial in determining whether a story gets told and how effectively it is presented. While recent decades have seen leaps and bounds in the development of approaches like differential privacy for numerical and categorical data sets, none of these techniques are directly applicable to settings where narrative structure is crucial to preserve. Here we begin an exploration of what kind of definitions could be achievable in such settings, and discuss the building blocks and interdisciplinary collaborations that could shape new solutions. Having scientific guarantees for anonymity in narrative forms could have far-reaching effects - in the peace of mind of potential tellers and subjects of stories, as well as in the legal sphere. This could ultimately expand the kinds of stories that can be told.



## 2023/901

* Title: Secure Multiparty Computation with Free Branching
* Authors: Aarushi Goel, Mathias Hall-Andersen, Aditya Hegde, Abhishek Jain
* [Permalink](https://eprint.iacr.org/2023/901)
* [Download](https://eprint.iacr.org/2023/901.pdf)

### Abstract

We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of a single active branch. Crucially, the identity of the active branch must remain hidden from the protocol participants.

While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO'20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving more than two parties.

In this work, we provide a generic framework for branching multi-party computation that supports any number of parties. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.



## 2023/902

* Title: SublonK: Sublinear Prover PlonK
* Authors: Arka Rai Choudhuri, Sanjam Garg, Aarushi Goel, Sruthi Sekar, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2023/902)
* [Download](https://eprint.iacr.org/2023/902.pdf)

### Abstract

We propose SublonK - a new zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). SublonK builds on PlonK [EPRINT'19], a popular state-of-the-art practical zkSNARK. Our new construction preserves all the great features of PlonK, i.e., it supports constant size proofs, constant time proof verification, a circuit-independent universal setup, as well as support for custom gates and lookup gates. Moreover, SublonK achieves improved prover running time over PlonK. In PlonK, the prover runtime grows with circuit size. Instead, in Sublonk, the prover runtime grows with the size of the "active part" of the circuit. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in SublonK grows only with the exercised execution path.

As an example, consider the zkRollup circuit. This circuit involves executing one of n code segments k times. For this case, using PlonK involves proving a circuit of size n.k code segments. In SublonK, the prover costs are close to proving a PlonK proof for a circuit of size roughly k code segments. Concretely, based on our implementation, for parameter choices derived from rollup contracts on Ethereum, n = 8, k = {2^{10},...,2^{16}}, the SublonK prover is approximately 4.6 times faster than the PlonK prover. Proofs in SublonK are 2.4KB, and can be verified in under 50ms.



## 2023/903

* Title: Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps
* Authors: Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2023/903)
* [Download](https://eprint.iacr.org/2023/903.pdf)

### Abstract

In this paper, we study oblivious key-value stores (OKVS) that enable encoding n key-value pairs into length $m$ encodings while hiding the input keys. The goal is to obtain high rate, $n/m$, with efficient encoding and decoding algorithms. We present $\mathsf{RB\text{-}OKVS}$ built on random band matrices that obtains near-optimal rates as high as 0.97 whereas prior works could only achieve rates up to 0.81 with similar encoding times.

Using $\mathsf{RB\text{-}OKVS}$, we obtain state-of-the-art protocols for private set intersection (PSI) and union (PSU). Our semi-honest PSI has up to 12% smaller communication and 13% reductions in monetary cost with slightly larger computation. We also obtain similar improvements for both malicious and circuit PSI. For PSU, our protocol obtains improvements of up to 22% in communication, 40% in computation and 21% in monetary cost. In general, we obtain the most communication- and cost-efficient protocols for all the above primitives.

Finally, we present the first connection between OKVS and volume-hiding encrypted multi-maps (VH-EMM) where the goal is to outsource storage of multi-maps while hiding the number of values associated with each key (i.e., volume). We present $\mathsf{RB\text{-}MM}$ with 16% smaller storage, 5x faster queries and 8x faster setup than prior works.



## 2023/904

* Title: Pseudorandom Strings from Pseudorandom Quantum States
* Authors: Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen
* [Permalink](https://eprint.iacr.org/2023/904)
* [Download](https://eprint.iacr.org/2023/904.pdf)

### Abstract

A fundamental result in classical cryptography is that pseudorandom generators are equivalent to one-way functions and in fact implied by nearly every classical cryptographic primitive requiring computational assumptions. In this work, we consider a variant of pseudorandom generators called quantum pseudorandom generators (QPRGs), which are quantum algorithms that (pseudo)deterministically map short random seeds to long pseudorandom strings. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes.

Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.

Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.



## 2023/905

* Title: $\mathsf{zkSaaS}$: Zero-Knowledge SNARKs as a Service
* Authors: Sanjam Garg, Aarushi Goel, Abhishek Jain, Guru-Vamsi Policharla, Sruthi Sekar
* [Permalink](https://eprint.iacr.org/2023/905)
* [Download](https://eprint.iacr.org/2023/905.pdf)

### Abstract

A decade of active research has led to practical constructions of zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) that are now being used in a wide variety of applications. Despite this astonishing progress, overheads in proof generation time remain significant.

In this work, we envision a world where consumers with low computational resources can outsource the task of proof generation to a group of untrusted servers in a privacy-preserving manner. The main requirement is that these servers should be able to collectively generate proofs at a faster speed (than the consumer). Towards this goal, we introduce a framework called zk-SNARKs-as-a-service ($\mathsf{zkSaaS}$) for faster computation of zk-SNARKs. Our framework allows for distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover. Moreover, the privacy of the prover's witness is ensured against any minority of colluding servers.

We design custom protocols in this framework that can be used to obtain faster runtimes for widely used zk-SNARKs, such as Groth16 [EUROCRYPT 2016], Marlin [EUROCRYPT 2020], and Plonk [EPRINT 2019]. We implement proof of concept zkSaaS for the Groth16 and Plonk provers. In comparison to generating these proofs on commodity hardware, we show that not only can we generate proofs for a larger number of constraints (without memory exhaustion), but can also get $\approx 22\times$ speed-up when run with 128 parties for $2^{25}$ constraints with Groth16 and $2^{21}$ gates with Plonk.



## 2023/906

* Title: Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions
* Authors: Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2023/906)
* [Download](https://eprint.iacr.org/2023/906.pdf)

### Abstract

We present a new, simple candidate broadcast encryption scheme for $N$ users with parameter size poly$(\log N)$. We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images, while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.



## 2023/907

* Title: Efficient Zero Knowledge for Regular Language
* Authors: Michael Raymond, Gillian Evers, Jan Ponti, Diya Krishnan, Xiang Fu
* [Permalink](https://eprint.iacr.org/2023/907)
* [Download](https://eprint.iacr.org/2023/907.pdf)

### Abstract

A succinct zero knowledge proof for regular language mem-
bership, i.e., to prove a secret string behind an encryption (hash) belongs
to a regular language is useful, e.g., for asserting that an encrypted email
is free of malware. The great challenge in practice is that the regular
language used is often huge. We present zkreg, a distributed commit-
and-prove system that handles such complexity. In zkreg, cryptographic
operations are encoded using arithmetic circuits, and input acceptance is
modeled as a zero knowledge subset problem using Σ-protocols. We in-
troduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects
Σ-protocols and the Groth16 system with O(1) proof size and verifier
cost. We present a close-to-optimal univariate instantiation of zk-VPD,
a zero knowledge variation of the KZG polynomial commitment scheme,
based on which an efficient zk-subset protocol is developed. We develop
a 2-phase proof scheme to further exploit the locality of Aho-Corasick
automata. To demonstrate the performance and scalability of zkreg, we
prove that all ELF files (encrypted and hashed) in a Linux CentOS 7
are malware free. Applying inner pairing product argument, we obtain
an aggregated proof of 1.96 MB which can be verified in 6.5 seconds.



## 2023/908

* Title: A Hardware-Software Co-Design for the Discrete Gaussian Sampling of FALCON Digital Signature
* Authors: Emre Karabulut, Aydin Aysu
* [Permalink](https://eprint.iacr.org/2023/908)
* [Download](https://eprint.iacr.org/2023/908.pdf)

### Abstract

Sampling random values from a discrete Gaussian distribution with high precision is a major and computationally intensive operation of upcoming or existing cryptographic standards. FALCON is one such algorithm that the National Institute of Standards and Technology chose to standardize as a next-generation, quantum-secure digital signature algorithm. The discrete Gaussian sampling of FALCON has both flexibility and efficiency needs—it constitutes 72% of total signature generation in reference software and requires sampling from a variable mean and standard deviation. Unfortunately, there are no prior works on accelerating this complete sampling procedure.
In this paper, we propose a hardware-software co-design for accelerating FALCON’s discrete Gaussian sampling subroutine. The proposed solution handles the flexible computations for setting the variable parameters in software and executes core operations with low latency, parameterized, and custom hardware. The hardware parameterization allows trading off area vs. performance. On a Xilinx SoC FPGA Architecture, the results show that compared to the reference software, our solution can accelerate the sampling up to 9.83× and the full signature scheme by 2.7×. Moreover, we quantified that our optimized multiplier circuits can improve the throughput over a straightforward implementation by 60%.



## 2023/909

* Title: Efficient 3PC for Binary Circuits with Application to Maliciously-Secure DNN Inference
* Authors: Yun Li, Yufei Duan, Zhicong Huang, Cheng Hong, Chao Zhang, Yifan Song
* [Permalink](https://eprint.iacr.org/2023/909)
* [Download](https://eprint.iacr.org/2023/909.pdf)

### Abstract

In this work, we focus on maliciously secure 3PC for binary circuits with honest majority. While the state-of-the-art (Boyle et al. CCS 2019) has already achieved the same amortized communication as the best-known semi-honest protocol (Araki et al. CCS 2016), they suffer from a large computation overhead: when comparing with the best-known implementation result (Furukawa et al. Eurocrypt 2017) which requires $9\times$ communication cost of Araki et al., the protocol by Boyle et al. is around $4.5\times$ slower than that of Furukawa et al.

In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation.

Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$.

Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.



## 2023/910

* Title: Amortized Functional Bootstrapping in less than 7ms, with $\tilde{O}(1)$ polynomial multiplications
* Authors: Zeyu Liu, Yunhao Wang
* [Permalink](https://eprint.iacr.org/2023/910)
* [Download](https://eprint.iacr.org/2023/910.pdf)

### Abstract

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap $n$ LWE ciphertexts simultaneously, reducing the total cost from $\tilde{O}(n^2)$ to $\tilde{O}(3^\epsilon n^{1+\frac{1}{\epsilon}})$ for arbitrary $\epsilon > 0$. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping.

In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.



## 2023/911

* Title: General Results of Linear Approximations over Finite Abelian Groups
* Authors: Zhongfeng Niu, Siwei Sun, Hailun Yan, Qi Wang
* [Permalink](https://eprint.iacr.org/2023/911)
* [Download](https://eprint.iacr.org/2023/911.pdf)

### Abstract

In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly symmetric-key primitives, the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. In this paper, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. We consider the nonlinearity, which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. The lower bound of the nonlinearity of a function $F:G\rightarrow H$ over an arbitrary finite Abelian group was first given by Pott in 2004. However, the result was restricted to the case that the size of $G$ divides the size of $H$ due to its connection to relative difference sets. We complete the generalization from $\mathbb{F}_2^n$ to finite Abelian groups and give the lower bound of $\lambda_F$ for all different cases. Our result is deduced by the new links that we established between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups.



## 2023/912

* Title: Randomness of random in Cisco ASA
* Authors: Ryad Benadjila, Arnaud Ebalard
* [Permalink](https://eprint.iacr.org/2023/912)
* [Download](https://eprint.iacr.org/2023/912.pdf)

### Abstract

It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis.

After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.

The current article describes our journey understanding Cisco ASA randomness issues through years, leading to CVE-2023-20107 [CVE-2023-20107, CSCvm90511]. More generally, it also provides technical and practical feedback on what can and cannot be done regarding entropy sources in association with DRBGs and other random processing mechanisms.



## 2023/913

* Title: Hidden Stream Ciphers and TMTO Attacks on TLS 1.3, DTLS 1.3, QUIC, and Signal
* Authors: John Preuß Mattsson
* [Permalink](https://eprint.iacr.org/2023/913)
* [Download](https://eprint.iacr.org/2023/913.pdf)

### Abstract

Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modelled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ciphers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offers a lower security level against TMTO attacks than expected from the key sizes. We provide detailed analyses of the key update mechanisms in TLS 1.3 and Signal, illustrate the importance of ephemeral key exchange, and show that the process that DTLS 1.3 and QUIC use to calculate AEAD limits is flawed. We provide many concrete recommendations for the analyzed protocols.



## 2023/914

* Title: Limits in the Provable Security of ECDSA Signatures
* Authors: Dominik Hartmann, Eike Kiltz
* [Permalink](https://eprint.iacr.org/2023/914)
* [Download](https://eprint.iacr.org/2023/914.pdf)

### Abstract

Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.

In this work, we study the question whether these strong idealized models are necessary for proving the security of ECDSA. Specifically, we focus on the programmability of ECDSA's "conversion function" which maps an elliptic curve point into its $x$-coordinate modulo the group order. Unfortunately, our main results are negative. We establish, by means of a meta reductions, that an algebraic security reduction for ECDSA can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for ECDSA is unlikely to exist without strong idealization.



## 2023/915

* Title: Attribute-based Single Sign-On: Secure, Private, and Efficient
* Authors: Tore Kasper Frederiksen, Julia Hesse, Bertram Poettering, Patrick Towa
* [Permalink](https://eprint.iacr.org/2023/915)
* [Download](https://eprint.iacr.org/2023/915.pdf)

### Abstract

A Single Sign-On (SSO) system allows users to access different remote services while authenticating only once. SSO can greatly improve the usability and security of online activities by dispensing with the need to securely remember or store tens or hundreds of authentication secrets. On the downside, today's SSO providers can track users' online behavior, and collect personal data that service providers want to see asserted before letting a user access their resources.

In this work, we propose a new policy-based Single Sign-On service, i.e., a system that produces access tokens that are conditioned on the user's attributes fulfilling a specified policy. Our solution is based on multi-party computation and threshold cryptography, and generates access tokens of standardized format. The central idea is to distribute the role of the SSO provider among several entities, in order to shield user attributes and access patterns from each individual entity. We provide a formal security model and analysis in the Universal Composability framework, against proactive adversaries. Our implementation and benchmarking show the practicality of our system for many real-world use cases.



## 2023/916

* Title: Unlinkability and Interoperability in Account-Based Universal Payment Channels
* Authors: Mohsen Minaei, Panagiotis Chatzigiannis, Shan Jin, Srinivasan Raghuraman, Ranjit Kumaresan, Mahdi Zamani, Pedro Moreno-Sanchez
* [Permalink](https://eprint.iacr.org/2023/916)
* [Download](https://eprint.iacr.org/2023/916.pdf)

### Abstract

Payment channels allow a sender to do multiple transactions with a receiver without recording each single transaction on-chain. While most of the current constructions for payment channels focus on UTXO-based cryptocurrencies with reduced scripting capabilities (e.g., Bitcoin or Monero), little attention has been given to the possible benefits of adapting such constructions to cryptocurrencies based on the account model and offering a Turing complete language (e.g., Ethereum).

The focus of this work is to implement efficient payment channels tailored to the capabilities of account-based cryptocurrencies with Turing-complete language support in order to provide scalable payments that are interoperable across different cryptocurrencies and unlinkable for third-parties (e.g., payment intermediaries). More concretely, we continue the line of research on cryptocurrency universal payment channels (UPC) which facilitate interoperable payment channel transactions across different ledgers in a hub-and-spoke model, by offering greater scalability than point-to-point architectures. Our design proposes two different versions, UPC and AUPC. For UPC we formally describe the protocol ideas sketched in previous work and evaluate our proof-of-concept implementation. Then, AUPC further extends the concept of universal payment channels by payment unlinkability against the intermediary server.



## 2023/917

* Title: Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments
* Authors: Tohru Kohrita, Patrick Towa
* [Permalink](https://eprint.iacr.org/2023/917)
* [Download](https://eprint.iacr.org/2023/917.pdf)

### Abstract

A multilinear polynomial is a multivariate polynomial that is linear in each variable. This paper presents a scheme to commit to multilinear polynomials and to later prove evaluations of committed polynomials. The construction of the scheme is generic and relies on additively homomorphic schemes to commit to univariate polynomials. As the construction requires to check that several committed univariate polynomials do not exceed given, separate bounds, the paper also gives a method to batch executions of any degree-check protocol on homomorphic commitments.
For a multilinear polynomial in n ≥ 2 variables, the instantiation of the scheme with a hiding version of KZG commitments (Kate, Zaverucha and Goldberg at Asiacrypt 2010) gives a pairing-based scheme with evaluations proofs in which the prover sends n + 3 first-group elements, performs at most 5 · 2n−1 + 1 first-group scalar multiplication and uses only n+2 random field elements to achieve the zero-knowledge property. Verification requires at most 2n + 2 first-group scalar multiplications, two second-group scalar multiplications and three pairing computations.



## 2023/918

* Title: Invertible Bloom Lookup Tables with Less Memory and Randomness
* Authors: Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
* [Permalink](https://eprint.iacr.org/2023/918)
* [Download](https://eprint.iacr.org/2023/918.pdf)

### Abstract

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions.

We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}(n + \log(1/\delta)\log\log(1/\delta))$ space and $\mathcal{O}(\log(\log(n)/\delta))$-wise independent hash functions.

As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-\Omega(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is highly non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest.



## 2023/919

* Title: Threshold Private Set Intersection with Better Communication Complexity
* Authors: Satrajit Ghosh, Mark Simkin
* [Permalink](https://eprint.iacr.org/2023/919)
* [Download](https://eprint.iacr.org/2023/919.pdf)

### Abstract

Given $\ell$ parties with sets $X_1, \dots, X_\ell$ of size $n$, we would like to securely compute the intersection $\cap_{i=1}^\ell X_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $t$.

In this work, we construct protocols with a quasilinear dependency on $t$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $n-t$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $\mathcal{O}(\lambda \ell \cdot\mathrm{poly}(t))$, where $\lambda$ is the security parameter, and transforms it into a protocol with communication complexity $\mathcal{O}(\lambda^2 \ell t \cdot\mathrm{polylog}(t))$.



## 2023/920

* Title: Beware Your Standard Cells! On Their Role in Static Power Side-Channel Attacks
* Authors: Jitendra Bhandari, Likhitha Mankali, Mohammed Nabeel, Ozgur Sinanoglu, Ramesh Karri, Johann Knechtel
* [Permalink](https://eprint.iacr.org/2023/920)
* [Download](https://eprint.iacr.org/2023/920.pdf)

### Abstract

The increase in leakage power from advanced tech nodes elevates the risk of static power side-channel (S-PSC) attacks. While protective measures exist, they involve a security cost trade-off. Hardware Trojans, particularly PSC-based ones, represent another significant threat. Despite acknowledging the link between static power leakage, advanced tech nodes, and vulnerability to S-PSC attacks, the role of the components at the heart of this sensitive interplay – the standard cells – has not been extensively studied in commercial-grade IC design. We analyze this relationship for commercial 28nm and 65nm nodes using a regular AES design. Our CAD framework permits design optimization while assessing S-PSC vulnerability. Contrary to the belief that high-performance designs are more vulnerable, we find timing constraints and threshold-voltage cell ratios are pivotal factors. Also, we discover that an attacker can deploy highly effective, stealthy PSC-based Trojans without any gate overheads or compromising timing paths.



## 2023/921

* Title: Efficient Card-Based Millionaires' Protocols via Non-Binary Input Encoding
* Authors: Koji Nuida
* [Permalink](https://eprint.iacr.org/2023/921)
* [Download](https://eprint.iacr.org/2023/921.pdf)

### Abstract

Comparison of integers, a traditional topic in secure multiparty computation since Yao's pioneering work on "Millionaires' Problem" (FOCS 1982), is also well studied in card-based cryptography. For the problem, Miyahara et al. (Theoretical Computer Science, 2020) proposed a protocol using binary cards (i.e., cards with two kinds of symbols) that is highly efficient in terms of numbers of cards and shuffles, and its extension to number cards (i.e., cards with distinct symbols). In this paper, with a different design strategy which we name "Tug-of-War technique", we propose new protocols based on binary cards and on number cards. For binary cards, our protocol improves the previous protocol asymptotically (in bit lengths of input integers) in terms of numbers of cards and shuffles when adopting ternary encoding of input integers. For number cards, at the cost of increasing the number of cards, our protocol improves the number of shuffles of the previous protocol even with binary encoding, and more with $q$-ary encoding where $q > 2$.



## 2023/922

* Title: mR$_{\text{LWE}}$-CP-ABE a revocable CP-ABE for Post-Quantum Cryptography
* Authors: Marco Cianfriglia, Elia Onofri, Marco Pedicini
* [Permalink](https://eprint.iacr.org/2023/922)
* [Download](https://eprint.iacr.org/2023/922.pdf)

### Abstract

We address the problem of user fast revocation in the lattice based CP-ABE by extending the scheme originally introduced in [A ciphertext policy attribute-based encryption scheme without pairings. J. Zhang, Z. Zhang - ICISC 2011]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice based CP-ABE scheme, hence providing post-quantum safety. In particular, we rely on semi-trusted "mediators" to provide a multi-step decryption capable of handling mediation without re-encryption.
We comment on the scheme and its application and we provide performance experiments on a prototype implementation in the ABE spin-off library of Palisade to evaluate the overhead compared with the original scheme.



## 2023/923

* Title: Video-Based Cryptanalysis: Extracting Cryptographic Keys from Video Footage of a Device’s Power LED
* Authors: Ben Nassi, Etay Iluz, Or Cohen, Ofek Vayner, Dudi Nassi, Boris Zadov, Yuval Elovici
* [Permalink](https://eprint.iacr.org/2023/923)
* [Download](https://eprint.iacr.org/2023/923.pdf)

### Abstract

In this paper, we present video-based cryptanalysis,
a new method used to recover secret keys from a device by
analyzing video footage of a device’s power LED. We show that
cryptographic computations performed by the CPU change the
power consumption of the device which affects the brightness of
the device’s power LED. Based on this observation, we show how
attackers can exploit commercial video cameras (e.g., an iPhone
13’s camera or Internet-connected security camera) to recover
secret keys from devices. This is done by obtaining video footage
of a device’s power LED (in which the frame is filled with the
power LED) and exploiting the video camera’s rolling shutter
to increase the sampling rate by three orders of magnitude
from the FPS rate (60 measurements per second) to the rolling
shutter speed (60K measurements per second in the iPhone 13
Pro Max). The frames of the video footage of the device’s power
LED are analyzed in the RGB space, and the associated RGB
values are used to recover the secret key by inducing the power
consumption of the device from the RGB values. We demonstrate
the application of video-based cryptanalysis by performing two
side-channel cryptanalytic timing attacks and recover: (1) a 256-
bit ECDSA key from a smart card by analyzing video footage of
the power LED of a smart card reader via a hijacked Internet-connected security camera located 16 meters away from the smart
card reader, and (2) a 378-bit SIKE key from a Samsung Galaxy
S8 by analyzing video footage of the power LED of Logitech Z120
USB speakers that were connected to the same USB hub (that
was used to charge the Galaxy S8) via an iPhone 13 Pro Max.
Finally, we discuss countermeasures, limitations, and the future
of video-based cryptanalysis in light of the expected improvements
in video cameras’ specifications.



## 2023/924

* Title: Generalized Initialization of the Duplex Construction
* Authors: Christoph Dobraunig, Bart Mennink
* [Permalink](https://eprint.iacr.org/2023/924)
* [Download](https://eprint.iacr.org/2023/924.pdf)

### Abstract

The duplex construction is already well analyzed with many papers proving its security in the random permutation model. However, so far, the first phase of the duplex, where the state is initialized with a secret key and an initialization vector ($\mathit{IV}$), is typically analyzed in a worst case manner. More detailed, it is always assumed that the adversary is allowed to choose the $\mathit{IV}$ on its will. In this paper, we analyze how the security changes if restrictions on the choice of the $\mathit{IV}$ are imposed, varying from the global nonce case over the random $\mathit{IV}$ case to the $\mathit{IV}$ on key case. The last one, in particular, is the duplex analogue of the use of a nonce masked with a secret in AES-GCM in TLS 1.3. We apply our findings to duplex-based encryption and authenticated encryption, and discuss the practical applications of our results.



## 2023/925

* Title: Homomorphic Indistinguishability Obfuscation and its Applications
* Authors: Kaartik Bhushan, Venkata Koppula, Manoj Prabhakaran
* [Permalink](https://eprint.iacr.org/2023/925)
* [Download](https://eprint.iacr.org/2023/925.pdf)

### Abstract

In this work, we propose the notion of homomorphic indistinguishability obfuscation ($\mathsf{HiO}$) and present a construction based on subexponentially-secure $\mathsf{iO}$ and one-way functions. An $\mathsf{HiO}$ scheme allows us to convert an obfuscation of circuit $C$ to an obfuscation of $C'\circ C$, and this can be performed obliviously (that is, without knowing the circuit $C$). A naive solution would be to obfuscate $C' \circ \mathsf{iO}(C)$. However, if we do this for $k$ hops, then the size of the final obfuscation is exponential in $k$. $\mathsf{HiO}$ ensures that the size of the final obfuscation remains polynomial after repeated compositions. As an application, we show how to build function-hiding hierarchical multi-input functional encryption and homomorphic witness encryption using $\mathsf{HiO}$.



## 2023/926

* Title: Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
* Authors: Nicolas Aragon, Victor Dyseryn, Philippe Gaborit
* [Permalink](https://eprint.iacr.org/2023/926)
* [Download](https://eprint.iacr.org/2023/926.pdf)

### Abstract

We present a new attack against the PSSI problem, one of the three problems at the root of security of Durandal, an efficient rank metric code-based signature scheme with a public key size of 15 kB and a signature size of 4 kB, presented at EUROCRYPT'19. Our attack recovers the private key using a leakage of information coming from several signatures produced with the same key. Our approach is to combine pairs of signatures and perform Cramer-like formulas in order to build subspaces containing a secret element. We break all existing parameters of Durandal: the two published sets of parameters claiming a security of 128 bits are broken in respectively $2^{66}$ and $2^{73}$ elementary bit operations, and the number of signatures required to finalize the attack is 1,792 and 4,096 respectively. We implemented our attack and ran experiments that demonstrated its success with smaller parameters.



## 2023/927

* Title: Collision Entropy Estimation in a One-Line Formula
* Authors: Alessandro Gecchele
* [Permalink](https://eprint.iacr.org/2023/927)
* [Download](https://eprint.iacr.org/2023/927.pdf)

### Abstract

Integer-order Rényi entropies are synthetic indices useful for the characterization of probability distributions. In recent decades, numerous studies have been conducted to arrive at valid estimates of these indices starting from experimental data, so to derive a suitable classification method for the underlying processes. However, optimal solutions have not been reached yet. A one-line formula limited to the estimation of collision entropy is presented here. The results of some specific Monte Carlo experiments gave evidence of its validity even for the very low densities of the data spread in high-dimensional sample spaces. The strengths of this method are unbiased consistency, generality and minimum computational cost.



## 2023/928

* Title: Restricting vectorial functions to affine spaces and deducing infinite families of 4-uniform permutations, in relation to the strong D-property
* Authors: Claude Carlet, Enrico Piccione
* [Permalink](https://eprint.iacr.org/2023/928)
* [Download](https://eprint.iacr.org/2023/928.pdf)

### Abstract

Given three positive integers $n<N$ and $M$, we study those functions $\mathcal{F}$ from the vector space $\mathbb{F}_2^N$ (possibly endowed with the field structure) to $\mathbb{F}_2^M$, which map at least one $n$-dimensional affine subspace of $\mathbb{F}_2^N$ to a subset of an affine subspace of dimension $n$, or at least of a dimension less than $M$. This provides functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$ for some $m$ (and in some cases, permutations) that have a simple representation over $\mathbb{F}_2^N$ or over $\mathbb{F}_{2^N}$. We show that the nonlinearity of $\mathcal{F}$ must not be too large for allowing this and that if it is zero, there automatically exists a strict affine subspace of its domain that is mapped by $\mathcal{F}$ into a subset of a strict affine subspace of its co-domain. In this case, we show that the nonlinearity of the restriction may be large. We study the other cryptographic properties of such restriction, viewed as an $(n,m)$-function (resp. an $(n,n)$-permutation). We then focus on the case of an $(N,N)$-function $\mathcal{F}$ equal to $\psi(\mathcal{G}(x))$ where $\mathcal{G}$ is almost perfect nonlinear (APN) and $\psi$ is a linear function with a kernel of dimension $1.$
We will build upon the follow fact: the restriction of $\mathcal{G}$ over an affine hyperplane $A$ has the D-property (introduced by Taniguchi after a result from Dillon) as an $(N-1,N)$-function, if and only if for every such $\psi$, the restriction of $\mathcal{F}(x)=\psi(\mathcal{G}(x))$ over $A$ is not an APN $(N-1,N-1)$-function. If this holds for all affine hyperplanes $A,$ we say that $\mathcal{G}$ has the strong D-property. The fact of not satisfying this nice property is also positive in a way since it allows to construct a number of APN $(N-1,N-1)$-functions from $\mathcal{G}$. We give a characterization of the strong D-property for crooked functions by means of their ortho-derivatives and we prove that the Gold APN function in dimension $N\geq 9$ odd does have the strong D-property. Completing a result from Taniguchi for $N\geq 6$ even, we can prove that the strong D-property of the Gold APN function in dimension $N$ holds if and only if $N=6$ or $N\geq 8$. Then we give a partial result on the Dobbertin APN power function and on this basis, we conjecture that it has the strong D-property. We then move our focus to infinite families of $(N-1,N-1)$-permutations constructed as the restriction of $(N,N)$-functions $\mathcal{F}(x)=\psi(\mathcal{G}(x))$ or $\mathcal{F}(x)=\psi(\mathcal{G}(x))+x$ where $\psi$ and $\mathcal{G}$ are as before but with the extra hypothesis that $\mathcal{G}$ is an APN permutation. There are in the literature two families of differentially 4-uniform permutations corresponding to this framework, but no proof was given that they are not APN. We investigate these constructions deeply and prove that they do not produce APN permutations in dimension $n=N-1$ even. We present our own construction and we show a relation between infinite families of APN $(N,N)$-permutations and infinite families of $4$-uniform $(N-1,N-1)$-permutations. This gives a deeper understanding on the problem of constructing infinite families of APN permutations in even dimension (for trying to solve the so-called big APN problem) with the method explored in this paper. This problem is also related to the strong D-property and we conjecture that some classes of APN power permutations have such property in dimension large enough. We show that only few APN permutations do not have the strong D-property (and this happens only for small dimension). Our construction gives many families of $4$-uniform $(N-1,N-1)$-permutations with high nonlinearity that are additionally, under some conditions, complete permutations.



## 2023/929

* Title: The tweakable block cipher family QARMAv2
* Authors: Roberto Avanzi, Subhadeep Banik, Orr Dunkelman, Maria Eichlseder, Shibam Ghosh, Marcel Nageler, Francesco Regazzoni
* [Permalink](https://eprint.iacr.org/2023/929)
* [Download](https://eprint.iacr.org/2023/929.pdf)

### Abstract

We introduce QARMAvii, a redesign of the tweakable block cipher QARMA to provide more robust security bounds and allow for longer tweaks,
while keeping very similar latency and area values.
The longer tweaks serve to address specific use cases and facilitate the design of modes of operation with higher security bounds.
This is achieved by adopting new key and tweak schedules, and by making some changes to the 128-bit versions,
as well as by performing a deeper security analysis.

The resulting cipher offers competitive latency and area in HW implementations.

Some of our results may be of independent interest.
This includes new MILP models of certain classes of diffusion matrices,
the comparative analysis of a full reflection cipher against an iterative half-cipher,
and our boomerang attack framework.



## 2023/930

* Title: Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification
* Authors: Jonathan Bootle, Alessandro Chiesa, Katerina Sotiraki
* [Permalink](https://eprint.iacr.org/2023/930)
* [Download](https://eprint.iacr.org/2023/930.pdf)

### Abstract

Succinct arguments that rely on the Merkle-tree paradigm introduced by Kilian (STOC 92) suffer from larger proof sizes in practice due to the use of generic cryptographic primitives. In contrast, succinct arguments with the smallest proof sizes in practice exploit homomorphic commitments. However these latter are quantum insecure, unlike succinct arguments based on the Merkle-tree paradigm.

A recent line of works seeks to address this limitation, by constructing quantum-safe succinct arguments that exploit lattice-based commitments. The eventual goal is smaller proof sizes than those achieved via the Merkle-tree paradigm. Alas, known constructions lack succinct verification.

In this paper, we construct the first interactive argument system for NP with succinct verification that, departing from the Merkle-tree paradigm, exploits the homomorphic properties of lattice-based commitments. For an arithmetic circuit with N gates, our construction achieves verification time polylog(N) based on the hardness of the Ring Short-Integer-Solution (RSIS) problem.

The core technique in our construction is a delegation protocol built from commitment schemes based on leveled bilinear modules, a new notion that we deem of independent interest. We show that leveled bilinear modules can be realized from pre-quantum and from post-quantum cryptographic assumptions.



## 2023/931

* Title: Compact Identity Based Encryption Based on n^{th} - Residuosity Assumption
* Authors: Sree Vivek S, S. Sharmila Deva Selvi, Ramarathnam Venkatesan, C. Pandu Rangan
* [Permalink](https://eprint.iacr.org/2023/931)
* [Download](https://eprint.iacr.org/2023/931.pdf)

### Abstract

Practical Identity Based Encryption (IBE) schemes use the costly bilinear pairing computation. Clifford Cock proposed an IBE based on quadratic residuosity in 2001 which does not use bilinear pairing but was not efficient in practice, due to the large ciphertext size. In 2007, Boneh et al. proposed the first space efficient IBE that was also based on quadratic residuosity problem. It was an improvement over Cock's scheme but still the time required for encryption was quartic in the security parameter. In this paper, we propose a compact, space and time efficient identity based encryption scheme without pairing, based on a variant of Paillier Cryptosystem and prove it to be CPA secure. We have also proposed a CCA secure scheme based on the basic IBE scheme using the Fujisaki-Okamoto transformation. We have proved both the schemes in the random oracle model.



## 2023/932

* Title: On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model
* Authors: Abtin Afshar, Kai-Min Chung, Yao-Ching Hsieh, Yao-Ting Lin, Mohammad Mahmoody
* [Permalink](https://eprint.iacr.org/2023/932)
* [Download](https://eprint.iacr.org/2023/932.pdf)

### Abstract

Time-lock puzzles wrap a solution $\mathrm{s}$ inside a puzzle $\mathrm{P}$ in such a way that ``solving'' $\mathrm{P}$ to find $\mathrm{s}$ requires significantly more time than generating the pair $(\mathrm{s},\mathrm{P})$, even if the adversary has access to parallel computing; hence it can be thought of as sending a message $\mathrm{s}$ to the future. It is known [Mahmoody, Moran, Vadhan, Crypto'11] that when the source of hardness is only a random oracle, then any puzzle generator with $n$ queries can be (efficiently) broken by an adversary in $O(n)$ rounds of queries to the oracle.

In this work, we revisit time-lock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of time-lock puzzles solely from quantum (accessible) random oracles. In particular, for any $n$-query classical puzzle generator, our attack only asks $O(n)$ (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing.

Assuming perfect completeness, we also show how to make the above attack run in exactly $n$ rounds while asking a total of $m\cdot n$ queries where $m$ is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask $n-1$ rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from $\Omega(mn \log n)$ to $mn$. Finally, assuming perfect completeness, we present an attack in the ``dual'' setting in which the puzzle generator is quantum while the solver is classical.

We then ask whether one can extend our classical-query attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv'2009] is false, then there is indeed a time-lock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto'22] about key agreements (that can have interactions in both directions) to time-lock puzzles (that only include unidirectional communication).



## 2023/933

* Title: Concrete NTRU Security and Advances in Practical Lattice-Based Electronic Voting
* Authors: Patrick Hough, Caroline Sandsbråten, Tjerand Silde
* [Permalink](https://eprint.iacr.org/2023/933)
* [Download](https://eprint.iacr.org/2023/933.pdf)

### Abstract

In recent years there has been much focus on the development of core cryptographic primitives based on lattice assumptions. This has been driven by the NIST call for post-quantum key encapsulation and digital signature specifications. However, there has been much less work on efficient privacy-preserving protocols with post-quantum security.

In this work we present an efficient electronic voting scheme from lattice assumptions, ensuring the long-term security of encrypted ballots and voters' privacy. The scheme relies on the NTRU and RLWE assumptions. We begin by conducting an extensive analysis of the concrete hardness of the NTRU problem. Extending the ternary-NTRU analysis of Ducas and van Woerden (ASIACRYPT 2021), we determine the concrete fatigue point of NTRU to be $q=0.0058\cdot\sigma^2\cdot d^{\: 2.484}$ (above which parameters become overstretched) for modulus $q$, ring dimension $d$, and secrets drawn from a Gaussian of parameter $\sigma$. Moreover, we demonstrate that the nature of this relation enables a more fine-grained choice of secret key sizes, leading to more efficient parameters in practice.

Using the above analysis, our second and main contribution is to significantly improve the efficiency of the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). Replacing the BGV encryption scheme with NTRU we obtain a factor $\times 5.3$ reduction in ciphertext size and $\times 2.6$ more efficient system overall, making the scheme suitable for use in real-world elections.

As an additional contribution, we analyse the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022). We note that the NTRU security is much lower than claimed and propose new parameters. This results in only a minor efficiency loss, enabled by our NTRU analysis where previous parameter selection techniques would have been much more detrimental.