## In this issue

1. [2022/1336] One-Wayness in Quantum Cryptography
2. [2024/677] Asynchronous Consensus without Trusted Setup or ...
3. [2024/678] Quantum-Safe Account Recovery for WebAuthn
4. [2024/679] Isotropic Quadratic Forms, Diophantine Equations ...
5. [2024/680] Universal Vector Commitments
6. [2024/681] HRA-Secure Homomorphic Lattice-Based Proxy Re- ...
7. [2024/682] Approximate PSI with Near-Linear Communication
8. [2024/683] A note on ``a new password-authenticated module ...
9. [2024/684] A Plug-and-Play Long-Range Defense System for ...
10. [2024/685] Committing AVID with Partial Retrieval and Optimal ...
11. [2024/686] Unstructured Inversions of New Hope
12. [2024/687] Levin–Kolmogorov Complexity is not in Linear Time
13. [2024/688] Succinct Functional Commitments for Circuits from k-Lin
14. [2024/689] Automated Creation of Source Code Variants of a ...
15. [2024/690] LPN-based Attacks in the White-box Setting
16. [2024/691] White-box filtering attacks breaking SEL masking: ...
17. [2024/692] Blink: An Optimal Proof of Proof-of-Work
18. [2024/693] A Note of $\mathsf{Anemoi}$ Gröbner Bases
19. [2024/694] Lower-Bounds on Public-Key Operations in PIR
20. [2024/695] Beale Cipher 1 and Cipher 3: Numbers With No Messages
21. [2024/696] A Theoretical Take on a Practical Consensus Protocol
22. [2024/697] LINE: Cryptosystem based on linear equations for ...
23. [2024/698] Private Computations on Streaming Data
24. [2024/699] An Efficient All-to-All GCD Algorithm for Low ...
25. [2024/700] Sublinear Distributed Product Checks on Replicated ...
26. [2024/701] Quantum Unpredictability
27. [2024/702] Security Analysis of Signal's PQXDH Handshake
28. [2024/703] An Efficient and Extensible Zero-knowledge Proof ...
29. [2024/704] Fully Automated Selfish Mining Analysis in ...
30. [2024/705] Large-Scale MPC: Scaling Private Iris Code ...
31. [2024/706] Linicrypt in the Ideal Cipher Model
32. [2024/707] Towards a Polynomial Instruction Based Compiler for ...
33. [2024/708] Automated Generation of Fault-Resistant Circuits
34. [2024/709] Masked Computation the Floor Function and its ...
35. [2024/710] BUFFing FALCON without Increasing the Signature Size
36. [2024/711] Non-Transferable Anonymous Tokens by Secret Binding
37. [2024/712] Quantum NV Sieve on Grover for Solving Shortest ...
38. [2024/713] Analyzing Pump and jump BKZ algorithm using ...
39. [2024/714] Learning with Quantization, Polar Quantizer, and ...
40. [2024/715] A New Cryptographic Algorithm
41. [2024/716] Unclonable Secret Sharing
42. [2024/717] An Improved Threshold Homomorphic Cryptosystem ...
43. [2024/718] PAC-Private Algorithms
44. [2024/719] Client-Efficient Online-Offline Private Information ...
45. [2024/720] MQ maps are not binding - Revisiting Multivariate ...
46. [2024/721] Real-world Universal zkSNARKs are non-malleable
47. [2024/722] Ultrametric integral cryptanalysis
48. [2024/723] $\mathsf{OPA}$: One-shot Private Aggregation with ...

## 2022/1336

* Title: One-Wayness in Quantum Cryptography
* Authors: Tomoyuki Morimae, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2022/1336)
* [Download](https://eprint.iacr.org/2022/1336.pdf)

### Abstract

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian [arXiv:2209.04101] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions proposed by Morimae and Yamakawa. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results.

(1) We define a weaker version of OWSGs, which we call weak OWSGs, and show that they are equivalent to OWSGs. It is a quantum analogue of the amplification theorem for classical weak one-way functions.

(2) (Bounded-time-secure) quantum digital signatures with quantum public keys are equivalent to OWSGs.

(3) Private-key quantum money schemes (with pure money states) imply OWSGs.

(4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. For EFI pairs, single-copy security suffices.

(5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.

## 2024/677

* Title: Asynchronous Consensus without Trusted Setup or Public-Key Cryptography
* Authors: Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/677)
* [Download](https://eprint.iacr.org/2024/677.pdf)

### Abstract

Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has $O(\kappa n^3)$ total communication and runs in expected $O(1)$ rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.

## 2024/678

* Title: Quantum-Safe Account Recovery for WebAuthn
* Authors: Douglas Stebila, Spencer Wilson
* [Permalink](https://eprint.iacr.org/2024/678)
* [Download](https://eprint.iacr.org/2024/678.pdf)

### Abstract

WebAuthn is a passwordless authentication protocol which allows users to authenticate to online services using public-key cryptography. Users prove their identity by signing a challenge with a private key, which is stored on a device such as a cell phone or a USB security token. This approach avoids many of the common security problems with password-based authentication.

WebAuthn's reliance on proof-of-possession leads to a usability issue, however: a user who loses access to their authenticator device either loses access to their accounts or is required to fall back on a weaker authentication mechanism. To solve this problem, Yubico has proposed a protocol which allows a user to link two tokens in such a way that one (the primary authenticator) can generate public keys on behalf of the other (the backup authenticator). With this solution, users authenticate with a single token, only relying on their backup token if necessary for account recovery. However, Yubico's protocol relies on the hardness of the discrete logarithm problem for its security and hence is vulnerable to an attacker with a powerful enough quantum computer.

We present a WebAuthn recovery protocol which can be instantiated with quantum-safe primitives. We also critique the security model used in previous analysis of Yubico's protocol and propose a new framework which we use to evaluate the security of both the group-based and the quantum-safe protocol. This leads us to uncover a weakness in Yubico's proposal which escaped detection in prior work but was revealed by our model. In our security analysis, we require the cryptographic primitives underlying the protocols to satisfy a number of novel security properties such as KEM unlinkability, which we formalize. We prove that well-known quantum-safe algorithms, including CRYSTALS-Kyber, satisfy the properties required for analysis of our quantum-safe protocol.

## 2024/679

* Title: Isotropic Quadratic Forms, Diophantine Equations and Digital Signatures
* Authors: Martin Feussner, Igor Semaev
* [Permalink](https://eprint.iacr.org/2024/679)
* [Download](https://eprint.iacr.org/2024/679.pdf)

### Abstract

This work introduces DEFI - an efficient hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. The form is public, but the construction is a trapdoor that depends on the scheme's private key. For polynomial rings over integers and rings of integers of algebraic number fields, the cryptanalysis is reducible to solving a quadratic Diophantine equation over the ring or, equivalently, to solving a system of quadratic Diophantine equations over rational integers. It is still an open problem whether quantum computers will have any advantage in solving Diophantine problems.