[continued from previous message]

During the standardisation process of post-quantum cryptography, NIST encourages research on side-channel analysis for candidate schemes. As the recommended lattice signature scheme, CRYSTALS-Dilithium, when implemented on hardware, has only been
subjected to the side-channel attack presented by Steffen et al. in IACR ePrint 2022. This attack is not complete and requires excessive traces. Therefore, we investigate the leakage of an FPGA (Kintex7) implementation of CRYSTALS-Dilithium using the CPA
method, where with a minimum of 70000 traces partial private key coefficients can be recovered. As far as we know, this is the first work that applies power leakage to sidechannel attacks on FPGA implementations of CRYSTALS-Dilithium. Furthermore, we
optimise the attack by extracting Point-of-Interests using known information due to parallelism (named CPA-PoI) and by iteratively utilising parallel leakages (named CPA-ITR). We experimentally demonstrate that when recovering the same number of key
coefficients, the CPA-PoI and CPA-ITR reduce the number of traces used by up to 16.67 percent and 25 percent, respectively, compared to the CPA method. When attacking with the same number of traces, the CPA-PoI method and the CPA-ITR method increase the
number of recovered key coefficients by up to 55.17 percent and 93.10 percent, respectively, compared to the CPA method. Our experiments confirm that the FPGA implementation of CRYSTALS-Dilithium is also very vulnerable to side-channel analysis.



## 2023/1892

* Title: Asymptotics of hybrid primal lattice attacks
* Authors: Daniel J. Bernstein
* [Permalink](https://eprint.iacr.org/2023/1892)
* [Download](https://eprint.iacr.org/2023/1892.pdf)

### Abstract

The literature gives the impression that (1) existing heuristics accurately predict how effective lattice attacks are, (2) non-ternary lattice systems are not vulnerable to hybrid multi-decoding primal attacks, and (3) the asymptotic exponents of attacks
against non-ternary systems have stabilized.

This paper shows that 1 contradicts 2 and that 1 contradicts 3: the existing heuristics imply that hybrid primal key-recovery attacks are exponentially faster than standard non-hybrid primal key-recovery attacks against the LPR PKE with any constant
error width. This is the first report since 2015 of an exponential speedup in heuristic non-quantum primal attacks against non-ternary LPR.

Quantitatively, for dimension n, modulus n^{Q_0+o(1)}, and error width w, a surprisingly simple hybrid attack reduces heuristic costs from 2^{(ρ+o(1))n} to 2^{(ρ-ρ H_0+o(1))n}, where z_0=2Q_0/(Q_0+1/2)^2, ρ=z_0 log_4(3/2), and H_0=1/(1+(lg w)/0.
057981z_0). This raises the questions of (1) what heuristic exponent is achieved by more sophisticated hybrid attacks and (2) what impact hybrid attacks have upon concrete cryptosystems whose security analyses have ignored hybrid attacks, such as Kyber-
512.



## 2023/1893

* Title: BOLT: Privacy-Preserving, Accurate and Efficient Inference for Transformers
* Authors: Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, Thomas Schneider
* [Permalink](https://eprint.iacr.org/2023/1893)
* [Download](https://eprint.iacr.org/2023/1893.pdf)

### Abstract

The advent of transformers has brought about significant advancements in traditional machine learning tasks. However, their pervasive deployment has raised concerns about the potential leakage of sensitive information during inference. Existing
approaches using secure multiparty computation (MPC) face limitations when applied to transformers due to the extensive model size and resource-intensive matrix-matrix multiplications. In this paper, we present BOLT, a privacy-preserving inference
framework for transformer models that supports efficient matrix multiplications and nonlinear computations. Combined with our novel machine learning optimizations, BOLT reduces the communication cost by 10.91x. Our evaluation on diverse datasets
demonstrates that BOLT maintains comparable accuracy to floating-point models and achieves 4.8-9.5x faster inference across various network settings compared to the state-of-the-art system.



## 2023/1894

* Title: Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
* Authors: Yilei Chen, Jiatu Li
* [Permalink](https://eprint.iacr.org/2023/1894)
* [Download](https://eprint.iacr.org/2023/1894.pdf)

### Abstract

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. $\textsf{Avoid}$) and the remote point problem (
abbrev. $\textsf{RPP}$). The upper and lower bounds for these meta problems provide a unified perspective on the complexity of specific explicit construction problems that were previously studied independently. An interesting question largely unaddressed
by previous works is whether $\textsf{Avoid}$ and $\textsf{RPP}$ are hard for simple circuits such as low-depth circuits.

In this paper, we demonstrate, under plausible cryptographic assumptions, that both the range avoidance problem and the remote point problem cannot be efficiently solved by nondeterministic search algorithms, even when the input circuits are as simple as
constant-depth circuits. This extends a hardness result established by Ilango, Li, and Williams (STOC '23) against deterministic algorithms employing witness encryption for $\textsf{NP}$, where the inputs to $\textsf{Avoid}$ are general Boolean circuits.

Our primary technical contribution is a novel construction of witness encryption inspired by public-key encryption for certain promise language in $\textsf{NP}$ that is unlikely to be $\textsf{NP}$-complete. We introduce a generic approach to transform a
public-key encryption scheme with particular properties into a witness encryption scheme for a promise language related to the initial public-key encryption scheme. Based on this translation and variants of standard lattice-based or coding-based PKE
schemes, we obtain, under plausible assumption, a provably secure witness encryption scheme for some promise language in $\textsf{NP}\setminus \textsf{coNP}_{/\textsf{poly}}$. Additionally, we show that our constructions of witness encryption are
plausibly secure against nondeterministic adversaries under a generalized notion of security in the spirit of Rudich's super-bits (RANDOM '97), which is crucial for demonstrating the hardness of $\textsf{Avoid}$ and $\textsf{RPP}$ against
nondeterministic algorithms.



## 2023/1895

* Title: The Patching Landscape of Elisabeth-4 and the Mixed Filter Permutator Paradigm
* Authors: Clément Hoffmann, Pierrick Méaux, François-Xavier Standaert
* [Permalink](https://eprint.iacr.org/2023/1895)
* [Download](https://eprint.iacr.org/2023/1895.pdf)

### Abstract

Filter permutators are a family of stream cipher designs that are aimed for hybrid homomorphic encryption. While originally operating on bits, they have been generalized to groups at Asiacrypt 2022, and instantiated
for evaluation with the TFHE scheme which favors a filter based on (negacyclic) Look Up Tables (LUTs). A recent work of Gilbert et al., to appear at Asiacrypt 2023, exhibited (algebraic) weaknesses in the Elisabeth-4 instance, exploiting the combination
of the 4-bit negacyclic LUTs it uses as filter. In this article, we explore the
landscape of patches that can be used to restore the security of such designs while maintaining their good properties for hybrid homomorphic encryption. Starting with minimum changes, we observe that just updating the filter function (still with small
negacyclic LUTs) is conceptually feasible, and propose the resulting Elisabeth-b4 design with three levels of NLUTs. We then show that a group permutator combining two different functions in the filter can simplify the analysis and improve performances.
We specify the Gabriel instance to illustrate this claim. We finally propose to modify the group filter permutator paradigm into
a mixed filter permutator, which considers the permutation of the key with elements in a group and a filter outputting elements in a different group. We specify the Margrethe instance as a first example of mixed filter permutator, with key elements in $\
mathbb{F}_2$ and output in $\mathbb{Z}_{16}$, that we believe well-suited for recent fully homomorphic encryption schemes that can efficiently evaluate larger (not negacyclic) LUTs.



## 2023/1896

* Title: Selective Delegation of Attributes in Mercurial Signature Credentials * Authors: Colin Putman, Keith M. Martin
* [Permalink](https://eprint.iacr.org/2023/1896)
* [Download](https://eprint.iacr.org/2023/1896.pdf)

### Abstract

Anonymous credential schemes enable service providers to verify information that a credential holder willingly discloses, without needing any further personal data to corroborate that information, and without allowing the user to be tracked from one
interaction to the next. Mercurial signatures are a novel class of anonymous credentials which show good promise as a simple and efficient construction without heavy reliance on zero-knowledge proofs. However, they still require significant development
in order to achieve the functionality that most existing anonymous credential schemes provide. Encoding multiple attributes of the credential holder in such a way that they can be disclosed selectively with each use of the credential is often seen as a
vital feature of anonymous credentials, and is one that mercurial signatures have not yet implemented. In this paper, we show a simple way to encode attributes in a mercurial signature credential and to regulate which attributes a credential holder can
issue when delegating their credential to another user. We also extend the security model associated with mercurial signatures to account for the inclusion of attributes, and prove the security of our extension with respect to the original mercurial
signature construction.



## 2023/1897

* Title: PRAC: Round-Efficient 3-Party MPC for Dynamic Data Structures
* Authors: Sajin Sasy, Adithya Vadapalli, Ian Goldberg
* [Permalink](https://eprint.iacr.org/2023/1897)
* [Download](https://eprint.iacr.org/2023/1897.pdf)

### Abstract

We present Private Random Access Computations (PRAC), a 3-party Secure Multi-Party Computation (MPC) framework to support random-access data structure algorithms for MPC with efficient communication in terms of rounds and bandwidth. PRAC extends the
state-of-the-art DORAM Duoram with a new implementation, more flexibility in how the DORAM memory is shared, and support for Incremental and Wide DPFs. We then use these DPF extensions to achieve algorithmic improvements in three novel oblivious data
structure protocols for MPC. PRAC exploits the observation that a secure protocol for an algorithm can gain efficiency if the protocol explicitly reveals information leaked by the algorithm inherently. We first present an optimized binary search
protocol that reduces the bandwidth from $O(\lg^2 n)$ to $O(\lg n)$ for obliviously searching over $n$ items. We then present an oblivious heap protocol with rounds reduced from $O(\lg n)$ to $O(\lg \lg n)$ for insertions, and bandwidth reduced from $O(\
lg^2 n)$ to $O(\lg n)$ for extractions. Finally, we also present the first oblivious AVL tree protocol for MPC where no party learns the data or the structure of the AVL tree, and can support arbitrary insertions and deletions with $O(\lg n)$ rounds and
bandwidth. We experimentally evaluate our protocols with realistic network settings for a wide range of memory sizes to demonstrate their efficiency. For instance, we observe our binary search protocol provides $>27\times$ and $>3\times$ improvements
in wall-clock time and bandwidth respectively over other approaches for a memory with $2^{26}$ items; for the same setting our heap's extract-min protocol achieves $>31\times$ speedup in wall-clock time and $>13\times$ reduction in bandwidth.



## 2023/1898

* Title: An Empirical Study of Cross-chain Arbitrage in Decentralized Exchanges * Authors: Ori Mazor, Ori Rottenstreich
* [Permalink](https://eprint.iacr.org/2023/1898)
* [Download](https://eprint.iacr.org/2023/1898.pdf)

### Abstract

Blockchain interoperability refers to the ability of blockchains to share information with each other. Decentralized Exchanges (DEXs) are peer-to-peer marketplaces where traders can exchange cryptocurrencies. Several studies have focused on arbitrage
analysis within a single blockchain, typically in Ethereum. Recently, we have seen a growing interest in cross-chain technologies to create a more interconnected blockchain network. We present a framework to study cross-chain arbitrage in DEXs. We use
this framework to analyze cross-chain arbitrages between two popular DEXs, PancakeSwap and QuickSwap, within a time frame of a month. While PancakeSwap is implemented on a blockchain named BNB Chain, QuickSwap is implemented on a different blockchain
named Polygon. The approach of this work is to study the cross-chain arbitrage through an empirical study. We refer to the number of arbitrages, their revenue as well as to their duration. This work lays the basis for understanding cross-chain arbitrage
and its potential impact on the blockchain technology.



## 2023/1899

* Title: Allowing Blockchain Loans with Low Collateral
* Authors: Tom Azoulay, Uri Carl, Ori Rottenstreich
* [Permalink](https://eprint.iacr.org/2023/1899)
* [Download](https://eprint.iacr.org/2023/1899.pdf)

### Abstract

Collateral is an item of value serving as security for the repayment of a loan. In blockchain-based loans, cryptocurrencies serve as the collateral. The high volatility of cryptocurrencies implies a serious barrier of entry with a common practice that
collateral values equal multiple times the value of the loan. As assets serving as collateral are locked, this requirement prevents many candidates from obtaining loans. In this paper, we aim to make loans more accessible by offering loans with lower
collateral, while keeping the risk for lenders bound. We propose a credit score based on data recovered from the blockchain to predict how likely a potential borrower is to repay a loan. Our protocol does not risk the initial amount granted by liquidity
providers, but only risks part of the interest yield gained from the borrower by the protocol in the past.



## 2023/1900

* Title: Proof of Compliance for Anonymous, Unlinkable Messages
* Authors: Mingxun Zhou, Elaine Shi, Giulia Fanti
* [Permalink](https://eprint.iacr.org/2023/1900)
* [Download](https://eprint.iacr.org/2023/1900.pdf)

### Abstract

Anonymous systems are susceptible to malicious activity. For instance, in anonymous payment systems, users may engage in illicit practices like money laundering. Similarly, anonymous federated learning systems decouple user updates to a central machine
learning model from the user's identity; malicious users can manipulate their updates to poison the model. Today, compliance with system-generated rules in such systems can be guaranteed at the level of a single message by utilizing Zero-Knowledge Proofs
(ZKP). However, it remains unclear how to prove compliance for rules that are defined over a collection of a user's messages, without compromising the unlinkability of the messages.

To address this challenge, we propose an efficient protocol called Shuffle-ZKP, which enables users within an unlinkable messaging system to collectively prove their compliance. Our protocol leverages a distributed and private set equality check protocol
along with generic Non-Interactive Zero-Knowledge (NIZK) proof systems. We also provide an additional attributing protocol to identify misbehaving users. We theoretically analyze the protocol's correctness and privacy properties; we then implement and
test it across multiple use cases. Our empirical results show that in use cases involving thousands of users, each user is able to generate a compliance proof within 0.2-10.6 seconds, depending on the use case, while the additional communication overhead
remains under 3KB. Furthermore, the protocol is computationally efficient on the server side; the verification algorithm requires a few seconds to handle thousands of users in all of our use cases.

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