## In this issue

1. [2022/1517] Best-of-Both-Worlds Multiparty Quantum Computation ...
2. [2023/791] New SIDH Countermeasures for a More Efficient Key ...
3. [2023/1526] Polynomial Time Cryptanalytic Extraction of Neural ...
4. [2023/1528] Unmodified Half-Gates is Adaptively Secure - So is ...
5. [2023/1532] Unclonable Non-Interactive Zero-Knowledge
6. [2023/1544] Arithmetic PCA for Encrypted Data
7. [2023/1545] Exploiting Small-Norm Polynomial Multiplication ...
8. [2023/1546] PERFORMANCE EVALUATION OF MACHINE LEARNING ...
9. [2023/1547] Further Improvements of the Estimation of Key ...
10. [2023/1548] Cheater Identification on a Budget: MPC with ...
11. [2023/1549] Signature-Free Atomic Broadcast with Optimal ...
12. [2023/1550] A Thorough Evaluation of RAMBAM
13. [2023/1551] Evaluating GPT-4’s Proficiency in Addressing ...
14. [2023/1552] Doubly Efficient Batched Private Information Retrieval
15. [2023/1553] Adaptively Secure BLS Threshold Signatures from DDH ...
16. [2023/1554] Cornucopia: Distributed randomness beacons at scale
17. [2023/1555] Polynomial IOPs for Memory Consistency Checks in ...
18. [2023/1556] Better Safe than Sorry: Recovering after ...
19. [2023/1557] Revisit Two Memoryless State-Recovery Cryptanalysis ...
20. [2023/1558] StaTI: Protecting against Fault Attacks Using ...
21. [2023/1559] AprèsSQI: Extra Fast Verification for SQIsign Using ...
22. [2023/1560] Check Alternating Patterns: A Physical Zero- ...
23. [2023/1561] LLM for SoC Security: A Paradigm Shift
24. [2023/1562] Generalized Implicit Factorization Problem
25. [2023/1563] Formal Analysis of Non-profiled Deep-learning Based ...
26. [2023/1564] Fast Blind Rotation for Bootstrapping FHEs
27. [2023/1565] Finding Shortest Vector Using Quantum NV Sieve on ...
28. [2023/1566] Optimized Quantum Implementation of SEED
29. [2023/1567] Depth-Optimized Quantum Implementation of ARIA
30. [2023/1568] Not Just Regular Decoding: Asymptotics and ...
31. [2023/1569] Advancing Scalability in Decentralized Storage: A ...
32. [2023/1570] Jackpot: Non-Interactive Aggregatable Lotteries
33. [2023/1571] Key Filtering in Cube Attacks from the ...
34. [2023/1572] Faulting Winternitz One-Time Signatures to forge ...
35. [2023/1573] Threshold Computation in the Head: Improved ...
36. [2023/1574] Efficient Pre-processing PIR Without Public-Key ...
37. [2023/1575] SoK: Web3 Recovery Mechanisms
38. [2023/1576] Towards Optimally Small Smoothness Bounds for ...
39. [2023/1577] Asymptotics and Improvements of Sieving for Codes
40. [2023/1578] A Scalable Coercion-resistant Blockchain Decision- ...
41. [2023/1579] KiloNova: Non-Uniform PCD with Zero-Knowledge ...
42. [2023/1580] Algorithmic Views of Vectorized Polynomial ...
43. [2023/1581] CryptoZoo: A Viewer for Reduction Proofs
44. [2023/1582] Time-Lock Puzzles with Efficient Batch Solving
45. [2023/1583] Realizing Flexible Broadcast Encryption: How to ...
46. [2023/1584] How to Garble Mixed Circuits that Combine Boolean ...
47. [2023/1585] How to Rationally Select Your Delegatee in PoS
48. [2023/1586] On the Round Complexity of Asynchronous Crusader ...
49. [2023/1587] A Single-Trace Message Recovery Attack on a Masked ...
50. [2023/1588] M&M'S: Mix and Match Attacks on Schnorr-type Blind ...
51. [2023/1589] Optimized Homomorphic Evaluation of Boolean Functions

## 2022/1517

* Title: Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort
* Authors: Kai-Min Chung, Mi-Ying (Miryam) Huang, Er-Cheng Tang, Jiapeng Zhang
* [Permalink](https://eprint.iacr.org/2022/1517)
* [Download](https://eprint.iacr.org/2022/1517.pdf)

### Abstract

Alon et al. (CRYPTO 2021) introduced a multiparty quantum computation protocol that is secure with identifiable abort (MPQC-SWIA). However, their protocol allows only inside MPQC parties to know the identity of malicious players. This becomes problematic when two groups of people disagree and need a third party, like a jury, to verify who the malicious party is. This issue takes on heightened significance in the quantum setting, given that quantum states may exist in only a single copy. Thus, we emphasize the necessity of a protocol with publicly verifiable identifiable abort (PVIA), enabling outside observers with only classical computational power to agree on the identity of the malicious party in case of an abort. However, achieving MPQC with PVIA poses significant challenges due to the no-cloning theorem, and previous works proposed by Mahadev (STOC 2018) and Chung et al. (Eurocrypt 2022) for classical verification of quantum computation fall short.

In this paper, we obtain the first MPQC-PVIA protocol assuming post-quantum oblivious transfer and a classical broadcast channel. The core component of our construction is a new authentication primitive called auditable quantum authentication (AQA) that identifies the malicious sender with overwhelming probability. Additionally, we provide the first MPQC protocol with best-of-both-worlds (BoBW) security, which guarantees output delivery with an honest majority and remains secure with abort even if the majority is dishonest. Our best-of-both-worlds MPQC protocol also satisfies PVIA upon abort.

## 2023/791

* Title: New SIDH Countermeasures for a More Efficient Key Exchange
* Authors: Andrea Basso, Tako Boris Fouotsa
* [Permalink](https://eprint.iacr.org/2023/791)
* [Download](https://eprint.iacr.org/2023/791.pdf)

### Abstract

The Supersingular Isogeny Diffie-Hellman (SIDH) protocol has been the main and most efficient isogeny-based encryption protocol, until a series of breakthroughs led to a polynomial-time key-recovery attack. While some countermeasures have been proposed, the resulting schemes are significantly slower and larger than the original SIDH.

In this work, we propose a new countermeasure technique that leads to significantly more efficient and compact protocols. To do so, we introduce the concept of artificially oriented curves, which are curves with an associated pair of subgroups. We show that this information is sufficient to build parallel isogenies and thus obtain an SIDH-like key exchange, while also revealing significantly less information compared to previous constructions.

After introducing artificially oriented curves, we formalize several related computational problems and thoroughly assess their presumed hardness. We then translate the SIDH key exchange to the artificially oriented setting, obtaining the key-exchange protocols binSIDH, or binary SIDH, and terSIDH, or ternary SIDH, which respectively rely on fixed-degree and variable-degree isogenies.

Lastly, we also provide a proof-of-concept implementation of the proposed protocols. Despite being implemented in a high-level language, terSIDH has very competitive running times, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.

## 2023/1526

* Title: Polynomial Time Cryptanalytic Extraction of Neural Network Models
* Authors: Isaac A. Canales-Martínez, Jorge Chavez-Saab, Anna Hambitzer, Francisco Rodríguez-Henríquez, Nitin Satpute, Adi Shamir
* [Permalink](https://eprint.iacr.org/2023/1526)
* [Download](https://eprint.iacr.org/2023/1526.pdf)

### Abstract

Billions of dollars and countless GPU hours are currently
spent on training Deep Neural Networks (DNNs) for a variety of tasks.
Thus, it is essential to determine the difficulty of extracting all the parameters of such neural networks when given access to their black-box
implementations. Many versions of this problem have been studied over
the last 30 years, and the best current attack on ReLU-based deep neural
networks was presented at Crypto’20 by Carlini, Jagielski, and Mironov.
It resembles a differential chosen plaintext attack on a cryptosystem,
which has a secret key embedded in its black-box implementation and
requires a polynomial number of queries but an exponential amount of
time (as a function of the number of neurons).
In this paper, we improve this attack by developing several new techniques that enable us to extract with arbitrarily high precision all the
real-valued parameters of a ReLU-based DNN using a polynomial number of queries and a polynomial amount of time. We demonstrate its
practical efficiency by applying it to a full-sized neural network for classifying the CIFAR10 dataset, which has 3072 inputs, 8 hidden layers with
256 neurons each, and about 1.2 million neuronal parameters. An attack
following the approach by Carlini et al. requires an exhaustive search
over 2^256 possibilities. Our attack replaces this with our new techniques,
which require only 30 minutes on a 256-core computer.

## 2023/1528

* Title: Unmodified Half-Gates is Adaptively Secure - So is Unmodified Three-Halves
* Authors: Xiaojie Guo, Kang Yang, Xiao Wang, Yu Yu, Zheli Liu
* [Permalink](https://eprint.iacr.org/2023/1528)
* [Download](https://eprint.iacr.org/2023/1528.pdf)

### Abstract

Adaptive security is a crucial property for garbling schemes in pushing the communication of garbled circuits to an offline phase when the input is unknown. In this paper, we show that the popular half-gates scheme by Zahur et al. (Eurocrypt’15), without any modification, is adaptively secure in the non-programmable random permutation model (npRPM). Since real implementations of selective-secure half-gates are already based on npRPM, our result shows that these implementations are already adaptively secure under the same condition where the selective security is proven. Additionally, we expand our analysis to cover the recent three-halves construction by Rosulek and Roy (Crypto’21); we also discuss some optimizations and separation when considering the programmable random permutation model instead.