From Newsgroup: sci.crypt

## In this issue
1. [2025/1443] Generic Partial Decryption as Feature Engineering ...
2. [2025/1444] The Best of Both KEMs: Securely Combining KEMs in ...
3. [2025/1445] Forgery Attack on a Secure Data Sharing for ...
4. [2025/1446] zip: Reducing Proof Sizes for Hash-Based SNARGs
5. [2025/1447] A New Paradigm for Privacy-Preserving Decision Tree ...
6. [2025/1448] Number Field Algorithms for Quaternion Ideal-SVP
7. [2025/1449] REFHE: Fully Homomorphic ALU
8. [2025/1450] Single-round Lattice-based Multisignatures
9. [2025/1451] MUSE-VFL: Multi-party Unified System for Private ...
10. [2025/1452] Not Easy to Prepare a Pesto: Cryptanalysis of a ...
11. [2025/1453] Password-Hardened Encryption Revisited
12. [2025/1454] Automated Verification of Proofs in the Universal ...
13. [2025/1455] Fully-Fluctuating Participation in Sleepy Consensus
14. [2025/1456] Provably Memory-Hard Proofs of Work With Memory- ...
15. [2025/1457] DOCrya: Access Control for Information-Theoretically ...
16. [2025/1458] INKE: Fast Isogeny-Based PKE using Intermediate Curves
17. [2025/1459] Not in The Prophecies: Practical Attacks on Nostr
18. [2025/1460] A Performance Comparison of the Homomorphic ...
19. [2025/1461] Hard Instances of Discrete Logarithm Problem and ...
20. [2025/1462] Large smooth twins from short lattice vectors
21. [2025/1463] Leakage-Resilient Circuits against NC1, Revisited
22. [2025/1464] Rumors MPC: GOD for Dynamic Committees Low ...
23. [2025/1465] CoRReCt: Compute, Record, Replay, Compare to Secure ...
24. [2025/1466] Revisiting Adaptively Secure IBE from Lattices with ...
25. [2025/1467] Optimized HPPK Cryptography for Post-Quantum Security
26. [2025/1468] Privacy-Preserving Machine Learning on Web Browsing ...
27. [2025/1469] Sample Efficient Search to Decision for $k$LIN
28. [2025/1470] Efficient Fuzzy Labeled PSI from Vector Ring-OLE
29. [2025/1471] NTWR Prime - redundant security based on NTRU Prime ...
30. [2025/1472] Hardness of M-LWE with General Distributions and ...
31. [2025/1473] Time-Space Trade-Offs for Sumcheck
## 2025/1443
* Title: Generic Partial Decryption as Feature Engineering for Neural Distinguishers
* Authors: Emanuele Bellini, Rocco Brunelli, David Gerault, Anna Hambitzer, Marco Pedicini
* [Permalink](https://eprint.iacr.org/2025/1443)
* [Download](https://eprint.iacr.org/2025/1443.pdf)
### Abstract
In Neural Cryptanalysis, a deep neural network is trained as a cryptographic distinguisher between pairs of ciphertexts $(F(X), F(X
\oplus \delta))$, where $F$ is either a random permutation or a block cipher, $\delta$ is a fixed difference. The AutoND framework aims to se neural distinguishers that are treated as a generic tool and discourages cipher-specific optimizations. On the other hand, works such as $[\text{LLS}^+24]$ obtain superior distinguishers by adding dedicated features, such as selected parts of the difference in the previous rounds, to the input of the neural distinguishers. In this paper, we study $\text{Generic Partial Decryption}$ as a feature engineering technique and integrate it within a fully automated pipeline, where we evaluate its effect independently of the number of pairs per sample, with which feature engineering is often combined. We show that this technique matches state-of-the-art dedicated approaches on Simon and Simeck. Additionally, we apply it to Aradi, and present a practical neural-assisted key recovery for 5 rounds, as well as a 7-rounds key recovery with $2^{70}$ time complexity. Additionally, we derive useful information from the neural distinguishers and propose a non-neural version of our 5-round key recovery.
## 2025/1444
* Title: The Best of Both KEMs: Securely Combining KEMs in Post-Quantum Hybrid Schemes
* Authors: Gorjan Alagic, Fahran Bajaj, Aybars Kocoglu
* [Permalink](https://eprint.iacr.org/2025/1444)
* [Download](https://eprint.iacr.org/2025/1444.pdf)
### Abstract
Transitioning secure information systems to post-quantum cryptography (PQC) comes with certain risks, such as the potential for switching to PQC schemes with as yet undiscovered vulnerabilities. Such risks can be mitigated by combining multiple schemes in such a way that the resulting hybrid scheme is secure provided at least one of the ingredient schemes is secure. In the case of key-encapsulation mechanisms (KEMs), this approach is already in use in practice, where the PQC scheme ML-KEM is combined with rCLtraditionalrCY X25519 key exchange.
Combining multiple KEMs to construct a single hybrid KEM is largely straightforward, except for the crucial choice of how to derive the final shared secret key. A generic method for doing this in a manner that preserves IND-CCA security is to include the keys and ciphertexts of all ingredient KEMs in an appropriate key derivation step. In the specialized X-Wing construction, one instead relies on a special property of ML-KEM to avoid including its ciphertext in key derivation.
In this work, we show that this optimization can be done in a more general setting. Specifically, when combining multiple KEMs one need not include the ciphertext of any KEM that satisfies ciphertext second preimage resistance (C2PRI)rCoprovided the key combination step is performed using a split-key pseudorandom function. We also prove that any KEM constructed from a certain set of Fujisaki-Okamoto (FO) transforms satisfies C2PRI in the random oracle model. This applies to KEMs such as BIKE, Classic McEliece, HQC, and ML-KEM.
## 2025/1445
* Title: Forgery Attack on a Secure Data Sharing for Industrial IoT
* Authors: Mojtaba Rfiee, Mehdi Abri
* [Permalink](https://eprint.iacr.org/2025/1445)
* [Download](https://eprint.iacr.org/2025/1445.pdf)
### Abstract
In recent years and with the emergence of the industrial revolution, the secure data sharing schemes have been developed in IoT platforms and have been recognized as a hot topic in industry and academia. These schemes enable IoT devices to securely share their sensed data in industrial environments with clients through an appropriate infrastructure and intermediary entities. The research conducted in this field shows the existence of various security challenges and solutions. Data privacy, data authentication, fairness and accountability are some of the most important security features presented. Recently, in paper [Sengupta-Ruj-Bit, TNSM 2023] proposed a secure sharing scheme and claimed that it covers all the mentioned security features even when entities collude with each other. In this paper, we investigate the security analysis of this scheme, and show that it does not cover the claimed fairness property. Therefore, the mentioned scheme is vulnerable and cannot be used as a valid scheme in real-world applications.
## 2025/1446
* Title: zip: Reducing Proof Sizes for Hash-Based SNARGs
* Authors: Giacomo Fenzi, Yuwen Zhang
* [Permalink](https://eprint.iacr.org/2025/1446)
* [Download](https://eprint.iacr.org/2025/1446.pdf)
### Abstract
The argument size of succinct non-interactive arguments (SNARG) is a crucial metric to minimize, especially when the SNARG is deployed within a bandwidth constrained environment.
We present a non-recursive proof compression technique to reduce the size of hash-based succinct arguments. The technique is black-box in the underlying succinct arguments, requires no trusted setup, can be instantiated from standard assumptions (and even when $\mathsf{P} = \mathsf{NP}$!) and is concretely efficient.
We implement and extensively benchmark our method on a number of concretely deployed succinct arguments, achieving compression across the board to as much as $60\%$ of the original proof size.
We further detail non-black-box analogues of our methods to further reduce the argument size.
## 2025/1447
* Title: A New Paradigm for Privacy-Preserving Decision Tree Evaluation
* Authors: Tianpei Lu, Bingsheng Zhang, Hao Li, Kui Ren
* [Permalink](https://eprint.iacr.org/2025/1447)
* [Download](https://eprint.iacr.org/2025/1447.pdf)
### Abstract
Privacy-preserving decision tree inference is a fundamental primitive in privacy-critical applications such as healthcare and finance, yet existing protocols still pay a heavy price for oblivious selection at every node. We introduce a new paradigm that eliminates this limitation by representing the entire tree as a permutation rather than an explicit set of nodes.
Under this representation, we can efficiently generate a shuffled randomized decision tree during the offline phase, where the indices can be directly revealed without leaking any information about the original tree structure. Our scheme significantly reduces both the online and offline computation and communication overhead compared to SOTA.
Comprehensive benchmarks show an 86 % reduction in online communication versus the state-of-the-art FSS protocol by Ji et al., and a 99.9 % reduction versus the OT-based protocol of Ma et al. Overall, our benchmark shows that our protocol achieves a performance improvement of $20\times$ over Ma et al.rCOs scheme and $4.5\times$ over Ji et al.rCOs scheme.
## 2025/1448
* Title: Number Field Algorithms for Quaternion Ideal-SVP
* Authors: Cong Ling, Andrew Mendelsohn, Christian Porter
* [Permalink](https://eprint.iacr.org/2025/1448)
* [Download](https://eprint.iacr.org/2025/1448.pdf)
### Abstract
We study the approximate Hermite Shortest Vector Problem (HSVP) in ideal lattices in orders of cyclic algebras. For one- and two-sided ideals respectively, we show that for almost all ideals we may solve HSVP in a sublattice of dimension at most one half (respectively, one quarter) of the original lattice dimension, with only small losses in the approximation factor. For two-sided ideals in a cryptographically-relevant family of maximal orders, we obtain approximation factors independent of the algebraic norm of the ideal. For one-sided ideals, we obtain a similar result for a large and natural family of ideal lattices. Finally, we turn our mathematical results into algorithms, and in the case of quaternion algebras, give an unconditional quantum polynomial time algorithm to solve HSVP in ideals of maximal orders of quaternion algebras, given an oracle for HSVP in ideals of maximal orders of number fields, in lower dimension.
## 2025/1449
* Title: REFHE: Fully Homomorphic ALU
* Authors: Zvika Brakerski, Offir Friedman, Daniel Golan, Alon Gurny, Dolev Mutzari, Ohad Sheinfeld
* [Permalink](https://eprint.iacr.org/2025/1449)
* [Download](https://eprint.iacr.org/2025/1449.pdf)
### Abstract
We present a fully homomorphic encryption scheme which natively supports arithmetic and logical operations over large "machine words", namely plaintexts of the form $\mathbb{Z}_{2^n}$ (e.g. $n=64$). Our scheme builds on the well-known BGV framework, but deviates in the selection of number field and in the encoding of messages. This allows us to support large message spaces with only modest effect on the noise growth.
Arithmetic operations (modulo $2^n$) are supported natively similarly to BGV-style FHE schemes, and we present an efficient bootstrapping procedure for our scheme. Our bootstrapping algorithm has the feature that along the way it decomposes our machine word into bits, so that during bootstrapping it is possible to perform logical operations (essentially addressing each bit in the message independently). This means that during a single bootstrapping cycle we can perform logical operations on $n$ bits. For example, a "greater than" operation (if $x> y$ output $1$, otherwise $0$), only requires a single subtraction and a single bootstrapping cycle.
Along the way we present a number of new tools and techniques, such as a generalization of the BGV modulus switching to a setting where the plaintext and ciphertext moduli are ideals (and not numbers).
## 2025/1450
* Title: Single-round Lattice-based Multisignatures
* Authors: Kittiphon Phalakarn, Vorapong Suppakitpaisarn, M. Anwar Hasan
* [Permalink](https://eprint.iacr.org/2025/1450)
* [Download](https://eprint.iacr.org/2025/1450.pdf)
### Abstract
This work presents a provably-secure lattice-based multisignature scheme which requires only a single round of communication, whereas the existing works need two or three rounds. The reduction in the number of rounds for the proposed scheme is achieved by utilizing lattice trapdoors. In order to generate multisignatures securely, our scheme however requires an honest centralized server that maintains the trapdoor of a shared matrix used in the scheme.
## 2025/1451
* Title: MUSE-VFL: Multi-party Unified System for Private and Communication Efficient Backpropagation in Vertical Federated Learning
* Authors: Ivan Tjuawinata, Yann Fraboni, Ziyao Liu, Jun Zhao, Pu Duan, Kwok-Yan Lam
* [Permalink](https://eprint.iacr.org/2025/1451)
* [Download](https://eprint.iacr.org/2025/1451.pdf)
### Abstract
Vertical federated learning (VFL) enables a cohort of parties with vertically partitioned data to collaboratively train a machine learning (ML) model without requiring them to centralise their data. Each party feeds its data to its local model, with output fed to a global model. However, this configuration requires parties to share some intermediary results during training, which include the output and the gradients of the local models. These intermediary results can reveal insights into the parties' data, and can be protected by secret sharing them with secure multiparty computation (MPC). However, this increases the total number of communications and makes the VFL training significantly slower. In this work, we introduce MUSE-VFL to accelerate the computation of the local gradients by using homomorphic encryption on top of MPC for parties to directly complete this computation during backpropagation. We show theoretically that MUSE-VFL improves the complexity of the MPC baseline. Our experiments, conducted on four different ML tasks, show that the runtime needed to compute the gradients of the local models significantly outweighs the combined runtime of all other steps. This highlights the significance of MUSE-VFL, with experiments demonstrating a training runtime faster by 30% to 35% for LAN and 32% to 50% for WAN.
## 2025/1452
* Title: Not Easy to Prepare a Pesto: Cryptanalysis of a Multivariate Public-Key Scheme from CCZ Equivalence
* Authors: Christof Beierle, Patrick Felke
* [Permalink](https://eprint.iacr.org/2025/1452)
* [Download](https://eprint.iacr.org/2025/1452.pdf)
### Abstract
Multivariate cryptography is one of the challenging candidates for post-quantum cryptography. There exists a huge variety of proposals, most of them have been broken substantially. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate
polynomials $\mathcal{F}$ (often quadratic). The secret polynomials $\mathcal{F}$
possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. In [Calderini, M., Caminata, A., Villa, I. A New Multivariate Primitive from CCZ Equivalence. J. Cryptol. 38, 25 (2025)], the authors addressed the above challenge by presenting a promising new way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions. The resulting proposal is called Pesto with security parameters $s,t,m,n,q$, where $n$ is the number of variables, $s,t,m\leq n$ and $q$ the size of the finite base field $\mathbb{F}_q$. In this paper we present an attack against Pesto by constructing an equivalent secret key from the public key. This attack has a precomputation phase with a complexity of \[\textrm{max}\left\{{\mathcal{O}\left(n^{6}(m-t)\right),\mathcal{O}\left(\frac{(m-t)(n-t)^2(n-t-s)q^s}{\mathcal{P}(q,n-t-s)}\right)}\right\}\]
base field operations on average and an online complexity of \[\mathcal{O}(q^s(m-t)(n-t-s) \cdot \min(m-t,n-t-s) + q^st (n-t)^2 + q^st^3)\] base field operations to decipher a message or forge a signature, where $\mathcal{P}(q,k) := \prod_{i=1}^k (1-1/q^i)$.
Thus, our attack breaks Pesto for any practical choice of the security parameters $n,m,s,t,q$ and renders the concrete construction underlying Pesto insecure.
## 2025/1453
* Title: Password-Hardened Encryption Revisited
* Authors: Ruben Baecker, Paul Gerhart, Dominique Schr||der
* [Permalink](https://eprint.iacr.org/2025/1453)
* [Download](https://eprint.iacr.org/2025/1453.pdf)
### Abstract
Passwords remain the dominant form of authentication on the Internet. The rise of single sign-on (SSO) services has centralized password storage, increasing the devastating impact of potential attacks and underscoring the need for secure storage mechanisms. A decade ago, Facebook introduced a novel approach to password security, later formalized in Pythia by Everspaugh et al. (USENIX'15), which proposed the concept of password hardening. The primary motivation behind these advances is to achieve provable security against offline brute-force attacks. This work initiated significant follow-on research (CCS'16, USENIX'17), including Password-Hardened Encryption (PHE) (USENIX'18, CCS'20), which was introduced shortly thereafter. Virgil Security commercializes PHE as a software-as-a-service solution and integrates it into its messenger platform to enhance security.
In this paper, we revisit PHE and provide both negative and positive contributions. First, we identify a critical weakness in the original design and present a practical cryptographic attack that enables offline brute-force attacks -- the very threat PHE was designed to mitigate. This weakness stems from a flawed security model that fails to account for real-world attack scenarios and the interaction of security properties with key rotation, a mechanism designed to enhance security by periodically updating keys. Our analysis shows how the independent treatment of security properties in the original model leaves PHE vulnerable. We demonstrate the feasibility of the attack by extracting passwords in seconds that were secured by the commercialized but open-source PHE provided by Virgil Security.
On the positive side, we propose a novel, highly efficient construction that addresses these shortcomings, resulting in the first practical PHE scheme that achieves security in a realistic setting. We introduce a refined security model that accurately captures the challenges of practical deployments, and prove that our construction meets these requirements. Finally, we provide a comprehensive evaluation of the proposed scheme, demonstrating its robustness and performance.
## 2025/1454
* Title: Automated Verification of Proofs in the Universal Composability Framework with Markov Decision Processes
* Authors: Maxim Jourenko, Marcus V||lker
* [Permalink](https://eprint.iacr.org/2025/1454)
* [Download](https://eprint.iacr.org/2025/1454.pdf)
### Abstract
Designing cryptographic protocols and proving these rigorously secure is an arduous and challenging task. Among the methods commonly used to prove security of cryptographic protocols, formalizing it in Canneti's Universal Composability (UC) Framework offers several benefits: (1) Modular design, (2) demonstrating that security remains under arbitrary composition and concurrent execution, (3) the security against any computationally polynomially bound adversary. However, working within the UC Framework can be cumbersome, requires a long time commitment by the prover, and it is prone to errors. While utilization of proof assistants in Cryptography and IT Security is a prominent research area, proof assistants for UC are still in their infancy. Here we show our ongoing work to utilize model checking for verification of proofs in the UC Framework, which to the best of our knowledge is the first attempt to do so. In this work we (1) formally create a Markov Decision Process (MDP) encoding a given proof in the UC Framework, (2) define and proof notions of soundness and completeness for the constructed MDP, (3) implement a proof of concept and (4) demonstrate practical feasibility through experimental evaluation. In summary, in this work we lay out the formal foundations for model checking UC proofs and create a tool that can not only be used for proof verification but also as an assistant for developing proofs in the UC Framework.
## 2025/1455
* Title: Fully-Fluctuating Participation in Sleepy Consensus
* Authors: Yuval Efron, Joachim Neu, Toniann Pitassi
* [Permalink](https://eprint.iacr.org/2025/1455)
* [Download](https://eprint.iacr.org/2025/1455.pdf)
### Abstract
Proof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren.
## 2025/1456
* Title: Provably Memory-Hard Proofs of Work With Memory-Easy Verification
* Authors: Jeremiah Blocki, Nathan Smearsoll
* [Permalink](https://eprint.iacr.org/2025/1456)
* [Download](https://eprint.iacr.org/2025/1456.pdf)
### Abstract
A Proof of Work (PoW) is an important construction for spam-mitigation and distributed consensus protocols. Intuitively, a PoW is a short proof that is easy for the verifier to check but moderately expensive for a prover to generate. However, existing proofs of work are not egalitarian in the sense that the amortized cost to generate a PoW proof using customized hardware is often several orders of magnitude lower than the cost for an honest party to generate a proof on a personal computer. Because Memory-Hard Functions (MHFs) appear to be egalitarian, there have been multiple attempts to construct Memory-Hard Proofs of Work (MHPoW) which require memory-hard computation to generate, but are efficient to verify. Biryukov and Khovratovich (Usenix, 2016) developed a MHPoW candidate called Merkkle Tree Proofs using used the Argon2d MHF. However, they did not provide a formal security proof and Dinur and Nadler (Crypto, 2017) found an attack which exploited the data-dependencies of the underlying Argon2d graph.
We revisit the security of the MTP framework and formally prove, in the parallel random oracle model, that the MTP framework is sound when instantiated with a suitable {\em data-independent} Memory-Hard function. We generically lower bound the cumulative memory cost (cmc) of any prover for the protocol by the pebbling cost of the ex-post facto graph. We also prove that as long as the underlying graph of the original iMHF is sufficiently depth-robust that, except with negligible probability, the ex-post facto will have high cumulative memory cost (cmc). In particular, if we instantiate the iMHF with DRSample then we obtain a MHPoW with the following properties: (1)
An honest prover for the protocol can run in sequential time $O(N)$, (2) The proofs have size $\mathtt{polylog}(N)$ and can be verified in time $\mathtt{polylog}(N)$ (3) Any malicious prover who produces a valid proof must incur high cumulative memory complexity at least $\Omega\left(\frac{N^2}{\log N}\right)$. We also develop general pebbling attacks to which we use to show that (1) any iMHF based MHPoW using the MTP framework has proof size at least $\Omega\left(\log^2 N/\log \log N \right)$, and (2) at least $\tilde{\Omega}(N^{0.32})$ when the iMHF is instantiated with Argon2i, the data-independent version of Argon2.
## 2025/1457
* Title: DOCrya: Access Control for Information-Theoretically Secure Key-Document Stores
* Authors: Yin Li, Sharad Mehrota, Shantanu Sharma, Komal Kumari
* [Permalink](https://eprint.iacr.org/2025/1457)
* [Download](https://eprint.iacr.org/2025/1457.pdf)
### Abstract
This paper presents a novel key-based access control technique for secure outsourcing key-value stores where values correspond to documents that are indexed and accessed using keys. The proposed approach adopts ShamirrCOs secret-sharing that offers unconditional or information-theoretic security. It supports keyword-based document retrieval while preventing leakage of the data, access rights of users, or the size (i.e., volume of the output that satisfies a query). The proposed approach allows servers to detect (and abort) malicious clients from gaining unauthorized access to data, and prevents malicious servers from altering data undetected while ensuring efficient access rCo it takes 231.5ms over 5,000 keywords across 500,000 files
## 2025/1458
* Title: INKE: Fast Isogeny-Based PKE using Intermediate Curves
* Authors: Hyeonhak Kim, Seokhie Hong, Suhri Kim
* [Permalink](https://eprint.iacr.org/2025/1458)
* [Download](https://eprint.iacr.org/2025/1458.pdf)
### Abstract
POK|e (Point-Based Key Exchange), proposed by Basso and Maino in Eurocrypt 2025, is currently the fastest known isogeny-based public key encryption scheme, combining a SIDH-like protocol with higher-dimensional isogenies. However, the higher-dimensional representation inherently requires discrete logarithm computations, which restricts the use of torsion points to smooth subgroups. As a result, reducing the size of the underlying prime $p$ is difficult, limiting further efficiency gains. In this work, we propose a variant of POK|e that retains the higher-dimensional representation but avoids discrete logarithm computations. By replacing the point with the intermediate curve as a shared secret, we are able to reduce the size of the prime $p$ and reduce the number of point evaluations, resulting in faster key generation, encryption, and decryption at the cost of a larger public key. We provide optimized C implementations of both POK|e and our variant. Our results demonstrate that the proposed method improves key generation and encryption by 16% and 22% respectively, and decryption by more than 50%, for all security levels. These results highlight the practicality of our approach, particularly in computation-constrained environments and applications where fast decryption is essential, such as data processing, network communication, and database encryption.
## 2025/1459
* Title: Not in The Prophecies: Practical Attacks on Nostr
* Authors: Hayato Kimura, Ryoma Ito, Kazuhiko Minematsu, Shogo Shiraki, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2025/1459)
* [Download](https://eprint.iacr.org/2025/1459.pdf)
### Abstract
Distributed social networking services (SNSs) recently received significant attention as an alternative to traditional, centralized SNSs, which have inherent limitations on user privacy and freedom.
We provide the first in-depth security analysis of Nostr, an open-source, distributed SNS protocol developed in 2019 with more than 1.1 million registered users.
We investigate the specification of Nostr and the client implementations and present a number of practical attacks allowing forgeries on various objects, such as encrypted direct messages (DMs), by a malicious user or a malicious server. Even more, we show a confidentiality attack against encrypted DMs by a malicious user exploiting a flaw in the link preview mechanism and the CBC malleability.
Our attacks are due to cryptographic flaws in the protocol specification and client implementation, some of which in combination elevate the forgery attack to a violation of confidentiality.
We verify the practicality of our attacks via Proof-of-Concept implementations and discuss how to mitigate them.
## 2025/1460
* Title: A Performance Comparison of the Homomorphic Encryption Schemes CKKS and TFHE
* Authors: Clemens Kr|+ger, Bhavinkumar Moriya, Dominik Schoop
* [Permalink](https://eprint.iacr.org/2025/1460)
* [Download](https://eprint.iacr.org/2025/1460.pdf)
### Abstract
Homomorphic encryption (HE) is a promising technique for privacy-preserving data analysis. Several HE schemes have been developed, with the CKKS and TFHE schemes being two of the most advanced. However, due to their differences, it is hard to compare their performance and suitability for a given application. We therefore conducted an empirical study of the performance of the two schemes in a comparable scenario. We benchmarked the commonly used operations addition, multiplication, division, square root, evaluation of a polynomial and a comparison function, each on a common pair of datasets with 65536 32-bit integers. Since the CKKS scheme is an approximate scheme, we set a requirement of at least 32 bits of precision to match that of the input data. Our results show that CKKS outperforms TFHE in most operations. TFHErCOs only advantage is its fast bootstrapping. Even though TFHE performs bootstrapping after every operation, while CKKS typically performs bootstrapping only after a certain number of multiplications, CKKSrCOs bootstrapping still presents a bottleneck. This can be seen specifically with the comparison operation, where TFHE is much faster than CKKS in many settings, as it requires several bootstrapping operations in CKKS due to its multiplicative depth. Generally speaking, CKKS should be preferred in applications which can be parallelized. CKKSrCOs advantages decreases in applications with a large depth that require many bootstrapping operations.
## 2025/1461
* Title: Hard Instances of Discrete Logarithm Problem and Cryptographic Applications
* Authors: Christopher Battarbee, Arman Darbinyan, Delaram Kahrobaei
* [Permalink](https://eprint.iacr.org/2025/1461)
* [Download](https://eprint.iacr.org/2025/1461.pdf)
### Abstract
Let f be an arbitrary positive integer valued function. The goal of this note is to show that one can construct a finitely generated group in which the discrete log problem is polynomially equivalent to computing the function f. In particular, we provide infinite, but finitely generated groups, in which the discrete logarithm problem is arbitrarily hard. As another application, we construct a family of two-generated groups that have polynomial time word problem and NP-complete discrete log problem. Additionally, using our framework, we propose a generic scheme of cryptographic protocols, which might be of independent interest.
## 2025/1462
* Title: Large smooth twins from short lattice vectors
* Authors: Erik Mulder, Bruno Sterner, Wessel van Woerden
* [Permalink](https://eprint.iacr.org/2025/1462)
* [Download](https://eprint.iacr.org/2025/1462.pdf)
### Abstract
Finding the largest pair of consecutive $B$-smooth integers is computationally challenging. Current algorithms to find such pairs have an exponential runtime -- which has only be provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such large pairs. The core idea is to solve the shortest vector problem (SVP) in a well constructed lattice. With this we are able to significantly increase $B$ and notably report the heuristically largest pair with $B = 751$ which has $196$-bits. By slightly modifying the lattice, we are able to find larger pairs for which one cannot conclusively say whether it is the largest or not for a given $B$. This notably includes a $213$-bit pair with $B = 997$ which is the largest pair found in this work.
## 2025/1463
* Title: Leakage-Resilient Circuits against NC1, Revisited
* Authors: Yuyu Wang
* [Permalink](https://eprint.iacr.org/2025/1463)
* [Download](https://eprint.iacr.org/2025/1463.pdf)
### Abstract
In this study, we revisit leakage-resilient circuits (LRCs) against NC1-leakage and propose new constructions that minimize the reliance on leak-free hardware. Specifically, we first present a stateless LRC scheme that is resilient to NC1-leakage, and then extend it to a leakage-tolerant circuit with auxiliary input (AI-LTC). By integrating this with a 2-adaptive leakage-resilient encoding scheme, we achieve a stateful LRC scheme that uses a secure hardware component. In comparison to the state-of-the-art constructions against NC1-leakage by Miles and Viola (STOC 2013), both the encoder during the leak-free phase in our stateless LRC and the secure hardware component in our stateful LRC are typically much smaller, as their sizes are independent of the original circuit size. Additionally, we provide a non-black-box instantiation of stateful LRC, resulting in a smaller compiled circuit. The security of all our constructions is based on the very mild worst-case assumption NC1reereoL/poly, which is strictly weaker than the assumption NC1reeL used by Miles and Viola.
Furthermore, we propose a generic conversion from AI-LTCs to non-interactive zero-knowledge proofs with offline simulation (oNIZK) for all NP in the fine-grained setting. Our instantiation derived from it has small common reference strings, perfect soundness, zero-knowledge against adversaries in NC1 under NC1reereoL/poly, and minimal verification complexity.
Finally, we show that any fine-grained oNIZK cannot simultaneously achieve perfect soundness and verifiable common reference strings, thereby ruling out the possibility of constructing stateful LRCs without secure hardware by eliminating the trusted setup of our AI-LTC.
## 2025/1464
* Title: Rumors MPC: GOD for Dynamic Committees Low Communication via Constant-Round Chat
* Authors: Bernardo David, Arup Mondal, Rahul Satish
* [Permalink](https://eprint.iacr.org/2025/1464)
* [Download](https://eprint.iacr.org/2025/1464.pdf)
### Abstract
Constructing MPC with ephemeral committees has gained a lot of attention since the seminal works on Fluid MPC and YOSO MPC (CRYPTO'21). However, most protocols in this setting focus on the extreme case of ephemeral committees who can only act for one round (\textit{i.e.,} the maximally fluid case). The Layered MPC model (CRYPTO'23) recasts this notion as a protocol execution against an adaptive rushing adversary over a layered interaction graph, where each committee sits on a layer and can only communicate with the immediate next committee. Although protocols with abort allow for linear communication complexity (CRYPTO'23, CiC'24), Perfect Layered MPC with guaranteed output delivery (GOD) and its statistically secure counterpart (TCC'24) suffer from $O(n^9)$ and $O(\kappa n^{18})$ communication complexity for $n$ parties per committee, respectively. In this work, we investigate communication complexity improvements gained in a relaxed Multi-Layered MPC model that allows for limited interaction among the parties in each committee, while still allowing only one round to communicate towards the immediate next committee. We construct Rumors MPC protocols, where the interaction among each committee's members is constant-round. Our protocols achieve GOD and optimal corruption threshold in the perfect (resp. statistical) security setting with committees acting for $\delta=5$ (resp. $\delta=13$) rounds and $O(n^6)$ (resp. $O(\kappa n^8)$) communication.
## 2025/1465
* Title: CoRReCt: Compute, Record, Replay, Compare to Secure Computations on Untrusted Systems
* Authors: Felix D||rre, Marco Liebel, Jeremias Mechler, J||rn M|+ller-Quade
* [Permalink](https://eprint.iacr.org/2025/1465)
* [Download](https://eprint.iacr.org/2025/1465.pdf)
### Abstract
If the system of an honest user is corrupted, all of its security may be lost: The system may perform computations using different inputs, report different outputs or perform a different computation altogether, including the leakage of secrets to an adversary.
In this paper, we present an approach that complements arbitrary computations to protect against the consequences of malicious systems. Tothis end, we adapt a well-known technique traditionally used to increase fault tolerance, namely redundant executions on different machines that are combined by a majority vote on the results. However, using this conceptually very simple technique for general computations is surprisingly difficult due to non-determinism on the hardware and software level that may cause the executions to deviate.
The CoRReCt approach, short for Compute, Record, Replay, Compare, considers two synchronized executions on different machines. Only if both executions lead to the same result, this result is returned. Our realization uses virtual machines (VMs): On one VM, the software is executed and non-deterministic events are recorded. On a second VM, the software is executed in lockstep and non-deterministic events are replayed. The outputs of both VMs, which are hosted on different machines, are compared by a dedicated trusted entity and only allowed if they match. The following security guarantees can be proven:
rCo Integrity: If at most one host is corrupted, then the computation is performed using the correct inputs and returns either the correct result or no result at all.
rCo Privacy: If timing side-channels are not considered and at most one host is corrupted, the additional leakage introduced by our approach can be bounded by $\log_2(n)$ bits, where n is the number of messages sent. If timing side-channels are considered and the recording system is honest, the same leakage bound can be obtained.
As VMs can be run on completely different host platforms, e.g. Windows on Intel x86-64 or OpenBSD on ARM, the assumption of at least one system being honest is very plausible.
To prove our security guarantees, we provide a proof within a formal model. To demonstrate the viability of our approach, we provide a ready-to-use implementation that allows the execution of arbitrary (networked) x86-64 Linux programs and discuss different real-world applications.
## 2025/1466
* Title: Revisiting Adaptively Secure IBE from Lattices with Smaller Modulus: A Conceptually Simple Framework with Low Overhead
* Authors: Weidan Ji, Zhedong Wang, Lin Lyu, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/1466)
* [Download](https://eprint.iacr.org/2025/1466.pdf)
### Abstract
Most adaptively secure identity-based encryption (IBE) constructions from lattices in the standard model follow the framework proposed by Agrawal et al. (EUROCRYPT 2010). However, this framework has an inherent restriction: the modulus is quadratic in the trapdoor norm. This leads to an unnecessarily large modulus, reducing the efficiency of the IBE scheme.
In this paper, we propose a novel framework for adaptively secure lattice-based IBE in the standard model, that removes this quadratic restriction of modulus while keeping the dimensions of the master public key, secret keys, and ciphertexts unchanged. More specifically, our key observation is that the original framework has a \textit{natural} cross-multiplication structure of trapdoor. Building on this observation, we design two novel algorithms with non-spherical Gaussian outputs that fully utilize this structure and thus remove the restriction. Furthermore, we apply our framework to various IBE schemes with different partitioning functions in both integer and ring settings, demonstrating its significant improvements and broad applicability.
Besides, compared to a concurrent and independent work by Ji et al. (PKC 2025), our framework is significantly simpler in design, and enjoys a smaller modulus, a more compact master public key and shorter ciphertexts.
## 2025/1467
* Title: Optimized HPPK Cryptography for Post-Quantum Security
* Authors: Randy Kuang
* [Permalink](https://eprint.iacr.org/2025/1467)
* [Download](https://eprint.iacr.org/2025/1467.pdf)
### Abstract
In this paper, we present an optimized construction of the Homomorphic Polynomial Public Key (HPPK) cryptosystem, a novel framework designed to provide enhanced security and efficiency in the post-quantum era. Our work introduces a layered cryptographic design that combines modular arithmetic permutations with an innovative additive random masking technique. This approach effectively obscures the underlying factorizable structure of the public key, thereby mitigating vulnerabilities to known lattice reduction attacks and other algebraic cryptanalyses. The security of our scheme is formally grounded in the computational hardness of three new problems: the Hidden Modulus Product Problem (HMPP), the HPPK Key Recovery Problem (HKRP), and the HPPK Secret Recovery Problem (HSRP). We demonstrate through rigorous analysis that the optimal attacks on our scheme are computationally infeasible for appropriately chosen parameters. Furthermore, we show that HPPK achieves remarkably compact key, ciphertext, and signature sizes, offering a significant advantage over leading NIST post-quantum finalists such as Kyber, Dilithium, and Falcon, particularly in bandwidth-constrained environments. The HPPK cryptosystem offers a compelling and mathematically-grounded solution for next-generation cryptography, delivering both provable security and practical efficiency.
## 2025/1468
* Title: Privacy-Preserving Machine Learning on Web Browsing for Public Opinion * Authors: Sam Buxbaum, Lucas M. Tassis, Lucas Boschelli, Giovanni Comarela, Mayank Varia, Mark Crovella, Dino P. Christenson
* [Permalink](https://eprint.iacr.org/2025/1468)
* [Download](https://eprint.iacr.org/2025/1468.pdf)
### Abstract
We present a real-world deployment of secure multiparty
computation to predict political preference from private web browsing
data. To estimate aggregate preferences for the 2024 U.S. presidential
election candidates, we collect and analyze secret-shared data from nearly
8000 users from August 2024 through February 2025, with over 2000
daily active users sustained throughout the bulk of the survey. The use
of MPC allows us to compute over sensitive web browsing data that
users would otherwise be more hesitant to provide. We collect data us-
ing a custom-built Chrome browser extension and perform our analysis
using the CrypTen MPC library. To our knowledge, we provide the first implementation under MPC of a model for the learning from label pro-
portions (LLP) problem in machine learning, which allows us to train on unlabeled web browsing data using publicly available polling and elec-
tion results as the ground truth. The client code is open source, and the remaining code will be open source in the future.
## 2025/1469
* Title: Sample Efficient Search to Decision for $k$LIN
* Authors: Andrej Bogdanov, Alon Rosen, Kel Zin Tan
* [Permalink](https://eprint.iacr.org/2025/1469)
* [Download](https://eprint.iacr.org/2025/1469.pdf)
### Abstract
The $k$LIN problem concerns solving noisy systems of random sparse linear equations mod 2. It gives rise to natural candidate hard CSP distributions and is a cornerstone of local cryptography. Recently, it was used in advanced cryptographic constructions, under the name 'sparse LPN'.
For constant sparsity $k$ and inverse polynomial noise rate, both search and decision versions of $k$LIN are statistically possible and conjectured to be computationally hard for $n\ll m\ll n^{k/2}$, where $m$ is the number of $k$-sparse linear equations, and $n$ is the number of variables.
We show an algorithm that given access to a distinguisher for
$(k-1)$LIN with $m$ samples, solves search $k$LIN with roughly $O(nm)$ samples. Previously, it was only known how to reduce from search $k$LIN with $O(m^3)$ samples, yielding meaningful guarantees for decision $k$LIN only when $m \ll n^{k/6}$.
The reduction succeeds even if the distinguisher has sub-constant advantage at a small additive cost in sample complexity. Our technique applies with some restrictions to Goldreich's function and $k$LIN with random coefficients over other finite fields.
## 2025/1470
* Title: Efficient Fuzzy Labeled PSI from Vector Ring-OLE
* Authors: Dung Bui, Kelong Cong
* [Permalink](https://eprint.iacr.org/2025/1470)
* [Download](https://eprint.iacr.org/2025/1470.pdf)
### Abstract
Fuzzy-labeled private set intersection (PSI) outputs the corresponding label if there is a ``fuzzy'' match between two items, for example, when the Hamming distance is low between the two items. Such protocols can be applied in privacy-preserving biometric authentication, proximity testing, and so on. The only fuzzy-labeled PSI protocol designed for practical purposes is by Uzun et al. (USENIXrCO21), which is based on homomorphic encryption. This design puts constraints on the item size, label size, and communication cost since it is difficult for homomorphic encryption to support large plaintext space and it is well-known that the ciphertext-expansion factor is large.
Our construction begins with a new primitive which we call vector ring-oblivious linear evaluation (vector ring-OLE). This primitive does not rely on existing instantiations of ring-OLE over the quotient ring, but leverages the more efficient vector-OLE. It is ideal for building unbalanced threshold-labeled PSI and is also of independent interest.
Our main contribution, fuzzy-labeled PSI, is bootstrapped from our threshold-labeled PSI protocol. Through a prototype implementation, we demonstrate our communication cost is up to $4.6\times$ better than the prior state-of-the-art with comparable end-to-end latency while supporting a significantly higher label size.
## 2025/1471
* Title: NTWR Prime - redundant security based on NTRU Prime and LWR problems
* Authors: Jakub Mielczarek, Ma+egorzata Zaj-Ocka
* [Permalink](https://eprint.iacr.org/2025/1471)
* [Download](https://eprint.iacr.org/2025/1471.pdf)
### Abstract
In this article, we introduce a new post-quantum cryptosystem, NTWR Prime, which is based on the NTRU Prime and Learning With Rounding (LWR) problems. This scheme is inspired by the NTWE construction proposed by Joel Gartner in 2023. Unlike NTWE, our algorithm employs an irreducible, non-cyclotomic polynomial whose Galois group is isomorphic to the symmetric group. Additionally, the LWR problem is used in place of the LWE problem, offering potential advantages for structural security due to its deterministic nature.
We conduct a security analysis demonstrating that solving the NTWR Prime problem requires solving both the underlying NTRU Prime and LWR problems. Consequently, given the absence of definitive post-quantum security proofs for these problems, our construction offers redundancy, which may fulfill the requirements of applications
with exceptionally high security standards. Importantly, we show that there exists a set of parameters satisfying the hardness assumptions for both contributing problems.
## 2025/1472
* Title: Hardness of M-LWE with General Distributions and Applications to Leaky Variants
* Authors: Katharina Boudgoust, Corentin Jeudy, Erkan Tairi, Weiqiang Wen
* [Permalink](https://eprint.iacr.org/2025/1472)
* [Download](https://eprint.iacr.org/2025/1472.pdf)
### Abstract
The Module Learning With Errors (M-LWE) problem has become a fundamental hardness assumption for lattice-based cryptography. It offers an attractive trade-off between strong robustness guarantees, sometimes directly based on worst-case lattice problems, and efficiency of the subsequent cryptographic primitives. Different flavors of M-LWE have then been introduced towards improving performance. Such variants look at different secret-error distributions and might allow for additional hints on the secret-error vector. Existing hardness results however only cover restricted classes of said distributions, or are tailored to specific leakage models. This lack of generality hinders the design of efficient and versatile cryptographic schemes, as each new distribution or leakage model requires a separate and nontrivial hardness evaluation.
In this work, we address this limitation by establishing the hardness of MLWE under general distributions. As a first step, we show that MLWE remains hard when the error vector follows an arbitrary bounded distribution with sufficient entropy, with some restriction on the number of samples. Building on this, we then reduce to the Hermite Normal Form (HNF) where the secret-error vector follows said arbitrary distribution. Overall, our result shows the actual shape of the distribution does not matter, as long as it keeps sufficient entropy.
To demonstrate the versatility of our framework, we further analyze a range of leakage scenarios. By examining the residual entropy given the leakage, we show that our results of M-LWE with general distributions encompass various types of leakage. More precisely, we cover exact and approximate linear hints which are widely used in recent cryptographic designs, as well as quadratic, and even non-algebraic forms, some of which were not yet covered by any theoretical hardness guarantees. The generality of our results aims at facilitating future cryptographic designs and security analyses.
## 2025/1473
* Title: Time-Space Trade-Offs for Sumcheck
* Authors: Anubhav Baweja, Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, Pratyush Mishra, Tushar Mopuri, Andrew Zitek-Estrada
* [Permalink](https://eprint.iacr.org/2025/1473)
* [Download](https://eprint.iacr.org/2025/1473.pdf)
### Abstract
The sumcheck protocol is a fundamental building block in the design of probabilistic proof systems, and has become a key component of recent work on efficient succinct arguments.
We study time-space tradeoffs for the prover of the sumcheck protocol in the streaming model, and provide upper and lower bounds that tightly characterize the efficiency achievable by the prover.
$\bullet{}$ For sumcheck claims about a single multilinear polynomial we demonstrate an algorithm that runs in time $O(kN)$ and uses space $O(N^{1/k})$ for any $k \geq 1$. For non-adaptive provers (a class which contains all known sumcheck prover algorithms) we show this tradeoff is optimal.
$\bullet{}$ For sumcheck claims about products of multilinear polynomials, we describe a prover algorithm that runs in time $O(N(\log \log N + k))$ and uses space $O(N^{1/k})$ for any $k \geq 1$. We show that, conditioned on the hardness of a natural problem about multiplication of multilinear polynomials, any ``natural'' prover algorithm that uses space $O(N^{1/2 - \varepsilon})$ for some $\varepsilon > 0$ must run in time $\Omega(N(\log \log N + \log \varepsilon))$.
We implement and evaluate the prover algorithm for products of multilinear polynomials. We show that our algorithm consumes up to $120\times$ less memory compare to the linear-time prover algorithm, while incurring a time overhead of less than $2\times$.
The foregoing algorithms and lowerbounds apply in the interactive proof model. We show that in the polynomial interactive oracle proof model one can in fact design a new protocol that achieves a better time-space tradeoff of $O(N^{1/k})$ space and $O(N(\log^* N + k))$ time for any $k \geq 1$.
--- Synchronet 3.21a-Linux NewsLink 1.2