## In this issue

1. [2023/148] PassPro: A Secure Password-based Authentication ...
2. [2024/219] Singular points of UOV and VOX
3. [2024/754] Adversary Resilient Learned Bloom Filters
4. [2024/1372] Coral: Maliciously Secure Computation Framework for ...
5. [2024/1373] Uncompressing Dilithium's public key
6. [2024/1374] Lifting approach against the SNOVA scheme
7. [2024/1375] ALGAES: An Authenticated Lattice-based Generic ...
8. [2024/1376] FDFB$^2$: Functional Bootstrapping via Sparse ...
9. [2024/1377] Security Strengthening of Threshold Symmetric Schemes
10. [2024/1378] Practical Blind Signatures in Pairing-Free Groups
11. [2024/1379] EvalRound+ Bootstrapping and its Rigorous Analysis ...
12. [2024/1380] EUCLEAK
13. [2024/1381] Reality Check on Side-Channels: Lessons learnt from ...
14. [2024/1382] Universal Context Commitment without Ciphertext ...
15. [2024/1383] Self-Orthogonal Minimal Codes From (Vectorial) ...
16. [2024/1384] Password-Protected Key Retrieval with(out) HSM ...
17. [2024/1385] Locally Verifiable Distributed SNARGs
18. [2024/1386] Problems and New Approaches for Crypto-Agility in ...
19. [2024/1387] SPADE: Digging into Selective and PArtial ...
20. [2024/1388] One-Way Functions and pKt Complexity
21. [2024/1389] DL-SITM: Deep Learning-Based See-in-the-Middle ...
22. [2024/1390] Cache Timing Leakages in Zero-Knowledge Protocols

## 2023/148

* Title: PassPro: A Secure Password-based Authentication Mechanism to Prevent Attacks
* Authors: Ripon Patgiri, Laiphrakpam Dolendro Singh
* [Permalink](https://eprint.iacr.org/2023/148)
* [Download](https://eprint.iacr.org/2023/148.pdf)

### Abstract

The password-based authentication system is a widely used authentication mechanism. However, it has several issues, including the domino effect, guessing attacks, dictionary attacks, rainbow table attacks, and database leakage issues. To address these issues, we present a client-side password hashing method called PassPro. PassPro uses two secrets and a domain word to shuffle the strings. The shuffled strings are converted into hash values and sent to the identity manager for authentication or identity creation. The shuffling is based on a pseudo-random algorithm. The legitimate user can reproduce the shuffled string again. The hash values are encrypted in the password database using a password-based encryption method with a mutually reproducible secret word for each user. Therefore, PassPro features- a) client-side password metering, b) client-side password hashing, c) prevention of the domino effect from leaked password database, d) protection of the password database leakage, e) encryption of the hash values using a mutually reproducible secret word, and g) prevention of dictionary and guessing attacks. Also, PassPro guarantees that adversaries, including authentication managers, cannot retrieve the user's original password and user ID. Alternatively, the original user ID and password cannot be retrieved even if the password database is given to the adversary. Furthermore, a password database's user ID and password are invalid in other domains, even if the user uses the same user ID and password in multiple domains.

## 2024/219

* Title: Singular points of UOV and VOX
* Authors: Pierre Pébereau
* [Permalink](https://eprint.iacr.org/2024/219)
* [Download](https://eprint.iacr.org/2024/219.pdf)

### Abstract

In this work, we study the singular locus of the varieties defined by the public keys of UOV and VOX, two multivariate quadratic signature schemes submitted to the additional NIST call for signature schemes.
Singular points do not exist for generic quadratic systems, which enables us to introduce a new algebraic attack against UOV-based schemes.
We show that this attack can be seen as an algebraic variant of the Kipnis-Shamir attack, which can be obtained in our framework as an enumerative approach of solving a bihomogeneous modeling of the computation of singular points.

We give a new attack for UOV$\hat +$ and VOX targeting singular points of the underlying UOV key.
Our attacks lower the security of the schemes, both asymptotically and in number of gates, showing in particular that the parameter sets proposed for these schemes do not meet the NIST security requirements.
More precisely, we show that the security of VOX/UOV$\hat +$ was overestimated by factors $2^{2}, 2^{18}, 2^{37}$ for security levels I, III, V respectively.

As an essential element of the attack on VOX, we introduce a polynomial time algorithm performing a key recovery from one vector, with an implementation requiring only $15$ seconds at security level V.

## 2024/754

* Title: Adversary Resilient Learned Bloom Filters
* Authors: Allison Bishop, Hayder Tirmazi
* [Permalink](https://eprint.iacr.org/2024/754)
* [Download](https://eprint.iacr.org/2024/754.pdf)

### Abstract

Creating an adversary resilient Learned Bloom Filter with provable guarantees is an open problem. We define a strong adversarial model for the Learned Bloom Filter. We also construct two adversary resilient variants of the Learned Bloom Filter called the Uptown Bodega Filter and the Downtown Bodega Filter. Our adversarial model extends an existing adversarial model designed for the Classical (i.e not ``Learned'') Bloom Filter by Naor Yogev and considers computationally bounded adversaries that run in probabilistic polynomial time (PPT). We show that if pseudo-random permutations exist, then a secure Learned Bloom Filter may be constructed with $\lambda$ extra bits of memory and at most one extra pseudo-random permutation in the critical path. We further show that, if pseudo-random permutations exist, then a high utility Learned Bloom Filter may be constructed with $2\lambda$ extra bits of memory and at most one extra pseudo-random permutation in the critical path. Finally, we construct a hybrid adversarial model for the case where a fraction of the workload is chosen by an adversary. We show realistic scenarios where using the Downtown Bodega Filter gives better performance guarantees compared to alternative approaches in this hybrid model.

## 2024/1372

* Title: Coral: Maliciously Secure Computation Framework for Packed and Mixed Circuits
* Authors: Zhicong Huang, Wen-jie Lu, Yuchen Wang, Cheng Hong, Tao Wei, WenGuang Chen
* [Permalink](https://eprint.iacr.org/2024/1372)
* [Download](https://eprint.iacr.org/2024/1372.pdf)

### Abstract

Achieving malicious security with high efficiency in dishonest-majority secure multiparty computation is a formidable challenge. The milestone works SPDZ and TinyOT have spawn a large family of protocols in this direction. For boolean circuits, state-of-the-art works (Cascudo et. al, TCC 2020 and Escudero et. al, CRYPTO 2022) have proposed schemes based on reverse multiplication-friendly embedding (RMFE) to reduce the amortized cost. However, these protocols are theoretically described and analyzed, resulting in a significant gap between theory and concrete efficiency.

Our work addresses existing gaps by refining and correcting several issues identified in prior research, leading to the first practically efficient realization of RMFE. We introduce an array of protocol enhancements, including RMFE-based quintuples and (extended) double-authenticated bits, aimed at improving the efficiency of maliciously secure boolean and mixed circuits. The culmination of these efforts is embodied in Coral, a comprehensive framework developed atop the MP-SPDZ library. Through rigorous evaluation across multiple benchmarks, Coral demonstrates a remarkable efficiency gain, outperforming the foremost theoretical approach by Escudero et al. (which incorporates our RMFE foundation albeit lacks our protocol enhancements) by a factor of 16-30×, and surpassing the leading practical implementation for Frederiksen et al. (ASIACRYPT 2015) by 4-7×.

## 2024/1373

* Title: Uncompressing Dilithium's public key
* Authors: Paco Azevedo Oliveira, Andersson Calle Viera, Benoît Cogliati, Louis Goubin
* [Permalink](https://eprint.iacr.org/2024/1373)
* [Download](https://eprint.iacr.org/2024/1373.pdf)

### Abstract

To be competitive with other signature schemes, the MLWE instance $\bf (A,t)$ on which Dilithium is based is compressed: the least significant bits of $\bf t$, which are denoted $\textbf{t}_0$, are considered part of the secret key.. Knowing $\bf t_0$ does not provide any information about the other data in the secret key, but it does allow the construction of much more efficient side-channel attacks. Yet to the best of our knowledge, there is no kown way to recover $\bf t_0$ from Dilithium signatures. In this work, we show that each Dilithium signature leaks information on $\bf t_0$, then we construct an attack that retrieves the vector $\bf t_0$ from Dilithium signatures. Experimentally, for Dilithium-2, $4\,000\,000$ signatures and $2$ hours are sufficient to recover $\textbf{t}_0$ on a desktop computer.

## 2024/1374

* Title: Lifting approach against the SNOVA scheme
* Authors: Shuhei Nakamura, Yusuke Tani, Hiroki Furue
* [Permalink](https://eprint.iacr.org/2024/1374)
* [Download](https://eprint.iacr.org/2024/1374.pdf)

### Abstract

In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of $\ell \times \ell $ matrices over $\mathbb{F}_q$.
This scheme has small public key and signature size and is a first round candidate of NIST PQC additional digital signature project.
Recently, Ikematsu and Akiyama, and Li and Ding show that the core matrices of SNOVA with $v$ vinegar-variables and $o$ oil-variables are regarded as the representation matrices of UOV with $\ell v$ vinegar-variables and $\ell o$ oil-variables over $\mathbb{F}_q$, and thus we can apply existing key recovery attacks as a plain UOV.
In this paper, we propose a method that reduces SNOVA to smaller UOV with $v$ vinegar-variables and $o$ oil-variables over $\mathbb{F}_{q^\ell }$. As a result, we show that the previous first round parameter sets at $\ell = 2$ do not meet the NIST PQC security levels. We also confirm that the present parameter sets are secure from existing key recovery attacks with our approach.