[continued from previous message]

Orion (Xie et al. CRYPTO'22) is a recent plausibly post-quantum zero-knowledge argument system with a linear time prover. It improves over Brakedown (Golovnev et al. ePrint'21 and CRYPTO'23) by reducing proof size and verifier complexity to be
polylogarithmic and additionally adds the zero-knowledge property. The argument system is demonstrated to be concretely efficient with a prover time being the fastest among all existing succinct proof systems and a proof size that is an order of
magnitude smaller than Brakedown. Since its publication in CRYPTO 2022, two revisions have been made to the zk-SNARK. First, there was an issue with how zero-knowledge was handled. Second, Orion was discovered to be unsound, which was then repaired
through the use of a commit-and-prove SNARK as an ``outer'' SNARK.

As we will show in this paper, unfortunately, Orion in its current revision is still unsound (with and without the zero-knowledge property) and we will demonstrate practical attacks on it. We then show how to repair Orion without additional assumptions,
which requies non-trivial fixes when aiming to preserve the linear time prover complexity. The proposed fixes lead to an even improved efficiency, i.e., smaller proof size and verifier time, over the claimed efficiency of the initial version of Orion.
Moreover, we provide the first rigorous security proofs and explicitly consider multi-point openings and non-interactivity. While revisiting Orion we make some additional contributions which might be of independent interest, most notable an improved code
randomization technique that retains the minimum relative distance.



## 2024/1165

* Title: Respire: High-Rate PIR for Databases with Small Records
* Authors: Alexander Burton, Samir Jordan Menon, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1165)
* [Download](https://eprint.iacr.org/2024/1165.pdf)

### Abstract

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, and recent works have made significant progress on reducing the concrete computational costs of single-server PIR. However, existing constructions have high
communication overhead, especially for databases with small records. In this work, we introduce Respire, a lattice-based PIR scheme tailored for databases of small records. To retrieve a single record from a database with over a million 256-byte records,
the Respire protocol requires just 6.1 KB of online communication; this is a 5.9x reduction compared to the best previous lattice-based scheme. Moreover, Respire naturally extends to support batch queries. Compared to previous communication-efficient
batch PIR schemes, Respire achieves a 3.4-7.1x reduction in total communication while maintaining comparable throughput (200-400 MB/s). The design of Respire relies on new query compression and response packing techniques based on ring switching in
homomorphic encryption.



## 2024/1166

* Title: On the Relationship between FuncCPA and FuncCPA+
* Authors: Takumi Shinozaki, Keisuke Tanaka, Masayuki Tezuka, Yusuke Yoshida
* [Permalink](https://eprint.iacr.org/2024/1166)
* [Download](https://eprint.iacr.org/2024/1166.pdf)

### Abstract

Akavia, Gentry, Halevi, and Vald introduced the security notion of function-chosen-plaintext-attack (FuncCPA security) for public-key encryption schemes.
FuncCPA is defined by adding a functional re-encryption oracle to the IND-CPA game.
This notion is crucial for secure computation applications where the server is allowed to delegate a part of the computation to the client.

Dodis, Halevi, and Wichs introduced a stronger variant called FuncCPA$^+$.
They showed FuncCPA$^+$ implies FuncCPA and conjectured that FuncCPA$^+$ is strictly stronger than FuncCPA.
They left an open problem to clarify the relationship between these variants.

Contrary to their conjecture, we show that FuncCPA is equivalent to FuncCPA$^+$.
We show it by two proofs with a trade-off between the number of queries and the number of function inputs.
Furthermore, we show these parameters determine the security levels of FuncCPA and FuncCPA$^+$.



## 2024/1167

* Title: Expanding the Toolbox: Coercion and Vote-Selling at Vote-Casting Revisited
* Authors: Tamara Finogina, Javier Herranz, Peter B. Roenne
* [Permalink](https://eprint.iacr.org/2024/1167)
* [Download](https://eprint.iacr.org/2024/1167.pdf)

### Abstract

Coercion is a challenging and multi-faceted threat that prevents people from expressing their will freely. Similarly, vote-buying does to undermine the foundation of free democratic elections. These threats are especially dire for remote electronic
voting, which relies on voters to express their political will freely but happens in an uncontrolled environment outside the polling station and the protection of the ballot booth. However, electronic voting in general, both in-booth and remote, faces a
major challenge, namely to ensure that voters can verify that their intent is captured correctly without providing a receipt of the cast vote to the coercer or vote buyer.

Even though there are known techniques to resist or partially mitigate coercion and vote-buying, we explicitly demonstrate that they generally underestimate the power of malicious actors by not accounting for current technological tools that could
support coercion and vote-selling.

In this paper, we give several examples of how a coercer can force voters to comply with his demands or how voters can prove how they voted. To do so, we use tools like blockchains, delay encryption, privacy-preserving smart contracts, or trusted
hardware. Since some of the successful coercion attacks occur on voting schemes that were supposed/claimed/proven to be coercion-resistant or receipt-free, the main conclusion of this work is that the coercion models should be re-evaluated, and new
definitions of coercion and receipt-freeness are necessary. We propose such new definitions as part of this paper and investigate their implications.



## 2024/1168

* Title: Time is not enough: Timing Leakage Analysis on Cryptographic Chips via Plaintext-Ciphertext Correlation in Non-timing Channel
* Authors: Congming Wei, Guangze Hong, An Wang, Jing Wang, Shaofei Sun, Yaoling Ding, Liehuang Zhu, Wenrui Ma
* [Permalink](https://eprint.iacr.org/2024/1168)
* [Download](https://eprint.iacr.org/2024/1168.pdf)

### Abstract

In side-channel testing, the standard timing analysis works when the vendor can provide a measurement to indicate the execution time of cryptographic algorithms. In this paper, we find that there exists timing leakage in power/electromagnetic channels,
which is often ignored in traditional timing analysis. Hence a new method of timing analysis is proposed to deal with the case where execution time is not available. Different execution time leads to different execution intervals, affecting the
locations of plaintext and ciphertext transmission. Our method detects timing leakage by studying changes in plaintext-ciphertext correlation when traces are aligned forward and backward. Experiments are then carried out on different cryptographic
devices. Furthermore, we propose an improved timing analysis framework which gives appropriate methods for different scenarios.



## 2024/1169

* Title: Attacking Tropical Stickel Protocol by MILP and Heuristic Optimization Techniques
* Authors: Sulaiman Alhussaini, Serge˘ı Sergeev
* [Permalink](https://eprint.iacr.org/2024/1169)
* [Download](https://eprint.iacr.org/2024/1169.pdf)

### Abstract

Known attacks on the tropical implementation of Stickel protocol involve solving a minimal covering problem, and this leads to an exponential growth in the time required to recover the secret key as the used polynomial degree increases. Consequently, it
can be argued that Alice and Bob can still securely execute the protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some
other semirings with idempotent addition (such as the max-min or fuzzy semiring). In this paper, we propose alternative methods to attacking Stickel protocol that avoid this minimal covering problem and the associated exponential time complexity. These
methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain global optimization techniques.



## 2024/1170

* Title: Rudraksh: A compact and lightweight post-quantum key-encapsulation mechanism
* Authors: Suparna Kundu, Archisman Ghosh, Angshuman Karmakar, Shreyas Sen, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/1170)
* [Download](https://eprint.iacr.org/2024/1170.pdf)

### Abstract

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data. In the face of the impending threat of
quantum computers on our public-key infrastructure, it is impossible to imagine the security and privacy of our digital world without integrating post-quantum cryptography (PQC) into these devices. Usually, due to the resource constraints of these
devices, the cryptographic schemes in these devices have to operate with very small memory and consume very little power. Therefore, we must provide a lightweight implementation of existing PQC schemes by possibly trading off the efficiency. The other
option that can potentially provide the most optimal result is by designing PQC schemes suitable for lightweight and low-power-consuming implementation. Unfortunately, the latter method has been largely ignored in PQC research.

In this work, we first provide a lightweight CCA-secure PQ key-encapsulation mechanism (KEM) design based on hard lattice problems. We have done a scrupulous and extensive analysis and evaluation of different design elements, such as polynomial size,
field modulus structure, reduction algorithm, secret and error distribution, etc., of a lattice-based KEM. We have optimized each of them to obtain a lightweight design. Our design provides a $100$ bit of PQ security and shows $\sim3$x improvement in
terms of area with respect to the state-of-the-art Kyber KEM, a PQ standard.



## 2024/1171

* Title: Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
* Authors: Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, Yuping Ye
* [Permalink](https://eprint.iacr.org/2024/1171)
* [Download](https://eprint.iacr.org/2024/1171.pdf)

### Abstract

In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group $G$ with a generator $g$ and a prime order $N$, and we want to prepare some advice of size $S$, such that we can efficiently distinguish $(g^{x},g^{y},g^{xy})$
from $(g^{x},g^{y},g^{z})$ in time $T$ for uniformly and independently chosen $x,y,z$ from $\mathbb{Z}_N$. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes, such as the Diffie–Hellman key
exchange protocol.

We prove that any generic preprocessing DDH algorithm (operating in any cyclic group) achieves advantage at most $O(ST^2 / N)$. This bound matches the best known attack up to poly-log factors, and confirms that DDH is as secure as the (seemingly harder)
discrete logarithm problem against preprocessing attacks. Our result resolves an open question by Corrigan-Gibbs and Kogan (EUROCRYPT 2018), who proved optimal bounds for many variants of discrete logarithm problems except DDH (with an $\tilde{O}(\sqrt{
ST^2/N})$ bound).

We obtain our results by adopting and refining the approach by Gravin, Guo, Kwok, Lu (SODA 2021) and by Yun (EUROCRYPT 2015). Along the way, we significantly simplified and extended the above techniques which may be of independent interest.
The highlights of our techniques are as follows:

(1) We obtain a simpler reduction from decisional problems against $S$-bit advice to their $S$-wise XOR lemmas against zero-advice, recovering the reduction by Gravin, Guo, Kwok and Lu (SODA 2021).
(2) We show how to reduce generic hardness of decisional problems to their variants in the simpler hyperplane query model proposed by Yun (EUROCRYPT 2015). This is the first work analyzing a decisional problem in Yun's model, answering an open problem
proposed by Auerbach, Hoffman, and Pascual-Perez (TCC 2023).
(3) We prove an $S$-wise XOR lemma of DDH in Yun's model. As a corollary, we obtain the generic hardness of the $S$-XOR DDH problem.



## 2024/1172

* Title: Generalized class group actions on oriented elliptic curves with level structure
* Authors: Sarah Arpin, Wouter Castryck, Jonathan Komada Eriksen, Gioella Lorenzon, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1172)
* [Download](https://eprint.iacr.org/2024/1172.pdf)

### Abstract

We study a large family of generalized class groups of imaginary quadratic orders $O$ and prove that they act freely and (essentially) transitively on the set of primitively $O$-oriented elliptic curves over a field $k$ (assuming this set is non-empty)
equipped with appropriate level structure. This extends, in several ways, a recent observation due to Galbraith, Perrin and Voloch for the ray class group. We show that this leads to a reinterpretation of the action of the class group of a suborder $O' \
subseteq O$ on the set of $O'$-oriented elliptic curves, discuss several other examples, and briefly comment on the hardness of the corresponding vectorization problems.



## 2024/1173

* Title: Cryptanalysis of Rank-2 Module-LIP with Symplectic Automorphisms
* Authors: Hengyi Luo, Kaijie Jiang, Yanbin Pan, Anyu Wang
* [Permalink](https://eprint.iacr.org/2024/1173)
* [Download](https://eprint.iacr.org/2024/1173.pdf)

### Abstract

At Eurocrypt'24, Mureau et al. formally defined the Lattice Isomorphism Problem for module lattices (module-LIP) in a number field $\mathbb{K}$, and proposed a heuristic randomized algorithm solving module-LIP for modules of rank 2 in $\mathbb{K}^2$ with
a totally real number field $\mathbb{K}$, which runs in classical polynomial time for a large class of modules and a large class of totally real number field under some reasonable number theoretic assumptions. In this paper, by introducing a (pseudo)
symplectic automorphism of the module, we successfully reduce the problem of solving module-LIP over CM number field to the problem of finding certain symplectic automorphism. Furthermore, we show that a weak (pseudo) symplectic automorphism can be
computed efficiently, which immediately turns out to be the desired automorphism when the module is in a totally real number field. This directly results in a provable deterministic polynomial-time algorithm solving module-LIP for rank-2 modules in $\
mathbb{K}^2$ where $\mathbb{K}$ is a totally real number field, without any assumptions or restrictions on the modules and the totally real number fields. Moreover, the weak symplectic automorphism can also be utilized to invalidate the omSVP assumption
employed in HAWK's forgery security analysis, although it does not yield any actual attacks against HAWK itself.



## 2024/1174

* Title: Grafted Trees Bear Better Fruit: An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack against Kyber
* Authors: Jinnuo Li, Chi Cheng, Muyan Shen, Peng Chen, Qian Guo, Dongsheng Liu, Liji Wu, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1174)
* [Download](https://eprint.iacr.org/2024/1174.pdf)

### Abstract

As a prominent category of side-channel attacks (SCAs), plaintext-checking (PC) oracle-based SCAs offer the advantages of generality and operational simplicity on a targeted device. At TCHES 2023, Rajendran et al. and Tanaka et al. independently proposed
the multiple-valued (MV) PC oracle, significantly reducing the required number of queries (a.k.a., traces) in the PC oracle. However, in practice, when dealing with environmental noise or inaccuracies in the waveform classifier, they still rely on
majority voting or the other technique that usually results in three times the number of queries compared to the ideal case.


In this paper, we propose an improved method to further reduce the number of queries of the MV-PC oracle, particularly in scenarios where the oracle is imperfect. Compared to the state-of-the-art at TCHES 2023, our proposed method reduces the number of
queries for a full key recovery by more than $42.5\%$. The method involves three rounds. Our key observation is that coefficients recovered in the first round can be regarded as prior information to significantly aid in retrieving coefficients in the
second round. This improvement is achieved through a newly designed grafted tree. Notably, the proposed method is generic and can be applied to both the NIST key encapsulation mechanism (KEM) standard Kyber and other significant candidates, such as Saber
and Frodo. We have conducted extensive software simulations against Kyber-512, Kyber-768, Kyber-1024, FireSaber, and Frodo-1344 to validate the efficiency of the proposed method. An electromagnetic attack conducted on real-world implementations, using
an STM32F407G board equipped with an ARM Cortex-M4 microcontroller and Kyber implementation from the public library \textit{pqm4}, aligns well with our simulations.



## 2024/1175

* Title: AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities
* Authors: Vlasis Koutsos, Sankarshan Damle, Dimitrios Papadopoulos, Sujit Gujar, Dimitris Chatzopoulos
* [Permalink](https://eprint.iacr.org/2024/1175)
* [Download](https://eprint.iacr.org/2024/1175.pdf)

### Abstract

In crowdsourcing systems, requesters publish tasks, and interested workers provide answers to get rewards. Worker anonymity motivates participation since it protects their privacy. Anonymity with unlinkability is an enhanced version of anonymity because
it makes it impossible to ``link'' workers across the tasks they participate in. Another core feature of crowdsourcing systems is worker quality which expresses a worker's trustworthiness and quantifies their historical performance. In this work, we
present AVeCQ, the first crowdsourcing system that reconciles these properties, achieving enhanced anonymity and verifiable worker quality updates. AVeCQ relies on a suite of cryptographic tools, such as zero-knowledge proofs, to (i) guarantee workers'
privacy, (ii) prove the correctness of worker quality scores and task answers, and (iii) commensurate payments. AVeCQ is developed modularly, where requesters and workers communicate over a platform that supports pseudonymity, information logging, and
payments. To compare AVeCQ with the state-of-the-art, we prototype it over Ethereum. AVeCQ outperforms the state-of-the-art in three popular crowdsourcing tasks (image annotation, average review, and Gallup polls). E.g., for an Average Review task with 5
choices and 128 workers AVeCQ is 40% faster (including computing and verifying necessary proofs, and blockchain transaction processing overheads) with the task's requester consuming 87% fewer gas.



## 2024/1176

* Title: A zero-trust swarm security architecture and protocols
* Authors: Alex Shafarenko
* [Permalink](https://eprint.iacr.org/2024/1176)
* [Download](https://eprint.iacr.org/2024/1176.pdf)

### Abstract

This report presents the security protocols and general trust architecture of the SMARTEDGE swarm computing platform. Part 1 describes the coordination protocols for use in a swarm production environment, e.g. a smart factory, and Part 2 deals with crowd-
sensing scenarios characteristic of traffic-control swarms.



## 2024/1177

* Title: Cryptanalysis of two post-quantum authenticated key agreement protocols
* Authors: Mehdi Abri, Hamid Mala
* [Permalink](https://eprint.iacr.org/2024/1177)
* [Download](https://eprint.iacr.org/2024/1177.pdf)

### Abstract

As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable
the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new protocols
that are resistant to quantum attacks has become essential. Extensive research in this area had led to the design of several post-quantum AKA schemes.
In this paper, we analyze two post-quantum AKA schemes proposed by Dharminder et al. [2022] and Pursharthi and Mishra. [2024] and demonstrate that these schemes are not secure against active adversaries. An adversary can impersonate an authorized user
to the server. We then propose reliable solutions to prevent these attacks.



## 2024/1178

* Title: Towards Quantum-Safe Blockchain: Exploration of PQC and Public-key Recovery on Embedded Systems
* Authors: Dominik Marchsreiter
* [Permalink](https://eprint.iacr.org/2024/1178)
* [Download](https://eprint.iacr.org/2024/1178.pdf)

### Abstract

Blockchain technology ensures accountability,
transparency, and redundancy in critical applications, includ-
ing IoT with embedded systems. However, the reliance on
public-key cryptography (PKC) makes blockchain vulnerable to
quantum computing threats. This paper addresses the urgent
need for quantum-safe blockchain solutions by integrating Post-
Quantum Cryptography (PQC) into blockchain frameworks.
Utilizing algorithms from the NIST PQC standardization pro-
cess, we aim to fortify blockchain security and resilience, partic-
ularly for IoT and embedded systems. Despite the importance
of PQC, its implementation in blockchain systems tailored for
embedded environments remains underexplored. We propose
a quantum-secure blockchain architecture, evaluating various
PQC primitives and optimizing transaction sizes through tech-
niques such as public-key recovery for Falcon, achieving up
to 17% reduction in transaction size. Our analysis identifies
Falcon-512 as the most suitable algorithm for quantum-secure
blockchains in embedded environments, with XMSS as a viable
stateful alternative. However, for embedded devices, Dilithium
demonstrates a higher transactions-per-second (TPS) rate
compared to Falcon, primarily due to Falcon’s slower sign-
ing performance on ARM CPUs. This highlights the signing
time as a critical limiting factor in the integration of PQC
within embedded blockchains. Additionally, we integrate smart
contract functionality into the quantum-secure blockchain,
assessing the impact of PQC on smart contract authentication.
Our findings demonstrate the feasibility and practicality of
deploying quantum-secure blockchain solutions in embedded
systems, paving the way for robust and future-proof IoT
applications.

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