Quantum-proof multi-source randomness extractors in the Markov model
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916781349666816 |
|---|---|
| author | Arnon, Rotem Portmann, Christopher Scholz, Volkher B. |
| author_facet | Arnon, Rotem Portmann, Christopher Scholz, Volkher B. |
| contents | Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1510_06743 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Quantum-proof multi-source randomness extractors in the Markov model Arnon, Rotem Portmann, Christopher Scholz, Volkher B. Quantum Physics Computational Complexity Cryptography and Security Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown. |
| title | Quantum-proof multi-source randomness extractors in the Markov model |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/1510.06743 |