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

IEEE Transactions on Information Theory

Robust Fuzzy Extractors and Authenticated Key Agreement From Close Secrets

Yevgeniy Dodis, Bhavana Kanukurthi, Jonathan I. Katz, Leonid Reyzin, Adam Smith

Published Aug 14, 2012• 99 citations
Publisher

Abstract

Consider two parties holding samples from correlated distributions$W$and$W^{\prime}$, respectively, where these samples are within distance$t$of each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret key$R$by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret${\ssr SK}_{\ssr Ext}$that they can use to generate a sequence of session keys$\{R_{j}\}$using multiple pairs$\{(W_{j}, W^{\prime}_{j})\}$. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects.The best prior solution for the keyless case with no errors (i.e.,$t=0$) requires the min-entropy of$W$to exceed$2n/3$, where$n$is the bit length of$W$. Our solution applies whenever the min-entropy of$W$exceeds the minimal threshold$n/2$, and yields a longer key.

DOI
10.1109/tit.2012.2200290

Related papers

Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets.

Yevgeniy Dodis, Bhavana Kanukurthi, Jonathan I. Katz +2 more

Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {Rj} using multiple pairs {(Wj, W ′ j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors. Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t = 0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t> 0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.

•Jan 1, 2010•2 citations

Key Agreement from Close Secrets over Unsecured Channels.

Bhavana Kanukurthi, Leonid Reyzin

We consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers. Our protocol can be seen as an interactive version of robust fuzzy extractors (Boyen et al., Eurocrypt 2005, Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.

•Jan 1, 2008•0 citations

Non-Malleable Extractors and Symmetric Key Cryptography from Weak Secrets.

Yevgeniy Dodis, Daniel Wichs

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetrickey primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n 2, and require poor parameters even when n 2 < k ≪ n. On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [RW03], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing “non-malleable” seeded randomness extractors — if an attacker sees a random seed X and comes up with an arbitrarily related seed X ′, then we bound the relationship between R = Ext(W;X) and R ′ = Ext(W;X ′). We also extend our two-round key agreement protocol to the “fuzzy ” setting, where Alice and Bob share “close ” (but not equal) secrets WA and WB, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.

•Jan 1, 2008•1 citation

Non-malleable extractors and symmetric key cryptography from weak secrets

Yevgeniy Dodis, Daniel Wichs

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•142 citations

A Bound For Multiparty Secret Key Agreement And Implications For A Problem Of Secure Computing

Himanshu Tyagi, Shun Watanabe

Abstract. We consider secret key agreement by multiple parties observ-ing correlated data and communicating interactively over an insecure communication channel. Our main contribution is a single-shot upper bound on the length of the secret keys that can be generated, with-out making any assumptions on the distribution of the underlying data. Heuristically, we bound the secret key length in terms of “how far ” is the joint distribution of the initial observations of the parties and the eaves-dropper from a distribution that renders the observations of the parties conditionally independent across some partition, when conditioned on the eavesdropper’s side information. The closeness of the two distribu-tions is measured in terms of the exponent of the probability of error of type II for a binary hypothesis testing problem, thus bringing out a structural connection between secret key agreement and binary hypoth-esis testing. When the underlying data consists of an independent and identically distributed sequence, an application of our bound recovers

•Dec 5, 2014•0 citations

New bounds on the information-theoretic key agreement of multiple terminals

Amin Gohari, Venkat Anantharam

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•14 citations
Consider two parties holding samples from correlated distributionsWWWandW′W^{\prime}W′, respectively, where these samples are within distancetttof each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret keyRRRby sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret\ssrSK\ssrExt{\ssr SK}_{\ssr Ext}\ssrSK\ssrExt​that they can use to generate a sequence of session keys{Rj}\{R_{j}\}{Rj​}using multiple pairs{(Wj,Wj′)}\{(W_{j}, W^{\prime}_{j})\}{(Wj​,Wj′​)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects.The best prior solution for the keyless case with no errors (i.e.,t=0t=0t=0) requires the min-entropy ofWWWto exceed2n/32n/32n/3, wherennnis the bit length ofWWW. Our solution applies whenever the min-entropy ofWWWexceeds the minimal thresholdn/2n/2n/2, and yields a longer key.
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {Rj} using multiple pairs {(Wj, W ′ j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors. Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t = 0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t> 0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.
We consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. Such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by Renner and Wolf (Eurocrypt 2004), although no protocol that runs in polynomial time was described. We propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers. Our protocol can be seen as an interactive version of robust fuzzy extractors (Boyen et al., Eurocrypt 2005, Dodis et al., Crypto 2006). While robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. In fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetrickey primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n 2, and require poor parameters even when n 2 < k ≪ n. On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [RW03], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing “non-malleable” seeded randomness extractors — if an attacker sees a random seed X and comes up with an arbitrarily related seed X ′, then we bound the relationship between R = Ext(W;X) and R ′ = Ext(W;X ′). We also extend our two-round key agreement protocol to the “fuzzy ” setting, where Alice and Bob share “close ” (but not equal) secrets WA and WB, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.
Abstract. We consider secret key agreement by multiple parties observ-ing correlated data and communicating interactively over an insecure communication channel. Our main contribution is a single-shot upper bound on the length of the secret keys that can be generated, with-out making any assumptions on the distribution of the underlying data. Heuristically, we bound the secret key length in terms of “how far ” is the joint distribution of the initial observations of the parties and the eaves-dropper from a distribution that renders the observations of the parties conditionally independent across some partition, when conditioned on the eavesdropper’s side information. The closeness of the two distribu-tions is measured in terms of the exponent of the probability of error of type II for a binary hypothesis testing problem, thus bringing out a structural connection between secret key agreement and binary hypoth-esis testing. When the underlying data consists of an independent and identically distributed sequence, an application of our bound recovers
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.