[digest] 2023 Week 3

[IACR ePrint Archive]

## In this issue

1. [2022/1247] Peek into the Black-Box: Interpretable Neural ...
2. [2023/19] Autoencoder-enabled Model Portability for Reducing ...
3. [2023/20] The Scholz conjecture on addition chain is true for ...
4. [2023/21] DLPFA: Deep Learning based Persistent Fault ...
5. [2023/22] Recommendation for a holistic secure embedded ISA ...
6. [2023/23] New Algorithm for Exhausting Optimal Permutations ...
7. [2023/24] It Runs and it Hides: A Function-Hiding ...
8. [2023/25] Quantum Attacks on Beyond-Birthday-Bound MACs
9. [2023/26] Fermat Factorization in the Wild
10. [2023/27] Verification of the (1–δ)-Correctness Proof of ...
11. [2023/28] Information-Theoretic Distributed Point Functions
12. [2023/29] Public Verification for Private Hash Matching
13. [2023/30] Earn While You Reveal: Private Set Intersection ...
14. [2023/31] Sassafras and Semi-Anonymous Single Leader Election
15. [2023/32] A Gentle Tutorial for Lattice-Based Cryptanalysis
16. [2023/33] Fast amortized KZG proofs
17. [2023/34] PROLEAD_SW - Probing-Based Software Leakage ...
18. [2023/35] Glitch-free is not Enough - Revisiting Glitch- ...
19. [2023/36] Differential analysis of the ternary hash function ...
20. [2023/37] Efficient Isogeny Proofs Using Generic Techniques
21. [2023/38] On the Amortized Communication Complexity of ...
22. [2023/39] Server-Supported Decryption for Mobile Devices
23. [2023/40] A Closer Look at the Chaotic Ring Oscillators based ...
24. [2023/41] Quantum-Safe Protocols and Application in Data ...
25. [2023/42] On Protecting SPHINCS+ Against Fault Attacks
26. [2023/43] RDS: FPGA Routing Delay Sensors for Effective ...
27. [2023/44] Complete Knowledge: Preventing Encumbrance of ...
28. [2023/45] A note on machine learning applied in ransomware ...
29. [2023/46] Cognitive Cryptography using behavioral features ...
30. [2023/47] Side-Channel Resistant Implementation Using Arbiter PUF
31. [2023/48] On-Line/Off-Line DCR-based Homomorphic Encryption ...
32. [2023/49] Implementing and Benchmarking Word-Wise Homomorphic ...
33. [2023/50] A Practical Template Attack on CRYSTALS-Dilithium
34. [2023/51] A proof of the Scholz conjecture on addition chains
35. [2023/52] Putting the Online Phase on a Diet: Covert Security ...
36. [2023/53] 𝑃3𝑉 : Privacy-Preserving Path Validation System for ...
37. [2023/54] On the Incoercibility of Digital Signatures
38. [2023/55] An analysis of a scheme proposed for electronic ...
39. [2023/56] Quantum Annealing for Subset Product and Noisy ...
40. [2023/57] DY Fuzzing: Formal Dolev-Yao Models Meet Protocol ...
41. [2023/58] SCALLOP: scaling the CSI-FiSh
42. [2023/59] Oil and Vinegar: Modern Parameters and Implementations
43. [2023/60] Silph: A Framework for Scalable and Accurate ...
44. [2023/61] Key-and-Signature Compact Multi-Signatures: A ...
45. [2023/62] Post-Quantum Secure Deterministic Wallet: ...
46. [2023/63] Threshold Signatures in the Multiverse
47. [2023/64] Computation of Hilbert class polynomials and ...
48. [2023/65] A Practical TFHE-Based Multi-Key Homomorphic ...
49. [2023/66] Plonkup scheme with multiple queries

## 2022/1247

* Title: Peek into the Black-Box: Interpretable Neural Network using SAT Equations in Side-Channel Analysis
* Authors: Trevor Yap, Adrien Benamira, Shivam Bhasin, Thomas Peyrin
* [Permalink](https://eprint.iacr.org/2022/1247)
* [Download](https://eprint.iacr.org/2022/1247.pdf)

### Abstract

Deep neural networks (DNN) have become a significant threat to the security of cryptographic implementations with regards to side-channel analysis (SCA), as they automatically combine the leakages without any preprocessing needed, leading to a more efficient attack. However, these DNNs for SCA remain mostly black-box algorithms that are very difficult to interpret. Benamira \textit{et al.} recently proposed an interpretable neural network called Truth Table Deep Convolutional Neural Network (TT-DCNN), which is both expressive and easier to interpret. In particular, a TT-DCNN has a transparent inner structure that can entirely be transformed into SAT equations after training.
In this work, we analyze the SAT equations extracted from a TT-DCNN when applied in SCA context, eventually obtaining the rules and decisions that the neural networks learned when retrieving the secret key from the cryptographic primitive (i.e., exact formula). As a result, we can pinpoint the critical rules that the neural network uses to locate the exact Points of Interest (PoIs). We validate our approach first on simulated traces for higher-order masking. However, applying TT-DCNN on real traces is not straightforward. We propose a method to adapt TT-DCNN for application on real SCA traces containing thousands of sample points. Experimental validation is performed on software-based ASCADv1 and hardware-based AES\_HD\_ext datasets. In addition, TT-DCNN is shown to be able to learn the exact countermeasure in a best-case setting.



## 2023/19

* Title: Autoencoder-enabled Model Portability for Reducing Hyperparameter Tuning Efforts in Side-channel Analysis
* Authors: Marina Krček, Guilherme Perin
* [Permalink](https://eprint.iacr.org/2023/019)
* [Download](https://eprint.iacr.org/2023/019.pdf)

### Abstract

Hyperparameter tuning represents one of the main challenges in deep learning-based profiling side-channel analysis. For each different side-channel dataset, the typical procedure to find a profiling model is applying hyperparameter tuning from scratch. The main reason is that side-channel measurements from various targets contain different underlying leakage distributions. Consequently, the same profiling model hyperparameters are usually not equally efficient for other targets. This paper considers autoencoders for dimensionality reduction to verify if encoded datasets from different targets enable the portability of profiling models and architectures. Successful portability reduces the hyperparameter tuning efforts as profiling model tuning is eliminated for the new dataset, and tuning autoencoders is simpler. We first search for the best autoencoder for each dataset and the best profiling model when the encoded dataset becomes the training set. Our results show no significant difference in tuning efforts using original and encoded traces, meaning that encoded data reliably represents the original data.
Next, we verify how portable is the best profiling model among different datasets. Our results show that tuning autoencoders enables and improves portability while reducing the effort in hyperparameter search for profiling models. Lastly, we present a transfer learning case where dimensionality reduction might be necessary if the model is tuned for a dataset with fewer features than the new dataset. In this case, tuning of the profiling model is eliminated and training time reduced.



## 2023/20

* Title: The Scholz conjecture on addition chain is true for infinitely many integers with ℓ(2n) = ℓ(n)
* Authors: Amadou TALL
* [Permalink](https://eprint.iacr.org/2023/020)
* [Download](https://eprint.iacr.org/2023/020.pdf)

### Abstract

It is known that the Scholz conjecture on addition chains is true for all integers n with ℓ(2n) = ℓ(n) + 1. There exists infinitely many integers with ℓ(2n) ≤ ℓ(n) and we don’t know if the conjecture still holds for them. The conjecture is also proven to hold for integers n with v(n) ≤ 5 and for infinitely many integers with v(n) = 6. There is no specific results on
integers with v(n) = 7. In [14], an infinite list of integers satisfying ℓ(n) = ℓ(2n) and v(n) = 7
is given by Thurber. In this paper, we prove that the conjecture holds for all of them.



## 2023/21

* Title: DLPFA: Deep Learning based Persistent Fault Analysis against Block Ciphers
* Authors: Yukun Cheng, Changhai Ou, Fan Zhang, Shihui Zheng
* [Permalink](https://eprint.iacr.org/2023/021)
* [Download](https://eprint.iacr.org/2023/021.pdf)

### Abstract

Deep learning techniques have been widely applied to side-channel analysis (SCA) in recent years and shown better performance compared with traditional methods. However, there has been little research dealing with deep learning techniques in fault analysis to date. This article undertakes the first study to introduce deep learning techniques into fault analysis to perform key recovery. We investigate the application of multi-layer perceptron (MLP) and convolutional neural network (CNN) in persistent fault analysis (PFA) and propose deep learning-based persistent fault analysis (DLPFA). DLPFA is first applied to advanced encryption standard (AES) to verify its availability. Then, to push the study further, we extend DLPFA to PRESENT, which is a lightweight substitution–permutation network (SPN)-based block cipher. The experimental results show that DLPFA can handle random faults and provide outstanding performance with a suitable selection of hyper-parameters.



## 2023/22

* Title: Recommendation for a holistic secure embedded ISA extension
* Authors: Florian Stolz, Marc Fyrbiak, Pascal Sasdrich, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2023/022)
* [Download](https://eprint.iacr.org/2023/022.pdf)

### Abstract

Embedded systems are a cornerstone of the ongoing digitization of our society, ranging from expanding markets around IoT and smart-X devices over to sensors in autonomous driving, medical equipment or critical infrastructures. Since a vast amount of embedded systems are safety-critical (e.g., due to their operation site), security is a necessity for their operation. However, unlike mobile, desktop, and server systems, where adversaries typically only act have remote access, embedded systems typically face attackers with physical access. Thus embedded system require an additional set of defense techniques, preferably leveraging hardware acceleration to minimize the impact on their stringent operation constraints. Over the last decade numerous defenses have been explored, however, they have often been analyzed in isolation.

In this work, we first systematically analyze the state of the art in defenses for both software exploitation and fault attacks on embedded systems. We then carefully design a holistic instruction set extension to augment the RISC-V instruction set architecture with instructions to deter against the threats analyzed in this work. Moreover we implement our design using the gem5 simulator system and a binary translation approach to arm software with our instruction set extension. Finally, we evaluate performance overhead on the MiBench2 benchmark suite. Our evaluation demonstrates a ROM overhead increase of 20% to defeat the aforementioned attacks.



## 2023/23

* Title: New Algorithm for Exhausting Optimal Permutations for Generalized Feistel Networks
* Authors: Stéphanie Delaune, Patrick Derbez, Arthur Gontier, Charles Prud'homme
* [Permalink](https://eprint.iacr.org/2023/023)
* [Download](https://eprint.iacr.org/2023/023.pdf)

### Abstract

The Feistel construction is one of the most studied ways of building block ciphers. Several generalizations were proposed in the literature, leading to the Generalized Feistel Network (GFN) construction, in which the round function operates on each pair of blocks in parallel until all branches are permuted. At FSE'10, Suzaki and Minematsu studied the diffusion of such construction, raising the question of how many rounds are required so that each block of the ciphertext depends on all blocks of the plaintext. Exhausting all possible permutations up to 16 blocks, they observed that there were always optimal permutations mapping even-number input blocks to odd-number output blocks and vice versa. Recently, both Cauchois et al. and Derbez et al. proposed new algorithms to build optimal even-odd permutations for up to 36 blocks.
In this paper, we present a new algorithm based on iterative path building to search for optimal Feistel permutation. This algorithm is much faster in exhausting optimal non-even-odd permutations than all the previous approaches. Our first result is a computational proof that no non-even-odd permutation reaches a better diffusion round than optimal even-odd permutations up to 32 blocks. Furthermore, it is well known that permutations with an optimal diffusion round do not always lead to optimal permutations against differential cryptanalysis. We investigate several new criteria to build permutations leading to more secure GFN.



## 2023/24

* Title: It Runs and it Hides: A Function-Hiding Construction for Private-Key Multi-Input Functional Encryption
* Authors: Alexandros Bakas, Antonis Michalas
* [Permalink](https://eprint.iacr.org/2023/024)
* [Download](https://eprint.iacr.org/2023/024.pdf)

### Abstract

Functional Encryption (FE) is a modern cryptographic technique that allows users to learn only a specific function of the encrypted data and nothing else about its actual content. While the first notions of security in FE revolved around the privacy of the encrypted data, more recent approaches also consider the privacy of the computed function. While in the public key setting, only a limited level of function-privacy can be achieved, in the private-key setting privacy potential is significantly larger. However, this potential is still limited by the lack of rich function families. For this work, we started by identifying the limitations of the current state-of-the-art approaches which, in its turn, allowed us to consider a new threat model for FE schemes. To the best of our knowledge, we here present the first attempt to quantify the leakage during the execution of an FE scheme. By leveraging the functionality offered by Trusted Execution Environments, we propose a construction that given any message-private functional encryption scheme yields a function-private one. Finally, we argue in favour of our construction's applicability on constrained devices by showing that it has low storage and computation costs.



## 2023/25

* Title: Quantum Attacks on Beyond-Birthday-Bound MACs
* Authors: Hong-Wei Sun, Bin-Bin Cai, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
* [Permalink](https://eprint.iacr.org/2023/025)
* [Download](https://eprint.iacr.org/2023/025.pdf)

### Abstract

In this paper, we investigate the security of several recent MAC constructions with provable security beyond the birthday bound (called BBB MACs) in the quantum setting. On the one hand, we give periodic functions corresponding to targeted MACs (including PMACX, PMAC with parity, HPxHP, and HPxNP), and we can recover secret states using Simon algorithm, leading to forgery attacks with complexity O(n). This implies our results realize an exponential speedup compared with the classical algorithm. Note that our attacks can even break some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, mPMAC+-p2, mLightMAC+-f, etc. On the other hand, we construct new hidden periodic functions based on SUM-ECBC-like MACs: SUM-ECBC, PolyMAC, GCM-SIV2, and 2K-ECBC−Plus, where periods reveal the information of the secret key. Then, by applying Grover-meets-Simon algorithm to specially constructed functions, we can recover full keys with O(2^(n/2)n) or O(2^(m/2)n) quantum queries, where n is the message block size and m is the length of the key. Considering the previous best quantum attack, our key-recovery attacks achieve a quadratic speedup.



## 2023/26

* Title: Fermat Factorization in the Wild
* Authors: Hanno Böck
* [Permalink](https://eprint.iacr.org/2023/026)
* [Download](https://eprint.iacr.org/2023/026.pdf)

### Abstract

We are applying Fermat’s factorization algorithm to sets of public RSA keys. Fermat’s factorization allows efficiently calculating the prime factors of a composite number if the difference between the two primes is small. Knowledge of the prime factors of an RSA public key allows efficiently calculating the private key. A flawed RSA key generation function that produces close primes can therefore be attacked with Fermat’s factorization.
We discovered a small number of vulnerable devices that generate such flawed RSA keys in the wild. These affect devices from two printer vendors - Canon and Fuji Xerox. Both use an underlying cryptographic module by Rambus.



## 2023/27

* Title: Verification of the (1–δ)-Correctness Proof of CRYSTALS-KYBER with Number Theoretic Transform
* Authors: Katharina Kreuzer
* [Permalink](https://eprint.iacr.org/2023/027)
* [Download](https://eprint.iacr.org/2023/027.pdf)

### Abstract

This paper describes a formalization of the specification and the algorithm of the cryptographic scheme CRYSTALS-KYBER as well as the verification of its (1 − δ)-correctness proof. During the formalization, a problem in the correctness proof was uncovered. In order to amend this
issue, a necessary property on the modulus parameter of the CRYSTALS-KYBER algorithm was introduced. This property is already implicitly fulfilled by the structure of the modulus prime used in the number theoretic transform (NTT). The NTT and its convolution theorem
in the case of CRYSTALS-KYBER was formalized as well. The formalization was realized in the theorem prover Isabelle.



## 2023/28

* Title: Information-Theoretic Distributed Point Functions
* Authors: Elette Boyle, Niv Gilboa, Yuval Ishai, Victor I. Kolobov
* [Permalink](https://eprint.iacr.org/2023/028)
* [Download](https://eprint.iacr.org/2023/028.pdf)

### Abstract

A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority.

We present the first statistically private 3-server DPF for domain size $N$ with subpolynomial key size $N^{o(1)}$. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.



## 2023/29

* Title: Public Verification for Private Hash Matching
* Authors: Sarah Scheffler, Anunay Kulshrestha, Jonathan Mayer
* [Permalink](https://eprint.iacr.org/2023/029)
* [Download](https://eprint.iacr.org/2023/029.pdf)

### Abstract

End-to-end encryption (E2EE) prevents online services from accessing user content. This important security property is also an obstacle for content moderation methods that involve content analysis. The tension between E2EE and efforts to combat child sexual abuse material (CSAM) has become a global flashpoint in encryption policy, because the predominant method of detecting harmful content---server-side perceptual hash matching on plaintext images---is unavailable.

Recent applied cryptography advances enable private hash matching (PHM), where a service can match user content against a set of known CSAM images without revealing the hash set to users or nonmatching content to the service. These designs, especially a 2021 proposal for identifying CSAM in Apple's iCloud Photos service, have attracted widespread criticism for creating risks to security, privacy, and free expression.

In this work, we aim to advance scholarship and dialogue about PHM by contributing new cryptographic methods for system verification by the general public. We begin with motivation, describing the rationale for PHM to detect CSAM and the serious societal and technical issues with its deployment. Verification could partially address shortcomings of PHM, and we systematize critiques into two areas for auditing: trust in the hash set and trust in the implementation. We explain how, while these two issues cannot be fully resolved by technology alone, there are possible cryptographic trust improvements.

The central contributions of this paper are novel cryptographic protocols that enable three types of public verification for PHM systems: (1) certification that external groups approve the hash set, (2) proof that particular lawful content is not in the hash set, and (3) eventual notification to users of false positive matches. The protocols that we describe are practical, efficient, and compatible with existing PHM constructions.



## 2023/30

* Title: Earn While You Reveal: Private Set Intersection that Rewards Participants
* Authors: Aydin Abadi, Steven Murdoch
* [Permalink](https://eprint.iacr.org/2023/030)
* [Download](https://eprint.iacr.org/2023/030.pdf)

### Abstract

In Private Set Intersection protocols (PSIs), a non-empty result always reveals something about the private input sets of the parties. Moreover, in various variants of PSI, not all parties necessarily receive or are interested in the result. Nevertheless, to date, the literature has assumed that those parties who do not receive or are not interested in the result still contribute their private input sets to the PSI for free, although doing so would cost them their privacy. In this work, for the first time, we propose a multi-party PSI, called “Anesidora”, that rewards parties who contribute their private input sets to the protocol. Anesidora is efficient; it mainly relies on symmetric key primitives and its computation and communication complexities are linear with the number of parties and set cardinality. It remains secure even if the majority of parties are corrupted by active colluding adversaries.



## 2023/31

* Title: Sassafras and Semi-Anonymous Single Leader Election
* Authors: Jeffrey Burdges, Handan Kılınç Alper, Alistair Stewart, Sergey Vasilyev
* [Permalink](https://eprint.iacr.org/2023/031)
* [Download](https://eprint.iacr.org/2023/031.pdf)

### Abstract

A single-leader election (SLE) is a way to elect one leader randomly among the parties in a distributed system. If the leader is secret (i.e., unpredictable) then it is called a secret single leader election (SSLE). In this paper, we model the security of SLE in the universally composable (UC) model. Our model is adaptable to various unpredictability levels for leaders that an SLE aims to provide. We construct an SLE protocol that we call semi-anonymous single leader election (SASLE). We show that SASLE is secure against adaptive adversaries in the UC model. SASLE provides a good amount of unpredictability level to most of the honest leaders while it does not provide unpredictability to the rest of them. In this way, we obtain better communication overhead by comparing the existing SSLE protocols. In the end, we construct a PoS-protocol (Sassafras) which deploys SASLE to elect the block producers. Sassafras benefits from the efficiency of SASLE and gains significant security both to grinding attacks and the private attack as shown by Azouvi and Cappelletti (ACM AFT 2021) because it elects a single block producer.



## 2023/32

* Title: A Gentle Tutorial for Lattice-Based Cryptanalysis
* Authors: Joseph Surin, Shaanan Cohney
* [Permalink](https://eprint.iacr.org/2023/032)
* [Download](https://eprint.iacr.org/2023/032.pdf)

### Abstract

The applicability of lattice reduction to a wide variety of cryptographic situations makes it an important part of the cryptanalyst's toolbox. Despite this, the construction of lattices and use of lattice reduction algorithms for cryptanalysis continue to be somewhat difficult to understand for beginners. This tutorial aims to be a gentle but detailed introduction to lattice-based cryptanalysis targeted towards the novice cryptanalyst with little to no background in lattices. We explain some popular attacks through a conceptual model that simplifies the various components of a lattice attack.



## 2023/33

* Title: Fast amortized KZG proofs
* Authors: Dankrad Feist, Dmitry Khovratovich
* [Permalink](https://eprint.iacr.org/2023/033)
* [Download](https://eprint.iacr.org/2023/033.pdf)

### Abstract

In this note we explain how to compute $n$ KZG proofs for a polynomial of degree $d$ in time superlinear of $(t+d)$. Our technique is used in lookup arguments and vector commitment schemes.



## 2023/34

* Title: PROLEAD_SW - Probing-Based Software Leakage Detection for ARM Binaries
* Authors: Jannik Zeitschner, Nicolai Müller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2023/034)
* [Download](https://eprint.iacr.org/2023/034.pdf)

### Abstract

A decisive contribution to the all-embracing protection of cryptographic software, especially on embedded devices, is the protection against SCA attacks. Masking countermeasures can usually be integrated into the software during the design phase. In theory, this should provide reliable protection against such physical attacks. However, the correct application of masking is a non-trivial task which often causes even experts to make mistakes. In addition to human-caused errors, micro-architectural CPU effects can lead even a seemingly theoretically correct implementation to fail satisfying the desired level of security in practice. This originates from different components of the underlying CPU which complicates the tracing of leakage back to a particular source and hence avoids to make general and device-independent statements about its security.
In this work, we adapt PROLEAD for the evaluation of masked software, which has recently been presented at CHES 2022 and originally developed as a simulation-based tool to evaluate masked hardware designs.
We enable to transfer the already known benefits of PROLEAD into the software world. These include (1) evaluation of larger designs compared to the state of the art, e.g. a full AES masked implementation, and (2) formal verification under the well-established robust probing security model. In short, together with an abstraction model for the micro-architecture, the robust probing model allows us to efficiently detect micro-architectural leakages while being independent of a concrete CPU design. As a concrete result, using PROLEAD_SW we evaluated the security of several publicly available masked software implementations and revealed multiple vulnerabilities.



## 2023/35

* Title: Glitch-free is not Enough - Revisiting Glitch-Extended Probing Model
* Authors: Daniel Lammers, Nicolai Müller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2023/035)
* [Download](https://eprint.iacr.org/2023/035.pdf)

### Abstract

Today, resistance to physical defaults is a necessary criterion for masking schemes. In this context, the focus has long been on designing masking schemes guaranteeing security in the presence of glitches. Sadly, immunity against glitches increases latency as registers must stop the glitch propagation. Previous works could reduce the latency by removing register stages but only by impractically increasing the circuit area. Nevertheless, some relatively new attempts avoid glitches by applying DRP logic styles. Promising works in this area include LMDPL, SESYM - both presented at CHES - and Self-Timed Masking - presented at CARDIS - enabling to mask arbitrary circuits with only one cycle latency. However, even if glitches no longer occur, there are other physical defaults that may violate the security of a masked circuit. Imbalanced delay of dual rails is a known problem for the security of DRP logic styles such as WDDL but not covered in formal security models.
In this work, we fill the gap by presenting the delay-extended probing security model, a generalization of the popular glitch-extended probing model, covering imbalanced delays. We emphasize the importance of such a model by a formal and practical security analysis of LMDPL, SESYM, and Self-Timed Masking. While we formally prove the delay-extended security of LMDPL and Self-Timed Masking, we show that SESYM fails to provide security under our defined security model what causes detectable leakage through experimental evaluations. Hence, as the message of this work, avoiding glitches in combination with d-probing security is not enough to guarantee physical security in practice.



## 2023/36

* Title: Differential analysis of the ternary hash function Troika
* Authors: Christina Boura, Margot Funk, Yann Rotella
* [Permalink](https://eprint.iacr.org/2023/036)
* [Download](https://eprint.iacr.org/2023/036.pdf)

### Abstract

Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over $\mathbb{F}_3$ in order to be used inside IOTA’s distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step in this direction by analyzing the propagation of differential trails of Troika and by providing bounds on the weight of its trails. For this, we adapt a well-known framework for trail search designed for KECCAK and provide new advanced techniques to handle the search on $\mathbb{F}_3$. Our work demonstrates that providing analysis tools for non-binary designs is a highly non-trivial research direction that needs to be enhanced in order to better understand the real security offered by such non-conventional primitives.



## 2023/37

* Title: Efficient Isogeny Proofs Using Generic Techniques
* Authors: Kelong Cong, Yi-Fu Lai, Shai Levin
* [Permalink](https://eprint.iacr.org/2023/037)
* [Download](https://eprint.iacr.org/2023/037.pdf)

### Abstract

Generating supersingular elliptic curves of unknown endomorphism ring has been a problem vexing isogeny-based cryptographers for several years. A recent development has proposed a trusted setup protocol to generate such a curve, where each participant generates and proves knowledge of an isogeny. Thus, the construction of efficient proofs of knowledge of isogeny has developed new interest.

Historically, the isogeny community has assumed that obtaining isogeny proofs of knowledge from generic proof systems, such as zkSNARKs, was not a practical approach. We contribute the first concrete result in this area by applying Aurora (EUROCRYPT'19), Ligero (CCS'17) and Limbo (CCS'21) to an isogeny path relation, and comparing their performance to a state-of-the-art, tailor-made protocol for the same relation. In doing so, we show that modern generic proof systems are competitive when applied to isogeny assumptions, and provide an order of magnitude ($10\textrm{-}30\times$) improvement to proof and verification times, with similar proof sizes. In addition, these proofs provide a stronger notion of soundness, and statistical zero-knowledge; a property that has only recently been achieved in isogeny PoKs. Independently, this technique shows promise as a component in the design of future isogeny-based or other post-quantum protocols.



## 2023/38

* Title: On the Amortized Communication Complexity of Byzantine Broadcast
* Authors: Atsuki Momose, Ling Ren, Elaine Shi, Jun Wan, Zhuolun Xiang
* [Permalink](https://eprint.iacr.org/2023/038)
* [Download](https://eprint.iacr.org/2023/038.pdf)

### Abstract

Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.



## 2023/39

* Title: Server-Supported Decryption for Mobile Devices
* Authors: Johanna Maria Kirss, Peeter Laud, Nikita Snetkov, Jelizaveta Vakarjuk
* [Permalink](https://eprint.iacr.org/2023/039)
* [Download](https://eprint.iacr.org/2023/039.pdf)

### Abstract

We propose a threshold encryption scheme with two-party decryption, where one of the keyshares may be stored and used in a device that is able to provide only weak security for it. We state the security properties the scheme needs to have to support such use-cases, and construct a scheme with these properties.



## 2023/40

* Title: A Closer Look at the Chaotic Ring Oscillators based TRNG Design
* Authors: Shuqin Su, Bohan Yang, Vladimir Rožić, Mingyuan Yang, Min Zhu, Shaojun Wei, Leibo Liu
* [Permalink](https://eprint.iacr.org/2023/040)
* [Download](https://eprint.iacr.org/2023/040.pdf)

### Abstract

TRNG is an essential component for security applications. A vulnerable TRNG could be exploited to facilitate potential attacks or be related to a reduced key space, and eventually results in a compromised cryptographic system. A digital FIRO-/GARO-based TRNG with high throughput and high entropy rate was introduced by Jovan Dj. Golić (TC’06). However, the fact that periodic oscillation is a main failure of FIRO-/GARO-based TRNGs is noticed in the paper (Markus Dichtl, ePrint’15). We verify this problem and estimate the consequential entropy loss using Lyapunov exponents and the test suite of the NIST SP 800-90B standard. To address the problem of periodic oscillations, we propose several implementation guidelines based on a gate-level model, a design methodology to build a reliable GARO-based TRNG, and an online test to improve the robustness of FIRO-/GARO-based TRNGs. The gate-level implementation guidelines illustrate the causes of periodic oscillations, which are verified by actual implementation and bifurcation diagram. Based on the design methodology, a suitable feedback polynomial can be selected by evaluating the feedback polynomials. The analysis and understanding of periodic oscillation and FIRO-/GARO-based TRNGs are deepened by delay adjustment. A TRNG with the selected feedback polynomial may occasionally enter periodic oscillations, due to active attacks and the delay inconstancy of implementations. This inconstancy might be caused by self-heating, temperature and voltage fluctuation, and the process variation among different silicon chips. Thus, an online test module, as one indispensable component of TRNGs, is proposed to detect periodic oscillations. The detected periodic oscillation can be eliminated by adjusting feedback polynomial or delays to improve the robustness. The online test module is composed of a lightweight and responsive detector with a high detection rate, outperforming the existing detector design and statistical tests. The areas, power consumptions and frequencies are evaluated based on the ASIC implementations of a GARO, the sampling circuit and the online test module. The gate-level implementation guidelines promote the future establishment of the stochastic model of FIRO-/GARO-based TRNGs with a deeper understanding.



## 2023/41

* Title: Quantum-Safe Protocols and Application in Data Security of Medical Records
* Authors: Adrian-Daniel Stefan, Ionut-Petrisor Anghel, Emil Simion
* [Permalink](https://eprint.iacr.org/2023/041)
* [Download](https://eprint.iacr.org/2023/041.pdf)

### Abstract

The use of traditional cryptography based on symmetric keys has been replaced with the revolutionary idea discovered by Diffie and Hellman in 1976 that fundamentally changed communication systems by ensuring a secure transmission of information over an insecure channel. Nowadays public key cryptography is frequently used for authentication in e-commerce, digital signatures and encrypted communication. Most of the public key cryptosystems used in practice are based on integer factorization (the famous RSA cryptosystem proposed by Rivest, Shamir and Adlemann), respectively on the discrete logarithm (in finite curves or elliptic curves). However these systems suffer from two potential drawbacks like efficiency because they must use large keys to maintain security and of course security breach with the advent of the quantum computer as a result of Peter Shor's discovery in 1999 of the polynomial algorithm for solving problems such factorization of integers and discrete logarithm.



## 2023/42

* Title: On Protecting SPHINCS+ Against Fault Attacks
* Authors: Aymeric Genêt
* [Permalink](https://eprint.iacr.org/2023/042)
* [Download](https://eprint.iacr.org/2023/042.pdf)

### Abstract

SPHINCS+ is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context of SPHINCS+ and analyzes the current algorithms that aim to prevent fault-based forgeries.

First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.



## 2023/43

* Title: RDS: FPGA Routing Delay Sensors for Effective Remote Power Analysis Attacks
* Authors: David Spielmann, Ognjen Glamocanin, Mirjana Stojilovic
* [Permalink](https://eprint.iacr.org/2023/043)
* [Download](https://eprint.iacr.org/2023/043.pdf)

### Abstract

State-of-the-art sensors for measuring FPGA voltage fluctuations are time-to-digital converters (TDCs). They allow detecting voltage fluctuations in the order of a few nanoseconds. The key building component of a TDC is a delay line, typically implemented as a chain of fast carry propagation multiplexers. In FPGAs, the fast carry chains are constrained to dedicated logic and routing, and need to be routed strictly vertically. In this work, we present an alternative approach to designing on-chip voltage sensors, in which the FPGA routing resources replace the carry logic. We present three variants of what we name a routing delay sensor (RDS): one vertically constrained, one horizontally constrained, and one free of any constraints. We perform a thorough experimental evaluation on both the Sakura-X side-channel evaluation board and the Alveo U200 datacenter card, to evaluate the performance of the RDS sensors in the context of a remote power side-channel analysis attack. The results show that our best RDS implementation in most cases outperforms the TDC. On average, for breaking the full 128-bit key of an AES-128 cryptographic core, an adversary requires 35% fewer side-channel traces when using the RDS than when using the TDC. Besides making the attack more effective, given the absence of the placement and routing constraint, the RDS sensor is also easier to deploy.



## 2023/44

* Title: Complete Knowledge: Preventing Encumbrance of Cryptographic Secrets
* Authors: Mahimna Kelkar, Kushal Babel, Philip Daian, James Austgen, Vitalik Buterin, Ari Juels
* [Permalink](https://eprint.iacr.org/2023/044)
* [Download](https://eprint.iacr.org/2023/044.pdf)

### Abstract

Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message.

The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually knowing sk. By permitting selective access to sk by an adversary, encumbrance of secrets can enable vote-selling in cryptographic voting schemes, illegal sale of credentials for online services, and erosion of deniability in anonymous messaging systems.

Unfortunately, existing proof-of-knowledge protocols fail to demonstrate that a secret is unencumbered. We therefore introduce and formalize a new notion called complete knowledge (CK). A proof (or argument) of CK shows that a prover does not just know a secret, but also has fully unencumbered knowledge, i.e., unrestricted ability to use the secret.

We introduce two practical CK schemes that use special-purpose hardware, specifically TEEs and off-the-shelf mining ASICs. We prove the security of these schemes and explore their practical deployment with a complete, end-to-end prototype that supports both. We show how CK can address encumbrance attacks identified in previous work. Finally, we introduce two new applications enabled by CK that involve proving ownership of blockchain assets.



## 2023/45

* Title: A note on machine learning applied in ransomware detection
* Authors: Manuela Horduna, Simona-Maria Lăzărescu, Emil Simion
* [Permalink](https://eprint.iacr.org/2023/045)
* [Download](https://eprint.iacr.org/2023/045.pdf)

### Abstract

Ransomware is a malware that employs encryption to hold a victim's data, causing irreparable loss and monetary incentives to individuals or business organizations.
The occurrence of ransomware attacks has been increasing significantly and as the attackers are investing more creativity and inventiveness into their threats, the struggle of fighting against ill-themed activities has become more difficult and even time and energy-draining.
Therefore, recent researches try to shed some light on combining machine learning with defense mechanisms for detecting this type of malware.
Machine learning allows anti-ransomware systems to become more accurate at predicting outcomes or behaviors of the attacks and is vastly used in the advanced research of cybersecurity.
In this paper we analyze how machine learning can improve malware recognition in order to stand against critical security issues, giving a brief, yet comprehensive overview of this thriving topic in order to facilitate future research. We also briefly present the most important events of 2022 in terms of ransomware attacks, providing details about the ransoms demanded.



## 2023/46

* Title: Cognitive Cryptography using behavioral features from linguistic-biometric data
* Authors: Jose Contreras
* [Permalink](https://eprint.iacr.org/2023/046)
* [Download](https://eprint.iacr.org/2023/046.pdf)

### Abstract

This study presents a proof-of-concept for a cognitive-based authentication system that uses an individual's writing style as a unique identifier to grant access to a system. A machine learning SVM model was trained on these features to distinguish between texts generated by each user. The stylometric feature vector was then used as an input to a key derivation function to generate a unique key for each user. The experiment results showed that the developed system achieved up to 87.42\% accuracy in classifying texts as written, and the generated keys were found to be secure and unique. We explore the intersection between natural intelligence, cognitive science, and cryptography, intending to develop a cognitive cryptography system. The proposed system utilizes behavioral features from linguistic-biometric data to detect and classify users through stylometry. This information is then used to generate a cryptographic key for authentication, providing a new level of security in access control. The field of cognitive cryptography is relatively new and has yet to be fully explored, making this research particularly relevant and essential. Through our study, we aim to contribute to understanding the potential of cognitive cryptography and its potential applications in securing access to sensitive information.



## 2023/47

* Title: Side-Channel Resistant Implementation Using Arbiter PUF
* Authors: Raja Adhithan RadhaKrishnan
* [Permalink](https://eprint.iacr.org/2023/047)
* [Download](https://eprint.iacr.org/2023/047.pdf)

### Abstract

The goals of cryptography are achieved using mathematically strong crypto-algorithms, which are adopted for securing data and
communication. Even though the algorithms are mathematically
secure, the implementation of these algorithms may be vulnerable to
side-channel attacks such as timing and power analysis attacks. One
of the effective countermeasures against such attacks is Threshold Implementation(TI). However, TI realization in crypto-device introduces
hardware complexity, so it shall not be suitable for resource-constrained
devices. Therefore, there is a need for efficient and effective countermeasure techniques for resource-constrained devices. In this work, we propose a lightweight countermeasure using an Arbiter Physical Unclonable Function (A-PUF) to obfuscate intermediate values in the register for rolled and unrolled implementation of Advanced Encryption Standard (AES). The countermeasure is realized in rolled (iterative) implementation of AES in a 65nm Field Programmable Gate Array (FPGA). We have analyzed the security strength and area of the obfuscated AES using A-PUF and compared it with conventional (rolled AES) and masked TI of AES. Further, we have illustrated the effectiveness of pre-charge and neutralizing countermeasures to strengthen the side channel resistance. We have discussed the complexity of mounting a side channel and modeling attacks on obfuscated AES using A-PUF.



## 2023/48

* Title: On-Line/Off-Line DCR-based Homomorphic Encryption and Applications
* Authors: Marc Joye
* [Permalink](https://eprint.iacr.org/2023/048)
* [Download](https://eprint.iacr.org/2023/048.pdf)

### Abstract

On-line/off-line encryption schemes enable the fast encryption of a message from a pre-computed coupon. The paradigm was put forward in the case of digital signatures.
This work introduces a compact public-key additively homomorphic encryption scheme. The scheme is semantically secure under the decisional composite residuosity (DCR) assumption. Compared to Paillier cryptosystem, it merely requires one or two integer additions in the on-line phase and no increase in the ciphertext size. This work also introduces a compact on-line/off-line trapdoor commitment scheme featuring the same fast on-line phase. Finally, applications to chameleon signatures are presented.



## 2023/49

* Title: Implementing and Benchmarking Word-Wise Homomorphic Encryption Schemes on GPU
* Authors: Hao Yang, Shiyu Shen, Wangchen Dai, Lu Zhou, Zhe Liu, Yunlei Zhao
* [Permalink](https://eprint.iacr.org/2023/049)
* [Download](https://eprint.iacr.org/2023/049.pdf)

### Abstract

Homomorphic encryption (HE) is one of the most promising techniques for privacy-preserving computations, especially the word-wise HE schemes that allow batched computations over ciphertexts. However, the high computational overhead hinders the deployment of HE in real-word applications. The GPUs are often used to accelerate the execution in such scenarios, while the performance of different HE schemes on the same GPU platform is still absent.
In this work, we implement three word-wise HE schemes BGV, BFV, and CKKS on GPU, with both theoretical and engineering optimizations. We optimize the hybrid key-switching technique, reducing the computational and memory overhead of this procedure. We explore several kernel fusing strategies to reuse data, which reduces the memory access and IO latency, and improves the overall performance. By comparing with the state-of-the-art works, we demonstrate the effectiveness of our implementation.
Meanwhile, we present a framework that finely integrates our implementation of the three schemes, covering almost all scheme functions and homomorphic operations. We optimize the management of pre-computation, RNS bases and memory in the framework, to provide efficient and low-latency data access and transfer. Based on this framework, we provide a thorough benchmark of the three schemes, which can serve as a reference for scheme selection and implementation in constructing privacy-preserving applications.



## 2023/50

* Title: A Practical Template Attack on CRYSTALS-Dilithium
* Authors: Alexandre Berzati, Andersson Calle Viera, Maya Chartouni, Steven Madec, Damien Vergnaud, David Vigilant
* [Permalink](https://eprint.iacr.org/2023/050)
* [Download](https://eprint.iacr.org/2023/050.pdf)

### Abstract

This paper presents a new profiling side-channel attack on the signature scheme CRYSTALS-Dilithium, which has been selected by the NIST as the new primary standard for quantum-safe digital signatures. This algorithm has a constant-time implementation with consideration for side-channel resilience. However, it does not protect against attacks that exploit intermediate data leakage. We exploit such a leakage on a vector generated during the signing process and whose costly protection by masking is a matter of debate. We design a template attack that enables us to efficiently predict whether a given coefficient in one coordinate of this vector is zero or not. Once this value has been completely reconstructed, one can recover, using linear algebra methods, part of the secret key that is sufficient to produce universal forgeries. While our paper deeply discusses the theoretical attack path, it also demonstrates the validity of the assumption regarding the required leakage model, from practical experiments with the reference implementation on an ARM Cortex-M4.



## 2023/51

* Title: A proof of the Scholz conjecture on addition chains
* Authors: Theophilus Agama
* [Permalink](https://eprint.iacr.org/2023/051)
* [Download](https://eprint.iacr.org/2023/051.pdf)

### Abstract

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove the inequality $$\iota(2^n-1)\leq n-1+\iota(n)$$ where $\iota(n)$ denotes the length of the shortest addition chain producing $n$.



## 2023/52

* Title: Putting the Online Phase on a Diet: Covert Security from Short MACs
* Authors: Sebastian Faust, Carmit Hazay, David Kretzler, Benjamin Schlosser
* [Permalink](https://eprint.iacr.org/2023/052)
* [Download](https://eprint.iacr.org/2023/052.pdf)

### Abstract

An important research direction in secure multi-party computation (MPC) is to improve the efficiency of the protocol. One idea that has recently received attention is to consider a slightly weaker security model than full malicious security -- the so-called setting of $\textit{covert security}$. In covert security, the adversary may cheat but only is detected with certain probability. Several works in covert security consider the offline/online approach, where during a costly offline phase correlated randomness is computed, which is consumed in a fast online phase. State-of-the-art protocols focus on improving the efficiency by using a covert offline phase, but ignore the online phase. In particular, the online phase is usually assumed to guarantee security against malicious adversaries. In this work, we take a fresh look at the offline/online paradigm in the covert security setting. Our main insight is that by weakening the security of the online phase from malicious to covert, we can gain significant efficiency improvements during the offline phase. Concretely, we demonstrate our technique by applying it to the online phase of the well-known TinyOT protocol (Nielsen et al., CRYPTO '12). The main observation is that by reducing the MAC length in the online phase of TinyOT to $t$ bits, we can guarantee covert security with a detection probability of $1- \frac{1}{2^t}$. Since the computation carried out by the offline phase depends on the MAC length, shorter MACs result in a more efficient offline phase and thus speed up the overall computation. Our evaluation shows that our approach reduces the communication complexity of the offline protocol by at least 35% for a detection rate up to $\frac{7}{8}$. In addition, we present a new generic composition result for analyzing the security of online/offline protocols in terms of concrete security.



## 2023/53

* Title: 𝑃3𝑉 : Privacy-Preserving Path Validation System for Multi-Authority Sliced Networks
* Authors: Weizhao Jin, Erik Kline, T. K. Satish Kumar, Lincoln Thurlow, Srivatsan Ravi
* [Permalink](https://eprint.iacr.org/2023/053)
* [Download](https://eprint.iacr.org/2023/053.pdf)

### Abstract

In practical operational networks, it is essential to validate path integrity, especially when untrusted intermediate nodes are from numerous network infrastructures operated by several network authorities. Current solutions often reveal the entire path to all parties involved, which may potentially expose the network structures to malicious intermediate attackers. Additionally, there is no prior work done to provide a systematic approach combining the complete lifecycle of packet delivery, i.e., path slicing, path validation and path rerouting, leaving these highly-intertwined modules completely separated. In this work, we present a decentralized privacy-preserving path validation system 𝑃3𝑉 that integrates our novel path validation protocol with an efficient path slicing algorithm and a malice-resilient path rerouting mechanism. Specifically, leveraging Non-Interactive Zero-Knowledge proofs, our path validation protocol XOR-Hash-NIZK protects the packet delivery tasks against information leakage about multi-hop paths and potentially the underlying network infrastructures. We implemented and evaluated our system on a state-of-the-art 5G Dispersed Computing Testbed simulating a multi-authority network. Our results show that while preserving the privacy of paths and nodes and enhancing the security of network service, our system optimizes the performance trade-off between network service quality and security/privacy.



## 2023/54

* Title: On the Incoercibility of Digital Signatures
* Authors: Ashley Fraser, Lydia Garms, Elizabeth A. Quaglia
* [Permalink](https://eprint.iacr.org/2023/054)
* [Download](https://eprint.iacr.org/2023/054.pdf)

### Abstract

We introduce incoercible digital signature schemes, a variant of a standard digital signature. Incoercible signatures enable signers, when coerced to produce a signature for a message chosen by an attacker, to generate fake signatures that are indistinguishable from real signatures, even if the signer is compelled to reveal their full history (including their secret signing keys and any randomness used to produce keys/signatures) to the attacker. Additionally, we introduce an authenticator that can detect fake signatures, which ensures that coercion is identified. We present a formal security model for incoercible signature schemes that comprises an established definition of unforgeability and captures new notions of weak receipt-freeness, strong receipt-freeness and coercion-resistance. We demonstrate that an incoercible signature scheme can be viewed as a transformation of any generic signature scheme. Indeed, we present two incoercible signature scheme constructions that are built from a standard signature scheme and a sender-deniable encryption scheme. We prove that our first construction satisfies coercion-resistance, and our second satisfies strong receipt-freeness. We conclude by presenting an extension to our security model: we show that our security model can be extended to the designated verifier signature scheme setting in an intuitive way as the designated verifier can assume the role of the authenticator and detect coercion during the verification process.



## 2023/55

* Title: An analysis of a scheme proposed for electronic voting systems
* Authors: Nicu Neculache, Vlad-Andrei Petcu, Emil Simion
* [Permalink](https://eprint.iacr.org/2023/055)
* [Download](https://eprint.iacr.org/2023/055.pdf)

### Abstract

Voting mechanisms allow the expression of the elections by a democratic approach. Any voting scheme must ensure, preferably in an efficient way, a series of safety measures such as confidentiality, integrity and anonymity. Since the 1980s, the concept of electronic voting became more and more of interest, being an advantageous or even necessary alternative for the organization of secure elections. In this paper, we give an overview for the e-voting mechanisms together with the security features they must fulfill. Then we focus on the blind signature paradigm, specifically on the Pairing Free Identity-Based Blind Signature Scheme with Message Recovery (PF-IDBS-MR). Our goal is to give a better understanding on the PF-IDBS-MR scheme by offering an adaptation on the standard voting protocol’s phases. More important, we analyze if the general security requirements and the recommendations proposed by the Council of Europe are met by the scheme.



## 2023/56

* Title: Quantum Annealing for Subset Product and Noisy Subset Product
* Authors: Trey Li
* [Permalink](https://eprint.iacr.org/2023/056)
* [Download](https://eprint.iacr.org/2023/056.pdf)

### Abstract

In recent works of Li the noisy subset product problem (also known as subset product with errors) was invented and applied to cryptography. To better understand its hardness, we give a quantum annealing algorithm for it. Our algorithm is the first algorithm for the problem. We also give the first quantum annealing algorithm for the subset product problem. The efficiencies of both algorithms rely on the fundamental efficiency of quantum annealing. At the end we give two lattice algorithms for both problems via solving the closest vector problem. The complexities of the lattice algorithms depend on the complexities of solving the closest vector problem in two special lattices. They are efficient when the special closest vector problems fall into the regime of bounded distance decoding problems that can be efficiently solved using existing methods based on the LLL algorithm or Babai's nearest plane algorithm.



## 2023/57

* Title: DY Fuzzing: Formal Dolev-Yao Models Meet Protocol Fuzz Testing
* Authors: Max Ammann, Lucca Hirschi, Steve Kremer
* [Permalink](https://eprint.iacr.org/2023/057)
* [Download](https://eprint.iacr.org/2023/057.pdf)

### Abstract

Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, i.e. attacks that solely exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is today still out of reach. This leaves open whether widely used protocol implementations are secure. Unfortunately, this blind spot hides numerous attacks, notably recent logical attacks on widely used TLS implementations introduced by implementation bugs.
We answer by proposing a novel and effective technique that we call DY model-guided fuzzing, which precludes logical attacks against protocol implementations. The main idea is to consider as possible test cases the set of abstract DY executions of the DY attacker, and use a mutation-based fuzzer to explore this set. The DY fuzzer concretizes each abstract execution to test it on the program under test. This approach enables reasoning at a more structural and security-related level of messages (e.g. decrypt a message and re-encrypt it with a different key) as opposed to random bit-level modifications that are much less likely to produce relevant logical adversarial behaviors. We implement a full-fledged and modular DY protocol fuzzer. We demonstrate its effectiveness by fuzzing three popular TLS implementations, resulting in the discovery of four novel vulnerabilities.



## 2023/58

* Title: SCALLOP: scaling the CSI-FiSh
* Authors: Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, Benjamin Wesolowski
* [Permalink](https://eprint.iacr.org/2023/058)
* [Download](https://eprint.iacr.org/2023/058.pdf)

### Abstract

We present SCALLOP: SCALable isogeny action based on
Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and
OSIDH, we use the group action of an imaginary quadratic order’s class
group on the set of oriented supersingular curves. Compared to CSIDH,
the main benefit of our construction is that it is easy to compute the
class-group structure; this data is required to uniquely represent— and
efficiently act by— arbitrary group elements, which is a requirement in,
e.g., the CSI-FiSh signature scheme by Beullens, Kleinjung and Vercauteren. The index-calculus algorithm used in CSI-FiSh to compute
the class-group structure has complexity L(1/2), ruling out class groups
much larger than CSIDH-512, a limitation that is particularly problematic in light of the ongoing debate regarding the quantum security of
cryptographic group actions.
Hoping to solve this issue, we consider the class group of a quadratic order of large prime conductor inside an imaginary quadratic field of small
discriminant. This family of quadratic orders lets us easily determine
the size of the class group, and, by carefully choosing the conductor,
even exercise significant control on it— in particular supporting highly
smooth choices. Although evaluating the resulting group action still has
subexponential asymptotic complexity, a careful choice of parameters
leads to a practical speedup that we demonstrate in practice for a security level equivalent to CSIDH-1024, a parameter currently firmly out of reach of index-calculus-based methods. However, our implementation
takes 35 seconds (resp. 12.5 minutes) for a single group-action evaluation at a CSIDH-512-equivalent (resp. CSIDH-1024-equivalent) security
level, showing that, while feasible, the SCALLOP group action does not
achieve realistically usable performance yet.



## 2023/59

* Title: Oil and Vinegar: Modern Parameters and Implementations
* Authors: Ward Beullens, Ming-Shing Chen, Shih-Hao Hung, Matthias J. Kannwischer, Bo-Yuan Peng, Cheng-Jhih Shih, Bo-Yin Yang
* [Permalink](https://eprint.iacr.org/2023/059)
* [Download](https://eprint.iacr.org/2023/059.pdf)

### Abstract

Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, either made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We show that, if parametrized appropriately, Oil and Vinegar still provides competitive performance compared to the new NIST standards by most measures (except for key size). At NIST security level 1, this results in either 128-byte signatures with 44 kB public keys or 96-byte signatures with 67 kB public keys. We revamp the state-of-the-art of Oil and Vinegar implementations for the Intel/AMD AVX2, the Arm Cortex-M4 microprocessor, the Xilinx Artix-7 FPGA, and the Armv8-A microarchitecture with the Neon vector instructions set.



## 2023/60

* Title: Silph: A Framework for Scalable and Accurate Generation of Hybrid MPC Protocols
* Authors: Edward Chen, Jinhao Zhu, Alex Ozdemir, Riad S. Wahby, Fraser Brown, Wenting Zheng
* [Permalink](https://eprint.iacr.org/2023/060)
* [Download](https://eprint.iacr.org/2023/060.pdf)

### Abstract

Many applications in finance and healthcare need access to data from multiple organizations. While these organizations can benefit from computing on their joint datasets, they often cannot share data with each other due to regulatory constraints and business competition. One way mutually distrusting parties can collaborate without sharing their data in the clear is to use secure multiparty computation (MPC). However, MPC’s performance presents a serious obstacle for adoption as it is difficult for users who lack expertise in advanced cryptography to optimize. In this paper, we present Silph, a framework that can automatically compile a program written in a high-level language to an optimized, hybrid MPC protocol that mixes multiple MPC primitives securely and
efficiently. Compared to prior works, our compilation speed is improved by up to 30000×. On various database analytics
and machine learning workloads, the MPC protocols generated by Silph match or outperform prior work by up to 3.6×.



## 2023/61

* Title: Key-and-Signature Compact Multi-Signatures: A Compiler with Realizations
* Authors: Shaoquan Jiang, Dima Alhadidi, Hamid Fazli Khojir
* [Permalink](https://eprint.iacr.org/2023/061)
* [Download](https://eprint.iacr.org/2023/061.pdf)

### Abstract

Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this paper, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our results is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with key-and-signature compact without a restart during signing process.



## 2023/62

* Title: Post-Quantum Secure Deterministic Wallet: Stateless, Hot/Cold Setting, and More Secure
* Authors: Mingxing Hu
* [Permalink](https://eprint.iacr.org/2023/062)
* [Download](https://eprint.iacr.org/2023/062.pdf)

### Abstract

Since the invention of Bitcoin, cryptocurrencies have gained
huge popularity. Crypto wallet, as the tool to store and manage the
cryptographic keys, is the primary entrance for the public to access
cryptocurrency funds. Deterministic wallet is an advanced wallet mecha-
nism that has been proposed to achieve some appealing virtues, such as
low-maintenance, easy backup and recovery, supporting functionalities
required by cryptocurrencies, and so on. However, the existing deter-
ministic wallet schemes especially in the quantum world still have a long
way to be practical. The first barrier is how to build a deterministic
wallet scheme without relying on the state, i.e., stateless. The stateful
deterministic wallet scheme must internally maintain and keep refreshing
synchronously a parameter named state which makes the implementa-
tion in practice become more complex. And once one of the states is
leaked, thereafter the security notion of unlinkability is cannot be guar-
anteed (referred to as the weak security notion of forward unlinkability).
The second barrier is how to derive the session secret keys from the
master secret key in one-way. There are security shortfalls in previous
works, they suffer a fatal vulnerability when a minor fault happens (say,
one derived key is compromised somehow), then the damage is not lim-
ited to the leaked derived key, instead, it spreads to the master key
and the whole system collapses. The third barrier is how to build a post-
quantum secure deterministic wallet scheme supporting hot/cold setting,
which is important since nearly all popular cryptocurrencies relied on the
hardness problems that can be broken by quantum adversaries, and the
hot/cold setting is a widely adopted method to effectively reduce the
exposure chance of secret keys and hence improving the security of the
system. The last barrier is how to build a deterministic wallet scheme
with standard security notion of unforgeability. It is motivated by pre-
vious works which are based on a weaker/nonstandard unforgeability
notion, in which the adversary is only allowed to query and forge the
signatures w.r.t. the public keys that were assigned by the challenger.

In this work, we present a new deterministic wallet scheme in quantum
world, which is stateless, supports hot/cold setting, satisfiies stronger
security notions, and is more efficient. In particular, we reformalize the
syntax and security models for deterministic wallets, capturing the func-
tionality and security requirements (including full unlinkability and stan-
dard unforgeability) imposed by the practice in cryptocurrency. Then
we propose a deterministic wallet construction and prove its security in the quantum random oracle model. Finally, we show our wallet scheme
is more practicable by analyzing an instantiation of our wallet scheme
based on the signature scheme Falcon.



## 2023/63

* Title: Threshold Signatures in the Multiverse
* Authors: Leemon Baird, Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, Yinuo Zhang
* [Permalink](https://eprint.iacr.org/2023/063)
* [Download](https://eprint.iacr.org/2023/063.pdf)

### Abstract

We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe.

We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink's use in the wild) each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 97$\times$ larger, (ii) have aggregation times 311$\times$ worse, or (iii) have signature size 39$\times$ and verification gas costs 3.38$\times$ larger. We also provide an open-source implementation and a detailed evaluation.



## 2023/64

* Title: Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves
* Authors: Antonin Leroux
* [Permalink](https://eprint.iacr.org/2023/064)
* [Download](https://eprint.iacr.org/2023/064.pdf)

### Abstract

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $P$. For that, we revisit the idea of working with supersingular elliptic curves.
The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has provided all the tools to perform the necessary tasks efficiently.

Our main ingredients are two new heuristic algorithms to compute the $j$-invariants of supersingular curves having an endomorphism ring contained in some set of isomorphism class of maximal orders. The first one is derived easily from the existing tools of isogeny-based cryptography, while the second introduces new ideas to perform that task efficiently for a big number of maximal orders.

From there, we obtain two main results.
First, we show that we can associate these two algorithms with some operations over the quaternion algebra ramified at $P$ and infinity to compute directly Hilbert and modular polynomials $\mod P$.
In that manner, we obtain the first algorithms to compute Hilbert (resp. modular) polynomials modulo $P$ for a good portion of all (resp. all) primes $P$ with a complexity in $O(\sqrt{|D|})$ for the discriminant $D$ (resp. $O(\ell^2)$ for the level $\ell$).
Due to the (hidden) complexity dependency on $P$, these algorithms do not outperform the best known algorithms for all prime $P$ but they still provide an asymptotic improvement for a range of prime going up to a bound that is sub-exponential in $|D|$ (resp. $\ell$).


Second, we revisit the CRT method for both class and modular polynomials. We show that applying our second heuristic algorithm over supersingular curves to the CRT approach yields the same asymptotic complexity as the best known algorithms based on ordinary curves and we argue that our new approach might be more efficient in practice.
The situation appears especially promising for modular polynomials, as our approach reduces the asymptotic cost of elliptic curve operations by a linear factor in the level $\ell$. We obtain an algorithm whose asymptotic complexity is now fully dominated by linear algebra and standard polynomial arithmetic over finite fields.



## 2023/65

* Title: A Practical TFHE-Based Multi-Key Homomorphic Encryption with Linear Complexity and Low Noise Growth
* Authors: Jakub Klemsa, Melek Önen, Yavuz Akın
* [Permalink](https://eprint.iacr.org/2023/065)
* [Download](https://eprint.iacr.org/2023/065.pdf)

### Abstract

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties.

In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.



## 2023/66

* Title: Plonkup scheme with multiple queries
* Authors: Alexandr Bulkin, Tim Dokchitser
* [Permalink](https://eprint.iacr.org/2023/066)
* [Download](https://eprint.iacr.org/2023/066.pdf)

### Abstract

There is a line of 'lookup' protocols to show that all elements of a sequence $f\in{\mathbb F}^n$ are contained in a table $t\in{\mathbb F}^d$, for some field ${\mathbb F}$. Lookup has become an important primitive in Zero Knowledge Virtual Machines, and is used for range checks and other parts of the proofs of a correct program execution. In this note we give several variants of the protocol. We adapt it to the situation when there are multiple lookups with the same table (as is usually the case with range checks), and handle also 'bounded lookup' that caps the number of repetitions.