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

Default journal

Key Extraction From General Nondiscrete Signals

Evgeny A. Verbitskiy, Pim Tuyls, Chibuzo Obi, Berry Schoenmakers, Boris Škorić

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

We address the problem of designing optimal schemes for the generation of secure crypto-\ngraphic keys from continuous noisy data. We argue that, contrary to the discrete case, a\nuniversal fuzzy extractor does not exist. This implies that in the continuous case, key ex-\ntraction schemes have to be designed for particular probability distributions. We extend the\nknown definitions of the correctness and security properties of fuzzy extractors. Our defini-\ntions apply to continuous as well as discrete variables.\nWe propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretisation, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise.\nFinally, we study the security implications of incomplete knowledge of the source's probability distribution P. We derive a bound on the min-entropy of the extracted key under the worst case assumption, where the attacker knows P exactly.

Related papers

Key Extraction From General Nondiscrete Signals

Evgeny A. Verbitskiy, Pim Tuyls, Chibuzo Obi +2 more

We address the problem of designing optimal schemes for the generation of secure cryptographic keys from continuous noisy data. We argue that, contrary to the discrete case, a universal fuzzy extractor does not exist. This implies that in the continuous case, key extraction schemes have to be designed for particular probability distributions. We extend the known definitions of the correctness and security properties of fuzzy extractors. Our definitions apply to continuous as well as discrete variables. We propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretization, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise. Finally, we study the security implications of incomplete knowledge of the source's probability distribution${\BBP }$. We derive a bound on the min-entropy of the extracted key under the worst-case assumption, where the attacker knows${\BBP }$exactly.

IEEE Transactions on Information Forensics and Security•Mar 30, 2010•48 citations

When Are Fuzzy Extractors Possible?

Benjamin W. Fuller, Leonid Reyzin, Adam Smith

Fuzzy extractors (Dodis et al., SIAM J. Computing 2008) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We quantify this property in a new notion called fuzzy min-entropy. We ask: is fuzzy min-entropy sufficient to build fuzzy extractors? We provide two answers for different settings. 1) If the construction is provided a description of the probability distribution W that defines the noisy source then fuzzy min-entropy is a sufficient condition for information-theoretic key extraction from W . 2) A more ambitious goal is to design a single extractor that works for all possible sources. This more ambitious goal is impossible: there is a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This is true in three settings: a) for standard fuzzy extractors, b) for fuzzy extractors that are allowed to sometimes be wrong, c) and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.

IEEE Transactions on Information Theory•Apr 1, 2020•25 citations

An efficient fuzzy extractor for limited noise

Boris Škorić, PT Tuyls

A fuzzy extractor is a security primitive that allows for reproducible extraction of an almost uniform key from a non-uniform noisy source. We analyze a fuzzy extractor scheme that uses universal hash functions for both information reconciliation and privacy amplification. This is a useful scheme when the number of error patterns likely to occur is limited, regardless of the error probabilities. We derive a sharp bound on the uniformity of the extracted key, making use of the concatenation property of universal hash functions and a recent tight formulation of the leftover hash lemma.

Dagstuhl Seminar Proceedings•Jan 1, 2010•8 citations

Reusable and robust fuzzy extractor for CRS-dependent sources

Yucheng Ma, Peisong Shen, Xue Tian +2 more

Abstract Fuzzy extractors allow for the extraction and reproduction of a nearly uniform string from a noisy and non-uniform source. Reusable and robust fuzzy extractors further require that the output string should remain pseudorandom under multiple extractions and any modification of public value should be detectable. Existing constructions of reusable and robust fuzzy extractors are all designed in the Common Reference String (CRS) model and work only for CRS-independent sources. In this work, we introduce a construction of reusable and robust fuzzy extractor for CRS-dependent sources. Our construction is built upon some well-studied cryptography, including a collision resistant hash function, a symmetric key encryption that keeps secure with respect to auxiliary input, a public key encryption and simulation-sound non-interactive zero-knowledge argument. We also present some instantiations of these primitives from Learning with Parity Noise (LPN) assumption and Short Integer Solution (SIS) assumption. These instantiations result in the first reusable and robust fuzzy extractor for CRS-dependent sources that can tolerate linear errors.

Cybersecurity•Jan 14, 2025•0 citations

Reusable Fuzzy Extractor from Isogeny-Based Assumptions

Yunhua Wen, Tianlong Jin, Wei Li

A fuzzy extractor is a foundational cryptographic component that enables the extraction of reproducible and uniformly random strings from sources with inherent noise, such as biometric traits. Reusable fuzzy extractor guarantees the security of multiple extractions from the same noisy source. In addition, although isogeny-based cryptography has become an important branch in post-quantum cryptography, the study of fuzzy extractors based on isogeny assumptions is still in its early stages and holds much room for improvement. In this paper, we give two reusable fuzzy extractor schemes derived from isogeny-based assumptions: one is based on the linear hidden shift assumption over group actions, while the other is built upon the group-action decisional Diffie–Hellman assumption within the isogeny framework. Both proposed constructions achieve post-quantum security and are capable of correcting a linear proportion of errors. They rely solely on fundamental cryptographic primitives, which ensure simplicity and efficiency. Additionally, the second construction is based on restricted effective group action, which is weaker than the effective group action used in the first construction, thereby offering greater practical applicability.

Symmetry•Jul 4, 2025•1 citation

Reusable Fuzzy Extractor Based on the LPN Assumption

Yiming Li, Shengli Liu, Dawu Gu +1 more

Abstract A fuzzy extractor derives uniformly random strings from noisy sources that are neither reliably reproducible nor uniformly random. The basic definition of fuzzy extractor was first formally introduced by Dodis et al. and has achieved various applications in cryptographic systems. However, it has been proved that a fuzzy extractor could become totally insecure when the same noisy random source is extracted multiple times. To solve this problem, the reusable fuzzy extractor is proposed. In this paper, we propose the first reusable fuzzy extractor based on the LPN assumption, which is efficient and resilient to linear fraction of errors. Furthermore, our construction serves as an alternative post-quantum reusable fuzzy extractor.

The Computer Journal•May 2, 2020•5 citations
We address the problem of designing optimal schemes for the generation of secure crypto-\ngraphic keys from continuous noisy data. We argue that, contrary to the discrete case, a\nuniversal fuzzy extractor does not exist. This implies that in the continuous case, key ex-\ntraction schemes have to be designed for particular probability distributions. We extend the\nknown definitions of the correctness and security properties of fuzzy extractors. Our defini-\ntions apply to continuous as well as discrete variables.\nWe propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretisation, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise.\nFinally, we study the security implications of incomplete knowledge of the source's probability distribution P. We derive a bound on the min-entropy of the extracted key under the worst case assumption, where the attacker knows P exactly.
We address the problem of designing optimal schemes for the generation of secure cryptographic keys from continuous noisy data. We argue that, contrary to the discrete case, a universal fuzzy extractor does not exist. This implies that in the continuous case, key extraction schemes have to be designed for particular probability distributions. We extend the known definitions of the correctness and security properties of fuzzy extractors. Our definitions apply to continuous as well as discrete variables. We propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretization, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise. Finally, we study the security implications of incomplete knowledge of the source's probability distribution${\BBP }$. We derive a bound on the min-entropy of the extracted key under the worst-case assumption, where the attacker knows${\BBP }$exactly.
Fuzzy extractors (Dodis et al., SIAM J. Computing 2008) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We quantify this property in a new notion called fuzzy min-entropy. We ask: is fuzzy min-entropy sufficient to build fuzzy extractors? We provide two answers for different settings. 1) If the construction is provided a description of the probability distribution W that defines the noisy source then fuzzy min-entropy is a sufficient condition for information-theoretic key extraction from W . 2) A more ambitious goal is to design a single extractor that works for all possible sources. This more ambitious goal is impossible: there is a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This is true in three settings: a) for standard fuzzy extractors, b) for fuzzy extractors that are allowed to sometimes be wrong, c) and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.
A fuzzy extractor is a security primitive that allows for reproducible extraction of an almost uniform key from a non-uniform noisy source. We analyze a fuzzy extractor scheme that uses universal hash functions for both information reconciliation and privacy amplification. This is a useful scheme when the number of error patterns likely to occur is limited, regardless of the error probabilities. We derive a sharp bound on the uniformity of the extracted key, making use of the concatenation property of universal hash functions and a recent tight formulation of the leftover hash lemma.
Abstract Fuzzy extractors allow for the extraction and reproduction of a nearly uniform string from a noisy and non-uniform source. Reusable and robust fuzzy extractors further require that the output string should remain pseudorandom under multiple extractions and any modification of public value should be detectable. Existing constructions of reusable and robust fuzzy extractors are all designed in the Common Reference String (CRS) model and work only for CRS-independent sources. In this work, we introduce a construction of reusable and robust fuzzy extractor for CRS-dependent sources. Our construction is built upon some well-studied cryptography, including a collision resistant hash function, a symmetric key encryption that keeps secure with respect to auxiliary input, a public key encryption and simulation-sound non-interactive zero-knowledge argument. We also present some instantiations of these primitives from Learning with Parity Noise (LPN) assumption and Short Integer Solution (SIS) assumption. These instantiations result in the first reusable and robust fuzzy extractor for CRS-dependent sources that can tolerate linear errors.
A fuzzy extractor is a foundational cryptographic component that enables the extraction of reproducible and uniformly random strings from sources with inherent noise, such as biometric traits. Reusable fuzzy extractor guarantees the security of multiple extractions from the same noisy source. In addition, although isogeny-based cryptography has become an important branch in post-quantum cryptography, the study of fuzzy extractors based on isogeny assumptions is still in its early stages and holds much room for improvement. In this paper, we give two reusable fuzzy extractor schemes derived from isogeny-based assumptions: one is based on the linear hidden shift assumption over group actions, while the other is built upon the group-action decisional Diffie–Hellman assumption within the isogeny framework. Both proposed constructions achieve post-quantum security and are capable of correcting a linear proportion of errors. They rely solely on fundamental cryptographic primitives, which ensure simplicity and efficiency. Additionally, the second construction is based on restricted effective group action, which is weaker than the effective group action used in the first construction, thereby offering greater practical applicability.
Abstract A fuzzy extractor derives uniformly random strings from noisy sources that are neither reliably reproducible nor uniformly random. The basic definition of fuzzy extractor was first formally introduced by Dodis et al. and has achieved various applications in cryptographic systems. However, it has been proved that a fuzzy extractor could become totally insecure when the same noisy random source is extracted multiple times. To solve this problem, the reusable fuzzy extractor is proposed. In this paper, we propose the first reusable fuzzy extractor based on the LPN assumption, which is efficient and resilient to linear fraction of errors. Furthermore, our construction serves as an alternative post-quantum reusable fuzzy extractor.