publications
publications by categories in reversed chronological order. generated by jekyll-scholar.
2025
- In SubmissionA Gaussian Leftover Hash Lemma for Modules over Number FieldsMartin R. Albrecht, Joël Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, and Ivy K. Y. Woo2025
Given a Gaussian matrix X, a Gaussian Leftover Hash Lemma (LHL) states that X ⋅v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over integers by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: ||v||/||X||. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-MSIS/k-MLWE) based on the hardness of SIS and LWE over modules (MSIS/MLWE) respectively, which was assumed without proof in prior works.
- ASIACRYPTA Simple IND-CCA Lattice-Based Threshold KEM from the BCHK+ TransformOleksandra Lapiha and Thomas PrestASIACRYPT, 2025
We present a simple IND-CCA lattice-based threshold KEM. At a high level, our design is based on the BCHK transform (Canetti et al., EUROCRYPT 2004), which we adapt to the lattice setting by combining it with the FO transform (Fujisaki and Okamoto, PKC 1999) in order to achieve decryption consistency. As for the BCHK transform, our construction requires a threshold identity-based encryption (TIBE) scheme with suitable properties. We build such an IBE by combining the ABB IBE (Agrawal, Boneh, Boyen, EUROCRYPT 2010) with recent advances in lattice threshold cryptography, such as the threshold-friendly signature Plover (Esgin et al., EUROCRYPT 2024) and a variant of the Threshold Raccoon scheme (Katsumata et al., CRYPTO 2024). The security proof of our scheme relies on a new assumption which we call the Coset-Hint-MLWE assumption, and which is a natural generalisation of the Hint-MLWE assumption (Kim et al., CRYPTO 2023). We prove the hardness of Coset-Hint-MLWE under standard assumptions. We believe this new assumption may be of independent interest. Unlike prior works on IND-CCA lattice-based threshold KEMs, our construction only relies on simple algorithmic tools and does not use heavy machinery such as multi-party computation or threshold fully homomorphic encryption.
- In SubmissionLeftover Hash Lemma(s) Over Cyclotomic RingsKatharina Boudgoust and Oleksandra LapihaCryptology ePrint Archive, 2025
In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially painful if one’s given setting does not fit exactly into prior studies. We argue that all prior approaches boil down to two different proof strategies, resulting in two main theorems. From there on, we are able to recover all previous flavours of seemingly independent LHLs as corollaries. Moreover, we showcase the power of our interpretation by providing new statements, covering mathematical settings not considered before. Our work further proves LHLs in the presence of leakage for both approaches and provides novel bounds for wide families of leakage functions.
- In SubmissionSelectively Blind Quantum ComputationAbbas Poshtvan, Oleksandra Lapiha, Mina Doosti, Dominik Leichtle, Luka Music, and Elham KashefiarXiv, 2025
Known protocols for secure delegation of quantum computations from a client to a server in an information theoretic setting require quantum communication. In this work, we investigate methods to reduce communication overhead. First, we establish an impossibility result by proving that server-side local processes cannot decrease quantum communication requirements of secure delegation protocols. We develop no-go results that prohibit such processes within an information theoretic framework. Second, we present a possibility result by introducing Selectively Blind Quantum Computing (SBQC), a novel functionality that allows the client to hide one among a known set of possible computations. We characterize how differences between computations in the protected set influence the number of qubits sent during our SBQC implementation, yielding a communication-optimal protocol. This approach reduces qubit communication drastically and demonstrates the trade-off between information leaked to the server and communication cost.
- ASIACRYPTPartial Lattice Trapdoors: How to Split Lattice Trapdoors, LiterallyMartin R. Albrecht, Russell W. F. Lai, Oleksandra Lapiha, and Ivy K. Y. WooASIACRYPT, 2025
Lattice trapdoor algorithms allow us to sample hard random lattices together with their trapdoors, given which short lattice vectors can be sampled efficiently. This enables a wide range of advanced cryptographic primitives. In this work, we ask: can we distribute lattice trapdoor algorithms non-interactively? We study a natural approach to sharing lattice trapdoors: splitting them into partial trapdoors for different lower-rank sublattices which allow the local sampling of short sublattice vectors. Given sufficiently many short sublattice vectors, these can then be combined to yield short vectors in the original lattice. Moreover, this process can be repeated an unbounded polynomial number of times without needing a party holding a full trapdoor to intervene. We further define one-wayness and indistinguishability properties for partial trapdoors. We establish that such objects exist that have non-trivial performance under standard assumptions. Specifically, we prove these properties for a simple construction from the κ-SIS and κ-LWE assumptions, which were previously shown to be implied by the plain SIS and LWE assumptions, respectively. The security proofs extend naturally to the ring or module settings under the respective analogues of these assumptions, which have been conjectured to admit similar reductions. Our partial trapdoors achieve non-trivial efficiency, with relevant parameters sublinear in the number of shareholders. Our construction is algebraic, without resorting to generic tools such as multiparty computation or fully homomorphic encryption. Consequently, a wide range of lattice-trapdoor-based primitives can be thresholdised non-interactively by simply substituting the trapdoor preimage sampling procedure with our partial analogue.
2024
- EUROCRYPTSLAP: Succinct Lattice-Based Polynomial Commitments from Standard AssumptionsMartin R. Albrecht, Giacomo Fenzi, Oleksandra Lapiha, and Ngoc Khanh NguyenIn Advances in Cryptology – EUROCRYPT, 2024
Recent works on lattice-based extractable polynomial commitments can be grouped into two classes: (i) non-interactive constructions that stem from the functional commitment by Albrecht, Cini, Lai, Malavolta and Thyagarajan (CRYPTO 2022), and (ii) lattice adaptations of the Bulletproofs protocol (S &P 2018). The former class enjoys security in the standard model, albeit a knowledge assumption is desired. In contrast, Bulletproof-like protocols can be made secure under falsifiable assumptions, but due to technical limitations regarding subtractive sets, they only offer inverse-polynomial soundness error. This issue becomes particularly problematic when transforming these protocols to the non-interactive setting using the Fiat-Shamir paradigm.
2021
- PreprintComparing Lattice Families for Bounded Distance Decoding near Minkowski’s Bound.Oleksandra LapihaCryptology ePrint Archive, 2021
In this report we analyse and compare the complexity of solving the Bounded Distance Decoding problem in two families for discrete logarithm lattices. Our algorithm uses the internal structure of the lattice to decode an error close to Minkowski’s bound efficiently. This procedure can be used as a decryption algorithm of an encryption scheme, where the internal structure of the lattice serves as a secret key. In addition, one of these lattices was used in [1] to construct a family of one way functions. We present cryptanalysis of the mentioned scheme and we prove that the stated size of the keys is insufficient for a required security level.
- JMCThe Eleventh Power Residue SymbolMarc Joye, Oleksandra Lapiha, Ky Nguyen, and David NaccacheJournal of Mathematical Cryptology, 2021
This paper presents an efficient algorithm for computing 11th-power residue symbols in the cyclotomic field Q(\zeta_11) where \zeta_11 is a primitive 11th root of unity. It extends an earlier algorithm due to Caranay and Scheidler (Int. J. Number Theory, 2010) for the 7th-power residue symbol. The new algorithm finds applications in the implementation of certain cryptographic schemes.