[digest] 2024 Week 51

## In this issue

1. [2023/1396] Accelerating Isogeny Walks for VDF Evaluation
2. [2023/1533] On Linear Equivalence, Canonical Forms, and Digital ...
3. [2024/2031] Covert 19th century political intrigues of Tenerife ...
4. [2024/2032] Carousel: Fully Homomorphic Encryption from Slot ...
5. [2024/2033] General Practical Cryptanalysis of the Sum of ...
6. [2024/2034] The Jacobi Factoring Circuit: Quantum Factoring ...
7. [2024/2035] A Heuristic Proof of P $\neq$ NP
8. [2024/2036] Simple is COOL: Graded Dispersal and its ...
9. [2024/2037] Multilateral Trade Credit Set-off in MPC via Graph ...
10. [2024/2038] Adaptive Special Soundness: Improved Knowledge ...
11. [2024/2039] Revisiting Boomerang Attacks on Lightweight ARX and ...
12. [2024/2040] Verified Foundations for Differential Privacy
13. [2024/2041] SeaSearch: Secure and Efficient Selection Queries
14. [2024/2042] A Note on Isogeny Group Action-Based Pseudorandom ...
15. [2024/2043] Efficient Error-tolerant Side-channel Attacks on ...
16. [2024/2044] Cryptographic Commitments on Anonymizable Data
17. [2024/2045] Cryptanalysis of TETRA Encryption Algorithms - ...
18. [2024/2046] Decompressing Dilithium's Public Key with Fewer ...
19. [2024/2047] Breaking and Provably Restoring Authentication: A ...
20. [2024/2048] How to Compress Garbled Circuit Input Labels, ...
21. [2024/2049] BBB Secure Arbitrary Length Tweak TBC from n-bit ...
22. [2024/2050] Simulation Secure Multi-Input Quadratic Functional ...
23. [2024/2051] Simple Power Analysis assisted Chosen Cipher-Text ...
24. [2024/2052] Improved Rejection Sampling for Compact Lattice ...
25. [2024/2053] Optimally Secure TBC Based Accordion Mode
26. [2024/2054] Greedy Algorithm for Representative Sets: ...
27. [2024/2055] Zeroed Out: Cryptanalysis of Weak PRFs in ...
28. [2024/2056] Exact Template Attacks with Spectral Computation
29. [2024/2057] Leveraging remote attestation APIs for secure image ...
30. [2024/2058] Learning with Errors from Nonassociative Algebras
31. [2024/2059] Minimizing the Use of the Honest Majority in YOSO ...
32. [2024/2060] "These results must be false": A usability ...

## 2023/1396

* Title: Accelerating Isogeny Walks for VDF Evaluation
* Authors: David Jacquemin, Anisha Mukherjee, Ahmet Can Mert, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2023/1396)
* [Download](https://eprint.iacr.org/2023/1396.pdf)

### Abstract

VDFs are characterized by sequential function evaluation but an immediate output verification. In order to ensure secure use of VDFs in real-world applications, it is important to determine the fastest implementation. Considering the point of view of an attacker (say with unbounded resources), this paper aims to accelerate the isogeny-based VDF proposed by De Feo-Mason-Petit-Sanso in 2019. It is the first work that implements a hardware accelerator for the evaluation step of an isogeny VDF. To meet our goal, we use redundant representations of integers and introduce a new lookup table-based algorithm for modular reduction. We also provide both a survey of elliptic curve arithmetic to arrive at the most cost-effective curve computations and an in-depth cost analysis of the different base degree isogeny and method for the isogeny evaluation. The evaluation step of a VDF is defined to be sequential, which means that there is limited scope for parallelism. Nevertheless, taking this constraint into account our proposed design targets the highest levels of parallelism possible on an architectural level of an isogeny VDF implementation. We provide a technology-independent metric to model the delay of isogeny evaluation, which a VDF developer can use to derive secure parameters. ASIC synthesis results in 28nm are used as a baseline to estimate VDF parameters.



## 2023/1533

* Title: On Linear Equivalence, Canonical Forms, and Digital Signatures
* Authors: Tung Chou, Edoardo Persichetti, Paolo Santini
* [Permalink](https://eprint.iacr.org/2023/1533)
* [Download](https://eprint.iacr.org/2023/1533.pdf)

### Abstract

Given two linear codes, the code equivalence problem asks to find an isometry mapping one code into the other.
The problem can be described in terms of group actions and, as such, finds a natural application in signatures derived from a Zero-Knowledge Proof system.

A recent paper, presented at Asiacrypt 2023, showed how a proof of equivalence can be significantly compressed by describing how the isometry acts only on an information set. Still, the resulting signatures are far from being optimal, as the size for a witness to this relation is still significantly larger than the theoretical lower bound, which is twice the security parameter.

In this paper, we fill this gap and propose a new notion of equivalence, which leads to a drastically reduced witness size. For many cases, the resulting size is exactly the optimal one given by the lower bound. We achieve this by introducing the framework of canonical representatives, that is, representatives for classes of codes which are equivalent under some notion of equivalence. We propose new notions of equivalence which encompass and further extend all the existing ones: this allows to identify broader classes of equivalent codes, for which the equivalence can be proved with a very compact witness. We associate these new notions to a specific problem, called Canonical Form Linear Equivalence Problem (CF-LEP), which we show to be as hard as the original one (when random codes are considered), providing reductions in both ways. As an added consequence, this reduction leads to a new solver for the code equivalence problem, which is the fastest solver when the finite field size is large enough. Finally, we show that our framework yields a remarkable reduction in signature size when compared to the LESS submission.

Our variant is able to obtain very compact signatures, around 2 KB or less, which are among the smallest in the code-based setting.



## 2024/2031

* Title: Covert 19th century political intrigues of Tenerife nobility revealed by cryptanalyzing an encrypted letter
* Authors: Jezabel Molina-Gil, Cándido Caballero-Gil, Judit Gutiérrez-de-Armas, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/2031)
* [Download](https://eprint.iacr.org/2024/2031.pdf)

### Abstract

This article presents a cryptanalysis of a 19th-century encrypted manuscript discovered in the archives of Conde de Siete Fuentes in Tenerife, Canary Islands, Spain. The manuscript, preserved by the heirs of the 6th Count of Valle de Salazar, utilizes a polyalphabetic substitution cipher. The cryptanalysis was performed by applying statistical frequency analysis and developing a Python script for decryption, resulting in the authors successfully deciphering the message. The decrypted letter reveals political communications discussing the strategic positioning of Tenerife as the capital, the dissolution of local councils, and the influence of key political figures. The analysis compares the cipher with historical encryption techniques, and identifies the unique characteristics of the manuscript’s encryption method. The study highlights the political dynamics and alliances within Tenerife’s nobility and their interactions with the central Spanish government, providing significant insights into, both, the cryptographic practices and political maneuvers of the time.



## 2024/2032

* Title: Carousel: Fully Homomorphic Encryption from Slot Blind Rotation Technique
* Authors: Seonhong Min, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/2032)
* [Download](https://eprint.iacr.org/2024/2032.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) enables secure computation of functions on ciphertexts without requiring decryption. Specifically, AP-like HE schemes exploit an intrinsic bootstrapping method called blind rotation. In blind rotation, a look-up table is homomorphically evaluated on the input ciphertext through the iterative multiplication of monomials. However, the algebraic structure of the multiplicative group of monomials imposes certain limitations on the input and output plaintext space: 1. only a fraction of the input plaintext space can be bootstrapped, 2. the output plaintext space is restricted to subsets of real numbers.

In this paper, we design a novel bootstrapping method called slot blind rotation. The key idea of our approach is to utilize the automorphism group instead of monomials. More specifically, the look-up table is encoded into a single polynomial using SIMD (Single Instruction Multiple Data) packing and is rotated via a series of homomorphic multiplications and automorphisms. This method achieves two significant advantages: 1. the entire input plaintext space can be bootstrapped, 2. a more broad output plaintext space, such as complex numbers or finite field/rings can be supported.

Finally, we present a new HE scheme leveraging the slot blind rotation technique and provide a proof-of-concept implementation. We also demonstrate the the benchmark results and provide recommended parameter sets.



## 2024/2033

* Title: General Practical Cryptanalysis of the Sum of Round-Reduced Block Ciphers and ZIP-AES
* Authors: Antonio Flórez-Gutiérrez, Lorenzo Grassi, Gregor Leander, Ferdinand Sibleyras, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2024/2033)
* [Download](https://eprint.iacr.org/2024/2033.pdf)

### Abstract

We introduce a new approach between classical security proofs of modes of operation and dedicated security analysis for known cryptanalysis families: General Practical Cryptanalysis. This allows us to analyze generically the security of the sum of two keyed permutations against known attacks. In many cases (of course, not all), we show that the security of the sum is strongly linked to that of the composition of the two permutations. This enables the construction of beyond-birthday bound secure low-latency PRFs by cutting a known-to-be-secure block cipher into two equal parts. As a side result, our general analysis shows an inevitable difficulty for the key recovery based on differential-type attacks against the sum, which leads to a correction of previously published attacks on the dedicated design Orthros.



## 2024/2034

* Title: The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
* Authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk
* [Permalink](https://eprint.iacr.org/2024/2034)
* [Download](https://eprint.iacr.org/2024/2034.pdf)

### Abstract

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number $N$, whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if not all exponents are the same. In particular, to factor an $n$-bit integer $N=P^2 Q$ (with $P$ and $Q$ prime, and $Q<2^m$ for some $m$), our circuit uses $\widetilde{O}(m)$ qubits and has depth at most $\widetilde{O}(m + n/m)$, with $\widetilde{O}(n)$ quantum gates. When $m=\Theta(n^a)$ with $2/3 < a < 1$, the space and depth are sublinear in $n$, yet no known classical algorithms exploit the relatively small size of $Q$ to run faster than general-purpose factoring algorithms. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known.

The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Crucially, our circuit reads the bits of the classical value $B$ in a streaming fashion, never storing more than $\widetilde{O}(\log A)$ qubits of quantum information at one time. In the context of the larger Jacobi algorithm for factoring $N = P^2Q$, this reduces the overall qubit count to be roughly proportional to the length of $Q$, rather than the length of $N$. Our circuit for computing the Jacobi symbol is also highly gate-efficient and parallelizable, achieving gate count $\widetilde{O}(\log B)$ and depth at most $\widetilde{O}(\log A + \log B/\log A)$. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems, such as computing the greatest common divisor, and thus could be of independent interest.



## 2024/2035

* Title: A Heuristic Proof of P $\neq$ NP
* Authors: Ping Wang
* [Permalink](https://eprint.iacr.org/2024/2035)
* [Download](https://eprint.iacr.org/2024/2035.pdf)

### Abstract

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. In this paper, we introduce a new language, the Add/XNOR problem, which has the simplest structure and perfect randomness, by extending the subset sum problem. We prove that P $\neq$ NP as it shows that the square-root complexity is necessary to solve the Add/XNOR problem. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time.



## 2024/2036

* Title: Simple is COOL: Graded Dispersal and its Applications for Byzantine Fault Tolerance
* Authors: Ittai Abraham, Gilad Asharov, Anirudh Chandramouli
* [Permalink](https://eprint.iacr.org/2024/2036)
* [Download](https://eprint.iacr.org/2024/2036.pdf)

### Abstract

The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size $L$ bits, its communication complexity is $O(nL+n^2 \log n)$, which is optimal up to a $\log n$ factor.
Unfortunately, Chen’s analysis is rather intricate and complex.

Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments.
Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible.  In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%.


In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.



## 2024/2037

* Title: Multilateral Trade Credit Set-off in MPC via Graph Anonymization and Network Simplex
* Authors: Enrico Bottazzi, Chan Nam Ngo, Masato Tsutsumi
* [Permalink](https://eprint.iacr.org/2024/2037)
* [Download](https://eprint.iacr.org/2024/2037.pdf)

### Abstract

Multilateral Trade Credit Set-off (MTCS) is a process run by a service provider that collects trade credit data (i.e. obligations from a firm to pay another firm) from a network of firms and detects cycles of debts that can be removed from the system. The process yields liquidity savings for the participants, who can discharge their debts without relying on expensive loans. We propose an MTCS protocol that protects firms' sensitive data, such as the obligation amount or the identity of the firms they trade with. Mathematically, this is analogous to solving the Minimum Cost Flow (MCF) problem over a graph of $n$ firms, where the $m$ edges are the obligations. State-of-the-art techniques for Secure MCF have an overall complexity of $O(n^{10} \log n)$ communication rounds, making it barely applicable even to small-scale instances. Our solution leverages novel secure techniques such as Graph Anonymization and Network Simplex to reduce the complexity of the MCF problem to $O(max(n, \log\log{n+m}))$ rounds of interaction per pivot operations in which $O(max(n^2, nm))$ comparisons and multiplications are performed. Experimental results show the tradeoff between privacy and optimality.



## 2024/2038

* Title: Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling
* Authors: Thomas Attema, Michael Klooß, Russell W. F. Lai, Pavlo Yatsyna
* [Permalink](https://eprint.iacr.org/2024/2038)
* [Download](https://eprint.iacr.org/2024/2038.pdf)

### Abstract

Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the  evelopment of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer
to specify (2) which is often simple(r).

Recently, works by Bünz–Fisch (TCC’23) and Aardal et al. (CRYPTO’24) provide new frameworks, called almost special soundness and predicate special soundness, respectively. To handle insufficiencies of special soundness, they deviate from its spirit and augment it in different ways. The necessity for their changes is that special soundness does not allow the challenges for useful sets of transcripts to depend on the transcripts themselves, but only on the challenges in the transcripts. As a consequence, (generalised) special soundness cannot express extraction strategies which reduce a computational problem to finding “inconsistent” accepting transcripts, for example in PCP/IOP-based or lattice-based proof systems, and thus provide (very) sub-optimal extractors. In this work, we introduce adaptive special soundness which captures extraction strategies exploiting inconsistencies between transcripts, e.g. transcripts containing different openings of the same commitment. Unlike (generalised) special soundness (Attema, Fehr, and Resch (TCC’23)), which specifies a target transcript structure, our framework allows specifying an extraction strategy which guides the extractor to sample challenges adaptively based on the history of prior transcripts. We extend the recent (almost optional) extractor of Attema, Fehr, Klooß and Resch (EPRINT 2023/1945) to our notion, and argue that it encompasses almost special soundness and predicate special soundness in many cases of interest.

As a challenging application, we modularise and generalise the lattice Bulletproofs analysis by Bünz–Fisch (TCC’23) using the adaptive special soundness framework. Moreover, we extend their analysis to the ring setting for a slightly wider selection of rings than rational integers.



## 2024/2039

* Title: Revisiting Boomerang Attacks on Lightweight ARX and AND-RX Ciphers with Applications to KATAN, SIMON and CHAM
* Authors: Li Yu, Je Sen Teh
* [Permalink](https://eprint.iacr.org/2024/2039)
* [Download](https://eprint.iacr.org/2024/2039.pdf)

### Abstract

In this paper, we investigate the security of lightweight block ciphers, focusing on those that utilize the ADD-Rotate-XOR (ARX) and AND-Rotate-XOR (AND-RX) design paradigms. More specifically, we examine their resilience against boomerang-style attacks. First, we propose an automated search strategy that leverages the boomerang connectivity table (BCT) for AND operations ($\wedge BCT$) to conduct a complete search for boomerang and rectangle distinguishers for AND-RX ciphers. The proposed search strategy automatically considers all possible $\wedge BCT$ switches in the middle of the boomerang to optimise distinguishing probability. The correctness of the search strategy was verified experimentally. We were able to find the best boomerang and rectangle distinguishers to date in the single-key model for lightweight block ciphers KATAN32/48/64} and SIMON32/48. Next, we investigated BCT properties of ARX ciphers and discovered that a truncated boomerang switch could be formulated for the lightweight ARX cipher, CHAM. We were able to find the best single-key and related-key rectangle distinguishers to date for Cham.  Our findings provide more accurate security margins of these lightweight ciphers against boomerang-style attacks.



## 2024/2040

* Title: Verified Foundations for Differential Privacy
* Authors: Markus de Medeiros, Muhammad Naveed, Tancrède Lepoint, Temesghen Kahsai, Tristan Ravitch, Stefan Zetzsche, Anjali Joshi, Joseph Tassarotti, Aws Albarghouthi, Jean-Baptiste Tristan
* [Permalink](https://eprint.iacr.org/2024/2040)
* [Download](https://eprint.iacr.org/2024/2040.pdf)

### Abstract

Differential privacy (DP) has become the gold standard for privacy-preserving data analysis, but implementing
it correctly has proven challenging. Prior work has focused on verifying DP at a high level, assuming the
foundations are correct and a perfect source of randomness is available. However, the underlying theory of
differential privacy can be very complex and subtle. Flaws in basic mechanisms and random number generation
have been a critical source of vulnerabilities in real-world DP systems.

In this paper, we present SampCert, the first comprehensive, mechanized foundation for differential privacy.
SampCert is written in Lean with over 12,000 lines of proof. It offers a generic and extensible notion of DP, a
framework for constructing and composing DP mechanisms, and formally verified implementations of Laplace
and Gaussian sampling algorithms. SampCert provides (1) a mechanized foundation for developing the next
generation of differentially private algorithms, and (2) mechanically verified primitives that can be deployed in
production systems. Indeed, SampCert’s verified algorithms power the DP offerings of Amazon Web Services
(AWS), demonstrating its real-world impact.

SampCert’s key innovations include: (1) A generic DP foundation that can be instantiated for various DP
definitions (e.g., pure, concentrated, Rényi DP); (2) formally verified discrete Laplace and Gaussian sampling
algorithms that avoid the pitfalls of floating-point implementations; and (3) a simple probability monad and
novel proof techniques that streamline the formalization. To enable proving complex correctness properties of
DP and random number generation, SampCert makes heavy use of Lean’s extensive Mathlib library, leveraging
theorems in Fourier analysis, measure and probability theory, number theory, and topology.



## 2024/2041

* Title: SeaSearch: Secure and Efficient Selection Queries
* Authors: Shantanu Sharma, Yin Li, Sharad Mehrotra, Nisha Panwar, Komal Kumari, Swagnik Roychoudhury
* [Permalink](https://eprint.iacr.org/2024/2041)
* [Download](https://eprint.iacr.org/2024/2041.pdf)

### Abstract

Information-theoretic or unconditional security provides the highest level of security --- independent of the computational capability of an adversary. Secret-sharing techniques achieve information-theoretic security by splitting a secret into multiple parts (called shares) and storing the shares across non-colluding servers. However, secret-sharing-based solutions suffer from high overheads due to multiple communication rounds among servers and/or information leakage due to access-patterns (i.e.., the identity of rows satisfying a query) and volume (i.e., the number of rows satisfying a query).

We propose SeaSearch, an information-theoretically secure approach that uses both additive and multiplicative secret-sharing, to efficiently support a large class of selection queries involving conjunctive, disjunctive, and range conditions. Two major contributions of SeaSearch are:
(i) a new search algorithm using additive shares based on fingerprints, which were developed for string-matching over cleartext; and
(ii) two row retrieval algorithms: one is based on multiplicative shares and another is based on additive shares.
SeaSearch does not require communication among servers storing shares and does not reveal any information to an adversary based on access-patterns and volume.



## 2024/2042

* Title: A Note on Isogeny Group Action-Based Pseudorandom Functions
* Authors: Yi-Fu Lai
* [Permalink](https://eprint.iacr.org/2024/2042)
* [Download](https://eprint.iacr.org/2024/2042.pdf)

### Abstract

In PKC'24, de Saint Guilhem and Pedersen give a pseudorandom function basing on a relaxed group action assumption in the semi-honest setting. Basing on the assumption, they build an oblivious pseudorandom function (OPRF). Later, a recent paper by Levin and Pedersen uses the same function to build a verifiable random function (VRF), using the same assumption.

We give a structural attack on this problem by reducing it to a few group action inverse problems (GAIP/DLog) over small subgroups. This reduction allows us to apply a CRT-based attack to recover the secret key, ultimately lowering the problem’s effective security strength to under 70 classical bits when using CSIDH-512. Hence the strength of their pseudorandom functions is bounded above by the GAIP over the largest prime order subgroup. Clearly, Kuperberg’s subexponential attack can be used to further reduce its quantum security.



## 2024/2043

* Title: Efficient Error-tolerant Side-channel Attacks on GPV Signatures Based on Ordinary Least Squares Regression
* Authors: Jaesang Noh, Dongwoo Han, Dong-Joon Shin
* [Permalink](https://eprint.iacr.org/2024/2043)
* [Download](https://eprint.iacr.org/2024/2043.pdf)

### Abstract

The Gentry-Peikert-Vaikuntanathan (GPV) framework is utilized for constructing digital signatures, which is proven to be secure in the classical/quantum random-oracle model. Falcon is such a signature scheme, recognized as a compact and efficient signature among NIST-standardized signature schemes. Although a signature scheme based on the GPV framework is theoretically highly secure, it could be vulnerable to side-channel attacks and hence further research on physical attacks is required to make a robust signature scheme.
 We propose a general secret key recovery attack on GPV signatures using partial information about signatures obtained from side-channel attack. The three main contributions are summarized as follows.
 First, we introduce, for the first time, a concept of vulnerable partial information of GPV signatures and propose a secret key recovery attack, called OLS attack, which effectively utilizes partial information. In contrast to the approaches of Guerreau et al. (CHES 2022) and Zhang et al. (Eurocrypt 2023), which utilize filtered (or processed) signatures with hidden parallelepiped or learning slice schemes, the OLS attack leverages all the available signatures without filtering. We prove that the secret key recovered by the OLS attack converges to the real secret key in probability as the number of samples increases.
 Second, we utilize Gaussian leakage as partial information for the OLS attack on Falcon. As a result, the OLS attack shows a significantly higher success rate with fewer samples than the existing attack schemes. Furthermore, by incorporating the DDGR attack, the OLS attack can recover the secret key using much less samples with a success rate close to 100%. Moreover, we propose more efficient OLS attack on Falcon, which reduces the number of required side-channel attacks.
 Third, we propose an error-tolerant power analysis attack using MAP decoding, which effectively corrects the errors in samples to utilize Gaussian leakage correctly. In conclusion, the OLS attack is expected to strengthen the security of the GPV signatures including Falcon.



## 2024/2044

* Title: Cryptographic Commitments on Anonymizable Data
* Authors: Xavier Bultel, Céline Chevalier, Charlène Jojon, Diandian Liu, Benjamin Nguyen
* [Permalink](https://eprint.iacr.org/2024/2044)
* [Download](https://eprint.iacr.org/2024/2044.pdf)

### Abstract

Local Differential Privacy (LDP) mechanisms consist of (locally) adding controlled noise to data in order to protect the privacy of their owner. In this paper, we introduce a new cryptographic primitive called LDP commitment. Usually, a commitment ensures that the committed value cannot be modified before it is revealed. In the case of an LDP commitment, however, the value is revealed after being perturbed by an LDP mechanism. Opening an LDP commitment therefore requires a proof that the mechanism has been correctly applied to the value, to ensure that the value is still usable for statistical purposes. We also present a security model for this primitive, in which we define the hiding and binding properties. Finally, we present a concrete scheme for an LDP staircase mechanism (generalizing the randomized response technique), based on classical cryptographic tools and standard assumptions. We provide an implementation in Rust that demonstrates its practical efficiency (the generation of a commitment requires just a few milliseconds). On the application side, we show how our primitive can be used to ensure simultaneously privacy, usability and traceability of medical data when it is used for statistical studies in an open science context. We consider a scenario where a hospital provides sensitive patients data signed by doctors to a research center after it has been anonymized, so that the research center can verify both the provenance of the data (i.e. verify the doctors’ signatures even though the data has been noised) and that the data has been correctly anonymized (i.e. is usable even though it has been anonymized).



## 2024/2045

* Title: Cryptanalysis of TETRA Encryption Algorithms - Episode 1: TEA-3
* Authors: Jens Alich, Amund Askeland, Subhadeep Banik, Tim Beyne, Anne Canteaut, Patrick Felke, Gregor Leander, Willi Meier, Lukas Stennes
* [Permalink](https://eprint.iacr.org/2024/2045)
* [Download](https://eprint.iacr.org/2024/2045.pdf)

### Abstract

We present the first public and in-depth cryptanalysis of TEA-3, a stream cipher used in TETRA radio networks that was kept secret until recently. While the same also holds for the six other TETRA encryption algorithms, we pick TEA-3 to start with as (i) it is not obviously weakened as TEA-{1,4,7} but (ii) in contrast to TEA-2 it is approved only for extra-European emergency service, and (iii) as already noted by [MBW23] the TEA-3 design surprisingly contains a non-bijective S-box.  Most importantly, we show that the 80-bit non-linear feedback shift register operating on the key decomposes into a cascade of two 40-bit registers. Although this hints at an intentional weakness at first glance, we are not able to lift our results to a practical attack. Other than that, we show how the balanced non-linear feedback functions used in the state register of TEA-3 can be constructed.



## 2024/2046

* Title: Decompressing Dilithium's Public Key with Fewer Signatures Using Side Channel Analysis
* Authors: Ruize Wang, Joel Gärtner, Elena Dubrova
* [Permalink](https://eprint.iacr.org/2024/2046)
* [Download](https://eprint.iacr.org/2024/2046.pdf)

### Abstract

The CRYSTALS-Dilithium digital signature scheme, selected by NIST as a post-quantum cryptography (PQC) standard under the name ML-DSA, employs a public key compression technique intended for performance optimization. Specifically, the module learning with error instance $({\bf A}, {\bf t})$ is compressed by omitting the low-order bits ${\bf t_0}$ of the vector ${\bf t}$. It was recently shown that knowledge of ${\bf t_0}$ enables more effective side-channel attacks on Dilithium implementations. Another recent work demonstrated a method for reconstructing ${\bf t_0}$ from multiple signatures. In this paper, we build on this method by applying profiled deep learning-assisted side-channel analysis to partially recover the least significant bit of ${\bf t_0}$ from power traces. As a result, the number of signatures required for the reconstruction of ${\bf t_0}$ can be reduced by roughly half. We demonstrate how the new ${\bf t_0}$ reconstruction method enhances the efficiency of recovering the secret key component ${\bf s}_1$, and thus facilitates digital signature forgery, on an ARM Cortex-M4 implementation of Dilithium.



## 2024/2047

* Title: Breaking and Provably Restoring Authentication: A Formal Analysis of SPDM 1.2 including Cross-Protocol Attacks
* Authors: Cas Cremers, Alexander Dax, Aurora Naska
* [Permalink](https://eprint.iacr.org/2024/2047)
* [Download](https://eprint.iacr.org/2024/2047.pdf)

### Abstract

The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios.
In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering all of its modes – especially the complex interaction between its different key-exchange modes – in the framework of the Tamarin prover, making our resulting model one of the most complex Tamarin models to date. To our surprise, Tamarin finds a cross-protocol attack that allows a network attacker to completely break authentication of the pre-shared key mode. We implemented our attack on the SPDM reference implementation, and reported the issue to the SPDM developers. DMTF registered our attack as a CVE with CVSS rating 9 (critical).
We propose a fix and develop the first formal symbolic proof using the Tamarin prover for the fixed SPDM 1.2 protocol as a whole. The resulting model of the main modes and their interactions is highly complex, and we develop supporting lemmas to enable proving properties in the Tamarin prover, including the absence of all cross-protocol attacks. Our fix has been incorporated into both the reference implementation and the newest version of the standard. Our results highlight the need for a holistic analysis of other internet standards and the importance of providing generalized security guarantees across entire protocols.



## 2024/2048

* Title: How to Compress Garbled Circuit Input Labels, Efficiently
* Authors: Marian Dietz, Hanjun Li, Huijia Lin
* [Permalink](https://eprint.iacr.org/2024/2048)
* [Download](https://eprint.iacr.org/2024/2048.pdf)

### Abstract

Garbled Circuits are essential building blocks in cryptography, and extensive research has explored their construction from both applied and theoretical perspectives. However, a challenge persists: While theoretically designed garbled circuits offer optimal succinctness--remaining constant in size regardless of the underlying circuit’s complexit--and are reusable for multiple evaluations, their concrete computational costs are prohibitively high. On the other hand, practically efficient garbled circuits, inspired by Yao’s garbled circuits, encounter limitations due to substantial communication bottlenecks and a lack of reusability.

To strike a balance, we propose a novel concept: online-offline garbling. This approach leverages instance-independent and (partially) reusable preprocessing during an offline phase, to enable the creation of constant-size garbled circuits in an online phase, while maintaining practical efficiency. Specifically, during the offline stage, the garbler generates and transmits a reference string, independent of the computation to be performed later. Subsequently, in the online stage, the garbler efficiently transforms a circuit into a constant-size garbled circuit. The evaluation process relies on both the reference string and the garbled circuit.

We demonstrate that by leveraging existing tools such as those introduced by Applebaum et al. (Crypto’13) and Chongwon et al. (Crypto’17), online-offline garbling can be achieved under a variety of assumptions, including the hardness of Learning With Errors (LWE), Computational Diffie-Hellman (CDH), and factoring. In contrast, without the help of an offline phase, constant-size garbling is only feasible under the LWE and circular security assumptions, or the existence of indistinguishability obfuscation. However, these schemes are still very inefficient, several orders of magnitude more costly than Yao-style garbled circuits.

To address this, we propose a new online-offline garbling scheme based on Ring LWE. Our scheme offers both asymptotic and concrete efficiency. It serves as a practical alternative to Yao-style garbled circuits, especially in scenarios where online communication is constrained. Furthermore, we estimate the concrete latency using our approach in realistic settings and demonstrate that it is 2-20X faster than using Yao-style garbled circuits. This improvement is estimated without taking into account parallelization of computation, which can lead to further performance improvement using our scheme.



## 2024/2049

* Title: BBB Secure Arbitrary Length Tweak TBC from n-bit Block Ciphers
* Authors: Arghya Bhattacharjee, Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, Sougata Mandal
* [Permalink](https://eprint.iacr.org/2024/2049)
* [Download](https://eprint.iacr.org/2024/2049.pdf)

### Abstract

At FSE'15, Mennink introduced two tweakable block ciphers, $\widetilde{F}[1]$ and $\widetilde{F}[2]$, both utilizing an $n$-bit tweak. It was demonstrated that $\widetilde{F}[1]$ is secure for up to $2^{2n/3}$ queries, while $\widetilde{F}[2]$ is secure for up to $2^n$ queries, assuming the underlying block cipher is an ideal cipher with $n$-bit key and $n$-bit data. Later, at ASIACRYPT'16, Wang et al. showed a birthday bound attack on Mennink's design (which was later corrected in the eprint version {\textbf eprint 2015/363}) and proposed 32 new candidates for tweakable block ciphers that are derived from $n$-bit ideal block ciphers. It was shown that all the $32$ constructions are provably secure up to $2^n$ queries. All the proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher, $\widetilde{G2}$, which uses $2n$-bit tweaks and is constructed from three $n$-bit block cipher calls, proving its security up to $n$ bits, assuming that the underlying block cipher is an ideal cipher.. They have also shown that it is impossible to design a tweakable block cipher with $2n$-bit tweaks using only two $n$-bit block cipher calls while achieving security beyond the birthday bound. In this paper, we advance this research further. We show that any tweakable block cipher design with $3n$-bit tweaks based on only three block cipher calls, where at least one key is tweak-independent, is vulnerable to a birthday bound distinguishing attack. We then propose a tweakable block cipher, $\widetilde{\textsf{G}_3}^*$ that uses three block cipher calls and admits $3n$-bit tweaks, achieves security up to $O(2^{2n/3})$ queries when all three block cipher keys are tweak-dependent. Furthermore, we prove that using four ideal block cipher calls, with at least one key being tweak-dependent, is necessary and sufficient to achieve $n$-bit security for a tweakable block cipher that admits $3n$-bit tweaks. Finally, we propose a tweakable block cipher, $\widetilde{\textsf{G}_r}$, which uses $(r+1)$ block cipher calls and processes $rn$-bit tweaks, achieving security up to $O(2^n)$ queries when at least one block cipher key is tweak-dependent.



## 2024/2050

* Title: Simulation Secure Multi-Input Quadratic Functional Encryption: Applications to Differential Privacy
* Authors: Ferran Alborch Escobar, Sébastien Canard, Fabien Laguillaumie
* [Permalink](https://eprint.iacr.org/2024/2050)
* [Download](https://eprint.iacr.org/2024/2050.pdf)

### Abstract

Multi-input functional encryption is a primitive that allows for the evaluation of an $\ell$-ary function over multiple ciphertexts, without learning any information about the underlying plaintexts. This type of computation is useful in many cases where one has to compute over encrypted data, such as privacy-preserving cloud services, federated learning, or more generally delegation of computation from multiple clients. It has recently been shown by Alborch et al. in PETS '24 to be useful to construct a randomized functional encryption scheme for obtaining differentially private data analysis over an encrypted database supporting linear queries.

In this work we propose the first secret-key multi-input quadratic functional encryption scheme satisfying simulation security. Current constructions supporting quadratic functionalities, proposed by Agrawal et al. in CRYPTO '21 and TCC '22, only reach indistinguishibility-based security. Our proposed construction is generic, and for a concrete instantiation, we propose a new function-hiding inner-product functional encryption scheme proven simulation secure against one challenge ciphertext in the standard model, which is of independent interest. We then use these two results to construct an efficient randomized quadratic functional encryption scheme, from which we obtain differentially private data analysis over an encrypted database supporting quadratic queries. Finally, we give and fully benchmark an implementation of the randomized scheme. This work is an extended version of the paper "Simulation Secure Multi-Input Quadratic Functional Encryption" at SAC '24, where the multi-input quadratic functional encryption scheme and function-hiding inner-product functional encryption schemes were first presented (Section 3 and Seciton 4).



## 2024/2051

* Title: Simple Power Analysis assisted Chosen Cipher-Text Attack on ML-KEM
* Authors: Alexandre Berzati, Andersson Calle Viera, Maya Chartouny, David Vigilant
* [Permalink](https://eprint.iacr.org/2024/2051)
* [Download](https://eprint.iacr.org/2024/2051.pdf)

### Abstract

Recent work proposed by Bernstein et al. (from EPRINT 2024) identified two timing attacks, KyberSlash1 and KyberSlash2, targeting ML-KEM decryption and encryption algorithms, respectively, enabling efficient recovery of secret keys.. To mitigate these vulnerabilities, correctives were promptly applied across implementations. In this paper, we demonstrate a very simple side-channel-assisted power analysis attack on the patched implementations of ML-KEM. Our result showed that original timing leakage can be shifted to power consumption leakage that can be exploited on specific data. We performed a practical validation of this attack on both the standard and a shuffled implementations of ML-KEM on a Cortex-M4 platform, confirming its effectiveness. Our approach enables the recovery of the ML-KEM secret key in just 30 seconds for the standard implementation, and approximately 3 hours for the shuffled implementation, achieving a 100% success rate in both cases.



## 2024/2052

* Title: Improved Rejection Sampling for Compact Lattice Signatures
* Authors: Joel Gärtner
* [Permalink](https://eprint.iacr.org/2024/2052)
* [Download](https://eprint.iacr.org/2024/2052.pdf)

### Abstract

One of the primary approaches used to construct lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Such a scheme may abort and restart during signing which corresponds to rejection sampling produced signatures to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be.

In this work, we develop a new method to construct signatures influenced by the rejection condition. This allows our rejection sampling to target significantly narrower output distributions than previous approaches, allowing much more compact signatures. The combined size of a signature and a verification key for the resulting scheme is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon.



## 2024/2053

* Title: Optimally Secure TBC Based Accordion Mode
* Authors: Nilanjan Datta, Avijit Dutta, Shibam Ghosh, Hrithik Nandi
* [Permalink](https://eprint.iacr.org/2024/2053)
* [Download](https://eprint.iacr.org/2024/2053.pdf)

### Abstract

The design of tweakable wide block ciphers has advanced significantly over the past two decades. This evolution began with the approach of designing a wide block cipher by Naor and Reingold. Since then, numerous tweakable wide block ciphers have been proposed, many of which build on existing block ciphers and are secure up to the birthday bound for the total number of blocks queried.. Although there has been a slowdown in the development of tweakable wide block cipher modes in last couple of years, the latest NIST proposal for accordion modes has reignited interest and momentum in the design and analysis of these ciphers. Although new designs have emerged, their security often falls short of optimal (i.e., $n$-bit) security, where $n$ is the output size of the primitive. In this direction, designing an efficient tweakable wide block cipher with $n$-bit security seems to be an interesting research problem. An optimally secure tweakable wide block cipher mode can easily be turned into a misuse-resistant RUP secure authenticated encryption scheme with optimal security. This paper proposes $\textsf{HCTR+}$, which turns an $n$-bit tweakable block cipher (TBC) with $n$-bit tweak into a variable input length tweakable block cipher. Unlike tweakable $\textsf{HCTR}$, $\textsf{HCTR+}$ ensures $n$-bit security regardless of tweak repetitions. We also propose two TBC-based almost-xor-universal hash functions, named $\textsf{PHASH+}$ and $\textsf{ZHASH+}$, and use them as the underlying hash functions in the $\textsf{HCTR+}$ construction to create two TBC-based $n$-bit secure tweakable wide block cipher modes, $\textsf{PHCTR+}$ and $\textsf{ZHCTR+}$. Experimental results show that both $\textsf{PHCTR+}$ and $\textsf{ZHCTR+}$ exhibit excellent software performance when their underlying TBC is instantiated with $\textsf{Deoxys-BC-128-128}$.



## 2024/2054

* Title: Greedy Algorithm for Representative Sets: Applications to IVLBC and GIFT-64 in Impossible Differential Attack
* Authors: Manjeet Kaur, Tarun Yadav, Manoj Kumar, Dhananjoy Dey
* [Permalink](https://eprint.iacr.org/2024/2054)
* [Download](https://eprint.iacr.org/2024/2054.pdf)

### Abstract

The impossible differential (ID) attack is crucial for analyzing the strength of block ciphers. The critical aspect of this technique is to identify IDs, and the researchers introduced several methods to detect them. Recently, the researchers extended the mixed-integer linear programming (MILP) approach by partitioning the input and output differences to identify IDs. The researchers proposed techniques to determine the representative set and partition table of a set over any nonlinear function. In this paper, we introduce a deterministic algorithm using the greedy approach~\cite{cormen2022introduction} for finding the representative set and partition table of a set over any nonlinear function. This algorithm iteratively selects the set that covers the maximum uncovered elements of the target set. This performs better than the existing algorithms in terms of time complexity. We use this algorithm to compute the representative sets and partition tables of the two block ciphers, IVLBC and GIFT-64, and identify 6-round IDs for them. Our research contributes a deterministic algorithm to compute the representative set and partition table of a set over any nonlinear function with at most 16-bit input size.



## 2024/2055

* Title: Zeroed Out: Cryptanalysis of Weak PRFs in Alternating Moduli
* Authors: Irati Manterola Ayala, Håvard Raddum
* [Permalink](https://eprint.iacr.org/2024/2055)
* [Download](https://eprint.iacr.org/2024/2055.pdf)

### Abstract

The growing adoption of secure multi-party computation (MPC) has driven the development of efficient symmetric key primitives tailored for MPC. Recent advancements, such as the alternating moduli paradigm, have shown promise but leave room for cryptographic and practical improvements. In this paper, we analyze a family of weak pseudorandom functions (wPRF) proposed at Crypto 2024, focusing on the One-to-One parameter sets. We demonstrate that these configurations fail to achieve their intended one-to-one mappings and exploit this observation to develop an efficient key recovery attack. The attacks reveal significant vulnerabilities, reducing the complexity of key recovery to O(2^(λ/2) log_2 (λ)) for the Standard One-to-One wPRF and O(2^(0.84λ)) for the Reversed Moduli variant– both substantially below their claimed λ-bit security. We validate our findings through experimental evaluations, confirming alignment between predicted and observed attack complexities.



## 2024/2056

* Title: Exact Template Attacks with Spectral Computation
* Authors: Meriem Mahar, Mammar Ouladj, Sylvain Guilley, Hacène Belbachir, Farid Mokrane
* [Permalink](https://eprint.iacr.org/2024/2056)
* [Download](https://eprint.iacr.org/2024/2056.pdf)

### Abstract

The so-called Gaussian template attacks (TA) is one of the optimal Side-Channel Analyses (SCA) when the measurements are captured with normal noise.
 In the SCA literature, several optimizations of its implementation are introduced, such as coalescence and spectral computation. The coalescence consists of averaging traces corresponding to the same plaintext value, thereby coalescing (synonymous: compacting) the dataset. Spectral computation consists of sharing the computational workload when estimating likelihood across key hypotheses.
 
 State-of-the-art coalescence leverages the Law of Large Numbers (LLN) to compute the mean of equivalent traces.
This approach comes with a drawback because the LLN is just an asymptotic approximation.
So it does not lead to an exact Template Attack, especially for a few number of traces.
  In this paper, we introduce a way of calculating the TA exactly and with the same computational complexity (using the spectral approach), without using the LLN, regardless of the number of messages.  
 
  For the experimental validation of this approach, we use the ANSSI SCA Database (ASCAD), with different numbers of messages and different amounts of samples per trace.
  Recall that this dataset concerns a software implementation of AES-128 bits, running on an ATMEGA-8515 microprocessor.



## 2024/2057

* Title: Leveraging remote attestation APIs for secure image sharing in messaging apps
* Authors: Joel Samper, Bernardo Ferreira
* [Permalink](https://eprint.iacr.org/2024/2057)
* [Download](https://eprint.iacr.org/2024/2057.pdf)

### Abstract

Sensitive pictures such as passport photos and nudes are commonly shared through mobile chat applications. One popular strategy for the privacy protection of this material is to use ephemeral messaging features, such as the view once snaps in Snapchat. However, design limitations and implementation bugs in messaging apps may allow attackers to bypass the restrictions imposed by those features on the received material. One way by which attackers may accomplish so is by tampering with the software stack on their own devices. In this paper, we propose and test a protection strategy based on a multiplatform system that encrypts and decrypts sensitive pictures on top of messaging apps and performs remote attestation with available app integrity APIs to safeguard its security. Our analysis and experiments show that, compared to previous proposals for image encryption in a middleware, remote attestation offers increased security, adds privacy benefits, simplifies integration, and improves usability by not requiring users to exchange key material a priori. In our experiments, it incurs an added average latency of 3.8 and 4.5 seconds when sending and receiving private pictures, respectively.



## 2024/2058

* Title: Learning with Errors from Nonassociative Algebras
* Authors: Andrew Mendelsohn, Cong Ling
* [Permalink](https://eprint.iacr.org/2024/2058)
* [Download](https://eprint.iacr.org/2024/2058.pdf)

### Abstract

We construct a provably-secure structured variant of Learning with Errors (LWE) using nonassociative cyclic division algebras, assuming the hardness of worst-case structured lattice problems, for which we are able to give a full search-to-decision reduction, improving upon the construction of Grover et al. named `Cyclic Learning with Errors' (CLWE). We are thus able to create structured LWE over cyclic algebras without any restriction on the size of secret spaces, which was required for CLWE as a result of its restricted security proof. We reduce the shortest independent vectors problem in ideal lattices, obtained from ideals in orders of such algebras, to the decision variant of LWE defined for nonassociative CDAs. We believe this variant has greater security and greater freedom with parameter choices than CLWE, and greater asymptotic efficiency of multiplication than module LWE. Our reduction requires new results in the ideal theory of such nonassociative algebras, which may be of independent interest. We then adapt an LPR-like PKE scheme to hold for nonassociative spaces, and discuss the efficiency and security of our construction, showing that it is immune to certain subfield attacks. Finally, we give example parameters to construct algebras for cryptographic use.



## 2024/2059

* Title: Minimizing the Use of the Honest Majority in YOSO MPC with Guaranteed Output Delivery
* Authors: Rishabh Bhadauria, James Hsin-yu Chiang, Divya Ravi, Jure Sternad, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2024/2059)
* [Download](https://eprint.iacr.org/2024/2059.pdf)

### Abstract

Cleve (STOC 86) shows that an honest majority is necessary for MPC with guaranteed output delivery. In this paper, we show that while an honest majority is indeed necessary, its involvement can be minimal. We demonstrate an MPC protocol with guaranteed output delivery, the majority of which is executed by a sequence of committees with dishonest majority; we leverage one committee with an honest majority, each member of which does work independent of the circuit size. Our protocol has the desirable property that every participant speaks only once (YOSO, Crypto 2021).
As a building block of independent interest, we introduce public computation, which is essentially privacy-free MPC with guaranteed output delivery (akin to smart contracts realized on blockchains). We instantiate public computation on a public bulletin board in three different ways (with different assumption / round / space utilization trade-offs).



## 2024/2060

* Title: "These results must be false": A usability evaluation of constant-time analysis tools
* Authors: Marcel Fourné, Daniel De Almeida Braga, Jan Jancar, Mohamed Sabt, Peter Schwabe, Gilles Barthe, Pierre-Alain Fouque, Yasemin Acar
* [Permalink](https://eprint.iacr.org/2024/2060)
* [Download](https://eprint.iacr.org/2024/2060.pdf)

### Abstract

Cryptography secures our online interactions, transactions, and trust. To achieve this goal, not only do the cryptographic primitives and protocols need to be secure in theory, they also need to be securely implemented by cryptographic library developers in practice.

However, implementing cryptographic algorithms securely is challenging, even for skilled professionals, which can lead to vulnerable implementations, especially to side-channel attacks. For timing attacks, a severe class of side-channel attacks, there exist a multitude of tools that are supposed to help cryptographic library developers assess whether their code is vulnerable to timing attacks. Previous work has established that despite an interest in writing constant-time code, cryptographic library developers do not routinely use these tools due to their general lack of usability. However, the precise factors affecting the usability of these tools remain unexplored. While many of the tools are developed in an academic context, we believe that it is worth exploring the factors that contribute to or hinder their effective use by cryptographic library developers.

To assess what contributes to and detracts from usability of tools that verify constant-timeness (CT), we conducted a two-part usability study with 24 (post) graduate student participants on 6 tools across diverse tasks that approximate real-world use cases for cryptographic library developers.

We find that all studied tools are affected by similar usability issues to varying degrees, with no tool excelling in usability, and usability issues preventing their effective use.

Based on our results, we recommend that effective tools for verifying CT need usable documentation, simple installation, easy to adapt examples, clear output corresponding to CT violations, and minimal noninvasive code markup. We contribute first steps to achieving these with limited academic resources, with our documentation, examples, and installation scripts.