[digest] 2023 Week 4

[IACR ePrint Archive]

## In this issue

1. [2023/67] Blind signatures from Zero-knowledge arguments
2. [2023/68] Privacy-Preserving Decision Tree Classification ...
3. [2023/69] On the (Im)plausibility of Public-Key Quantum Money ...
4. [2023/70] A new side-channel attack on RSA prime numbers ...
5. [2023/71] A security analysis comparison between Signal, ...
6. [2023/72] Non-Interactive Secure Computation of Inner-Product ...
7. [2023/73] FssNN: Communication-Efficient Secure Neural ...
8. [2023/74] Random Sources in Private Computation
9. [2023/75] Silicon Echoes: Non-Invasive Trojan and Tamper ...
10. [2023/76] Bake It Till You Make It: Heat-induced Leakage from ...
11. [2023/77] Lattice-Based Blind Signatures: Short, Efficient, ...
12. [2023/78] An Efficient Multi-Signature Scheme for Blockchain
13. [2023/79] The challenges of proving solvency while preserving ...
14. [2023/80] PLASMA: Private, Lightweight Aggregated Statistics ...
15. [2023/81] Parakeet: Practical Key Transparency for End-to-End ...
16. [2023/82] Specialized Proof of Confidential Knowledge (SPoCK)
17. [2023/83] MacORAMa: Optimal Oblivious RAM with Integrity
18. [2023/84] Single-tiered hybrid PoW consensus protocol to ...
19. [2023/85] The Security of ChaCha20-Poly1305 in the Multi-user ...
20. [2023/86] Flyover: A Repayment Protocol for Fast Bitcoin ...
21. [2023/87] Verification of Correctness and Security Properties ...
22. [2023/88] Individual Cryptography
23. [2023/89] Compilation and Backend-Independent Vectorization ...
24. [2023/90] Unlimited Results: Breaking Firmware Encryption of ...
25. [2023/91] Satisfiability Modulo Finite Fields
26. [2023/92] Estimation of Shor's Circuit for 2048-bit Integers ...
27. [2023/93] Automated Side-Channel Attacks using Black-Box ...
28. [2023/94] Portunus: Re-imagining access control in ...
29. [2023/95] On TLS for the Internet of Things, in a Post ...
30. [2023/96] MPC With Delayed Parties Over Star-Like Networks
31. [2023/97] Universally Composable NIZKs: Circuit-Succinct, ...
32. [2023/98] Belief Propagation Meets Lattice Reduction: ...
33. [2023/99] Scalable Multiparty Garbling
34. [2023/100] Meteor: Improved Secure 3-Party Neural Network ...
35. [2023/101] Practical Preimage Attack on 3-Round Keccak-256
36. [2023/102] Cache-timing attack against HQC
37. [2023/103] Fair Delivery of Decentralised Randomness Beacon
38. [2023/104] Optimizations and Trade-offs for HElib
39. [2023/105] Gate-Level Masking of Streamlined NTRU Prime ...
40. [2023/106] Deuring for the People: Supersingular Elliptic ...
41. [2023/107] The Tip5 Hash Function for Recursive STARKs
42. [2023/108] Grotto: Screaming fast $(2 + 1)$-PC for ...
43. [2023/109] SoK: Modeling for Large S-boxes Oriented to ...

## 2023/67

* Title: Blind signatures from Zero-knowledge arguments
* Authors: Paulo L. Barreto, Gustavo H. M. Zanon
* [Permalink](https://eprint.iacr.org/2023/067)
* [Download](https://eprint.iacr.org/2023/067.pdf)

### Abstract

We propose a novel methodology to obtain $B$lind signatures that is fundamentally based on the idea of hiding part of the underlying plain signatures under a $Z$ero-knowledge argument of knowledge of the whole signature (hence the shorthand, $BZ$). Our proposal is necessarily non-black-box and stated in the random oracle model. We illustrate the technique by describing two instantiations: a classical setting based on the traditional discrete logarithm assumption, and a post-quantum setting based on the commutative supersingular isogeny Diffie-Hellman (CSIDH) assumption.



## 2023/68

* Title: Privacy-Preserving Decision Tree Classification Using VBB-Secure Cryptographic Obfuscation
* Authors: Shalini Banerjee, Steven D. Galbraith, Giovanni Russello
* [Permalink](https://eprint.iacr.org/2023/068)
* [Download](https://eprint.iacr.org/2023/068.pdf)

### Abstract

The use of data as a product and service has given momentum to the extensive uptake of complex machine learning algorithms that focus on performing prediction with popular tree-based methods such as decision trees classifiers. With increasing adoption over a wide array of sensitive applications, a significant need to protect the confidentiality of the classifier model and user data is identified. The existing literature safeguards them using interactive solutions based on expensive cryptographic approaches, where an encrypted classifier model interacts with the encrypted queries and forwards the encrypted classification to the user. Adding to that, the state-of-art protocols for protecting the privacy of the model do not contain model-extraction attacks.

We design an efficient virtual black-box obfuscator for binary decision trees and use the random oracle paradigm to analyze the security of our construction. To thwart model-extraction attacks, we restrict to evasive decision trees, as black-box access to the classifier does not allow a PPT adversary to extract the model. While doing so, we present an encoder for hiding parameters in an interval-membership function. Our exclusive goal behind designing the obfuscator is that, not only will the solution increase the class of functions that has cryptographically secure obfuscators, but also address the open problem of non-interactive prediction in privacy-preserving classification using computationally inexpensive cryptographic hash functions.



## 2023/69

* Title: On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
* Authors: Prabhanjan Ananth, Zihan Hu, Henry Yuen
* [Permalink](https://eprint.iacr.org/2023/069)
* [Download](https://eprint.iacr.org/2023/069.pdf)

### Abstract

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge.

These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry's compressed oracle technique.



## 2023/70

* Title: A new side-channel attack on RSA prime numbers generation
* Authors: Isac Iulian-George, Emil Simion
* [Permalink](https://eprint.iacr.org/2023/070)
* [Download](https://eprint.iacr.org/2023/070.pdf)

### Abstract

The purpose of this article is to present,illustrate and to put in evidence a new side-
channel attack on RSA cryptosystem based on the generation of prime numbers. The
vulnerability of the cryptosystem is spotted during the execution of the key generation step.The probability of success of the attack is around 10-15% in the case of realistic parameters



## 2023/71

* Title: A security analysis comparison between Signal, WhatsApp and Telegram
* Authors: Corina-Elena Bogos, Răzvan Mocanu, Emil Simion
* [Permalink](https://eprint.iacr.org/2023/071)
* [Download](https://eprint.iacr.org/2023/071.pdf)

### Abstract

This paper aims to provide a security analysis comparison between three popular instant messaging apps: Signal, WhatsApp and Telegram. The analysis will focus on the encryption protocols used by each app and the security features they offer. The paper will evaluate the strengths and weaknesses of each app, and provide a summary of their overall security posture. Additionally, this paper will discuss other considerations such as user base, data collection and usage policies, and other features which may impact the security of the apps. The results of this analysis will provide insights for individuals and organizations looking to choose a secure instant messaging app for their communication needs.
In this paper we reviewed the main encryption standards and we compared the features, traffic analysis, protocols, performance and recent security breaches for WhatsApp, Signal and Telegram. The paper includes packet sniffing using Wireshark and Fiddler.



## 2023/72

* Title: Non-Interactive Secure Computation of Inner-Product from LPN and LWE
* Authors: Geoffroy Couteau, Maryam Zarezadeh
* [Permalink](https://eprint.iacr.org/2023/072)
* [Download](https://eprint.iacr.org/2023/072.pdf)

### Abstract

We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors.

We give constructions of this primitive from a common template, which can be instantiated under either the LPN (with non-negligible correctness error) or the LWE (with negligible correctness error) assumptions. Our construction uses a novel twist on the standard non-interactive key exchange based on the Alekhnovich cryptosystem, which upgrades it to a non-interactive inner product protocol almost for free. In addition to being non-interactive, our constructions have linear communication (with constants smaller than all known alternatives) and small computation: using LPN or LWE with quasi-cyclic codes, we estimate that encoding a length-$2^{20}$ vector over a 32-bit field takes less that 2s on a standard laptop; decoding amounts to a single cheap inner-product.

We show how to remove the non-negligible error in our LPN instantiation using a one-time, logarithmic-communication preprocessing. Eventually, we show to to upgrade its security to the malicious model using new sublinear-communication zero-knowledge proofs for low-noise LPN samples, which might be of independent interest.



## 2023/73

* Title: FssNN: Communication-Efficient Secure Neural Network Training via Function Secret Sharing
* Authors: Peng Yang, Zoe L. Jiang, Shiqi Gao, Jiehang Zhuang, Hongxiao Wang, Junbin Fang, Siuming Yiu, Yulin Wu
* [Permalink](https://eprint.iacr.org/2023/073)
* [Download](https://eprint.iacr.org/2023/073.pdf)

### Abstract

This Paper proposes FssNN, a communication-efficient secure two-party computation framework for evaluating privacy-preserving neural network via function secret sharing (FSS) in semi-honest adversary setting. In FssNN, two parties with input data in secret sharing form perform secure linear computations using additive secret haring and non-linear computations using FSS, and obtain secret shares of model parameters without disclosing their input data. To decrease communication cost, we split the protocol into online and offline phases where input-independent correlated randomness is generated in offline phase while only lightweight ``non-cryptographic'' computations are executed in online phase. Specifically, we propose $\mathsf{BitXA}$ to reduce online communication in linear computation, DCF to reduce key size of the FSS scheme used in offline phase for nonlinear computation. To further support neural network training, we enlarge the input size of neural network to $2^{32}$ via ``MPC-friendly'' PRG.

We implement the framework in Python and evaluate the end-to-end system for private training between two parties on standard neural networks. FssNN achieves on MNIST dataset an accuracy of 98.0%, with communication cost of 27.52GB and runtime of 0.23h per epoch in the LAN settings. That shows our work advances the state-of-the-art secure computation protocol for neural networks.



## 2023/74

* Title: Random Sources in Private Computation
* Authors: Geoffroy Couteau, Adi Rosén
* [Permalink](https://eprint.iacr.org/2023/074)
* [Download](https://eprint.iacr.org/2023/074.pdf)

### Abstract

We consider multi-party information-theoretic private computation. Such computation inherently requires the use of local randomness by the parties, and the question of minimizing the total number of random bits used for given private computations has received considerable attention in the literature.

In this work we are interested in another question: given a private computation, we ask how many of the players need to have access to a random source, and how many of them can be deterministic parties. We are further interested in the possible interplay between the number of random sources in the system and the total number of random bits necessary for the computation.

We give a number of results. We first show that, perhaps surprisingly, $t$ players (rather than $t+1$) with access to a random source are sufficient for the information-theoretic $t$-private computation of any deterministic functionality over $n$ players for any $t<n/2$; by a result of (Kushilevitz and Mansour, PODC'96), this is best possible. This means that, counter intuitively, while private computation is impossible without randomness, it is possible to have a private computation even when the adversary can control all parties who can toss coins (and therefore sees all random coins). For randomized functionalities we show that $t+1$ random sources are necessary (and sufficient).

We then turn to the question of the possible interplay between the number of random sources and the necessary number of random bits. Since for only very few settings in private computation meaningful bounds on the number of necessary random bits are known, we consider the AND function, for which some such bounds are known. We give a new protocol to $1$-privately compute the $n$-player AND function, which uses a single random source and $6$ random bits tossed by that source. This improves, upon the currently best known results (Kushilevitz et al., TCC'19), at the same time the number of sources and the number of random bits (KOPRT19 gives a $2$-source, $8$-bits protocol). This result gives maybe some evidence that for $1$-privacy, using the minimum necessary number of sources one can also achieve the necessary minimum number of random bits. We believe however that our protocol is of independent interest for the study of randomness in private computation.



## 2023/75

* Title: Silicon Echoes: Non-Invasive Trojan and Tamper Detection using Frequency-Selective Impedance Analysis
* Authors: Tahoura Mosavirik, Saleh Khalaj Monfared, Maryam Saadat Safa, Shahin Tajik
* [Permalink](https://eprint.iacr.org/2023/075)
* [Download](https://eprint.iacr.org/2023/075.pdf)

### Abstract

The threat of chip-level tampering and its detection is a widely researched field. Hardware Trojan insertions are prominent examples of such tamper events. Altering the placement and routing of a design or removing a part of a circuit for side-channel leakage/fault sensitivity amplification are other instances of such attacks. While semi- and fully-invasive physical verification methods can confidently detect such stealthy tamper events, they are costly, time-consuming, and destructive. On the other hand, virtually all proposed non-invasive side-channel methods suffer from noise and, therefore, have low confidence. Moreover, they require activating the tampered part of the circuit (e.g., the Trojan trigger) to compare and detect the modification. In this work, we introduce a general non-invasive post-silicon tamper detection technique applicable to all sorts of tamper events at the chip level without requiring the activation of the malicious circuit. Our method relies on the fact that all classes of physical modifications (regardless of their physical, activation, or action characteristics) alter the impedance of the chip. Hence, characterizing the impedance can lead to the detection of the tamper events. To sense the changes in the impedance, we deploy known RF tools, namely, scattering parameters, in which we inject sine wave signals with high frequencies to the power distribution network (PDN) of the system and measure the “echo” of the signal. The reflected signals in various frequency bands reveal different tamper events based on their impact size on the die. To validate our claims, we performed extensive measurements on several proof-of-concept tampered hardware implementations realized on an FPGA manufactured with a 28 nm technology. Based on these groundbreaking results, we demonstrate that stealthy hardware Trojans, as well as sophisticated modifications of P&R, can be detected with high confidence.



## 2023/76

* Title: Bake It Till You Make It: Heat-induced Leakage from Masked Neural Networks
* Authors: Dev M. Mehta, Mohammad Hashemi, David S. Koblah, Domenic Forte, Fatemeh Ganji
* [Permalink](https://eprint.iacr.org/2023/076)
* [Download](https://eprint.iacr.org/2023/076.pdf)

### Abstract

Masking has become one of the most effective approaches for securing hardware designs against side-channel attacks. Irrespective of the effort put into correctly implementing masking schemes on a field programmable gate array (FPGA), leakage can be unexpectedly observed. This is due to the fact that the assumption underlying all masked designs, i.e., the leakages of different shares are independent of each other, may no longer hold in practice. In this regard, extreme temperatures have been shown to be an important factor in inducing leakage, even in correctly-masked designs. This has previously been verified using an external heat generator (i.e., a climate chamber). In this paper, we examine whether the leakage can be induced using the circuit components themselves. Specifically, we target masked neural networks (NNs) in FPGAs, with one of the main building blocks being block random access memory (BRAM) and flip-flops (FFs). In this respect, thanks to the inherent characteristics of NNs, our novel internal heat generators leverage solely the memories devoted to storing the user’s input, especially when frequently writing alternating patterns into BRAMs and FFs. The possibility of observing first-order leakage is evaluated by considering one of the most recent and successful first-order secure masked NNs, namely ModuloNET. ModuloNET is specifically designed for FPGAs, where BRAMs are used for storing the inputs and intermediate computations. Our experimental results demonstrate that undesirable first-order leakage can be observed by increasing the temperature when an alternating input is applied to the masked NN. To give a better understanding of the impact of extreme heat, we further perform a similar test on the design with FFs storing the input, where the same conclusion can be drawn.



## 2023/77

* Title: Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal
* Authors: Ward Beullens, Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler
* [Permalink](https://eprint.iacr.org/2023/077)
* [Download](https://eprint.iacr.org/2023/077.pdf)

### Abstract

We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-SIS assumption. We also give a construction of a ``keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. The signature size in this case is only $48$ bytes, but more work needs to be done to explore the efficiency of the protocol which generates the signature.



## 2023/78

* Title: An Efficient Multi-Signature Scheme for Blockchain
* Authors: Mostefa Kara, Abdelkader Laouid, Mohammad Hammoudeh
* [Permalink](https://eprint.iacr.org/2023/078)
* [Download](https://eprint.iacr.org/2023/078.pdf)

### Abstract

Blockchain is a newly emerging technology, however, it has proven effective in many applications because it provides multiple advantages, mainly as it represents a trust system in which data is encrypted in a way that cannot be tampered with or forged. Because it contains many details such as smart contracts, consensus, authentication, etc. the blockchain is a fertile ground for researchers where they can continually improve previous versions of these concepts. This paper introduces a new multi-signature scheme based on RSA. This scheme is designed to reduce the blockchain's size and prevent known attacks and is also applicable in many other settings that require multi-signatures. Our scheme is in the plain public key model, which means nodes do not need to prove knowledge or possession of their private key. In which, whatever the number of signers, the final signature size is equal to $O(k)$ where $k$ is a security parameter and no interaction between signers is needed. To verify that a number of parties have signed a shared message $m$, a verifier needs the signature, list of signers, and the message $m$. The presented practical short accountable-subgroup multi-signature (ASM) scheme allows a valid signature to disclose which subset generated the signature. It is worth noting that our multi-signatures with public key aggregation is an interactive two-round protocol and a multi-signature model applied to the entire block and not to individual transactions.



## 2023/79

* Title: The challenges of proving solvency while preserving privacy.
* Authors: Tabacaru Robert, Anghel Florin, Asandoaiei David, Simion Emil
* [Permalink](https://eprint.iacr.org/2023/079)
* [Download](https://eprint.iacr.org/2023/079.pdf)

### Abstract

The increasing popularity of blockchain technology has affected the way we view many fields related to computer science, with E-commerce being no exception. The distributed nature and transparency of blockchain-based systems is one of its main perks, but it also raises some issues
when it comes to privacy.
Zero-knowledge proofs are very powerful building blocks when it comes to building privacy-preserving protocols, so, naturally, they have attracted a lot of attention in the last years. Following the recent collapse of the very popular crypto exchange FTX, we believe it is important to analyse how such events can be prevented in the future. This paper aims to highlight solutions that use zero-knowledge to prove solvency.



## 2023/80

* Title: PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries with Full Security
* Authors: Dimitris Mouris, Pratik Sarkar, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2023/080)
* [Download](https://eprint.iacr.org/2023/080.pdf)

### Abstract

The private heavy-hitters problem is a data-collection task where many clients possess private bit strings, and data-collection servers aim to identify the most popular strings without learning anything about the clients' inputs. The recent work of Poplar constructed a protocol for private heavy hitters but their solution was susceptible to additive attacks by a malicious server, compromising both the correctness and the security of the protocol.

In this paper, we introduce PLASMA, a private analytics framework that addresses these challenges by using three data-collection servers and a novel primitive, called verifiable incremental distributed point function (VIDPF). PLASMA allows each client to non-interactively send a message to the servers as its input and then go offline. Our new VIDPF primitive employs lightweight techniques based on efficient hashing and allows the servers to non-interactively validate client inputs and preemptively reject malformed ones.

PLASMA drastically reduces the communication overhead incurred by the servers using our novel batched consistency checks. Specifically, our server-to-server communication depends only on the number of malicious clients, as opposed to the total number of clients, yielding a $182\times$ and $235\times$ improvement over Poplar and other state-of-the-art sorting-based protocols respectively. Compared to recent works, PLASMA enables both client input validation and succinct communication, while ensuring full security. At runtime, PLASMA computes the 1000 most popular strings among a set of 1 million client-held 32-bit strings in 67 seconds and 256-bit strings in less than 20 minutes respectively.



## 2023/81

* Title: Parakeet: Practical Key Transparency for End-to-End Encrypted Messaging
* Authors: Harjasleen Malvai, Lefteris Kokoris-Kogias, Alberto Sonnino, Esha Ghosh, Ercan Oztürk, Kevin Lewi, Sean Lawlor
* [Permalink](https://eprint.iacr.org/2023/081)
* [Download](https://eprint.iacr.org/2023/081.pdf)

### Abstract

Encryption alone is not enough for secure end-to-end encrypted messaging: a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components: (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store.

To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed ''compaction'', as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks.



## 2023/82

* Title: Specialized Proof of Confidential Knowledge (SPoCK)
* Authors: Tarak Ben Youssef, Riad S. Wahby
* [Permalink](https://eprint.iacr.org/2023/082)
* [Download](https://eprint.iacr.org/2023/082.pdf)

### Abstract

Flow is a high-throughput blockchain with a dedicated step for executing the transactions in a block and a subsequent verification step performed by Verification Nodes. To enforce integrity of the blockchain, the protocol requires a component that prevents Verification Nodes from approving execution results without checking. In our preceding work, we have sketched out an approach called Specialized Proof of Confidential Knowledge (SPoCK). Using SPoCK, nodes can provide evidence to a third party that they both executed the same transaction sequence without revealing the resulting execution trace. The previous Flow white paper presented a basic implementation of such scheme.
In this note, we introduce a new SPoCK implementation that is more concise and more efficient than the previous proposal. We first provide a formal generic description of a SPoCK scheme as well as its security definition. Then we propose a new construction of SPoCK based on the BLS signature scheme. We support the new scheme with its proof of security under the
appropriate computation assumptions.



## 2023/83

* Title: MacORAMa: Optimal Oblivious RAM with Integrity
* Authors: Surya Mathialagan, Neekon Vafa
* [Permalink](https://eprint.iacr.org/2023/083)
* [Download](https://eprint.iacr.org/2023/083.pdf)

### Abstract

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM queries is necessary assuming $O(1)$ client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.



## 2023/84

* Title: Single-tiered hybrid PoW consensus protocol to encourage decentralization in bitcoin
* Authors: GyuChol.Kim
* [Permalink](https://eprint.iacr.org/2023/084)
* [Download](https://eprint.iacr.org/2023/084.pdf)

### Abstract

We propose a single-tiered hybrid Proof-of-Work consensus protocol to encourage decentralization in bitcoin. Our new mechanism comprises coupled puzzles of which properties differ from each other; the one is the extant outsourceable bitcoin puzzle while the other is non-outsourceable. Our new protocol enables miners to solve either puzzle as they want; therefore, blocks can be generated by either puzzle. Our hybrid consensus can be successfully implemented in bitcoin, because it is backward-compatible with existing bitcoin mining equipment(more precisely, existing bitcoin mining ASICs)



## 2023/85

* Title: The Security of ChaCha20-Poly1305 in the Multi-user Setting
* Authors: Jean Paul Degabriele, Jérôme Govinden, Felix Günther, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2023/085)
* [Download](https://eprint.iacr.org/2023/085.pdf)

### Abstract

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.



## 2023/86

* Title: Flyover: A Repayment Protocol for Fast Bitcoin Transfers over Federated Pegs
* Authors: Javier Álvarez Cid-Fuentes, Diego Angel Masini, Sergio Demian Lerner
* [Permalink](https://eprint.iacr.org/2023/086)
* [Download](https://eprint.iacr.org/2023/086.pdf)

### Abstract

As the number of blockchain projects grows, efficient cross-chain interoperability becomes more necessary. A common cross-chain protocol is the two-way peg, which is typically used to transfer assets between blockchains and their sidechains. The criticality of cross-chain protocols require that they are designed with strong security models, which can reduce usability in the form of long transfer times. In this paper, we present Flyover, a repayment protocol to speed up the transfer of bitcoins over federated pegs by allowing untrusted liquidity providers to advance funds for the users. Transfer times are reduced because liquidity providers do not have the same security requirements as the underlying cross-chain protocol. We illustrate the Flyover protocol on the cross-chain interoperability protocol that connects Bitcoin to the RSK sidechain and show how Flyover can reduce transfer times without reducing security. In addition to this, Flyover extends the cross-chain protocol by allowing liquidity providers to make smart contract calls on RSK on behalf of the user.



## 2023/87

* Title: Verification of Correctness and Security Properties for CRYSTALS-KYBER
* Authors: Katharina Kreuzer
* [Permalink](https://eprint.iacr.org/2023/087)
* [Download](https://eprint.iacr.org/2023/087.pdf)

### Abstract

This paper describes a formalization of the specification and the algorithm of the public key encryption scheme CRYSTALS-KYBER as well as the verification of its $\delta$-correctness and indistinguishability under chosen plaintext attack (IND-CPA) security proof. The algorithms and proofs were formalized with only minimal assumptions in a modular way to verify the proofs for all possible parameter sets. During the formalization in this flexible setting, problems in the correctness proof were uncovered. Furthermore, the security of CRYSTALS-KYBER under IND-CPA was verified using a game-based approach. As the security property does not hold for the original version of CRYSTALS-KYBER, we only show the IND-CPA security for the latest versions. The security proof was verified under the hardness assumption of the module Learning-with-Errors Problem. The formalization was realized in the theorem prover Isabelle and is foundational.



## 2023/88

* Title: Individual Cryptography
* Authors: Stefan Dziembowski, Sebastian Faust, Tomasz Lizurej
* [Permalink](https://eprint.iacr.org/2023/088)
* [Download](https://eprint.iacr.org/2023/088.pdf)

### Abstract

We initiate a formal study of individual cryptography Informally speaking, an algorithm Alg is individual if in every implementation of Alg there always exists an individual user that has full knowledge of the cryptographic secrets S used by Alg. In particular, it should be infeasible to design implementations of this algorithm that would hide the secret S by distributing it between a group of parties using an MPC protocol, or via outsourcing it to a trusted execution environment.



## 2023/89

* Title: Compilation and Backend-Independent Vectorization for Multi-Party Computation
* Authors: Benjamin Levy, Ben Sherman, Muhammad Ishaq, Lindsey Kennard, Ana Milanova, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2023/089)
* [Download](https://eprint.iacr.org/2023/089.pdf)

### Abstract

Recent years have witnessed a push to bring multi-party computation (MPC) to practice and make it accessible to the end user/programmer. Despite novel ideas, on frontend language design (e.g., Wysteria, Viaduct), backend protocol design and implementation (e.g., ABY, MOTION), or both (e.g., SPDZ), classical compiler optimizations remain largely under-utilized (if not completely unused) in MPC programming. A likely reason is that such optimizations are often applied on a middle-end intermediate representation such as SSA.

We put forth a methodology for an MPC programming compilation toolchain, which by mimicking the compilation methodology of standard imperative languages enables middle-end optimizations on MPC, yielding significant improvements. To this direction we devise an MPC circuit compiler that allows MPC programming in what is essentially Python, and inherits the structure (and therefore optimization opportunities) of the classical compilation pipeline. Our key conceptual contribution is advancing an intermediate language, which we call MPC-IR, that can be viewed as the analogue, in an MPC program’s compilation, of (enriched) SSA form. MPC-IR is a particularly appealing intermediate language as it allows backend-independent optimizations, a close analogy to machine independent optimizations in classical compilers. Demonstrating the power of our approach, we focus on a specific
backend-independent optimization, SIMD-vectorization: We devise a novel classical-compiler-inspired automatic SIMD-vectorization on MPC-IR, which we show leads to significant speedup in circuit generation time and running time, as well as significant reduction in communication size and number of gates over the corresponding iterative schedule.

We implement and benchmark our compiler from a Python-like program to an optimized circuit that can be fed into an MPC backend (for our benchmarks we make use of the MOTION backend for MPC). We view our exhaustive benchmarks as both a way to validate our optimization and end-to-end compiler, and as a contribution, by itself, to a more complete benchmarks suite for MPC programming—such benchmarks suites are common in classical compilers.



## 2023/90

* Title: Unlimited Results: Breaking Firmware Encryption of ESP32-V3
* Authors: Karim M. Abdellatif, Olivier Hériveaux, Adrian Thillard
* [Permalink](https://eprint.iacr.org/2023/090)
* [Download](https://eprint.iacr.org/2023/090.pdf)

### Abstract

Because of the rapid growth of Internet of Things (IoT), embedded systems have become an interesting target for experienced attackers. ESP32~\cite{tech-ref-man} is a low-cost and low-power system on chip (SoC) series created by Espressif Systems. The firmware extraction of such embedded systems is a real threat to the manufacturer as it breaks its intellectual property and raises the risk of creating equivalent systems with less effort and resources. In 2019, LimitedResults~\cite{LimitedResultsPown} published power glitch attacks which resulted in dumping secure boot and flash encryption keys stored in the eFuses of ESP32. Therefore, Espressif patched this vulnerability and then advised its customers to use ESP32-V3, which is an updated SoC revision. This new version is hardened against fault injection attacks in hardware and software as announced by Espressif~\cite{ESPpatch}. In this paper, we present for the first time a deep hardware security evaluation for ESP32-V3. The main goal of this evaluation is to extract the firmware encryption key stored in the eFuses. This evaluation includes Fault Injection (FI) and Side-Channel (SC) attacks. First, we use Electromagnetic FI (EMFI) in order to show that ESP32-V3 doesn't resist EMFI. However, by experimental results, we show that this version contains a revised bootloader compared to ESP32-V1, which hardens dumping the eFuse keys by FI. Second, we perform a full SC analysis on the AES accelerator of ESP32-V3. We show that an attacker with a physical access to the device can extract all the keys of the hardware AES-256 after collecting 60K power measurements during the execution of the AES block. Third, we present another SC analysis for the firmware decryption mechanism, by targeting the decryption operation during the power up. Using this knowledge, we demonstrate that the full 256-bit AES firmware encryption key, which is stored in the eFuses, can be recovered by SC analysis using 300K power measurements. Finally, we apply practically the firmware encryption attack on Jade hardware wallet \cite{jade}.



## 2023/91

* Title: Satisfiability Modulo Finite Fields
* Authors: Alex Ozdemir, Gereon Kremer, Cesare Tinelli, Clark Barrett
* [Permalink](https://eprint.iacr.org/2023/091)
* [Download](https://eprint.iacr.org/2023/091.pdf)

### Abstract

We study satisfiability modulo the theory of finite fields and give a
decision procedure for this theory. We implement our procedure for prime
fields inside the cvc5 SMT solver. Using this theory, we construct SMT
queries that verify the correctness of various zero knowledge proof
compilers on various input programs. Our experiments show that our
implementation is vastly superior to previous approaches (which encode
field arithmetic using integers or bit-vectors).



## 2023/92

* Title: Estimation of Shor's Circuit for 2048-bit Integers based on Quantum Simulator
* Authors: Junpei Yamaguchi, Masafumi Yamazaki, Akihiro Tabuchi, Takumi Honda, Tetsuya Izu, Noboru Kunihiro
* [Permalink](https://eprint.iacr.org/2023/092)
* [Download](https://eprint.iacr.org/2023/092.pdf)

### Abstract

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. In the largest case, $N=511$ was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024-bit and 2048-bit integers. In our estimation, Shor's quantum circuit for factoring 1024-bit integers requires $2.78 \times 10^{11}$ gates, and with depth $2.24 \times 10^{11}$, while $2.23 \times 10^{12}$ gates, and with depth $1.80 \times 10^{12}$ for 2048-bit integers.



## 2023/93

* Title: Automated Side-Channel Attacks using Black-Box Neural Architecture Search
* Authors: Pritha Gupta, Jan Peter Drees, Eyke Hüllermeier
* [Permalink](https://eprint.iacr.org/2023/093)
* [Download](https://eprint.iacr.org/2023/093.pdf)

### Abstract

The usage of convolutional neural networks (CNNs) to break cryptographic systems through hardware side-channels has enabled fast and adaptable attacks on devices like smart cards and TPMs. Current literature proposes fixed CNN architectures designed by domain experts to break such systems, which is time-consuming and unsuitable for attacking a new system. Recently, an approach using neural architecture search (NAS), which is able to acquire a suitable architecture automatically, has been explored. These works use the secret key information in the attack dataset for optimization and only explore two different search strategies using one-dimensional CNNs. We propose a NAS approach that relies only on using the profiling dataset for optimization, making it fully black-box. Using a large-scale experimental parameter study, we explore which choices for NAS, such as 1-D or 2-D CNNs and search strategy, produce the best results on 10 state-of-the-art datasets for Hamming weight and identity leakage models. We show that applying the random search strategy on 1-D inputs results in a high success rate and retrieves the correct secret key using a single attack trace on two of the datasets. This combination matches the attack efficiency of fixed CNN architectures, outperforming them in 4 out of 10 datasets. Our experiments also point toward the need for repeated attack evaluations of machine learning-based solutions in order to avoid biased performance estimates.



## 2023/94

* Title: Portunus: Re-imagining access control in distributed systems
* Authors: Watson Ladd, Marloes Venema, Tanya Verma
* [Permalink](https://eprint.iacr.org/2023/094)
* [Download](https://eprint.iacr.org/2023/094.pdf)

### Abstract

TLS termination, which is essential to network and security infrastructure providers, is an extremely latency sensitive operation that benefits from access to sensitive key material close to the edge. However, increasing regulatory concerns prompt customers to demand sophisticated controls on where their keys may be accessed. While traditional access-control solutions rely on a highly available centralized process to enforce access, the round-trip latency and
decreased fault tolerance make this approach unappealing. Furthermore, the desired level of customer control is at odds with customizing the distribution process for each key.

To solve this dilemma, we have designed and implemented Portunus, a cryptographic storage and access control system built using a variant of public-key cryptography called attribute-based encryption (ABE). Using Portunus, TLS keys are protected using ABE under a policy chosen by the customer. Each server is issued unique ABE keys based on its attributes, allowing it to decrypt only the TLS keys for which it satisfies the policy. Thus, the encrypted keys can be stored at the edge, with access control enforced passively through ABE. If a server receives a TLS connection but is not authorized to decrypt the necessary TLS key, the request is forwarded directly to the nearest authorized server, further avoiding the need for a centralized coordinator. In comparison, a trivial instantiation of this system using standard public-key cryptography might wrap each TLS key with the key of every authorized data center. This strategy, however, multiplies the storage overhead by the number of data centers. We have deployed Portunus on Cloudflare's global network of over 400 data centers. Our measurements indicate that we can handle millions of requests per second globally, making it one of the largest deployments of ABE.



## 2023/95

* Title: On TLS for the Internet of Things, in a Post Quantum world
* Authors: Michael Scott
* [Permalink](https://eprint.iacr.org/2023/095)
* [Download](https://eprint.iacr.org/2023/095.pdf)

### Abstract

The TLS (Transport Layer Security) protocol is the most important, most attacked, most analysed and most used cryptographic protocol in the world today. TLS is critical to the integrity of the Internet, and if it were to be broken e-commerce would become impossible, with very serious implications for the global economy. Furthermore TLS is likely to assume even greater significance in the near future with the rapid growth of an Internet of Things (IoT) -- a multiplicity of internet connected devices all engaged in secure inter-communication. However the impending invention of a Cryptographically Relevant Quantum Computer (CRQC) would represent an existential threat to TLS in its current form. As it stands the latest version TLS1.3, benefiting as it does from years of research and study, provides effective security, but it must soon be updated to resist this new threat. In this research we first undertake a new clean-room implementation of a small-footprint open source TLS1.3, written in C++ and Rust, and suitable for IoT applications. Our implementation is designed to be cryptographically agile, so that it can easily accomodate new post-quantum cryptographic primitives. Next we use this new implementation as a vehicle to study the impact of going post-quantum, with a particular emphasis on the impact on the Internet of Things. Finally we showcase the flexibility of our implementation by proposing an implementation of TLS that uses identity-based encryption to mitigate this impact.



## 2023/96

* Title: MPC With Delayed Parties Over Star-Like Networks
* Authors: Mariana Gama, Emad Heydari Beni, Emmanuela Orsini, Nigel P. Smart, Oliver Zajonc
* [Permalink](https://eprint.iacr.org/2023/096)
* [Download](https://eprint.iacr.org/2023/096.pdf)

### Abstract

While the efficiency of secure multi-party computation protocols has greatly increased in the last few years, these improvements and protocols are often based on rather unrealistic, idealised, assumptions about how technology is deployed in the real world. In this work we examine multi-party computation protocols in the presence of two major constraints present in deployed systems. Firstly, we consider the situation where the parties are connected not by direct point-to-point connections, but by a star-like topology with a few central post-office style relays. Secondly, we consider MPC protocols with a strong honest majority ($n \gg t/2$) in which we have stragglers (some parties are progressing slower than others). We model stragglers by allowing the adversary to delay messages to and from some parties for a given length of time.

We first show that having only a single honest rely is enough to ensure consensus of the messages sent within a protocol; secondly, we show that special care must be taken to describe multiplication protocols in the case of relays and stragglers and that some well known protocols do not guarantee privacy and correctness in this setting; thirdly, we present an efficient honest-majority MPC protocol which can be run on top of the relays and which provides active-security with abort in the case of a strong honest majority, even when run with stragglers. We back up our protocol presentation with both experimental evaluations and simulations of the effect of the relays and delays on our protocol.



## 2023/97

* Title: Universally Composable NIZKs: Circuit-Succinct, Non-Malleable and CRS-Updatable
* Authors: Behzad Abdolmaleki, Noemi Glaeser, Sebastian Ramacher, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2023/097)
* [Download](https://eprint.iacr.org/2023/097.pdf)

### Abstract

Non-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (so called zk-SNARKs) increasingly see real-world adoption in large and complex systems.

A requirement that turns out to be important for NIZKs is ensuring non-malleability of proofs, which can be achieved via the property of simulation extractability (SE). Moreover, many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and in practice it is desirable to reduce the trust in the CRS generation. Latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large and complex systems is the secure composition of protocols, e.g., via using the Universal Composability (UC) framework. Relying on the UC frameworks allows to arbitrarily and securely compose protocols in a modular way.

In this work, we are interested in whether zk-SNARKs can provide all these desired properties. This is a tricky task as the UC framework rules out several natural techniques for such a construction. Our main result is to show that achieving these properties is indeed possible in a generic and modular way when slightly relaxing the succinctness properties of zk-SNARKs to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness $w$. We will argue that for various practical applications of zk-SNARKs this overhead is perfectly tolerable. Our starting point is a framework by Abdolmaleki et al. called Lamassu (ACM CCS'20) which we extend in several directions. Moreover, we implement our compiler on top of Sonic (ACM CCS'19) and provide benchmarks as well as a discussion on the choice of the required primitives.



## 2023/98

* Title: Belief Propagation Meets Lattice Reduction: Security Estimates for Error-Tolerant Key Recovery from Decryption Errors
* Authors: Julius Hermelink, Erik Mårtensson, Simona Samardjiska, Peter Pessl, Gabi Dreo Rodosek
* [Permalink](https://eprint.iacr.org/2023/098)
* [Download](https://eprint.iacr.org/2023/098.pdf)

### Abstract

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information.

We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods -- we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities.

Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.



## 2023/99

* Title: Scalable Multiparty Garbling
* Authors: Gabrielle Beck, Aarushi Goel, Aditya Hegde, Abhishek Jain, Zhengzhong Jin, Gabriel Kaptchuk
* [Permalink](https://eprint.iacr.org/2023/099)
* [Download](https://eprint.iacr.org/2023/099.pdf)

### Abstract

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can not realistically accommodate large numbers of parties. In this work we present the first global-scale multiparty garbling protocol. The per-party communication complexity of our protocol decreases as the number of parties participating in the protocol increases---for the first time matching the asymptotic communication complexity of non-constant round MPC protocols. Our protocol achieves malicious security in the honest-majority setting and relies on the hardness of the Learning Party with Noise assumption.



## 2023/100

* Title: Meteor: Improved Secure 3-Party Neural Network Inference with Reducing Online Communication Costs
* Authors: Ye Dong, Xiaojun Chen, Weizhan Jing, Kaiyun Li, Weiping Wang
* [Permalink](https://eprint.iacr.org/2023/100)
* [Download](https://eprint.iacr.org/2023/100.pdf)

### Abstract

Secure neural network inference has been a promising solution to private Deep-Learning-as-a-Service, which enables the service provider and user to execute neural network inference without revealing their private inputs. However, the expensive overhead of current schemes is still an obstacle when applied in real applications. In this work, we present \textsc{Meteor}, an online communication-efficient and fast secure 3-party computation neural network inference system aginst semi-honest adversary in honest-majority. The main contributions of \textsc{Meteor} are two-fold: \romannumeral1) We propose a new and improved 3-party secret sharing scheme stemming from the \textit{linearity} of replicated secret sharing, and design efficient protocols for the basic cryptographic primitives, including linear operations, multiplication, most significant bit extraction, and multiplexer. \romannumeral2) Furthermore, we build efficient and secure blocks for the widely used neural network operators such as Matrix Multiplication, ReLU, and Maxpool, along with exploiting several specific optimizations for better efficiency. Our total communication with the setup phase is a little larger than SecureNN (PoPETs'19) and \textsc{Falcon} (PoPETs'21), two state-of-the-art solutions, but the gap is not significant when the online phase must be optimized as a priority. Using \textsc{Meteor}, we perform extensive evaluations on various neural networks. Compared to SecureNN and \textsc{Falcon}, we reduce the online communication costs by up to $25.6\times$ and $1.5\times$, and improve the running-time by at most $9.8\times$ (resp. $8.1\times$) and $1.5\times$ (resp. $2.1\times$) in LAN (resp. WAN) for the online inference.



## 2023/101

* Title: Practical Preimage Attack on 3-Round Keccak-256
* Authors: Xiaoen Lin, Le He, Hongbo Yu
* [Permalink](https://eprint.iacr.org/2023/101)
* [Download](https://eprint.iacr.org/2023/101.pdf)

### Abstract

This paper combines techniques from several previous papers with some modifications to improve the previous cryptanalysis of 3-round Keccak-256. Furthermore, we propose a fast rebuilding method to improve the efficiency of solving equation systems. As a result, the guessing times of finding a preimage for 3-round Keccak-256 are decreased from $2^{65}$ to $2^{52}$, and the solving time of each guess is decreased from $2^{9}$ 3-round Keccak calls to $2^{5.3}$ 3-round Keccak calls. We identify a preimage of all '0' digest for 3-round Keccak-256 to support the effectiveness of our methodology.



## 2023/102

* Title: Cache-timing attack against HQC
* Authors: Senyang Huang, Rui Qi Sim, Chitchanok Chuengsatiansup, Qian Guo, Thomas Johansson
* [Permalink](https://eprint.iacr.org/2023/102)
* [Download](https://eprint.iacr.org/2023/102.pdf)

### Abstract

In this paper, we present the first chosen-ciphertext (CC) cache-timing attacks on the reference implementation of HQC.
We build a cache-timing based distinguisher for implementing a plaintext-checking (PC) oracle. The PC oracle uses side-channel information to check if a given ciphertext decrypts to a given message.
This is done by identifying a vulnerability during the generating process of two vectors in the reference implementation of HQC.
We also propose a new method of using PC oracles for chosen-ciphertext side-channel attacks against HQC, which may have independent interest.

We show a general proof-of-concept attack, where we use the Flush&Reload technique and also derive, in more detail, a practical attack on an HQC execution on Intel SGX, where the Prime&Probe technique is used.
We show the exact path to do key recovery by explaining the detailed steps, using the PC oracle. In both scenarios, the new attack requires $53,857$ traces on average with much fewer PC oracle calls than the timing attack of Guo et al. CHES 2022 on an HQC implementation.



## 2023/103

* Title: Fair Delivery of Decentralised Randomness Beacon
* Authors: Runchao Han, Jiangshan Yu
* [Permalink](https://eprint.iacr.org/2023/103)
* [Download](https://eprint.iacr.org/2023/103.pdf)

### Abstract

Thesecurityofmanyprotocolssuchasvotingandblockchains relies on a secure source of randomness. Decentralised Randomness Beacon (DRB) has been considered as a promising approach, where a set of participants jointly generates a sequence of random outputs. While the DRBs have been extensively studied, they failed to capture the advantage that some participants learn random outputs earlier than other participants. In time-sensitive protocols whose execution depends on the randomness from a DRB, such an advantage allows the adversary to behave adaptively according to random outputs, compromising the fairness and/or security in these protocols.

In this paper, we formalise a new property, delivery-fairness, to quantify the advantage. In particular, we distinguish two aspects of delivery-fairness, namely length-advantage, i.e., how many random outputs an adversary can learn earlier than correct participants, and time-advantage, i.e., how much time an adversary can learn a given random output earlier than correct participants. In addition, we prove the lower bound of delivery-fairness showing optimal guarantee. We further analyse the delivery-fairness guarantee of state-of-the-art DRBs and discuss insights, which, we show through case studies, could help improve delivery-fairness of existing systems to its optimal.



## 2023/104

* Title: Optimizations and Trade-offs for HElib
* Authors: Anamaria Costache, Lea Nürnberger, Rachel Player
* [Permalink](https://eprint.iacr.org/2023/104)
* [Download](https://eprint.iacr.org/2023/104.pdf)

### Abstract

In this work, we investigate the BGV scheme as implemented
in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what
was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most $1.8$ bits off the experimentally observed values, they are as much as $29$ bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be $k$ times larger than the current ciphertext modulus $Q_i$. For a ratio of subsequent ciphertext moduli $\log\left( \frac{Q_i}{Qi−1}\right) = 54$ (a very common choice in HElib), we can optimise $k$ by up to $26$ bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.



## 2023/105

* Title: Gate-Level Masking of Streamlined NTRU Prime Decapsulation in Hardware
* Authors: Georg Land, Adrian Marotzke, Jan Richter-Brockmann, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2023/105)
* [Download](https://eprint.iacr.org/2023/105.pdf)

### Abstract

Streamlined NTRU Prime is a lattice-based Key Encapsulation Mechanism
(KEM) that is, together with X25519, currently the default algorithm in OpenSSH 9. Being based on lattice assumptions, it is assumed to be secure also against attackers with access to large-scale quantum computers. While Post-Quantum Cryptography (PQC) schemes have been subject to extensive research in the recent years, challenges remain with respect to protection mechanisms against attackers that have additional side-channel information such as the power consumption of a device processing secret data. As a countermeasure to such attacks, masking has been shown to be a promising and effective approach. For public-key schemes, including any recent PQC schemes, usually a mixture of Boolean and arithmetic approaches are applied on an algorithmic level. Our generic hardware implementation of Streamlined NTRU Prime decapsulation, however, follows an idea that until now was assumed to be only applicable to symmetric cryptography: gate-level masking. There, a hardware design that consists of logic gates is transformed into a secure implementation by replacing each gate with a composably secure gadget that operates on uniform random shares of secret values. In our work, we show the feasibility of applying this approach also to PQC schemes and present the first Public-Key Cryptography (PKC) – pre- and post-quantum – implementation masked at gate level considering several trade-offs and design choices. We synthesize our implementation both for Artix-7 Field-Programmable Gate Arrays (FPGAs) and 45 nm Application-Specific Integrated Circuits (ASICs), yielding practically feasible results regarding area, randomness demand and latency. Finally, we also analyze the applicability of our concept to Kyber which will be standardized by the National Institute of Standards and Technology (NIST).



## 2023/106

* Title: Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic
* Authors: Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková, Mattia Veroni
* [Permalink](https://eprint.iacr.org/2023/106)
* [Download](https://eprint.iacr.org/2023/106.pdf)

### Abstract

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields.
In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic.
Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method.
To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size.
One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice.
Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists' and cryptographers' needs when working with endomorphism rings of supersingular elliptic curves.
This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes.
Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20].
We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign.



## 2023/107

* Title: The Tip5 Hash Function for Recursive STARKs
* Authors: Alan Szepieniec, Alexander Lemmens, Jan Ferdinand Sauer, Bobbin Threadbare
* [Permalink](https://eprint.iacr.org/2023/107)
* [Download](https://eprint.iacr.org/2023/107.pdf)

### Abstract

This paper specifies a new arithmetization-oriented hash function called Tip5. It uses the SHARK design strategy with low-degree power maps in combination with lookup tables, and is tailored to the field with $p=2^{64}-2^{32}+1$ elements.

The context motivating this design is the recursive verification of STARKs. This context imposes particular design constraints, and therefore the hash function's arithmetization is discussed at length.



## 2023/108

* Title: Grotto: Screaming fast $(2 + 1)$-PC for $\mathbb{Z}_{2^{n}}$ via (2, 2)-DPFs
* Authors: Kyle Storrier, Adithya Vadapalli, Allan Lyons, Ryan Henry
* [Permalink](https://eprint.iacr.org/2023/108)
* [Download](https://eprint.iacr.org/2023/108.pdf)

### Abstract

We introduce Grotto, a framework and C++ library for space- and time-efficient $(2+1)$-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over $\mathbb{Z}_{2^{n}}$. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ``tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a single DPF what state-of-the-art approaches require many DCFs to do. Our open-source Grotto implementation supports evaluating dozens of useful functions out of the box, including trigonometric and hyperbolic functions (and their inverses); various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common (univariate) activation functions from the deep-learning literature.



## 2023/109

* Title: SoK: Modeling for Large S-boxes Oriented to Differential Probabilities and Linear Correlations (Long Paper)
* Authors: Ling Sun, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2023/109)
* [Download](https://eprint.iacr.org/2023/109.pdf)

### Abstract

Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three strategies for developing SAT models for 8-bit S-boxes that are geared toward differential probabilities and linear correlations. While these approaches cannot guarantee a minimum model size, the time needed to obtain models is drastically reduced. The newly proposed SAT model for large S-boxes enables us to establish that the upper bound on the differential probability for 14 rounds of SKINNY-128 is 2^{-131}, thereby completing the unsuccessful work of Abdelkhalek et al. We also analyse the seven AES-based constructions C1 - C7 designed by Jean and Nikolic and compute the minimum number of active S-boxes necessary to cause an internal collision using the SAT method. For two constructions C3 and C5, the current lower bound on the number of active S-boxes is increased, resulting in a more precise security analysis for these two structures.