All papers in 2024 (569 results)

Last updated:  2024-04-12
An overview of symmetric fuzzy PAKE protocols
Johannes Ottenhues
Fuzzy password authenticated key exchange (fuzzy PAKE) protocols enable two parties to securely exchange a session-key for further communication. The parties only need to share a low entropy password. The passwords do not even need to be identical, but can contain some errors. This may be due to typos, or because the passwords were created from noisy biometric readings. In this paper we provide an overview and comparison of existing fuzzy PAKE protocols. Furthermore, we analyze certain security properties of these protocols and argue that the protocols can be expected to be slightly more secure in practice than can be inferred from their theoretical guarantees.
Last updated:  2024-04-12
Communication-Efficient Multi-Party Computation for RMS Programs
Thomas Attema, Aron van Baarsen, Stefan van den Berg, Pedro Capitão, Vincent Dunning, and Lisa Kohl
Despite much progress, general-purpose secure multi-party computation (MPC) with active security may still be prohibitively expensive in settings with large input datasets. This particularly applies to the secure evaluation of graph algorithms, where each party holds a subset of a large graph. Recently, Araki et al. (ACM CCS '21) showed that dedicated solutions may provide significantly better efficiency if the input graph is sparse. In particular, they provide an efficient protocol for the secure evaluation of "message passing" algorithms, such as the PageRank algorithm. Their protocol's computation and communication complexity are both $\tilde{O}(M\cdot B)$ instead of the $O(M^2)$ complexity achieved by general-purpose MPC protocols, where $M$ denotes the number of nodes and $B$ the (average) number of incoming edges per node. On the downside, their approach achieves only a relatively weak security notion; $1$-out-of-$3$ malicious security with selective abort. In this work, we show that PageRank can instead be captured efficiently as a restricted multiplication straight-line (RMS) program, and present a new actively secure MPC protocol tailored to handle RMS programs. In particular, we show that the local knowledge of the participants can be leveraged towards the first maliciously-secure protocol with communication complexity linear in $M$, independently of the sparsity of the graph. We present two variants of our protocol. In our communication-optimized protocol, going from semi-honest to malicious security only introduces a small communication overhead, but results in quadratic computation complexity $O(M^2)$. In our balanced protocol, we still achieve a linear communication complexity $O(M)$, although with worse constants, but a significantly better computational complexity scaling with $O(M\cdot B)$. Additionally, our protocols achieve security with identifiable abort and can tolerate up to $n-1$ corruptions.
Last updated:  2024-04-12
Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting
Aron van Baarsen and Marc Stevens
Private set intersection (PSI) is a cryptographic functionality for two parties to learn the intersection of their input sets, without leaking any other information. Circuit-PSI is a stronger PSI functionality where the parties learn only a secret-shared form of the desired intersection, thus without revealing the intersection directly. These secret shares can subsequently serve as input to a secure multiparty computation of any function on this intersection. In this paper we consider several settings in which parties take part in multiple Circuit-PSI executions with the same input set, and aim to amortize communications and computations. To that end, we build up a new framework for Circuit-PSI around generalizations of oblivious (programmable) PRFs that are extended with offline setup phases. We present several efficient instantiations of this framework with new security proofs for this setting. As a side result, we obtain a slight improvement in communication and computation complexity over the state-of-the art Circuit-PSI protocol by Bienstock et al. (USENIX '23). Additionally, we present a novel Circuit-PSI protocol from a PRF with secret-shared outputs, which has linear communication and computation complexity in the parties' input set sizes, and incidentally, it realizes ``almost malicious'' security, making it the first major step in this direction since the protocol by Huang et al. (NDSS '12). Lastly, we derive the potential amortizations over multiple protocol executions, and observe that each of the presented instantiations is favorable in at least one of the multiple-execution settings.
Last updated:  2024-04-12
A Near-Linear Quantum-Safe Third-Party Private Set Intersection Protocol
Foo Yee Yeo and Jason H. M. Ying
Third-party private set intersection (PSI) enables two parties, each holding a private set to compute their intersection and reveal the result only to an inputless third party. In this paper, we present efficient third-party PSI protocols, which significantly lower the computational workload compared to prior work. Our work is motivated by real-world applications such as contact tracing whereby expedition is essential while concurrently preserving privacy. Our construction attains a near-linear computational complexity of $O(n^{1+\varepsilon})$ for large dataset size $n$, where $\varepsilon>0$ is any fixed constant, and achieves post-quantum security. For a quantum-safe third-party PSI protocol, this significantly improves upon the current known best of $O(n^{2.5+o(1)})$. Our improvements stem from algorithmic changes and the incorporation of new techniques along with precise parameter selections to achieve a tight asymptotic bound.
Last updated:  2024-04-12
On the construction of quantum circuits for S-boxes with different criteria based on the SAT solver
Da Lin, Chunli Yang, Shengyuan Xu, Shizhu Tian, and Bing Sun
The substitution box (S-box) is often used as the only nonlinear component in symmetric-key ciphers, leading to a significant impact on the implementation performance of ciphers in both classical and quantum application scenarios by S-box circuits. Taking the Pauli-X gate, the CNOT gate, and the Toffoli gate (i.e., the NCT gate set) as the underlying logic gates, this work investigates the quantum circuit implementation of S-boxes based on the SAT solver. Firstly, we propose encoding methods of the logic gates and the NCT-based circuit, based on which we construct STP models for implementing S-boxes. By applying the proposed models to the S-boxes of several well-known cryptographic algorithms, we construct optimal implementations with different criteria for the 4-bit S-boxes and provide the implementation bounds of different criteria for the 5-bit S-boxes. Since S-boxes in the same affine equivalence class share most of the important properties, we then build STP models to further investigate optimizing S-box circuits based on affine equivalence. According to the applications, for almost all the tested 4-bit S-boxes, there always exists an equivalent S-box that can be implemented with half the number of logic gates. Besides, we encode some important cryptographic properties and construct STP models to design S-boxes with given criteria configurations on implementation and properties. As an application, we find an S-box with the same cryptographic properties as the S-box of KECCAK that can be implemented with only 5 NCT gates, even though the application of our models indicates that implementing the KECCAK S-box requires more than 9 NCT gates. Notably, the inputs of the proposed models are tweakable, which makes the models possess some functions not currently available in the public tools for constructing optimized NCT-based circuits for S-boxes.
Last updated:  2024-04-12
Multiple Group Action Dlogs with(out) Precomputation
Alexander May and Massimo Ostuzzi
Let $\star: G \times X \rightarrow X$ be the action of a group $G$ of size $N=|G|$ on a set $X$. Let $y = g \star x \in X$ be a group action dlog instance, where our goal is to compute the unknown group element $g \in G$ from the known set elements $x,y \in X$. The Galbraith-Hess-Smart (GHS) collision finding algorithm solves the group action dlog in $N^{\frac 1 2}$ steps with polynomial memory. We show that group action dlogs are suitable for precomputation attacks. More precisely, for any $s,t$ our precomputation algorithm computes within $st$ steps a hint of space complexity $s$, which allows to solve any group action dlog in an online phase within $t$ steps. A typical instantiation is $s=t=N^{\frac 1 3}$, which gives precomputation time $N^{\frac 2 3}$ and space $N^{\frac 1 3}$, and online time only $N^{\frac 1 3}$. Moreover, we show that solving multiple group action dlog instances $y_1, \ldots , y_m$ allows for speedups. Namely, our collision finding algorithm solves $m$ group action dlogs in $\sqrt{m}N^{\frac 1 2}$ steps, instead of the straight-forward $mN^{\frac 1 2}$ steps required for running $m$ times GHS. Interestingly, our multi instance algorithm (with precomputation) can be seen as a special case of our precomputation algorithm. Our multiple instance approach can be freely combined with our precomputations, allowing for a variety of tradeoffs. Technically, our precomputation and multiple instance group action dlog attacks are adaptations of the techniques from the standard dlog setting in abelian groups. While such an adaptation seems natural, it is per se unclear which techniques transfer from the dlog to the more restricted group dlog setting, for which $X$ does not offer a group structure. Our algorithms have direct implications for all group action based cryptosystems, such as CSIDH and its variants. We provide experimental evidence that our techniques work well in the CSIDH setting.
Last updated:  2024-04-11
A Note on Related-Tweakey Impossible Differential Attacks
Xavier Bonnetain and Virginie Lallemand
In this short note we review the technique proposed at ToSC 2018 by Sadeghi et al. for attacks built upon several related-tweakey impossible differential trails. We show that the initial encryption queries are improper and lead the authors to misevaluating a filtering value in the key recovery phase. We identified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the results of Sadeghi et al., and in three of them the issue was propagated. We thus present a careful analysis of these types of attacks and give generic complexity formulas similar to the ones proposed by Boura et al. at Asiacrypt 2014. We apply these to the aforementioned papers and provide patched versions of their attacks. The main consequence is an increase in the memory complexity. We show that in many cases (a notable exception being quantum impossible differentials) it is possible to recover the numeric estimates of the flawed analysis, and in all cases we were able to build a correct attack reaching the same number of rounds.
Last updated:  2024-04-11
Practical Proofs of Parsing for Context-free Grammars
Harjasleen Malvai, Gregory Neven, Andrew Miller, and Siam Hussain
In this work-in-progress, we present a series of protocols to efficiently prove statements about strings in context-free grammars (CFGs). Our main protocol for proving proofs of correct parsing for strings in a CFG flexibly accommodates different instantiations of zero-knowledge proof systems as well as accumulation schemes. While improvements in the modular cryptographic primitives can be carried over for improvements in our protocols, even simpler proof systems, which do not support state-of-the-art techniques such as permutation checks can generate proofs of correct parsing of a string of size $n$ by proving the correctness of a circuit of size $\mathcal{O}(cn)$, where $c$ is the cost of verifying a set membership proof in the chosen accumulation scheme.
Last updated:  2024-04-11
SQIAsignHD: SQIsignHD Adaptor Signature
Farzin Renan and Péter Kutas
Adaptor signatures can be viewed as a generalized form of the standard digital signature schemes where a secret randomness is hidden within a signature. Adaptor signatures are a recent cryptographic primitive and are becoming an important tool for blockchain applications such as cryptocurrencies to reduce on-chain costs, improve fungibility, and contribute to off-chain forms of payment in payment-channel networks, payment-channel hubs, and atomic swaps. However, currently used adaptor signature constructions are vulnerable to quantum adversaries due to Shor’s algorithm. In this work, we introduce SQIAsignHD, a new quantum-resistant adaptor signature scheme based on isogenies of supersingular elliptic curves, using SQIsignHD - as the underlying signature scheme - and exploiting the idea of the artificial orientation on the supersingular isogeny Diffie-Hellman key exchange protocol, SIDH, as the underlying hard relation. We, furthermore, show that our scheme is secure in the Quantum Random Oracle Model (QROM).
Last updated:  2024-04-11
Two-Party Decision Tree Training from Updatable Order-Revealing Encryption
Robin Berger, Felix Dörre, and Alexander Koch
Running machine learning algorithms on encrypted data is a way forward to marry functionality needs common in industry with the important concerns for privacy when working with potentially sensitive data. While there is already a growing field on this topic and a variety of protocols, mostly employing fully homomorphic encryption or performing secure multiparty computation (MPC), we are the first to propose a protocol that makes use of a specialized encryption scheme that allows to do secure comparisons on ciphertexts and update these ciphertexts to be encryptions of the same plaintexts but under a new key. We call this notion Updatable Order-Revealing Encryption (uORE) and provide a secure construction using a key-homomorphic pseudorandom function. In a second step, we use this scheme to construct an efficient three-round protocol between two parties to compute a decision tree (or forest) on labeled data provided by both parties. The protocol is in the passively-secure setting and has some leakage on the data that arises from the comparison function on the ciphertexts. We motivate how our protocol can be compiled into an actively-secure protocol with less leakage using secure enclaves, in a graceful degradation manner, e.g. falling back to the uORE leakage, if the enclave becomes fully transparent. We also analyze the leakage of this approach, giving an upper bound on the leaked information. Analyzing the performance of our protocol shows that this approach allows us to be much more efficient (especially w.r.t. the number of rounds) than current MPC-based approaches, hence allowing for an interesting trade-off between security and performance.
Last updated:  2024-04-11
Convolution-Friendly Image Compression in FHE
Axel Mertens, Georgio Nicolas, and Sergi Rovira
Fully Homomorphic Encryption (FHE) is a powerful tool that brings privacy and security to all sorts of applications by allowing us to perform additions and multiplications directly on ciphertexts without the need of the secret key. Some applications of FHE that were previously overlooked but have recently been gaining traction are data compression and image processing. Practically, FHE enables applications such as private satellite searching, private object recognition, or even encrypted video editing. We propose a practical FHE-friendly image compression and processing pipeline where an image can be compressed and encrypted on the client-side, sent to a server which decompresses it homomorphically and then performs image processing in the encrypted domain before returning the encrypted result to the client. Inspired by JPEG, our pipeline also relies on discrete cosine transforms and quantization to simplify the representation of an image in the frequency domain, making it possible to effectively use a compression algorithm. This pipeline is designed to be compatible with existing image-processing techniques in FHE, such as pixel-wise processing and convolutional filters. Using this technique, a high-definition ($1024\times1024$) image can be homomorphically decompressed, processed with a convolutional filter and re-compressed in under $24.7$s, while using ~8GB memory.
Last updated:  2024-04-10
Scoring the predictions: a way to improve profiling side-channel attacks
Damien Robissout, Lilian Bossuet, and Amaury Habrard
Side-channel analysis is an important part of the security evaluations of hardware components and more specifically of those that include cryptographic algorithms. Profiling attacks are among the most powerful attacks as they assume the attacker has access to a clone device of the one under attack. Using the clone device allows the attacker to make a profile of physical leakages linked to the execution of algorithms. This work focuses on the characteristics of this profile and the information that can be extracted from its application to the attack traces. More specifically, looking at unsuccessful attacks, it shows that by carefully ordering the attack traces used and limiting their number, better results can be achieved with the same profile. Using this method allows us to consider the classical attack method, i.e. where the traces are randomly ordered, as the worst case scenario. The best case scenario is when the attacker is able to successfully order and select the best attack traces. A method for identifying efficient ordering when using deep learning models as profiles is also provided. A new loss function "Scoring loss" is dedicated to training machine learning models that give a score to the attack prediction and the score can be used to order the predictions.
Last updated:  2024-04-10
Permutation-Based Hash Chains with Application to Password Hashing
Charlotte Lefevre and Bart Mennink
Hash chain based password systems are a useful way to guarantee authentication with one-time passwords. The core idea is specified in RFC 1760 as S/Key. At CCS 2017, Kogan et al. introduced T/Key, an improved password system where one-time passwords are only valid for a limited time period. They proved security of their construction in the random oracle model under a basic modeling of the adversary. In this work, we make various advances in the analysis and instantiation of hash chain based password systems. Firstly, we describe a slight generalization called U/Key that allows for more flexibility in the instantiation and analysis, and we develop a security model that refines the adversarial strength into offline and online complexity, that can be used beyond the random oracle model, and that allows to argue multi-user security directly. Secondly, we derive a new security proof of U/Key in the random oracle model, as well as dedicated and tighter security proofs of U/Key instantiated with a sponge construction and a truncated permutation. When applied to T/Key, these results improve significantly over the earlier results: whereas the originally suggested instantiation using SHA-256 achieved 128 bits of security using a hash function with a state size of 384 bits, with a truncated permutation construction one can achieve 128 bits of security already with a state size of 256 bits.
Last updated:  2024-04-10
Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage
Leonie Reichert, Gowri R Chandran, Phillipp Schoppmann, Thomas Schneider, and Björn Scheuermann
Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of information leaks, access patterns and volume patterns, allow for database reconstruction attacks. In this paper, we present Menhir, an oblivious TEE database that hides access patterns with ORAM guarantees and volume patterns through differential privacy. The database allows range and point queries with SQL-like WHERE-clauses. It builds on the state-of-the-art oblivious AVL tree construction Oblix (S&P'18), which by itself does not protect against volume leakage. We show how volume leakage can be exploited in range queries and improve the construction to mitigate this type of attack. We prove the correctness and obliviousness of Menhir. Our evaluation shows that our approach is feasible and scales well with the number of rows and columns in the database.
Last updated:  2024-04-10
Quantum Algorithms for Lattice Problems
Yilei Chen
Show abstract
We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all $n$-dimensional lattices within approximation factors of $\tilde{\Omega}(n^{4.5})$. Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors. To develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.
Last updated:  2024-04-12
Leakage-Abuse Attacks Against Structured Encryption for SQL
Alexander Hoover, Ruth Ng, Daren Khu, Yao'an Li, Joelle Lim, Derrick Ng, Jed Lim, and Yiyang Song
Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed. We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some information about the distribution of underlying data, a common model in prior work. They achieve partial query recovery against select operations and partial plaintext recovery against join operations. We prove the optimality and near-optimality of two new attacks, in a Bayesian inference framework. We complement our theoretical results with an empirical investigation testing the performance of our attacks against real-world data and show they can successfully recover a substantial proportion of queries and plaintexts. In addition to our new attacks, we provide proofs showing that the conditional optimality of a previously proposed leakage-abuse attack and that inference against join operations is NP-hard in general.
Last updated:  2024-04-09
Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations
Yuxi Xue, Xingye Lu, Man Ho Au, and Chengru Zhang
In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp. verification), where the output of the offline signing (resp. verification) can be re-used across signatures of the same ring. For a ring size $n$, our framework requires a SoK of the NP statement with size $\log n$. To instantiate our framework, we adapt the well-known post-quantum secure non-interactive argument of knowledge (NIAoK), ethSTARK, into an SoK. This SoK inherents the post-quantum security and has a signature size poly-logarithmic in the size of the NP statement. Thus, our resulting LRS has a signature size of $O(\text{polylog}(\log n))$. By comparison, existing post-quantum ring signatures, regardless of linkability considerations, have signature sizes of $O(\log n)$ at best. Furthermore, leveraging online/offline verification, part of the verification of signatures on the same ring can be shared, resulting in a state-of-the-art amortized verification cost of $O(\text{polylog}(\log n))$. Our LRS also performs favourably against existing schemes in practical scenarios. Concretely, our scheme has the smallest signature size among all post-quantum ring signatures for any ring size larger than $32$. In our experiment, at $128$-bit security and ring size of $1024$, our LRS has a size of $29$KB, and an amortized verification cost of $0.3$ ms, surpassing the state-of-the-art by a significant margin. Even without considering amortization, the verification time for a single signature is $128$ ms, which is still 10x better than state-of-the-art succinct construction, marking it comparable to those featuring linear signature size. A similar performance advantage can also be seen at signing.
Last updated:  2024-04-09
Insights from building a blockchain-based metaverse
Mario Yaksetig
This paper presents an in-depth exploration of the development and deployment of a Layer 1 (L1) blockchain designed to underpin metaverse experiences. As the digital and physical realms become increasingly intertwined, the metaverse emerges as a frontier for innovation, demanding robust, scalable, and secure infrastructure. The core of our investigation centers around the challenges and insights gained from constructing a blockchain framework capable of supporting the vast, dynamic environments of the metaverse. Through the development process, we identified key areas of focus: interoperability, performance and scalability, cost, identity, privacy, security, and accessibility. Our findings indicate that most challenges can be effectively addressed through the implementation of cryptography and subnets (i.e., Avalanche architecture), which allow for segmented, optimized environments within the broader metaverse ecosystem. This approach not only enhances performance but also provides a flexible framework for managing the diverse needs of metaverse applications.
Last updated:  2024-04-09
Probabilistic Algorithms with applications to countering Fault Attacks on Lattice based Post-Quantum Cryptography
Nimish Mishra and Debdeep Mukhopadhyay
Fault attacks that exploit the propagation of effective/ineffective faults present a richer attack surface than Differential Fault Attacks, in the sense that the adversary depends on a single bit of information to eventually leak secret cryptographic material. In the recent past, a number of propagation-based fault attacks on Lattice-based Key Encapsulation Mechanisms have been proposed; many of which have no known countermeasures. In this work, we propose an orthogonal countermeasure principle that does not follow adhoc strategies (like shuffling operations on secret coefficients), but rather depends on cryptographically-backed guarantees to provide quantifiable defence against aforementioned fault attacks. Concretely, we propose a framework that uses rejection sampling (which has been traditionally used as alternatives to trapdoors) to convert otherwise deterministic algorithms to probabilistic ones. Our specific goals allow careful selection of distributions such that our framework functions with a constant number of retries (around $2-3$) for unfaulted executions. In other words, should a fault be injected, the probability of success is negligible; for correct execution however, the probability of success is overwhelmingly high. Using our framework, we hence enable probabilistic decryptions in Kyber, NewHope, and Masked Kyber, and completely cut-off fault propagation in known attacks on these constructions, allowing a sound defence against known fault attacks in literature.
Last updated:  2024-04-09
Fast Parallelizable Misuse-Resistant Authenticated Encryption: Low Latency (Decryption-Fast) SIV
Mustafa Khairallah
MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other call. Romulus-M and LMDAE are two other more recent MRAE secure schemes based on TBCs that target low area hardware. However, they are unparallelizable so they are slower than their counterparts. In this paper, we present two new AEAD modes and four instantiations based on Tweakable Block Ciphers. These new modes target equipping high-speed applications on parallel platforms with nonce misuse resistant AEAD (MRAE). The first mode, LLSIV, targets similar performance on single-core platforms to SCT-2, while eliminating the bottlenecks that make SCT-2 not fully parallelizable. The enhanced parallelism allows LLSIV to encrypt significantly more blocks on parallel platforms, compared to SCT-2, in the same amount of time. LLSIV is based on the NaT MAC, where each ciphertext block can itself be viewed as an instance of NaT when the plaintext is prepended with $0^n$. The trade-off is that LLSIV requires the inverse function of the TBC. However, the inverse function is used only once per message and we demonstrate that for parallel implementations it represents a very small overhead. We give an instantiation of LLSIV based on the SKINNY-128-384 TBC, and a pruned scheme, dubbed pLLSIV, which targets enhanced performance compared both SCT-2 and LLSIV on all platforms, while having reduced security claims. It relies on the recently popularized prove-then-prune methodology to take full advantage of the properties of LLSIV. This leads to a significant performance improvement, making pLLSIV even faster than online TBC-based schemes that are not MRAE-secure. Last but not least, we give an instantiation that uses the primitives used in AES-GCM-SIV: the PolyVal hash function and AES. Our instantiation is faster than AES-GCM-SIV on all platforms and have better bounds. On the other hand, it relies on the ideal cipher model as it uses the ICE TBC proposed as part of the Remus AEAD design. The second mode we describe is LLDFV. It uses ideas from LLSIV combined the Decryption-Fast SIV (DFV) framework proposed recently by Minematsu. The goal is to reduce the number of calls to the TBC by one, while making the scheme as parallelizable as LLSIV. This makes the scheme faster that DFV on all platforms.
Last updated:  2024-04-09
Integral Attack on the Full FUTURE Block Cipher
Zeyu Xu, Jiamin Cui, Kai Hu, and Meiqin Wang
FUTURE is a recently proposed lightweight block cipher that achieved a remarkable hardware performance due to careful design decisions. FUTURE is an Advanced Encryption Standard (AES)-like Substitution-Permutation Network (SPN) with 10 rounds, whose round function consists of four components, i.e., SubCell, MixColumn, ShiftRow and AddRoundKey. Unlike AES, it is a 64-bit-size block cipher with a 128-bit secret key, and the state can be arranged into 16 cells. Therefore, the operations of FUTURE including its S-box is defined over $\mathbb{F}_2^4$. The previous studies have shown that the integral properties of 4-bit S-boxes are usually weaker than larger-size S-boxes, thus the number of rounds of FUTURE, i.e., 10 rounds only, might be too aggressive to provide enough resistance against integral cryptanalysis. In this paper, we mount the integral cryptanalysis on FUTURE. With state-of-the-art detection techniques, we identify several integral distinguishers of 7 rounds of FUTURE. By extending this 7-round distinguisher by 3 forward rounds, we manage to recover all the 128 bits secret keys from the full FUTURE cipher without the full codebook for the first time. To further achieve better time complexity, we also present a key recovery attack on full FUTURE with full codebook. Both attacks have better time complexity than existing results.
Last updated:  2024-04-09
Efficient isochronous fixed-weight sampling with applications to NTRU
Décio Luiz Gazzoni Filho, Tomás S. R. Silva, and Julio López
We present a solution to the open problem of designing an efficient, unbiased and timing attack-resistant shuffling algorithm for NTRU fixed-weight sampling. Although it can be implemented without timing leakages of secret data in any architecture, we illustrate with ARMv7-M and ARMv8-A implementations; for the latter, we take advantage of architectural features such as NEON and conditional instructions, which are representative of features available on architectures targeting similar systems, such as Intel. Our proposed algorithm improves asymptotically upon the current approach, which is based on constant-time sorting networks ($O(n)$ versus $O(n \log^2 n)$), and an implementation of the new algorithm is also faster in practice, by a factor of up to $6.91\ (591\%)$ on ARMv8-A cores and $12.58\ (1158\%)$ on the Cortex-M4; it also requires fewer uniform random bits. This translates into performance improvements for NTRU encapsulation, compared to state-of-the-art implementations, of up to 50% on ARMv8-A cores and 71% on the Cortex-M4, and small improvements to key generation (up to 2.7% on ARMv8-A cores and 6.1% on the Cortex-M4), with negligible impact on code size and a slight improvement in RAM usage for the Cortex-M4.
Last updated:  2024-04-08
Efficient Permutation Correlations and Batched Random Access for Two-Party Computation
Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, and Harshal Shah
In this work we define the notion of a permutation correlation $(\pi,A,B,C)$ s.t. $\pi(A)=B+C$ for a random permutation $\pi$ of $n$ elements and vectors $A,B,C\in \mathbb{F}^n$. We demonstrate the utility of this correlation for a wide range of applications. The correlation can be derandomized to obliviously shuffle a secret-shared list, permute a secret-shared list by a secret-shared permutation, and more. Similar techniques have emerged as a popular building block for the honest majority protocols when efficient batched random access is required, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more. We present the highly flexible notion of permutation correlation and argue that it should be viewed as a first class primitive in the MPC practitioner's toolbox. We give two novel protocols for efficiently generating a random permutation correlation. The first makes use of recent advances in MPC-friendly PRFs to obtain a protocol requiring $O(n\ell)$ OTs/time and constant rounds to permute $n$ $\ell$-bit strings. Unlike the modern OT extension techniques we rely on, this was previously only achievable from relatively more expensive public-key cryptography, e.g. Paillier or LWE. We implement this protocol and demonstrate that it can generate a correlation for $n=2^{20},\ell=128$ in 19 seconds and $\sim2\ell n$ communication, a 15 \& $1.1\times$ improvement over the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is \emph{sublinear} in the string length $\ell$, i.e. the communication and number of OTs is $O(n\log \ell)$. The latter protocol is ideal for the setting when you need to repeatedly permute secret-shared data by the same permutation, e.g. in graph algorithms. Finally, we present a suite of highly efficient protocols for performing various batched random access operations. These include a class of protocols we refer to as \emph{extraction}, which allow a user to \emph{mark} a subset of $X$ and have this subset obliviously extracted into an output list. Additionally, the parties can specify an \emph{arbitrary} selection function $\sigma:[n]\rightarrow[n]$ and obtain shares of $\sigma(X)=(X_{\sigma(1)},\ldots,X_{\sigma(n)})$ from $X$. We implement these protocols and report on their performance.
Last updated:  2024-04-08
Share with Care: Breaking E2EE in Nextcloud
Martin R. Albrecht, Matilda Backendal, Daniele Coppola, and Kenneth G. Paterson
Nextcloud is a leading cloud storage platform with more than 20 million users. Nextcloud offers an end-to-end encryption (E2EE) feature that is claimed to be able “to keep extremely sensitive data fully secure even in case of a full server breach”. They also claim that the Nextcloud server “has Zero Knowledge, that is, never has access to any of the data or keys in unencrypted form”. This is achieved by having encryption and decryption operations that are done using file keys that are only available to Nextcloud clients, with those file keys being protected by a key hierarchy that ultimately relies on long passphrases known exclusively to the users. We provide the first detailed documentation and security analysis of Nextcloud's E2EE feature. Nextcloud's strong security claims motivate conducting the analysis in the setting where the server itself is considered malicious. We present three distinct attacks against the E2EE security guarantees in this setting. Each one enables the confidentiality and integrity of all user files to be compromised. All three attacks are fully practical and we have built proof-of-concept implementations for each. The vulnerabilities make it trivial for a malicious Nextcloud server to access and manipulate users' data. We have responsibly disclosed the three vulnerabilities to Nextcloud. The second and third vulnerabilities have been remediated. The first was addressed by temporarily disabling file sharing from the E2EE feature until a redesign of the feature can be made. We reflect on broader lessons that can be learned for designers of E2EE systems.
Last updated:  2024-04-08
Optimal Asynchronous Byzantine Consensus with Fair Separability
Vincent Gramoli, Zhenliang Lu, Qiang Tang, and Pouriya Zarbafian
Despite ensuring both consistency and liveness, state machine replication protocols remain vulnerable to adversaries who manipulate the transaction order. To address this, researchers have proposed order-fairness techniques that rely either on building dependency graphs between transactions, or on assigning sequence numbers to transactions. Existing protocols that handle dependency graphs suffer from sub-optimal performance, resilience, or security. On the other hand, Pompe (OSDI '20) introduced the novel ordering notion of ordering linearizability that uses sequence numbers. However, Pompe's ordering only applies to committed transactions, opening the door to order-fairness violation when there are network delays, and vulnerability to performance downgrade when there are Byzantine attackers. A stronger notion, fair separability, was introduced to require ordering on all observed transactions. However, no implementation of fair separability exists. In this paper, we introduce a protocol for state machine replication with fair separability ($\mathsf{SMRFS}$); moreover, our protocol has communication complexity $\mathcal{O}(n\ell+\lambda n^2)$, where $n$ is the number of processes, $\ell$ is the input (transaction) size, and $\lambda$ is the security parameter. This is optimal when $\ell\geq \lambda n$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{SMRFS}$ is the first protocol to achieve fair separability, and the first implementation of fair ordering that has optimal communication complexity and optimal Byzantine resilience.
Last updated:  2024-04-08
A post-quantum Distributed OPRF from the Legendre PRF
Novak Kaluderovic, Nan Cheng, and Katerina Mitrokotsa
A distributed OPRF allows a client to evaluate a pseudorandom function on an input chosen by the client using a distributed key shared among multiple servers. This primitive ensures that the servers learn nothing about the input nor the output, and the client learns nothing about the key. We present a post-quantum OPRF in a distributed server setting, which can be computed in a single round of communication between a client and the servers. The only server-to-server communication occurs during a precomputation phase. The algorithm is based on the Legendre PRF which can be computed from a single MPC multiplication among the servers. To this end we propose two MPC approaches to evaluate the Legendre PRF based on replicated and optimised secret sharing, respectively. Furthermore, we propose two methods that allows us to perform MPC multiplication in an efficient way that are of independent interest. By employing the latter, we are able to evaluate the Legendre OPRF in a fashion that is quantum secure, verifiable and secure against malicious adversaries under a threshold assumption, as well as computable in a single round of interaction. To the best of our knowledge, our proposed distributed OPRFs are the first post-quantum secure offering such properties. We also provide an implementation of our protocols, and benchmark it against existing OPRF constructions.
Last updated:  2024-04-08
A Note on the Common Haar State Model
Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin
Common random string model is a popular model in classical cryptography with many constructions proposed in this model. We study a quantum analogue of this model called the common Haar state model, which was also studied in an independent work by Chen, Coladangelo and Sattath (arXiv 2024). In this model, every party in the cryptographic system receives many copies of one or more i.i.d Haar states. Our main result is the construction of a statistically secure PRSG with: (a) the output length of the PRSG is strictly larger than the key size, (b) the security holds even if the adversary receives $O\left(\frac{\lambda}{(\log(\lambda))^{1.01}} \right)$ copies of the pseudorandom state. We show the optimality of our construction by showing a matching lower bound. Our construction is simple and its analysis uses elementary techniques.
Last updated:  2024-04-08
Breaking Bicoptor from S$\&$P 2023 Based on Practical Secret Recovery Attack
Jun Xu, Zhiwei Li, and Lei Hu
At S$\&$P 2023, a family of secure three-party computing protocols called Bicoptor was mainly proposed by Huawei Technology in China, which is used to compute non-linear functions in privacy preserving machine learning. In these protocols, two parties $P_0, P_1$ respectively hold the corresponding shares of the secret, while a third party $P_2$ acts as an assistant. The authors claimed that neither party in the Bicoptor can independently compromise the confidentiality of the input, intermediate, or output. In this paper, we point out that this claim is incorrect. The assistant $P_2$ can recover the secret in the DReLU protocol, which is the basis of Bicoptor. The restoration of its secret will result in the security of the remaining protocols in Bicoptor being compromised. Specifically, we provide two secret recovery attacks regarding the DReLU protocol. The first attack method belongs to a clever enumeration method, which is mainly due to the derivation of the modular equation about the secret and its share. The key of the second attack lies in solving the small integer root problem of a modular equation, as the lattices involved are only 3 or 4 dimensions, the LLL algorithm can effectively work. For the system settings selected by Bicoptor, our experiment shows that the desired secret in the DReLU protocol can be restored within one second on a personal computer. Therefore, when using cryptographic protocols in the field of privacy preserving machine learning, it is not only important to pay attention to design overhead, but also to be particularly careful of potential security threats.
Last updated:  2024-04-07
Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank
Loïc Bidoux, Thibauld Feneuil, Philippe Gaborit, Romaric Neveu, and Matthieu Rivain
The MPC-in-the-Head (MPCitH) paradigm is widely used for building post-quantum signature schemes, as it provides a versatile way to design proofs of knowledge based on hard problems. Over the years, the MPCitH landscape has changed significantly, with the most recent improvement coming from VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH). While a straightforward application of these frameworks already improve the existing MPCitH-based signatures, we show in this work that we can adapt the arithmetic constraints representing the underlying security assumptions (here called the modeling) to achieve smaller sizes using these new techniques. More precisely, we explore existing modelings for the rank syndrome decoding (RSD) and MinRank problems and we introduce a new modeling, named dual support decomposition, which achieves better sizes with the VOLEitH and TCitH frameworks by minimizing the size of the witnesses. While this modeling is naturally more efficient than the other ones for a large set of parameters, we show that it is possible to go even further and explore new areas of parameters. With these new modeling and parameters, we obtain low-size witnesses which drastically reduces the size of the ``arithmetic part'' of the signature. We apply our new modeling to both TCitH and VOLEitH frameworks and compare our results to RYDE, MiRitH, and MIRA signature schemes. We obtain signature sizes below 4 kB for 128 bits of security with N=256 parties (a.k.a. leaves in the GGM trees) and going as low as $\approx$ 3.5 kB with N=2048, for both RSD and MinRank. This represents an improvement of more than 1.5 kB compared to the original submissions to the 2023 NIST call for additional signatures. We also note that recent techniques optimizing the sizes of GGM trees are applicable to our schemes and further reduce the signature sizes by a few hundred bytes, bringing them arround 3 kB (for 128 bits of security with N=2048).
Last updated:  2024-04-07
Lattice-Based Timed Cryptography
Russell W. F. Lai and Giulio Malavolta
Timed cryptography studies primitives that retain their security only for a predetermined amount of time, such as proofs of sequential work and time-lock puzzles. This feature has proven to be useful in a large number of practical applications, e.g. randomness generation, sealed-bid auctions, and fair multi-party computation. However, the current state of affairs in timed cryptography is unsatisfactory: Virtually all efficient constructions rely on a single sequentiality assumption, namely that repeated squaring in unknown order groups cannot be parallelised. This is a single point of failure in the classical setting and is even false against quantum adversaries. In this work we put forward a new sequentiality assumption, which essentially says that a repeated application of the standard lattice-based hash function cannot be parallelised. We provide concrete evidence of the validity of this assumption and perform some initial cryptanalysis. We also propose a new template to construct proofs of sequential work, based on lattice techniques.
Last updated:  2024-04-07
Supersingular Hashing using Lattès Maps
Daniel Larsson
In this note we propose a variant (with four sub-variants) of the Charles--Goren--Lauter (CGL) hash function using Lattès maps over finite fields. These maps define dynamical systems on the projective line. The underlying idea is that these maps ``hide'' the $j$-invariants in each step in the isogeny chain, similar to the Merkle--Damgård construction. This might circumvent the problem concerning the knowledge of the starting (or ending) curve's endomorphism ring, which is known to create collisions in the CGL hash function. Let us, already in the abstract, preface this note by remarking that we have not done any explicit computer experiments and benchmarks (apart from a small test on the speed of computing the orbits), nor do we make any security claims. Part of the reason for this is the author's lack of competence in complexity theory and evaluation of security claims. Instead this note is only meant as a presentation of the main idea, the hope being that someone more competent will find it interesting enough to pursue further.
Last updated:  2024-04-07
A comment on "Comparing the MOV and FR reductions in elliptic curve cryptography" from EUROCRYPT'99
Qiping Lin and Fengmei Liu
In general the discrete logarithm problem is a hard problem in the elliptic curve cryptography, and the best known solving algorithm have exponential running time. But there exists a class of curves, i.e. supersingular elliptic curves, whose discrete logarithm problem has a subexponential solving algorithm called the MOV attack. In 1999, the cost of the MOV reduction is still computationally expensive due to the power of computers. We analysis the cost of the MOV reduction and the discrete logarithm problem of the curves in \cite{HSSI99} using Magma with an ordinary computer.
Last updated:  2024-04-06
Confidential and Verifiable Machine Learning Delegations on the Cloud
Wenxuan Wu, Soamar Homsi, and Yupeng Zhang
With the growing adoption of cloud computing, the ability to store data and delegate computations to powerful and affordable cloud servers have become advantageous for both companies and individual users. However, the security of cloud computing has emerged as a significant concern. Particularly, Cloud Service Providers (CSPs) cannot assure data confidentiality and computations integrity in mission-critical applications. In this paper, we propose a confidential and verifiable delegation scheme that advances and overcomes major performance limitations of existing Secure Multiparty Computation (MPC) and Zero Knowledge Proof (ZKP). Secret-shared Data and delegated computations to multiple cloud servers remain completely confidential as long as there is at least one honest MPC server. Moreover, results are guaranteed to be valid even if all the participating servers are malicious. Specifically, we design an efficient protocol based on interactive proofs, such that most of the computations generating the proof can be done locally on each server. In addition, we propose a special protocol for matrix multiplication where the overhead of generating the proof is asymptotically smaller than the time to evaluate the result in MPC. Experimental evaluation demonstrates that our scheme significantly outperforms prior work, with the online prover time being 1-2 orders of magnitude faster. Notably, in the matrix multiplication protocol, only a minimal 2% of the total time is spent on the proof generation. Furthermore, we conducted tests on machine learning inference tasks. We executed the protocol for a fully-connected neural network with 3 layers on the MNIST dataset and it takes 2.6 seconds to compute the inference in MPC and generate the proof, 88× faster than prior work. We also tested the convolutional neural network of Lenet with 2 convolution layers and 3 dense layers and the running time is less than 300 seconds across three servers.
Last updated:  2024-04-06
Highly-Effective Backdoors for Hash Functions and Beyond
Mihir Bellare, Doreen Riepel, and Laura Shea
We study the possibility of schemes whose public parameters have been generated along with a backdoor. We consider the goal of the big-brother adversary to be two-fold: It desires utility (it can break the scheme) but also exclusivity (nobody else can). Starting with hash functions, we give new, strong definitions for these two goals, calling the combination high effectiveness. We then present a construction of a backdoored hash function that is highly effective, meaning provably meets our new definition. As an application, we investigate forgery of X.509 certificates that use this hash function. We then consider signatures, again giving a definition of high effectiveness, and showing that it can be achieved. But we also give some positive results, namely that for the Okamoto and Katz-Wang signature schemes, certain natural backdoor strategies are provably futile. Our backdoored constructions serve to warn that backdoors can be more powerful and damaging than previously conceived, and to help defenders and developers identify potential backdoors by illustrating how they might be built. Our positive results illustrate that some schemes do offer more backdoor resistance than others, which may make them preferable.
Last updated:  2024-04-05
NodeGuard: A Highly Efficient Two-Party Computation Framework for Training Large-Scale Gradient Boosting Decision Tree
Tianxiang Dai, Yufan Jiang, Yong Li, and Fei Mei
The Gradient Boosting Decision Tree (GBDT) is a well-known machine learning algorithm, which achieves high performance and outstanding interpretability in real-world scenes such as fraud detection, online marketing and risk management. Meanwhile, two data owners can jointly train a GBDT model without disclosing their private dataset by executing secure Multi-Party Computation (MPC) protocols. In this work, we propose NodeGuard, a highly efficient two party computation (2PC) framework for large-scale GBDT training and inference. NodeGuard guarantees that no sensitive intermediate results are leaked in the training and inference. The efficiency advantage of NodeGuard is achieved by applying a novel keyed bucket aggregation protocol, which optimizes the communication and computation complexity globally in the training. Additionally, we introduce a probabilistic approximate division protocol with an optimization for re-scaling, when the divisor is publicly known. Finally, we compare NodeGuard to state-of-the-art frameworks, and we show that NodeGuard is extremely efficient. It can improve the privacy preserving GBDT training performance by a factor of 5.0 to 131 in LAN and 2.7 to 457 in WAN.
Last updated:  2024-04-05
CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model
Simon Jeanteur, Laura Kovács, Matteo Maffei, and Michael Rawson
Cryptographic protocols are hard to design and prove correct, as witnessed by the ever-growing list of attacks even on protocol standards. Symbolic models of cryptography enable automated formal security proofs of such protocols against an idealized cryptographic model, which abstracts away from the algebraic properties of cryptographic schemes and thus misses attacks. Computational models of cryptography yield rigorous guarantees but support at present only interactive proofs and/or restricted classes of protocols (e.g., stateless ones). A promising approach is given by the computationally complete symbolic attacker (CCSA) model, formalized in the BC Logic, which aims at bridging and getting the best of the two worlds, obtaining cryptographic guarantees by symbolic protocol analysis. The BC Logic is supported by a recently developed interactive theorem prover, namely Squirrel, which enables machine-checked interactive security proofs, as opposed to automated ones, thus requiring expert knowledge both in the cryptographic space as well as on the reasoning side. In this paper, we introduce the CryptoVampire cryptographic protocol verifier, which for the first time fully automates proofs of trace properties in the BC Logic. The key technical contribution is a first-order formalization of protocol properties with tailored handling of subterm relations. As such, we overcome the burden of interactive proving in higher-order logic and automatically establish soundness of cryptographic protocols using only first-order reasoning. Our first-order encoding of cryptographic protocols is challenging for various reasons. On the theoretical side, we restrict full first-order logic with cryptographic axioms to ensure that, by losing the expressivity of the higher-order BC Logic, we do not lose soundness of cryptographic protocols in our first-order encoding. On the practical side, CryptoVampire integrates dedicated proof techniques using first-order saturation algorithms and heuristics, which all together enable leveraging the state-of-the-art Vampire first-order automated theorem prover as the underlying proving engine of CryptoVampire. Our experimental results showcase the effectiveness of CryptoVampire as a standalone verifier as well as in terms of automation support for Squirrel.
Last updated:  2024-04-05
HyCaMi: High-Level Synthesis for Cache Side-Channel Mitigation
Heiko Mantel, Joachim Schmidt, Thomas Schneider, Maximilian Stillger, Tim Weißmantel, and Hossein Yalame
Cache side-channels are a major threat to cryptographic implementations, particularly block ciphers. Traditional manual hardening methods transform block ciphers into Boolean circuits, a practice refined since the late 90s. The only existing automatic approach based on Boolean circuits achieves security but suffers from performance issues. This paper examines the use of Lookup Tables (LUTs) for automatic hardening of block ciphers against cache side-channel attacks. We present a novel method combining LUT-based synthesis with quantitative static analysis in our HyCaMi framework. Applied to seven block cipher implementations, HyCaMi shows significant improvement in efficiency, being 9.5$\times$ more efficient than previous methods, while effectively protecting against cache side-channel attacks. Additionally, for the first time, we explore balancing speed with security by adjusting LUT sizes, providing faster performance with slightly reduced leakage guarantees, suitable for scenarios where absolute security and speed must be balanced.
Last updated:  2024-04-07
Analysing Cryptography in the Wild - A Retrospective
Martin R. Albrecht and Kenneth G. Paterson
We reflect on our experiences analysing cryptography deployed “in the wild” and give recommendations to fellow researchers about this process.
Last updated:  2024-04-06
Avoiding Trusted Setup in Isogeny-based Commitments
Gustave Tchoffo Saah, Tako Boris Fouotsa, Emmanuel Fouotsa, and Célestin Nkuimi-Jugnia
In 2021, Sterner proposed a commitment scheme based on supersingular isogenies. For this scheme to be binding, one relies on a trusted party to generate a starting supersingular elliptic curve of unknown endomorphism ring. In fact, the knowledge of the endomorphism ring allows one to compute an endomorphism of degree a power of a given small prime. Such an endomorphism can then be split into two to obtain two different messages with the same commitment. This is the reason why one needs a curve of unknown endomorphism ring, and the only known way to generate such supersingular curves is to rely on a trusted party or on some expensive multiparty computation. We observe that if the degree of the endomorphism in play is well chosen, then the knowledge of the endomorphism ring is not sufficient to efficiently compute such an endomorphism and in some particular cases, one can even prove that endomorphism of a certain degree do not exist. Leveraging these observations, we adapt Sterner's commitment scheme in such a way that the endomorphism ring of the starting curve can be known and public. This allows us to obtain isogeny-based commitment schemes which can be instantiated without trusted setup requirements.
Last updated:  2024-04-05
An efficient key generation algorithm for GR-NTRU over dihedral group
Vikas Kumar, Ali Raya, and Aditi Kar Gangopadhyay
In this article, we focus on deriving an easily implementable and efficient method of constructing units of the group ring of dihedral group. We provide a necessary and sufficient condition that relates the units in the group ring of dihedral group with the units in the group ring of cyclic group. Using this relation and the methods available for inversion in the group ring of the cyclic group, we introduce an algorithm to construct units efficiently and check its performance experimentally.
Last updated:  2024-04-05
Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest
Hojune Shin, Jina Choi, Dain Lee, Kyoungok Kim, and Younho Lee
Show abstract
This paper introduces a new method for training decision trees and random forests using CKKS homomorphic encryption (HE) in cloud environments, enhancing data privacy from multiple sources. The innovative Homomorphic Binary Decision Tree (HBDT) method utilizes a modified Gini Impurity index (MGI) for node splitting in encrypted data scenarios. Notably, the proposed training approach operates in a single cloud security domain without the need for decryption, addressing key challenges in privacy-preserving machine learning. We also propose an efficient method for inference utilizing only addition for path evaluation even when both models and inputs are encrypted, achieving O(1) multiplicative depth. Experiments demonstrate that this method surpasses the previous study by Akavia et al.'s by at least 3.7 times in the speed of inference. The study also expands to privacy-preserving random forests, with GPU acceleration ensuring feasibly efficient performance in both training and inference.
Last updated:  2024-04-04
The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
Momonari Kudo and Kazuhiro Yokoyama
Determining the complexity of computing Gröbner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gröbner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors’ previous work and gives additional results on the solving degrees and important behaviors of Gröbner basis computation.
Last updated:  2024-04-04
Slice more? It leaks: Analysis on the paper ``On the Feasibility of Sliced Garbling''
Taechan Kim
Recent improvements to garbled circuits are mainly focused on reducing their size. The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting. This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015). Recently, Ashur, Hazay, and Satish (eprint 2024/389) proposed a scheme that requires $4/3\kappa + O(1)$ bits for garbling AND gates. Precisely they extended the idea of slicing introduced by Rosulek and Roy to garble 3-input gates of the form $g(u,v,w) := u(v+w)$. By setting $w = 0$, it can be used to garble AND gates with the improved communication costs. However, in this paper, we observe that the scheme proposed by Ashur, Hazy, and Satish leaks information on the permute bits, thereby allowing the evaluator to reveal information on the private inputs. To be precise, we show that in their garbling scheme, the evaluator can compute the bits $\alpha$ and $\beta + \gamma$, where $\alpha$, $\beta$, and $\gamma$ are the private permute bits of the input labels $A$, $B$, and $C$, respectively.
Last updated:  2024-04-04
Optimizing and Implementing Fischlin's Transform for UC-Secure Zero-Knowledge
Yi-Hsiu Chen and Yehuda Lindell
Fischlin's transform (CRYPTO 2005) is an alternative to the Fiat-Shamir transform that enables straight-line extraction when proving knowledge. In this work we focus on the problem of using the Fischlin transform to construct UC-secure zero-knowledge from Sigma protocols, since UC security -- that guarantees security under general concurrent composition -- requires straight-line (non-rewinding) simulators. We provide a slightly simplified transform that is much easier to understand, and present algorithmic and implementation optimizations that significantly improve the running time. It appears that the main obstacles to the use of Fischlin in practice is its computational cost and implementation complexity (with multiple parameters that need to be chosen). We provide clear guidelines and a simple methodology for choosing parameters, and show that with our optimizations the running-time is far lower than expected. For just one example, on a 2023 MacBook, the cost of proving the knowledge of discrete log with Fischlin is only 0.41ms (on a single core). We also extend the transform so that it can be applied to batch proofs, and show how this can be much more efficient than individually proving each statement. As a contribution of independent interest, we present a new algorithm for polynomial evaluation on any series of sequential points that does not require roots of unity. We hope that this paper will both encourage and help practitioners implement the Fischlin transform where relevant.
Last updated:  2024-04-04
Privacy Preserving Biometric Authentication for Fingerprints and Beyond
Marina Blanton and Dennis Murphy
Biometric authentication eliminates the need for users to remember secrets and serves as a convenient mechanism for user authentication. Traditional implementations of biometric-based authentication store sensitive user biometry on the server and the server becomes an attractive target of attack and a source of large-scale unintended disclosure of biometric data. To mitigate the problem, we can resort to privacy-preserving computation and store only protected biometrics on the server. While a variety of secure computation techniques is available, our analysis of privacy-preserving biometric computation and biometric authentication constructions revealed that available solutions fall short of addressing the challenges of privacy-preserving biometric authentication. Thus, in this work we put forward new constructions to address the challenges. Our solutions employ a helper server and use strong threat models, where a client is always assumed to be malicious, while the helper server can be semi-honest or malicious. We also determined that standard secure multi-party computation security definitions are insufficient to properly demonstrate security in the two-phase (enrollment and authentication) entity authentication application. We thus extend the model and formally show security in the multi-phase setting, where information can flow from one phase to another and the set of participants can change between the phases. We implement our constructions and show that they exhibit practical performance for authentication in real time.
Last updated:  2024-04-03
A Time-Space Tradeoff for the Sumcheck Prover
Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, and Andrew Zitek-Estrada
The sumcheck protocol is an interactive protocol for verifying the sum of a low-degree polynomial over a hypercube. This protocol is widely used in practice, where an efficient implementation of the (honest) prover algorithm is paramount. Prior work contributes highly-efficient prover algorithms for the notable special case of multilinear polynomials (and related settings): [CTY11] uses logarithmic space but runs in superlinear time; in contrast, [VSBW13] runs in linear time but uses linear space. In this short note, we present a family of prover algorithms for the multilinear sumcheck protocol that offer new time-space tradeoffs. In particular, we recover the aforementioned algorithms as special cases. Moreover, we provide an efficient implementation of the new algorithms, and our experiments show that the asymptotics translate into new concrete efficiency tradeoffs.
Last updated:  2024-04-03
Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK
Sophie Schmieg
In "Keeping up with the KEMs" Cremers et al. introduced various binding models for KEMs. The authors show that ML-KEM is LEAK-BIND-K-CT and LEAK-BIND-K-PK, i.e. binding the ciphertext and the public key in the case of an adversary having access, but not being able to manipulate the key material. They further conjecture that ML-KEM also has MAL-BIND-K-PK, but not MAL-BIND-K-CT, the binding of public key or ciphertext to the shared secret in the case of an attacker with the ability to manipulate the key material. This short paper demonstrates that ML-KEM does neither have MALBIND-K-CT nor MAL-BIND-K-PK, due to the attacker being able to produce mal-formed private keys, giving concrete examples for both. We also suggest mitigations, and sketch a proof for binding both ciphertext and public key when the attacker is not able to manipulate the private key as liberally.
Last updated:  2024-04-02
Cryptanalysis of Secure and Lightweight Conditional Privacy-Preserving Authentication for Securing Traffic Emergency Messages in VANETs
Mahender Kumar
In their paper, Wei et al. proposed a lightweight protocol for conditional privacy-preserving authentication in VANET. The protocol aims to achieve ultra-low transmission delay and efficient system secret key (SSK) updating. Their protocol uses a signature scheme with message recovery to authenticate messages. This scheme provides security against adaptively chosen message attacks. However, our analysis reveals a critical vulnerability in the scheme. It is susceptible to replay attacks, meaning a malicious vehicle can replay a message multiple times at different timestamps. This action undermines the overall effectiveness of conditional privacy. We suggest possible solutions to address these vulnerabilities and enhance the security of VANET communication.
Last updated:  2024-04-02
LIT-SiGamal: An efficient isogeny-based PKE based on a LIT diagram
Tomoki Moriya
In this paper, we propose a novel isogeny-based public key encryption (PKE) scheme named LIT-SiGamal. This is based on a LIT diagram and SiGamal. SiGamal is an isogeny-based PKE scheme that uses a commutative diagram with an auxiliary point. LIT-SiGamal uses a LIT diagram which is a commutative diagram consisting of large-degree horizontal isogenies and relatively small-degree vertical isogenies, while the original SiGamal uses a CSIDH diagram. A strength of LIT-SiGamal is efficient encryption and decryption. QFESTA is an isogeny-based PKE scheme proposed by Nakagawa and Onuki, which is a relatively efficient scheme in isogeny-based PKE schemes. In our experimentation with our proof-of-concept implementation, the computational time of the encryption of LIT-SiGamal is as efficient as that of QFESTA, and that of the decryption of LIT-SiGamal is about $5$x faster than that of QFESTA.
Last updated:  2024-04-02
A note on securing insertion-only Cuckoo filters
Fernando Virdia and Mia Filić
We describe a small tweak to Cuckoo filters that allows securing them under insertions using the techniques from Filić et al. (ACM CCS 2022), without the need for an outer PRF call.
Last updated:  2024-04-02
On implementation of Stickel's key exchange protocol over max-min and max-$T$ semirings
Sulaiman Alhussaini and Serge˘ı Sergeev
Given that the tropical Stickel protocol and its variants are all vulnerable to the generalized Kotov-Ushakov attack, we suggest employing the max-min semiring and, more generally, max-$T$ semiring where the multiplication is based on a $T-$norm, as a framework to implement the Stickel protocol. While the Stickel protocol over max-min semiring or max-$T$ semiring remains susceptible to a form of Kotov-Ushakov attack, we demonstrate that it exhibits significantly increased resistance against this attack when compared to the tropical (max-plus) implementation.
Last updated:  2024-04-02
Software-Defined Cryptography: A Design Feature of Cryptographic Agility
Jihoon Cho, Changhoon Lee, Eunkyung Kim, Jieun Lee, and Beumjin Cho
Cryptographic agility, or crypto-agility, is a design feature that enables agile updates to new cryptographic algorithms and standards without the need to modify or replace the surrounding infrastructure. This paper examines the prerequisites for crypto-agility and proposes its desired design feature. More specifically, we investigate the design characteristics of widely deployed cybersecurity paradigms, i.e., zero trust, and apply its design feature to crypto-agility, achieving greater visibility and automation in cryptographic management.
Last updated:  2024-04-09
Fast pairings via biextensions and cubical arithmetic
Damien Robert
Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, \ldots, pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions. This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt these algorithms to pairings on any model of abelian varieties with a polarisation $\Phi_D$, as long as we have an explicit theorem of the square for $D$. In particular, we give explicit formulas for the arithmetic of the biextension (and cubical torsor structure) associated to the divisor $D=2(0_E)$ on an elliptic curve. We derive very efficient pairing formulas on elliptic curves and Kummer lines. Notably for generic pairings on Montgomery curves, our cubical biextension ladder algorithm to compute pairings costs only $15M$ by bits, which as far as I know is faster than any pairing doubling formula in the literature.
Last updated:  2024-04-01
Similar Data is Powerful: Enhancing Inference Attacks on SSE with Volume Leakages
Björn Ho, Huanhuan Chen, Zeshun Shi, and Kaitai Liang
Searchable symmetric encryption (SSE) schemes provide users with the ability to perform keyword searches on encrypted databases without the need for decryption. While this functionality is advantageous, it introduces the potential for inadvertent information disclosure, thereby exposing SSE systems to various types of attacks. In this work, we introduce a new inference attack aimed at enhancing the query recovery accuracy of RefScore (presented at USENIX 2021). The proposed approach capitalizes on both similar data knowledge and an additional volume leakage as auxiliary information, facilitating the extraction of keyword matches from leaked data. Empirical evaluations conducted on multiple real-world datasets demonstrate a notable enhancement in query recovery accuracy, up to 19.5%. We also analyze the performance of the proposed attack in the presence of diverse countermeasures.
Last updated:  2024-04-01
Inject Less, Recover More: Unlocking the Potential of Document Recovery in Injection Attacks Against SSE
Manning Zhang, Zeshun Shi, Huanhuan Chen, and Kaitai Liang
Searchable symmetric encryption has been vulnerable to inference attacks that rely on uniqueness in leakage patterns. However, many keywords in datasets lack distinctive leakage patterns, limiting the effectiveness of such attacks. The file injection attacks, initially proposed by Cash et al. (CCS 2015), have shown impressive performance with 100% accuracy and no prior knowledge requirement. Nevertheless, this attack fails to recover queries with underlying keywords not present in the injected files. To address these limitations, our research introduces a novel attack strategy called LEAP-Hierarchical Fusion Attack (LHFA) that combines the strengths of both file injection attacks and inference attacks. Before initiating keyword injection, we introduce a new approach for inert/active keyword selection. In the phase of selecting injected keywords, we focus on keywords without unique leakage patterns and recover them, leveraging their presence for document recovery. Our goal is to achieve an amplified effect in query recovery. We demonstrate a minimum query recovery rate of 1.3 queries per injected keyword with a 10% data leakage of a real-life dataset, and initiate further research to overcome challenges associated with non-distinctive keywords.
Last updated:  2024-04-01
Zero-Knowledge Proof Vulnerability Analysis and Security Auditing
Xueyan Tang, Lingzhi Shi, Xun Wang, Kyle Charbonnet, Shixiang Tang, and Shixiao Sun
Zero-Knowledge Proof (ZKP) technology marks a revolutionary advancement in the field of cryptography, enabling the verification of certain information ownership without revealing any specific details. This technology, with its paradoxical yet powerful characteristics, provides a solid foundation for a wide range of applications, especially in enhancing the privacy and security of blockchain technology and other cryptographic systems. As ZKP technology increasingly becomes a part of the blockchain infrastructure, its importance for security and integrity becomes more pronounced. However, the complexity of ZKP implementation and the rapid iteration of the technology introduce various vulnerabilities, challenging the privacy and security it aims to offer. This study bases on the integrity, soundness, and zero-knowledge properties of ZKP to meticulously classify existing vulnerabilities and deeply explores multiple categories of vulnerabilities, including integrity issues, soundness problems, information leakage, and non-standardized cryptographic implementations. Furthermore, we propose a set of defense strategies that include a rigorous security audit process and a robust distributed network security ecosystem. This audit strategy employs a divide-and-conquer approach, segmenting the project into different levels, from the application layer to the platform-nature infrastructure layer, using threat modeling, linear code checking, and internal cross-review, among other means, aimed at comprehensively identifying vulnerabilities in ZKP circuits, revealing design flaws in ZKP applications, and accurately identifying inaccuracies in the integration process of ZKP primitives.
Last updated:  2024-04-12
Quantum Implementation and Analysis of SHA-2 and SHA-3
Kyungbae Jang, Sejin Lim, Yujin Oh, Hyunjun Kim, Anubhab Baksi, Sumanta Chakraborty, and Hwajeong Seo
Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3, and 5) and SHA-2 or SHA-3 (levels 2 and 4). In assessing the security strength of cryptographic algorithms against quantum threats, accurate predictions of quantum resources are crucial. Following the work of Jaques et al. in Eurocrypt 2020, NIST estimated security levels 1, 3, and 5, corresponding to quantum circuit size for finding the key for AES-128, AES-192, and AES-256, respectively. This work has been recently followed-up by Huang et al. (Asiacrypt'22) and Liu et al. (Asiacrypt'23). However, for levels 2 and 4, which relate to the collision finding for the SHA-2 and SHA-3 hash functions, quantum attack complexities are probably not well-studied. In this paper, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.
Last updated:  2024-04-09
Single Trace is All It Takes: Efficient Side-channel Attack on Dilithium
Zehua Qiao, Yuejun Liu, Yongbin Zhou, Yuhan Zhao, and Shuyi Chen
As the National Institute of Standards and Technology (NIST) concludes its post-quantum cryptography (PQC) competition, the winning algorithm, Dilithium, enters the deployment phase in 2024. This phase underscores the importance of conducting thorough practical security evaluations. Our study offers an in-depth side-channel analysis of Dilithium, showcasing the ability to recover the complete private key, ${s}_1$, within ten minutes using just two signatures and achieving a 60% success rate with a single signature. We focus on analyzing the polynomial addition in Dilithium, $z=y+{cs}_1$, by breaking down the attack into two main phases: the recovery of $y$ and ${cs}_1$ through side-channel attacks, followed by the resolution of a system of error-prone equations related to ${cs}_1$. Employing Linear Regression-based profiled attacks enables the successful recovery of the full $y$ value with a 40% success rate without the necessity for initial filtering. The extraction of ${cs}_1$ is further improved using a CNN model, which boasts an average success rate of 75%. A significant innovation of our research is the development of a constrained optimization-based residual analysis technique. This method efficiently recovers ${s}_1$ from a large set of error-containing equations concerning ${cs}_1$, proving effective even when only 10% of the equations are accurate. We conduct a practical attack on the Dilithium2 implementation on an STM32F4 platform, demonstrating that typically two signatures are sufficient for complete private key recovery, with a single signature sufficing in optimal conditions. Using a general-purpose PC, the full private key can be reconstructed in ten minutes.
Last updated:  2024-03-31
A Black-box Attack on Fixed-Unitary Quantum Encryption Schemes
Cezary Pilaszewicz, Lea R. Muth, and Marian Margraf
We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state $\ket{\psi}$. This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme and suggest how to improve it to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption schemes to ensure their security against quantum adversaries, even in a black-box setting.
Last updated:  2024-03-31
DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE
Zeyu Liu, Katerina Sotiraki, Eran Tromer, and Yunhao Wang
Show abstract
Oblivious message retrieval (OMR) allows messages resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks from malicious senders (i.e., DoS-resistant) under standard assumptions? In this paper, we first prove that a prior construction OMRp2 is DoS-resistant under a standard LWE assumption, resolving an open conjecture of prior works. Then, we present DoS-PerfOMR: a provably DoS-resistant OMR construction that is 12x faster than OMRp2, and (almost) matches the performance of the state-of-the-art OMR scheme that is not DoS-resistant. As a building block, we analyze the snake-eye resistance property for general PKE schemes. We construct a new lattice-based PKE scheme, LWEmongrass that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying OMRp2. We also show that the natural candidates (e.g., RingLWE PKE) are not snake-eye resistant. Of independent interest, we introduce two variants of LWE with side information, as components towards proving the properties of LWEmongrass, and reduce standard LWE to them for the parameters of interest.
Last updated:  2024-03-31
Distribution of cycles in supersingular $\ell$-isogeny graphs
Eli Orvis
Recent work by Arpin, Chen, Lauter, Scheidler, Stange, and Tran counted the number of cycles of length $r$ in supersingular $\ell$-isogeny graphs. In this paper, we extend this work to count the number of cycles that occur along the spine. We provide formulas for both the number of such cycles, and the average number as $p \to \infty$, with $\ell$ and $r$ fixed. In particular, we show that when $r$ is not a power of $2$, cycles of length $r$ are disproportionately likely to occur along the spine. We provide experimental evidence that this result holds in the case that $r$ is a power of $2$ as well.
Last updated:  2024-03-30
Secure Multi-Party Linear Algebra with Perfect Correctness
Jules Maire and Damien Vergnaud
We present new secure multi-party computation protocols for linear algebra over a finite field, which improve the state-of-the-art in terms of security. We look at the case of \emph{unconditional security with perfect correctness}, i.e., information-theoretic security without errors. We notably propose an expected constant-round protocol for solving systems of $m$ linear equations in $n$ variables over $\mathbb{F}_q$ with expected complexity $O(k(n^{2.5} + m^{2.5}+n^2m^{0.5}))$ where $k > m(m+n)+1$ (complexity is measured in terms of the number of secure multiplications required). The previous proposals were not error-free: known protocols can indeed fail and thus reveal information with probability $\Omega(\textsf{poly}(m)/q)$. Our protocols are simple and rely on existing computer-algebra techniques, notably the Preparata-Sarwate algorithm, a simple but poorly known ``baby-step giant-step'' method for computing the characteristic polynomial of a matrix, and techniques due to Mulmuley for error-free linear algebra in positive characteristic.
Last updated:  2024-04-01
An Efficient SNARK for Field-Programmable and RAM Circuits
Jehyuk Jang and Jamie Judd
The advancement of succinct non-interactive argument of knowledge (SNARK) with constant proof size has significantly enhanced the efficiency and privacy of verifiable computation. Verifiable computation finds applications in distributed computing networks, particularly in scenarios where nodes cannot be generally trusted, such as blockchains. However, fully harnessing the efficiency of SNARK becomes challenging when the computing targets in the network change frequently, as the SNARK verification can involve some untrusted preprocess of the target, which is expected to be reproduced by other nodes. This problem can be addressed with two approaches: One relieves the reproduction overhead by reducing the dimensionality of preprocessing data; The other utilizes verifiable machine computation, which eliminates the dependency on preprocess at the cost of increased overhead to SNARK proving and verification. In this paper, we propose a new SNARK with constant proof size applicable to both approaches. The proposed SNARK combines the efficiency of Groth16 protocol, albeit lacking universality for new problems, and the universality of PlonK protocol, albeit with significantly larger preprocessing data dimensions. Consequently, we demonstrate that our proposed SNARK maintains the efficiency and the universality while significantly reducing the dimensionality of preprocessing data. Furthermore, our SNARK can be seamlessly applied to the verifiable machine computation, requiring a proof size smaller about four to ten times than other related works.
Last updated:  2024-03-29
A Decentralized Federated Learning using Reputation
Olive Chakraborty and Aymen Boudguiga
Nowadays Federated learning (FL) is established as one of the best techniques for collaborative machine learning. It allows a set of clients to train a common model without disclosing their sensitive and private dataset to a coordination server. The latter is in charge of the model aggregation. However, FL faces some problems, regarding the security of updates, integrity of computation and the availability of a server. In this paper, we combine some new ideas like clients’ reputation with techniques like secure aggregation using Homomorphic Encryption and verifiable secret sharing using Multi-Party Computation techniques to design a decentralized FL system that addresses the issues of incentives, security and availability amongst others. One of the original contributions of this work is the new leader election protocol which uses a secure shuffling and is based on a proof of reputation. Indeed, we propose to select an aggregator among the clients participating to the FL training using their reputations. That is, we estimate the reputation of each client at every FL iteration and then we select the next round aggregator from the set of clients with the best reputations. As such, we remove misbehaving clients (e.g., byzantines) from the list of clients eligible for the role of aggregation server.
Last updated:  2024-03-29
RSA-Based Dynamic Accumulator without Hashing into Primes
Victor Youdom Kemmoe and Anna Lysyanskaya
A cryptographic accumulator is a compact data structure for representing a set of elements coming from some domain. It allows for a compact proof of membership and, in the case of a universal accumulator, non-membership of an element x in the data structure. A dynamic accumulator, furthermore, allows elements to be added to and deleted from the accumulator. Previously known RSA-based dynamic accumulators were too slow in practice because they required that an element in the domain be represented as a prime number. Accumulators based on settings other than RSA had other drawbacks such as requiring a prohibitively large common reference string or a trapdoor, or not permitting deletions. In this paper, we construct RSA-based dynamic universal accumulators that do not require that the accumulated elements be represented as primes. We also show how to aggregate membership and non-membership witnesses and batch additions and deletions. We demonstrate that the efficiency gains compared to previously known RSA-based accumulators are substantial, and, for the first time, make cryptographic accumulators a viable candidate for a certificate revocation mechanism as part of a WebPKI-type system.
Last updated:  2024-03-29
Polylogarithmic Proofs for Multilinears over Binary Towers
Benjamin E. Diamond and Jim Posen
We introduce a polylogarithmic-verifier polynomial commitment scheme for multilinears over towers of binary fields. To achieve this, we adapt an idea of Zeilberger, Chen and Fisch's BaseFold ('23) to the setting of binary towers, using FRI (ICALP '18)'s binary-field variant. In the process, we reinterpret Lin, Chung and Han (FOCS '14)'s novel polynomial basis so as to make apparent its compatibility with FRI. We moreover introduce a "packed" version of our protocol, which supports—with no embedding overhead during its commitment phase—multilinears over tiny fields (including that with just two elements). Our protocol leverages a new multilinear FRI-folding technique, and exploits the recent tensor proximity gap of Diamond and Posen (Commun. Cryptol. '24). We achieve concretely small proofs for enormous binary multilinears, shrinking the proofs of Diamond and Posen ('23) by an order of magnitude.
Last updated:  2024-04-01
Two Levels are Better than One: Dishonest Majority MPC with $\widetilde{O}(|C|)$ Total Communication
Alexander Bienstock and Kevin Yeo
In recent years, there has been tremendous progress in improving the communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting, where $t<(1-\varepsilon)\cdot n$ for some constant $0<\varepsilon\leq 1/2$, the recent works Sharing Transformation (Goyal $\textit{et al.}$, CRYPTO'22) and SuperPack (Escudero $\textit{et al.}$, EUROCRYPT'23) presented protocols with information-theoretic online phases achieving $O(1)$ communication per multiplication gate, across all parties. However, the former assumes that their offline phase is instantiated by a trusted party, while the latter instantiates their offline phase with $\Omega(n)$ communication per multiplication gate assuming oblivious linear evaluation (OLE) correlations. In this work, we present a dishonest majority MPC protocol for $t< (1-\varepsilon)\cdot n$ with $\widetilde{O}(1)$ total communication per multiplication gate across both the offline and online phases, or $\widetilde{O}(|C|)$ total communication for any arithmetic circuit $C$. To do so, we securely instantiate the offline phase of Sharing Transformation, assuming some OLE correlations. The major bottleneck in instantiating the offline phases of both Sharing Transformation and SuperPack is generating random packed beaver triples of the form $[\boldsymbol{a}], [\boldsymbol{b}], [\boldsymbol{c}]$, for random $\boldsymbol{a},\boldsymbol{b}\in\mathbb{F}^k$, and $\boldsymbol{c}=\boldsymbol{a}*\boldsymbol{b}\in\mathbb{F}^k$, where $k=\Omega(n)$ is the $\textit{packing parameter}$. We overcome this barrier by presenting a packed beaver triple protocol with $\widetilde{O}(n)$ total communication, or $\widetilde{O}(1)$ communication per underlying triple. Our packed beaver triple protocol consists of two levels of randomness extraction. The first level uses a relaxation of super-invertible matrices that we introduce, called $\textit{weakly}$ super-invertible matrices, in which sub-matrices have sufficiently high (but not necessarily full) rank. This weakening enables matrix constructions with only $O(n)$ non-zero entries, which is a primary reason for the efficiency of our protocol. Our second level of extraction is based on the $\textit{triple extraction}$ protocol of (Choudhury and Patra, Trans. Inform. Theory '17).
Last updated:  2024-03-29
Best of Two Worlds: Efficient, Usable and Auditable Biometric ABC on the Blockchain
Neyire Deniz Sarier
In [1], two generic constructions for biometric-based non-transferable Attribute Based Credentials (biometric ABC) are presented, which offer different trade-offs between efficiency and trust assumptions. In this paper, we focus on the second scheme denoted as BioABC-ZK that tries to remove the strong (and unrealistic) trust assumption on the Reader R, and show that BioABC-ZK has a security flaw for a colluding R and Verifier V. Besides, BioABC-ZK lacks GDPR-compliance, which requires secure processing of biometrics, for instance in form of Fuzzy Extractors, as opposed to (i) storing the reference biometric template aBio in the user's mobile phone and (ii) processing of biometrics using an external untrusted R, whose foreign manufacturers are unlikely to adjust their products according to GDPR. The contributions of this paper are threefold. First, we review efficient biometric ABC schemes to identify the privacy-by-design criteria for them. In view of these principles, we propose a new architecture for biometric ABC of [2] by adapting the recently introduced core/helper setting of [3]. Briefly, a user in our modified setting is composed of a constrained core device (a SIM card) inside a helper device (a smart phone with dual SIM and face recognition feature), which -as opposed to [1]- does not need to store aBio. This way, the new design provides Identity Privacy without the need for an external R and/or a dedicated hardware per user such as a biometric smart card reader or a tamper proof smart card as in current hardware-bound credential systems. Besides, the new system maintains minimal hardware requirements on the SIM card -only responsible for storing ABC and helper data-, which results in easy adoption and usability without loosing efficiency, if recently introduced key derivation scheme of [4] and the modified ABC scheme of [2] are employed together. As a result, a total overhead of 500 milliseconds to a showing of a comparable non-biometric ABC is obtained instead of the 2.1 seconds in [1] apart from the removal of computationally expensive pairings. Finally, as different from [1], auditing is achieved via Blockchain instead of proving in zero-knowledge the actual biometric matching by the user to reveal malicious behavior of R and V.
Last updated:  2024-03-28
Anonymous Revocable Identity-Based Encryption Supporting Anonymous Revocation
Kwangsu Lee
Anonymous identity-based encryption (AIBE) is an extension of identity-based encryption (IBE) that enhances the privacy of a ciphertext by providing ciphertext anonymity. In this paper, we introduce the concept of revocable IBE with anonymous revocation (RIBE-AR), which is capable of issuing an update key and hiding the revoked set of the update key that efficiently revokes private keys of AIBE. We first define the security models of RIBE-AR and propose an efficient RIBE-AR scheme in bilinear groups. Our RIBE-AR scheme is similar to the existing RIBE scheme in terms of efficiency, but is the first RIBE scheme to provide additional ciphertext anonymity and revocation privacy. We show that our RIBE-AR scheme provides the selective message privacy, selective identity privacy, and selective revocation privacy.
Last updated:  2024-03-28
Side Channel Resistant Sphincs+
Scott Fluhrer
Here is a potential way to create a SLH-DSA-like\cite{DraftFIPS205} key generation/signer that aspires to be resistant to DPA side channel attacks. We say that it is “SLH-DSA-like”, because it does not follow the FIPS 205 method of generating signatures (in particular, it does not have the same mapping from private key, messages, opt\_rand to signatures), however it does generate public keys and signatures that are compatible with the standard signature verification method, and with the same security (with a small security loss against side channel attacks). In our tests, this idea performed 1.7 times slower compared to an unprotected version.
Last updated:  2024-03-28
CCA Secure Updatable Encryption from Non-Mappable Group Actions
Jonas Meers and Doreen Riepel
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019). Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the necessary homomorphic properties, the introduced noise allows only a bounded number of updates. Group actions have become an important alternative, however, their structure is limited. The only known UE scheme by Leroux and Roméas (IACR ePrint 2022/739) uses effective triple orbital group actions which uses additional algebraic structure of CSIDH. Using an ideal cipher, similar to the group-based scheme $\mathsf{SHINE}$ (Boyd et al., CRYPTO 2020), requires the group action to be mappable, a property that natural isogeny-based group actions do not satisfy. At the same time, other candidates based on non-commutative group actions suffer from linearity attacks. For these reasons, we explicitly ask how to construct UE from group actions that are not mappable. As a warm-up, we present $\mathsf{BIN}\text{-}\mathsf{UE}$ which uses a bit-wise approach and is CPA secure based on the well-established assumption of weak pseudorandomness and in the standard model. We then construct the first actively secure UE scheme from post-quantum assumptions. Our scheme $\mathsf{COM}\text{-}\mathsf{UE}$ extends $\mathsf{BIN}\text{-}\mathsf{UE}$ via the Tag-then-Encrypt paradigm. We prove CCA security in the random oracle model based on a stronger computational assumption. We justify the hardness of our new assumption in the algebraic group action model.
Last updated:  2024-04-01
Number-Theoretic Transform Architecture for Fully Homomorphic Encryption from Hypercube Topology
Jingwei Hu, Yuhong Fang, and Wangchen Dai
This paper introduces a high-performance and scalable hardware architecture designed for the Number-Theoretic Transform (NTT), a fundamental component extensively utilized in lattice-based encryption and fully homomorphic encryption schemes. The underlying rationale behind this research is to harness the advantages of the hypercube topology. This topology serves to significantly diminish the volume of data exchanges required during each iteration of the NTT, reducing it to a complexity of $\Omega(\log N)$. Concurrently, it enables the parallelization of $N$ processing elements. This reduction in data exchange operations is of paramount importance. It not only facilitates the establishment of interconnections among the $N$ processing elements but also lays the foundation for the development of a high-performance NTT design. This is particularly valuable when dealing with large values of $N$.
Last updated:  2024-03-28
On the Security of Data Markets and Private Function Evaluation
István Vajda
The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation and its relaxed version was introduced in [Horvath, 2019]. In this article, we propose and examine several different approaches for such tasks with computational and information theoretical security against static corruption adversary. The latter level of security implies quantum-security. We also build known techniques and constructions into our solution where they fit into our tasks. The main cryptographic primitive, naturally related to the task is 1-out-of-n oblivious transfer. We use Secure Multiparty Computation techniques and in one of the constructions functional encryption primitive. The analysis of the computational complexity of the constructions shows that the considered tasks can efficiently be implemented, however it depends on the range of parameter values (e.g. size of database, size of the set of permitted function), the execution environment (e.g. concurrency) and of course on the level of security.
Last updated:  2024-03-28
Two-Round Threshold Signature from Algebraic One-More Learning with Errors
Thomas Espitau, Shuichi Katsumata, and Kaoru Takemure
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world. In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the algebraic one-more learning with errors (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of AOMMLWE based on the standard MLWE and MSIS assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.
Last updated:  2024-03-28
Reducing Signature Size of Matrix-code-based Signature Schemes
Tung Chou, Ruben Niederhagen, Lars Ran, and Simona Samardjiska
This paper shows novel techniques to reduce the signature size of the code-based signature schemes MEDS and ALTEQ, by a large factor. For both schemes, the signature size is dominated by the responses for rounds with nonzero challenges, and we reduce the signature size by reducing the size of these responses. For MEDS, each of the responses consists of $m^2 + n^2$ field elements,while in our new protocol each response consists of only $2k$ ($k$ is usually chosen to be close to $m$ and $n$) field elements. For ALTEQ, each of the responses consists of $n^2$ field elements, while in our new protocol each response consists of about $\sqrt{2} n^{3/2}$ field elements. In both underlying $\Sigma$-protocols of the schemes, the prover generates a random isometry and sends the corresponding isometry to the verifier as the response. Instead of doing this, in our new protocols, the prover derives an isometry from some random code words and their presumed (full or partial) images. The prover sends the corresponding code words and images to the verifier as the response, so that the verifier can derive an isometry in the same way. Interestingly, it turns out that each response takes much fewer field elements to represent in this way.
Last updated:  2024-03-28
HW-token-based Common Random String Setup
István Vajda
In the common random string model, the parties executing a protocol have access to a uniformly random bit string. It is known that under standard intractability assumptions, we can realize any ideal functionality with universally composable (UC) security if a trusted common random string (CrS) setup is available. It was always a question of where this CrS should come from since the parties provably could not compute it themselves. Trust assumptions are required, so minimizing the level of such trust is a fundamentally important task. Our goal is to design a CrS setup protocol under a weakened trust assumption. We present an HW-token-based CrS setup for 2-party cryptographic protocols using a single token only. Our protocol is a UC-secure realization of ideal common random string functionality FCrS. We show the multiple-session security of the protocol and we also consider the multi-party extension of it.
Last updated:  2024-03-27
Reckle Trees: Updatable Merkle Batch Proofs with Applications
Charalampos Papamanthou, Shravan Srinivasan, Nicolas Gailly, Ismael Hishon-Rezaizadeh, Andrus Salumets, and Stjepan Golemac
We propose Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees' distinguishing feature is their support for succinct batch proofs that are updatable - enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Our technical approach is based on embedding the computation of the batch hash inside the recursive Merkle verification via a hash-based accumulator called canonical hashing. Due to this embedding, our batch proofs can be updated in logarithmic time, whenever a Merkle leaf (belonging to the batch or not) changes, by maintaining a data structure that stores previously-computed recursive proofs. Assuming enough parallelism, our batch proofs are also computable in $O(\log n)$ parallel time - independent of the size of the batch. As a natural extension of Reckle trees, we also introduce Reckle+ trees. Reckle+ trees provide updatable and succinct proofs for certain types of Map/Reduce computations. In this setting, a prover can commit to a memory $\mathsf{M}$ and produce a succinct proof for a Map/Reduce computation over a subset $I$ of $\mathsf{M}$. The proof can be efficiently updated whenever $I$ or $\mathsf{M}$ changes. We present and experimentally evaluate two applications of Reckle+ trees, dynamic digest translation and updatable BLS aggregation. In dynamic digest translation we are maintaining a proof of equivalence between Merkle digests computed with different hash functions, e.g., one with a SNARK-friendly Poseidon and the other with a SNARK-unfriendly Keccak. In updatable BLS aggregation we maintain a proof for the correct aggregation of a $t$-aggregate BLS key, derived from a $t$-subset of a Merkle-committed set of individual BLS keys. Our evaluation using Plonky2 shows that Reckle trees and Reckle+ trees have small memory footprint, significantly outperform previous approaches in terms of updates and verification time, enable applications that were not possible before due to huge costs involved (Reckle trees are up to 200 times faster), and have similar aggregation performance with previous implementations of batch proofs.
Last updated:  2024-03-27
Statistical testing of random number generators and their improvement using randomness extraction
Cameron Foreman, Richie Yeung, and Florian J. Curchod
Random number generators (RNGs) are notoriously hard to build and test, especially in a cryptographic setting. Although one cannot conclusively determine the quality of an RNG by testing the statistical properties of its output alone, running numerical tests is both a powerful verification tool and the only universally applicable method. In this work, we present and make available a comprehensive statistical testing environment (STE) that is based on existing statistical test suites. The STE can be parameterised to run lightweight (i.e. fast) all the way to intensive testing, which goes far beyond what is required by certification bodies. With it, we benchmark the statistical properties of several RNGs, comparing them against each other. We then present and implement a variety of post-processing methods, in the form of randomness extractors, which improve the RNG's output quality under different sets of assumptions and analyse their impact through numerical testing with the STE.
Last updated:  2024-03-27
Updatable Policy-Compliant Signatures
Christian Badertscher, Monosij Maitra, Christian Matt, and Hendrik Waldner
Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality, or only senders that are at least 18 years old can send to members of the computer science department. PCS further requires attribute-privacy – nothing about the users’ attributes is revealed from their public keys and signatures apart from whether the attributes satisfy the policy or not. The policy in a PCS scheme is fixed once and for all during the setup. Therefore, a policy update requires a redistribution of all keys. This severely limits the practicality of PCS. In this work, we introduce the notion of updatable policy-compliant signatures (UPCS) extending PCS with a mechanism to efficiently update the policy without redistributing keys to all participants. We define the notion of UPCS and provide the corresponding security definitions. We then provide a generic construction of UPCS based on digital signatures, a NIZK proof system, and a so-called secret-key two-input partially-hiding predicate encryption (2-PHPE) scheme. Unfortunately, the only known way to build the latter for general two-input predicates is using indistinguishability obfuscation. We show that the reliance on the heavy tool of 2-PHPE is inherent to build UPCS by proving that non-interactive UPCS implies 2-PHPE. To circumvent the reliance on 2-PHPE, we consider interactive UPCS, which allows the sender and receiver to interact during the message signing procedure. In this setting, we present two schemes: the first one requires only a digital signature scheme, a NIZK proof system, and secure two-party computation. This scheme works for arbitrary policies, but requires sender and receiver to engage in a two-party computation protocol for each policy update. Our second scheme additionally requires a (single-input) predicate-encryption scheme but, in turn, only requires a single interaction between sender and receiver, independent of the updates. In contrast to 2-PHPE, single-input predicate encryption for certain predicate classes is known to exist (e.g., from pairings) under more concrete and well-understood assumptions.
Last updated:  2024-03-27
One Tree to Rule Them All: Optimizing GGM Trees and OWFs for Post-Quantum Signatures
Carsten Baum, Ward Beullens, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, and Peter Scholl
The use of MPC-in-the-Head (MPCitH)-based zero-knowledge proofs of knowledge (ZKPoK) to prove knowledge of a preimage of a one-way function (OWF) is a popular approach towards constructing efficient post-quantum digital signatures. Starting with the Picnic signature scheme, many optimized MPCitH signatures using a variety of (candidate) OWFs have been proposed. Recently, Baum et al. (CRYPTO 2023) showed a fundamental improvement to MPCitH, called VOLE-in-the-Head (VOLEitH), which can generically reduce the signature size by at least a factor of two without decreasing computational performance or introducing new assumptions. Based on this, they designed the FAEST signature which uses AES as the underlying OWF. However, in comparison to MPCitH, the behavior of VOLEitH when using other OWFs is still unexplored. In this work, we improve a crucial building block of the VOLEitH and MPCitH approaches, the so-called all-but-one vector commitment, thus decreasing the signature size of VOLEitH and MPCitH signature schemes. Moreover, by introducing a small Proof of Work into the signing procedure, we can improve the parameters of VOLEitH (further decreasing signature size) without compromising the computational performance of the scheme. Based on these optimizations, we propose three VOLEitH signature schemes FAESTER, KuMQuat, and MandaRain based on AES, MQ, and Rain, respectively. We carefully explore the parameter space for these schemes and implement each, showcasing their performance with benchmarks. Our experiments show that these three signature schemes outperform MPCitH-based competitors that use comparable OWFs, in terms of both signature size and signing/verification time.
Last updated:  2024-03-27
Guess and Determine Analysis Based on Set Split
Zhe CEN, Xiutao FENG, Zhangyi WANG, Yamin ZHU, and Chunping CAO
The guess and determine attack is a common method in cryptanalysis. Its idea is to firstly find some variables which can deduced all remaining variables in a cipher and then traverse all values of these variables to find a solution. People usually utilize the exhausted search to find these variables. However, it is not applicable any more when the number of variables is a bit large. In this work we propose a guess and determine analysis based on set split to find as few variables as possible in the first step of guess and determine attack, which is a kind of exhausted search based on trading space for time and is more effective than the latter. Firstly we give an idea of set split in detail by introducing some conceptions such as base set, likely solution region and so on. And then we discuss how to utilize the set split to achieve a guess and determine analysis and give its specific implementation scheme. Finally, comparing it with the other two guess and determine analysis based on the exhausted search and the MILP method, we illustrate the effectiveness of our method by two ciphers Snow 2.0 and Enocoro-128v2. Our method spends about 0.000103 seconds finding a best solution of 9 variables for the former and 0.13 seconds finding a best solution of 18 variables for the latter in a personal Macbook respectively, which are better than those of both the exhausted search and the MILP method.
Last updated:  2024-03-28
Improving Generic Attacks Using Exceptional Functions
Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, and André Schrottenloher
Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle. In this paper, we expand the use of such functions in generic cryptanalysis with several new attacks. First, we improve the attack of Gilbert et al. from O(2^3c/4) to O(2^2c/3), where c is the capacity. This new attack uses a nested pair of functions with exceptional behavior, where the second function is defined over the cycle of the first one. Next, we introduce several new generic attacks against hash combiners, notably using small cycles to improve the complexities of the best existing attacks on the XOR combiner, Zipper Hash and Hash-Twice. Last but not least, we propose the first quantum second preimage attack against Hash-Twice, reaching a quantum complexity O(2^3n/7).
Last updated:  2024-03-26
Real-Valued Somewhat-Pseudorandom Unitaries
Zvika Brakerski and Nir Magrafta
We explore a very simple distribution of unitaries: random (binary) phase -- Hadamard -- random (binary) phase -- random computational-basis permutation. We show that this distribution is statistically indistinguishable from random Haar unitaries for any polynomial set of orthogonal input states (in any basis) with polynomial multiplicity. This shows that even though real-valued unitaries cannot be completely pseudorandom (Haug, Bharti, Koh, arXiv:2306.11677), we can still obtain some pseudorandom properties without giving up on the simplicity of a real-valued unitary. Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice, assuming that the input is orthogonal and flat (that is, has high min-entropy when measured in the computational basis). Using quantum-secure one-way functions (which imply quantum-secure pseudorandom functions and permutations), we obtain an efficient cryptographic instantiation of the above.
Last updated:  2024-03-25
Anamorphic Encryption: New Constructions and Homomorphic Realizations
Dario Catalano, Emanuele Giunta, and Francesco Migliaro
The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator. The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys. Over the last year several works considered this question and proposed constructions, novel extensions and strengthened definitions. In this work we make progress on the study of this primitive in three main directions. First, we show that two general and well established encryption paradigms, namely hybrid encryption and the IBE-to-CCA transform, admit very simple and natural anamorphic extensions. Next, we show that anamorphism, far from being a phenomenon isolated to "basic" encryption schemes, extends also to homomorphic encryption. We show that some existing homomorphic schemes, (and most notably the fully homomorphic one by Gentry, Sahai and Waters) can be made anamorphic, while retaining their homomorphic properties both with respect to the regular and the covert message. Finally we refine the notion of anamorphic encryption by envisioning the possibility of splitting the anamorphic key into an encryption component (that only allows to encrypt covert messages) and a decryption component. This makes possible for a receiver to set up several, independent, covert channels associated with a single covert key.
Last updated:  2024-03-25
A Variation on Knellwolf and Meier's Attack on the Knapsack Generator
Florette Martinez
Pseudo-random generators are deterministic algorithms that take in input a random secret seed and output a flow of random-looking numbers. The Knapsack generator, presented by Rueppel and Massey in 1985 is one of the many attempt at designing a pseudo-random generator that is cryptographically secure. It is based on the subset-sum problem, a variant of the Knapsack optimization problem, which is considered computationally hard. In 2011 Simon Knellwolf et Willi Meier found a way to go around this hard problem and exhibited a weakness of this generator. In addition to be able to distinguish the outputs from the uniform distribution, they designed an algorithm that retrieves a large portion of the secret. We present here an alternate version of the attack, with similar costs, that works on the same range of parameters but retrieves a larger portion of the secret.
Last updated:  2024-03-25
Harmonizing PUFs for Forward Secure Authenticated Key Exchange with Symmetric Primitives
Harishma Boyapally, Durba Chatterjee, Kuheli Pratihar, Sayandeep Saha, Debdeep Mukhopadhyay, and Shivam Bhasin
Physically Unclonable Functions (PUFs) have been a potent choice for enabling low-cost, secure communication. However, in most applications, one party holds the PUF, and the other securely stores the challenge-response pairs (CRPs). It does not remove the need for secure storage entirely, which is one of the goals of PUFs. This paper proposes a PUF-based construction called Harmonizing PUFs ($\textsf{H_PUF}$s), allowing two independent PUFs to generate the same outcome without storing any confidential data. As an application of $\textsf{H_PUF}$ construction, we present $\textsf{H-AKE}$: a low-cost authenticated key exchange protocol for resource-constrained nodes that is secure against replay and impersonation attacks. The novelty of the protocol is that it achieves forward secrecy without requiring to perform asymmetric group operations like elliptic curve scalar multiplications underlying traditional key-exchange techniques.
Last updated:  2024-03-25
Lower data attacks on Advanced Encryption Standard
Orhun Kara
The Advanced Encryption Standard (AES) is one of the most commonly used and analyzed encryption algorithms. In this work, we present new combinations of some prominent attacks on AES, achieving new records in data requirements among attacks, utilizing only $2^4$ and $2^{16}$ chosen plaintexts (CP) for 6-round and 7-round AES-192/256 respectively. One of our attacks is a combination of a meet-in-the-middle (MiTM) attack with a square attack mounted on 6-round AES-192/256 while another attack combines an MiTM attack and an integral attack, utilizing key space partitioning technique, on 7-round AES-192/256. Moreover, we illustrate that impossible differential (ID) attacks can be viewed as the dual of MiTM attacks in certain aspects which enables us to recover the correct key using the meet-in-the-middle (MiTM) technique instead of sieving through all potential wrong keys in our ID attack. Furthermore, we introduce the constant guessing technique in the inner rounds which significantly reduces the number of key bytes to be searched. The time and memory complexities of our attacks remain marginal.
Last updated:  2024-03-27
Single Server PIR via Homomorphic Thorp Shuffles
Ben Fisch, Arthur Lazzaretti, Zeyu Liu, and Charalampos Papamanthou
Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$ interacts with the server, which holds a $N$-bit string $\textsf{DB}$ in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single server client-preprocessing model, initially idealized by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run some joint preprocessing algorithm, after which the client can retrieve elements of the server's string $\textsf{DB}$ privately in time sublinear in $N$. All known constructions of single server client-preprocessing PIR rely on one of the following two paradigms: (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth ($O_\lambda (N)$) circuit under FHE in order to execute the preprocessing phase. In this paper, we construct a single server client-preprocessing PIR scheme which achieves both sublinear offline bandwidth (the client does not have to download the whole database offline) and a low-depth (i.e. $O_\lambda(1)$), highly parallelizable preprocessing circuit. We estimate that on a single thread, our scheme's preprocessing time should be more than 350x times faster than in prior single server client-preprocessing PIR constructions. Moreover, with parallelization, the latency reduction would be even more drastic. In addition, this construction also allows for updates in $O_\lambda (1)$ time, something not achieved before in this model.
Last updated:  2024-03-22
Watermarkable and Zero-Knowledge Verifiable Delay Functions from any Proof of Exponentiation
Charlotte Hoffmann and Krzysztof Pietrzak
A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof $\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for the proof of exponentiation (PoE) certifying that $y=x^{2^T}$, with Wesolowski (Eurocrypt'19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS'19). A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt'22) are short-lived proofs and signatures, which are proofs and signatures which are only sound for some time $t$, but after that can be forged by anyone. For this they rely on "watermarkable VDFs", where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on "zero-knowledge VDFs", where instead of the output $y$, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski's PoE, for the watermarkable VDFs there's currently no security proof. In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al.. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al's construction in several dimensions (faster forging times, weaker assumptions). A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for $y=x^{2^T}$, but instead give a (watermarked or zk) proof for the more basic statement that $x',y'$ satisfy $x'=x^r,y'=y^r$ for some $r$, together with a normal PoE for $y'=(x')^{2^T}$.
Last updated:  2024-03-22
Folding-based zkLLM
Wilbert W
This paper introduces a new approach to construct zero-knowledge large language models (zkLLM) based on the Folding technique. We first review the concept of Incrementally Verifiable Computation (IVC) and compare the IVC constructions based on SNARK and Folding. Then we discuss the necessity of Non-uniform IVC (NIVC) and present several Folding schemes that support more expressive circuits, such as SuperNova, Sangria, Origami, HyperNova, and Protostar. Based on these techniques, we propose a zkLLM design that uses a RAM machine architecture with a set of opcodes. We define corresponding constraint circuits for each opcode and describe the workflows of the prover and verifier. Finally, we provide examples of opcodes to demonstrate the circuit construction methods. Our zkLLM design achieves high efficiency and expressiveness, showing great potential for practical applications.
Last updated:  2024-03-25
Making Hash-based MVBA Great Again
Hanwen Feng, Zhenliang Lu, Tiancheng Mai, and Qiang Tang
Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others. Recent efforts (Lu et al, PODC' 20) have pushed the communication complexity of $\mathsf{MVBA}$ to optimal $O(\ell n + \lambda n^2)$, which, however, heavily rely on ``heavyweight'' cryptographic tools, such as non-interactive threshold signatures. The computational cost of algebraic operations, the susceptibility to quantum attacks, and the necessity of a trusted setup associated with threshold signatures present significant remaining challenges. There is a growing interest in information-theoretic or hash-based constructions (historically called signature-free constructions). Unfortunately, the state-of-the-art hash-based $\mathsf{MVBA}$ (Duan et al., CCS'23) incurs a large $O(\ell n^2 + \lambda n^3)$-bits communication, which in turn makes the hash-based $\mathsf{MVBA}$inferior performance-wise comparing with the ``classical'' ones. Indeed, this was clearly demonstrated in our experimental evaluations. To make hash-based $\mathsf{MVBA}$ actually realize its full potential, in this paper, we introduce an $\mathsf{MVBA}$ with adaptive security, and $\widetilde{O}(\ell n + \lambda n^2)$ communication, exclusively leveraging conventional hash functions. Our new $\mathsf{MVBA}$ achieves nearly optimal communication, devoid of heavy operations, surpassing both threshold signature-based schemes and the hash-based scheme in many practical settings, as demonstrated in our experiments. For example, in scenarios with a network size of $n = 201$ and an input size of $1.75$ MB, our $\mathsf{MVBA}$ exhibits a latency that is 81\% lower than that of the existing hash-based $\mathsf{MVBA}$ and 47\% lower than the threshold signature-based $\mathsf{MVBA}$. Our new construction also achieves optimal parameters in other metrics such as $O(1)$ rounds and $O(n^2)$ message complexity, except with a sub-optimal resilience, tolerating up to $20\%$ Byzantine corruptions (instead of $33\%$). Given its practical performance advantages, our new hash-based $\mathsf{MVBA}$ naturally leads to better asynchronous distributed protocols, by simply plugging it into existing frameworks.
Last updated:  2024-03-21
The Security of SHA2 under the Differential Fault Characteristic of Boolean Functions
Weiqiong Cao, Hua Chen, Hongsong Shi, Haoyuan Li, Jian Wang, and Jingyi Feng
SHA2 has been widely adopted across various traditional public-key cryptosystems, post-quantum cryptography, personal identification, and network communication protocols, etc. Hence, ensuring the robust security of SHA2 is of critical importance. There have been several differential fault attacks based on random word faults targeting SHA1 and SHACAL-2. However, extending such random word-based fault attacks to SHA2 proves significantly more difficult due to the heightened complexity of the boolean functions in SHA2. In this paper, assuming random word faults, we find some distinctive differential properties within the boolean functions in SHA2. Leveraging these findings, we propose a new differential fault attack methodology that can be effectively utilized to recover the final message block and its corresponding initial vector in SHA2, forge HMAC-SHA2 messages, extract the key of SHACAL-2, and extend our analysis to similar algorithm like SM3. We validate the effectiveness of these attacks through rigorous simulations and theoretical deductions, revealing that they indeed pose substantial threats to the security of SHA2. In our simulation-based experiments, our approach necessitates guessing $T$ bits within a register, with $T$ being no more than $5$ at most, and having a approximate $95\%$ (for SHA512) probability of guessing just $1$ bit. Moreover, upon implementing a consecutive series of 15 fault injections, the success probability for recovering one register (excluding the guessed bits) approaches $100\%$. Ultimately, approximately 928 faulty outputs based on random word faults are required to carry out the attack successfully.
Last updated:  2024-03-24
Large Language Models for Blockchain Security: A Systematic Literature Review
Zheyuan He, Zihao Li, and Sen Yang
Large Language Models (LLMs) have emerged as powerful tools in various domains involving blockchain security (BS). Several recent studies are exploring LLMs applied to BS. However, there remains a gap in our understanding regarding the full scope of applications, impacts, and potential constraints of LLMs on blockchain security. To fill this gap, we conduct a literature review on LLM4BS. As the first review of LLM's application on blockchain security, our study aims to comprehensively analyze existing research and elucidate how LLMs contribute to enhancing the security of blockchain systems. Through a thorough examination of scholarly works, we delve into the integration of LLMs into various aspects of blockchain security. We explore the mechanisms through which LLMs can bolster blockchain security, including their applications in smart contract auditing, identity verification, anomaly detection, vulnerable repair, and so on. Furthermore, we critically assess the challenges and limitations associated with leveraging LLMs for blockchain security, considering factors such as scalability, privacy concerns, and adversarial attacks. Our review sheds light on the opportunities and potential risks inherent in this convergence, providing valuable insights for researchers, practitioners, and policymakers alike.
Last updated:  2024-03-21
OPSA: Efficient and Verifiable One-Pass Secure Aggregation with TEE for Federated Learning
Zhangshuang Guan, Yulin Zhao, Zhiguo Wan, and Jinsong Han
In federated learning, secure aggregation (SA) protocols like Flamingo (S\&P'23) and LERNA (ASIACRYPT'23) have achieved efficient multi-round SA in the malicious model. However, each round of their aggregation requires at least three client-server round-trip communications and lacks support for aggregation result verification. Verifiable SA schemes, such as VerSA (TDSC'21) and Eltaras et al.(TIFS'23), provide verifiable aggregation results under the security assumption that the server does not collude with any user. Nonetheless, these schemes incur high communication costs and lack support for efficient multi-round aggregation. Executing SA entirely within Trusted Execution Environment (TEE), as desined in SEAR (TDSC'22), guarantees both privacy and verifiable aggregation. However, the limited physical memory within TEE poses a significant computational bottleneck, particularly when aggregating large models or handling numerous clients. In this work, we introduce OPSA, a multi-round one-pass secure aggregation framework based on TEE to achieve efficient communication, streamlined computation and verifiable aggregation all at once. OPSA employs a new strategy of revealing shared keys in TEE and instantiates two types of masking schemes. Furthermore, a result verification module is designed to be compatible with any type of SA protocol instantiated under the OPSA framework with weaker security assumptions. Compared with the state-of-the-art schemes, OPSA achieves a 2$\sim$10$\times$ speedup in multi-round aggregation while also supporting result verification simultaneously. OPSA is more friendly to scenarios with high network latency and large-scale model aggregation.
Last updated:  2024-03-21
CheckOut: User-Controlled Anonymization for Customer Loyalty Programs
Matthew Gregoire, Rachel Thomas, and Saba Eskandarian
To resist the regimes of ubiquitous surveillance imposed upon us in every facet of modern life, we need technological tools that subvert surveillance systems. Unfortunately, while cryptographic tools frequently demonstrate how we can construct systems that safeguard user privacy, there is limited motivation for corporate entities engaged in surveillance to adopt these tools, as they often clash with profit incentives. This paper demonstrates how, in one particular aspect of everyday life -- customer loyalty programs -- users can subvert surveillance and attain anonymity, without necessitating any cooperation or modification in the behavior of their surveillors. We present the CheckOut system, which allows users to coordinate large anonymity sets of shoppers to hide the identity and purchasing habits of each particular user in the crowd. CheckOut scales up and systematizes past efforts to subvert loyalty surveillance, which have been primarily ad-hoc and manual affairs where customers physically swap loyalty cards to mask their real identities. CheckOut allows increased scale while ensuring that the necessary computing infrastructure does not itself become a new centralized point of privacy failure. Of particular importance to our scheme is a protocol for loyalty programs that offer reward points, where we demonstrate how CheckOut can assist users in paying each other back for loyalty points accrued while using each others' loyalty accounts. We present two different mechanisms to facilitate redistributing rewards points, offering trade-offs in functionality, performance, and security.
Last updated:  2024-03-25
Accumulation without Homomorphism
Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang
Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions. In this paper, we answer this question affirmatively by constructing an accumulation scheme from *non-homomorphic* vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors. Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such *bounded-depth* accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.
Last updated:  2024-03-25
Extremely Simple (Almost) Fail-Stop ECDSA Signatures
Mario Yaksetig
Fail-stop signatures are digital signatures that allow a signer to prove that a specific forged signature is indeed a forgery. After such a proof is published, the system can be stopped. We introduce a new simple ECDSA fail-stop signature scheme. Our proposal is based on the minimal assumption that an adversary with a quantum computer is not able to break the (second) preimage resistance of a cryptographically-secure hash function. Our scheme is as efficient as traditional ECDSA, does not limit the number of signatures that a signer can produce, and relies on minimal security assumptions. Using our construction, the signer has minimal computational overhead in the signature producing phase and produces a signature indistinguishable from a 'regular' ECDSA signature.
Last updated:  2024-03-20
Sailfish: Towards Improving Latency of DAG-based BFT
Nibesh Shrestha, Aniket Kate, and Kartik Nayak
Existing DAG-based BFT protocols exhibit long latency to commit decisions. The primary reason for such a long latency is having a leader every 2 or more “rounds”. Even under honest leaders, these protocols require two or more reliable broadcast (RBC) instances to commit the proposal submitted by the leader (leader vertex), and additional RBCs to commit other proposals (non-leader vertices). In this work, we present Sailfish, the first DAG-based BFT that supports a leader vertex in each round. Under honest leaders, Sailfish maintains a commit latency of one RBC round plus $1\delta$ to commit the leader vertex (where $\delta$ is the actual transmission latency of a message) and only an additional RBC round to commit non-leader vertices.
Last updated:  2024-03-20
Knot-based Key Exchange protocol
Silvia Sconza and Arno Wildi
We propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action. In our proposal, the semigroup is the set of oriented knots in $\mathbb{S}^3$ with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key starting from the same knot represented in two different ways. In particular, we use finite type invariants. The security of the protocol is guaranteed by the hardness of decomposing knots in the semigroup.
Last updated:  2024-03-20
Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, and Damien Vergnaud
Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (instead of quadratic in Mohassel and Franklin's work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of designing multi-party protocols for privacy-preserving operations on private sets, like private disjointness test or private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variant which always returns a correct result.
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.