Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence

Hiroki Okada, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi

Published Jan 1, 2023• 0 citations
Publisher
DOI
10.1007/978-3-031-33488-7_26

Related papers

Discrete Gaussians Modulo Sub-Lattices: New Leftover Hash Lemmas for Discrete Gaussians

Haoxiang Jin, Feng-Hao Liu, Zhedong Wang +1 more

Lecture notes in computer science•Jan 1, 2025•4 citations

Discrete Gaussian Leftover Hash Lemma over Infinite Domains

Shweta Agrawal, Craig Gentry, Shai Halevi +1 more

Lecture notes in computer science•Jan 1, 2013•58 citations

Quantum Rényi Divergence

Marco Tomamichel

SpringerBriefs in mathematical physics•Oct 8, 2015•1 citation

Improved Robustness and Versatility of Lattice-Based Cryptography

Huijing Gong

Current public key cryptosystems that are based on the hardness of integer factorization and discrete logarithm are insecure in the presence of large-scale quantum computers. Much effort has been devoted to replacing the quantum-insecure cryptosystems with newly developed "post-quantum" cryptosystem candidates, conjectured to be secure against quantum attack. Lattice-based cryptography has been widely recognized as a prominent candidate for practical post-quantum security.This dissertation improves the robustness and versatility of lattice-based cryptography through the following three contributions: 1. Chapter 3 introduces a constant-round protocol for unauthenticated group key exchange (i.e., with security against a passive eavesdropper). Group key exchange protocols allow a set of N parties to agree on a shared, secret key by communicating over a public network. Our protocol is based on the hardness of a lattice problem, which hence yields (plausible) post-quantum security. 2. In Chapter 4, we propose a framework for cryptanalysis of lattice-based schemes when certain types of information about the secret are leaked. Our framework generalizes the primal lattice reduction attack. The generalization allows for integrating the leaked information progressively before running a final lattice reduction step. Our framework can estimate the amount of security loss caused by the leaked information, and perform lattice reduction attacks with leaked information when computationally feasible. 3. Chapter 5 introduces an approach towards a ring analogue of the Leftover Hash Lemma (LHL). The LHL is a mathematical tool often used in the analysis of various lattice-based cryptosystems, as well as their leakage-resilient counterparts. However, it does not hold in the ring setting, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt '13) proved a "regularity lemma," which is used in the ring setting instead of the LHL; however, this applies only for centered, spherical Gaussian inputs, while the LHL applies when the input is drawn from any high min-entropy distribution. Our approach generalizes the "regularity lemma" of Lyubashevsky et al. to certain conditional distributions. A number of Ring-Learning with Errors based cryptosystems can achieve certain leakage resilience properties using our results.

•Jan 1, 2021•0 citations

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations

Some Properties of the kth-partial Rényi Entropy

Yun Cheng, Yuan Li

International Journal of Theoretical Physics•Apr 7, 2014•1 citation
Current public key cryptosystems that are based on the hardness of integer factorization and discrete logarithm are insecure in the presence of large-scale quantum computers. Much effort has been devoted to replacing the quantum-insecure cryptosystems with newly developed "post-quantum" cryptosystem candidates, conjectured to be secure against quantum attack. Lattice-based cryptography has been widely recognized as a prominent candidate for practical post-quantum security.This dissertation improves the robustness and versatility of lattice-based cryptography through the following three contributions: 1. Chapter 3 introduces a constant-round protocol for unauthenticated group key exchange (i.e., with security against a passive eavesdropper). Group key exchange protocols allow a set of N parties to agree on a shared, secret key by communicating over a public network. Our protocol is based on the hardness of a lattice problem, which hence yields (plausible) post-quantum security. 2. In Chapter 4, we propose a framework for cryptanalysis of lattice-based schemes when certain types of information about the secret are leaked. Our framework generalizes the primal lattice reduction attack. The generalization allows for integrating the leaked information progressively before running a final lattice reduction step. Our framework can estimate the amount of security loss caused by the leaked information, and perform lattice reduction attacks with leaked information when computationally feasible. 3. Chapter 5 introduces an approach towards a ring analogue of the Leftover Hash Lemma (LHL). The LHL is a mathematical tool often used in the analysis of various lattice-based cryptosystems, as well as their leakage-resilient counterparts. However, it does not hold in the ring setting, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt '13) proved a "regularity lemma," which is used in the ring setting instead of the LHL; however, this applies only for centered, spherical Gaussian inputs, while the LHL applies when the input is drawn from any high min-entropy distribution. Our approach generalizes the "regularity lemma" of Lyubashevsky et al. to certain conditional distributions. A number of Ring-Learning with Errors based cryptosystems can achieve certain leakage resilience properties using our results.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.