About: Leftover hash lemma

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Leftover hash lemma Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatProbabilityTheorems, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLeftover_hash_lemma&invfp=IFP_OFF&sas=SAME_AS_OFF

The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Imagine that you have a secret key X that has n uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn the values of some t < n bits of that key, but you do not know which t bits. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of about n − t bits, over which the adversary has almost no knowledge. Since the adversary knows all but n − t bits, this is almost optimal.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 yago:WikicatProbabilityTheorems
rdfs:label	Leftover hash lemma (en)
rdfs:comment	The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Imagine that you have a secret key X that has n uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn the values of some t < n bits of that key, but you do not know which t bits. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of about n − t bits, over which the adversary has almost no knowledge. Since the adversary knows all but n − t bits, this is almost optimal. (en)
dcterms:subject	Probability theorems Theory of cryptography
Wikipage page ID	7006101 (xsd:integer)
Wikipage revision ID	947153268 (xsd:integer)
Link from a Wikipage to another Wikipage	Probability theorems Information-theoretic security Cryptography Rényi entropy Optimal Russell Impagliazzo Statistical distance Quantum key distribution Min-entropy Leonid Levin Key (cryptography) Hash function K-independent hashing Almost all Discrete uniform distribution Lemma (mathematics) Randomness extractor Random variable Adversary (cryptography) Theory of cryptography Bit Michael Luby Universal hashing Shannon entropy
Link from a Wikipage to an external page	http://portal.acm.org/citation.cfm%3Fcoll=GUIDE&dl=GUIDE&id=312213 http://portal.acm.org/citation.cfm%3Fcoll=GUIDE&dl=GUIDE&id=45477 http://ieeexplore.ieee.org/xpls/abs_all.jsp%3Fisnumber=10153&arnumber=476316&type=ref
sameAs	Leftover hash lemma Leftover hash lemma Leftover hash lemma Leftover hash lemma
dbp:wikiPageUsesTemplate	dbt:Math dbt:Mvar dbt:Reflist
has abstract	The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Imagine that you have a secret key X that has n uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn the values of some t < n bits of that key, but you do not know which t bits. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of about n − t bits, over which the adversary has almost no knowledge. Since the adversary knows all but n − t bits, this is almost optimal. More precisely, the leftover hash lemma tells us that we can extract a length asymptotic to (the min-entropy of X) bits from a random variable X that are almost uniformly distributed. In other words, an adversary who has some partial knowledge about X, will have almost no knowledge about the extracted value. That is why this is also called privacy amplification (see privacy amplification section in the article Quantum key distribution). Randomness extractors achieve the same result, but use (normally) less randomness. Let X be a random variable over and let . Let be a 2-universal hash function. If then for S uniform over and independent of X, we have: where U is uniform over and independent of S. is the min-entropy of X, which measures the amount of randomness X has. The min-entropy is always less than or equal to the Shannon entropy. Note that is the probability of correctly guessing X. (The best guess is to guess the most probable value.) Therefore, the min-entropy measures how difficult it is to guess X. is a statistical distance between X and Y. (en)
prov:wasDerivedFrom	wikipedia-en:Leftover_hash_lemma?oldid=947153268&ns=0
page length (characters) of wiki page	4677 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Leftover_hash_lemma
is Link from a Wikipage to another Wikipage of	Information-theoretic security List of lemmas ♯P Types of physical unclonable function Catalog of articles in probability theory Leftover hash-lemma Privacy amplification
is Wikipage redirect of	Leftover hash-lemma Privacy amplification
is foaf:primaryTopic of	wikipedia-en:Leftover_hash_lemma

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 51 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software