## In this issue

1. [2023/807] Ready to SQI? Safety First! Towards a constant-time ...
2. [2024/163] On Tweakable Correlation Robust Hashing against Key ...
3. [2024/164] Faster BGV Bootstrapping for Power-of-Two ...
4. [2024/165] Adaptively-Sound Succinct Arguments for NP from ...
5. [2024/166] A Practical MinRank Attack Against VOX
6. [2024/167] Creating from Noise: Trace Generations Using ...
7. [2024/168] Breaking the Cubic Barrier: Distributed Key and ...
8. [2024/169] Machine Learning based Blind Side-Channel Attacks ...
9. [2024/170] Train Wisely: Multifidelity Bayesian Optimization ...
10. [2024/171] Approximate Methods for the Computation of Step ...
11. [2024/172] Relaxed Functional Bootstrapping: A New Perspective ...
12. [2024/173] Constant-Size zk-SNARKs in ROM from Falsifiable ...
13. [2024/174] QPP and HPPK: Unifying Non-Commutativity for ...
14. [2024/175] Lossy Cryptography from Code-Based Assumptions
15. [2024/176] The impact of data-heavy, post-quantum TLS 1.3 on ...
16. [2024/177] Registered Functional Encryption for Quadratic ...
17. [2024/178] Fast Public-Key Silent OT and More from Constrained ...
18. [2024/179] Traitor Tracing without Trusted Authority from ...
19. [2024/180] Exploiting RPMB authentication in a closed source ...
20. [2024/181] Functional Bootstrapping for FV-style Cryptosystems
21. [2024/182] FileDES: A Secure, Scalable and Succinct ...
22. [2024/183] On Security Proofs of Existing Equivalence Class ...
23. [2024/184] Threshold Raccoon: Practical Threshold Signatures ...
24. [2024/185] Vortex: A List Polynomial Commitment and its ...
25. [2024/186] RAD-FS - Inherent and Embedded SCA-Security in ...
26. [2024/187] On the bijectivity of the map $\chi$
27. [2024/188] HomeRun: High-efficiency Oblivious Message ...
28. [2024/189] ZeroAuction: Zero-Deposit Sealed-bid Auction via ...
29. [2024/190] Constructing Committing and Leakage-Resilient ...
30. [2024/191] A Simpler and More Efficient Reduction of DLog to ...
31. [2024/192] Direct FSS Constructions for Branching Programs and ...
32. [2024/193] MQ Does Not Reduce to TUOV
33. [2024/194] Helium: Scalable MPC among Lightweight Participants ...
34. [2024/195] PQC-AMX: Accelerating Saber and FrodoKEM on the ...
35. [2024/196] Subfield attack: leveraging composite-degree ...
36. [2024/197] Alba: The Dawn of Scalable Bridges for Blockchains
37. [2024/198] Distributed Randomness using Weighted VRFs
38. [2024/199] Formal Security Proofs via Doeblin Coefficients: ...
39. [2024/200] A Better Proof-of-Work Fork Choice Rule
40. [2024/201] Breaking the decisional Diffie-Hellman problem in ...
41. [2024/202] Fully Homomorphic Encryption beyond IND-CCA1 ...
42. [2024/203] Application-Aware Approximate Homomorphic ...
43. [2024/204] PerfOMR: Oblivious Message Retrieval with Reduced ...
44. [2024/205] A Generalized Distributed RSA Key Generation
45. [2024/206] Kronos: A Robust Sharding Blockchain Consensus with ...
46. [2024/207] NIZKs with Maliciously Chosen CRS: Subversion ...
47. [2024/208] Asymmetric Cryptography from Number Theoretic ...
48. [2024/209] General Adversary Structures in Byzantine Agreement ...
49. [2024/210] Rollerblade: Replicated Distributed Protocol ...

## 2023/807

* Title: Ready to SQI? Safety First! Towards a constant-time implementation of isogeny-based signature, SQIsign
* Authors: David Jacquemin, Anisha Mukherjee, Péter Kutas, Sujoy SINHA ROY
* [Permalink](https://eprint.iacr.org/2023/807)
* [Download](https://eprint.iacr.org/2023/807.pdf)

### Abstract

NIST has already published the first round of submissions for additional post-quantum signature schemes and the only isogeny-based candidate is SQIsign. It boasts the
most compact key and signature sizes among all post-quantum signature schemes.
However, its current implementation does not address side-channel resistance. This
work is the first to identify a potential side-channel vulnerability in SQIsign. At
certain steps within the signing procedure, it relies on Cornacchia’s algorithm to
represent an integer as a sum of squares of two integers. This algorithm in turn uses
a ‘half-GCD’ (half-greatest common divisor) sub-routine based on Euclid’s division
algorithm which has often been exploited for side-channel attacks. We show that if
the inputs of Cornacchia’s algorithm leak, then one can retrieve the signing key in
polynomial time. Also, since there is no constant-time implementation for SQIsign,
we propose two timing attack-resistant versions of Cornacchia’s algorithm. The
first version uses a constant-time ‘half-GCD’ algorithm that runs a fixed number
of times for a given upper bound based on the bit-size of the inputs. The second
version is based on the two-dimensional lattice reduction algorithm. We show that
randomizing the starting basis with an unimodular matrix would make the execution
time independent of the input.

## 2024/163

* Title: On Tweakable Correlation Robust Hashing against Key Leakages
* Authors: Chun Guo, Xiao Wang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/163)
* [Download](https://eprint.iacr.org/2024/163.pdf)

### Abstract

We continue the study of blockcipher-based (tweakable) correlation robust hash functions, which are central building blocks of circuit garbling and oblivious-transfer extension schemes. As results, we first enhance the multi-user tweakable correlation robust notion of Guo et al. (CRYPTO 2020) with a {\it key leaking oracle} that tells the adversary whether a certain user key satisfies the adversarially-chosen predicate. We then investigate the state-of-the-art hash construction of Guo et al. with respect to our new security definition, providing security proof as well as matching attacks. As an application, we exhibit an OT extension protocol with non-trivial multi-user security.

## 2024/164

* Title: Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT
* Authors: Shihe Ma, Tairong Huang, Anyu Wang, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2024/164)
* [Download](https://eprint.iacr.org/2024/164.pdf)

### Abstract

Power-of-two cyclotomics is a popular choice when instantiating the BGV scheme because of its efficiency and compliance with the FHE standard. However, in power-of-two cyclotomics, the linear transformations in BGV bootstrapping cannot be decomposed into sub-transformations for acceleration with existing techniques. Thus, they can be highly time-consuming when the number of slots is large, degrading the advantage brought by the SIMD property of the plaintext space. By exploiting the algebraic structure of power-of-two cyclotomics, this paper derives explicit decomposition of the linear transformations in BGV bootstrapping into NTT-like sub-transformations, which are highly efficient to compute homomorphically. Moreover, multiple optimizations are made to evaluate homomorphic linear transformations, including modified BSGS algorithms, trade-offs between level and time, and specific simplifications for thin and general bootstrapping. We implement our method on HElib. With the number of slots ranging from 4096 to 32768, we obtain a 7.35x$\sim$143x improvement in the running time of linear transformations and a 4.79x$\sim$66.4x improvement in bootstrapping throughput, compared to previous works or the naive approach.

## 2024/165

* Title: Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
* Authors: Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/165)
* [Download](https://eprint.iacr.org/2024/165.pdf)

### Abstract

A succinct non-interactive argument (SNARG) for $\mathsf{NP}$ allows a prover to convince a verifier that an $\mathsf{NP}$ statement $x$ is true with a proof of size $o(|x| + |w|)$, where $w$ is the associated $\mathsf{NP}$ witness.. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for $\mathsf{NP}$ in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for $\mathsf{NP}$ from falsifiable assumptions. All previous SNARGs for $\mathsf{NP}$ in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).

## 2024/166

* Title: A Practical MinRank Attack Against VOX
* Authors: Hao Guo, Jintai Ding
* [Permalink](https://eprint.iacr.org/2024/166)
* [Download](https://eprint.iacr.org/2024/166.pdf)

### Abstract

VOX is a UOV-like signature scheme submitted to Round 1 additional signatures of NIST PQC standardization process. In 2023 Furue and Ikematsu proposed a rectangular MinRank attack on VOX, resulting in the submitters changing their parameters to counter this attack. In this paper we propose a new type of MinRank attack called padded MinRank attack. We show that the attack is highly efficient in its running time, taking less than one minute to break eight of nine parameters and about eight hours for the remaining one. Therefore the parameters of VOX should be reexamined to ensure its safety.

## 2024/167

* Title: Creating from Noise: Trace Generations Using Diffusion Model for Side-Channel Attack
* Authors: Trevor Yap, Dirmanto Jap
* [Permalink](https://eprint.iacr.org/2024/167)
* [Download](https://eprint.iacr.org/2024/167.pdf)