I wonder how sound Trevisan's extractor can be against quantum side information. I checked many papers. And all of these papers were aiming to explain how sound Trevisan's Extractor is against quantum side information but they all have the same information; the papers include:

  1. what is an extractor?

  2. what is a strong extractor?

  3. what is the trevisan extractor?

  4. some entropy explanations(they are the same as for other extractor types)

and after that papers finish without explaining the reason for soundness against quantum side information

Can someone explain this to me briefly?

Best regards

  • $\begingroup$ You may want to read this: doi.org/10.1137/100813683 $\endgroup$
    – Patriot
    Mar 7, 2021 at 13:29
  • $\begingroup$ Do you primarily want to ask: "How is Trevisan's extractor sound in the presence of quantum side information?" $\endgroup$
    – Patriot
    Mar 7, 2021 at 13:48
  • $\begingroup$ yes this is my question $\endgroup$
    – quest
    Mar 7, 2021 at 18:53

1 Answer 1


In quantum key distribution communicators can bound the amount of information (quantum side channel entropy) that an eavesdropper can obtain about the transmitted key based on the fidelity of the transmissions. If an $n$-bit key has been transmitted and at most $n-m$ bits of information are available to an eavesdropper then a strong extractor (such as the Trevisan construction) can then used to produce an $m$-bit key about which the eavesdropper has essentially no information and which is therefore ideally suited as strong cryptographic key. This process is called privacy amplification by quantum key distribution practitioners.

UPDATE in response to query 7/3: Not all strong extractors can be proven resilient to quantum side-channel information. Also, an instance of an extractor must be chosen uniformly at random from a strong family. The advantage of the Trevisan extractor is that good extraction can be shown from a small family and so choosing an extractor from the family consumes less strong random information. In particular most families resilient to quantum information consume strong random seeds of length $O(n)$, but the Trevisan family consumes seeds of length $O((\log n)^3)$. The down side is that the computational overhead of the Trevisan family is markedly worse than its competitors.

It is possible that other extractors are resilient to quantum information, but we can prove this for the Trevisan construction. The ability to form this proof is largely because the construction is really $m$ independent 1-bit extractors. This means that significant information about the whole output can be used to deduce significant information about a single bit and so we only need to prove the resilience of an individual bit. This argument is very heuristic, a full technical argument is in appendix B of De et al.

  • $\begingroup$ thanks for your answers. But why is Trevisan's extractor specifically important. Don't we have other strong extractors other than Trevisan's extractor $\endgroup$
    – quest
    Mar 7, 2021 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.