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

Journal of Information Security and Applications

Novel improvements and extensions of the extractable results about (leakage-resilient) privacy schemes with imperfect randomness

Yanqing Yao, Zhoujun Li

Published Feb 21, 2025• 0 citations
Publisher
DOI
10.1016/j.jisa.2025.104008

Related papers

An Improvement Upon the Bounds for the Local Leakage Resilience of Shamir’s Secret Sharing Scheme

Dustin Kasser

Lecture notes in computer science•Dec 2, 2024•7 citations

Random Robust Secret Sharing with Perfect Privacy and its Applications

Mohammad Hassan Ameri, Jeremiah Blocki

•Sep 16, 2026•0 citations

Privacy with Imperfect Randomness

Yevgeniy Dodis, Yanqing Yao

We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: – Low levels of expressiveness generically imply strong impossibility results for both traditional and differential privacy. – Separability implies expressiveness; NON-separability is equivalent to “weak bit extraction”. – While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general “block sources”. As direct corollaries of these general results, we get the following corollaries: – Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. – First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back extremely quickly once the source becomes slightly more realistic (e.g., a realistic “block source”). – Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.

•Jan 1, 2014•0 citations

On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

Divesh Aggarwal, Eldon Chung, Maciej Obremski +1 more

Lecture notes in computer science•Jan 1, 2022•1 citation

Thinking Inside The Box: Privacy Against Stronger Adversaries

Eldon Chung

In this thesis, we study extensions of statistical cryptographic primitives. In particular we study leakage-resilient secret sharing, non-malleable extractors, and immunized ideal one-way functions. The thesis is divided into three main chapters. In the first chapter, we show that 2-out-of-2 leakage resilient (and also non-malleable) secret sharing requires randomness sources that are also extractable. This rules out the possibility of using min-entropic sources. In the second, we introduce collision-resistant seeded extractors and show that any seeded extractor can be made collision resistant at a small overhead in seed length. We then use it to give a two-source non-malleable extractor with entropy rate 0.81 in one source and polylogarithmic in the other. The non-malleable extractor lead to the first statistical privacy amplification protocol against memory tampering adversaries. In the final chapter, we study the hardness of the data structure variant of the 3SUM problem which is motivated by a recent construction to immunise random oracles against pre-processing adversaries. We give worst-case data structure hardness for the 3SUM problem matching known barriers in data structures for adaptive adversaries. We also give a slightly stronger lower bound in the case of non-adaptivity. Lastly, we give a novel result in the bit-probe setting.

arXiv:2406.16313•Jun 24, 2024•1 citation

Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model.

Joël Alwen, Yevgeniy Dodis, Daniel Wichs

We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of

•Jan 1, 2009•0 citations
We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: – Low levels of expressiveness generically imply strong impossibility results for both traditional and differential privacy. – Separability implies expressiveness; NON-separability is equivalent to “weak bit extraction”. – While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general “block sources”. As direct corollaries of these general results, we get the following corollaries: – Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. – First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back extremely quickly once the source becomes slightly more realistic (e.g., a realistic “block source”). – Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.
In this thesis, we study extensions of statistical cryptographic primitives. In particular we study leakage-resilient secret sharing, non-malleable extractors, and immunized ideal one-way functions. The thesis is divided into three main chapters. In the first chapter, we show that 2-out-of-2 leakage resilient (and also non-malleable) secret sharing requires randomness sources that are also extractable. This rules out the possibility of using min-entropic sources. In the second, we introduce collision-resistant seeded extractors and show that any seeded extractor can be made collision resistant at a small overhead in seed length. We then use it to give a two-source non-malleable extractor with entropy rate 0.81 in one source and polylogarithmic in the other. The non-malleable extractor lead to the first statistical privacy amplification protocol against memory tampering adversaries. In the final chapter, we study the hardness of the data structure variant of the 3SUM problem which is motivated by a recent construction to immunise random oracles against pre-processing adversaries. We give worst-case data structure hardness for the 3SUM problem matching known barriers in data structures for adaptive adversaries. We also give a slightly stronger lower bound in the case of non-adaptivity. Lastly, we give a novel result in the bit-probe setting.
We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of