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

Leakage-Resilient Secret Sharing with Constant Share Size

Ivan Tjuawinata, Chaoping Xing

We consider the leakage resilience of AG code-based ramp secret sharing schemes extending the leakage resilience of linear threshold secret sharing schemes over prime fields done by Benhamouda et al. Since there is not any explicit efficient construction of AG codes over prime fields, we consider constructions over prime fields with the help of concatenation method and those over field extensions. Extending the Fourier analysis done by Benhamouda et al., concatenated algebraic geometric codes over prime fields do produce some nice leakage-resilient secret sharing schemes. One natural and curious question is whether AG codes over extension fields produce better leakage-resilient secret sharing schemes than the construction based on concatenated AG codes. Such construction provides several advantages compared to the construction over prime fields using concatenation method. First, AG codes over extension fields give secret sharing schemes with smaller reconstruction for a fixed privacy parameter t. Second, concatenated AG codes do not enjoy strong multiplicity and hence they are not applicable to secure MPC schemes. It is also confirmed that indeed AG codes over extension fields have stronger leakage-resilience under some reasonable assumptions. These three advantages strongly motivate the study of secret sharing schemes from AG codes over extension fields. The current paper has two main contributions: 1, we obtain leakage-resilient secret sharing schemes with constant share sizes and unbounded numbers of players. Like Shamir secret scheme, our schemes enjoy multiplicity and hence can be applied to MPC. 2, via a sophisticated Fourier Analysis, we analyze the leakage-resilience of secret sharing schemes from codes over extension fields. This is of its own theoretical interest independent of its application to secret sharing schemes from algebraic geometric codes over extension fields.

arXiv:2105.03074•May 7, 2021•1 citation

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

Constructing Locally Leakage-Resilient Linear Secret-Sharing Schemes

Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad +1 more

Lecture notes in computer science•Jan 1, 2021•18 citations

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•0 citations
We consider the leakage resilience of AG code-based ramp secret sharing schemes extending the leakage resilience of linear threshold secret sharing schemes over prime fields done by Benhamouda et al. Since there is not any explicit efficient construction of AG codes over prime fields, we consider constructions over prime fields with the help of concatenation method and those over field extensions. Extending the Fourier analysis done by Benhamouda et al., concatenated algebraic geometric codes over prime fields do produce some nice leakage-resilient secret sharing schemes. One natural and curious question is whether AG codes over extension fields produce better leakage-resilient secret sharing schemes than the construction based on concatenated AG codes. Such construction provides several advantages compared to the construction over prime fields using concatenation method. First, AG codes over extension fields give secret sharing schemes with smaller reconstruction for a fixed privacy parameter t. Second, concatenated AG codes do not enjoy strong multiplicity and hence they are not applicable to secure MPC schemes. It is also confirmed that indeed AG codes over extension fields have stronger leakage-resilience under some reasonable assumptions. These three advantages strongly motivate the study of secret sharing schemes from AG codes over extension fields. The current paper has two main contributions: 1, we obtain leakage-resilient secret sharing schemes with constant share sizes and unbounded numbers of players. Like Shamir secret scheme, our schemes enjoy multiplicity and hence can be applied to MPC. 2, via a sophisticated Fourier Analysis, we analyze the leakage-resilience of secret sharing schemes from codes over extension fields. This is of its own theoretical interest independent of its application to secret sharing schemes from algebraic geometric codes over extension fields.
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.