Two-source extractors secure against quantum adversaries

Roy Kasher; Julia Kempe

doi:10.1007/978-3-642-15369-3_49

Two-source extractors secure against quantum adversaries

Roy Kasher, Julia Kempe

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [5] two-source inner product extractor and its multi-bit variant by Dodis et al. [9]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages	656-669
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-15369-3_49
State	Published - 2010
Event	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain Duration: Sep 1 2010 → Sep 3 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6302 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Country/Territory	Spain
City	Barcelona
Period	9/1/10 → 9/3/10

Keywords

Extractors
Quantum Information

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-15369-3_49

Cite this

Kasher, R., & Kempe, J. (2010). Two-source extractors secure against quantum adversaries. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings (pp. 656-669). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS). https://doi.org/10.1007/978-3-642-15369-3_49

Two-source extractors secure against quantum adversaries. / Kasher, Roy; Kempe, Julia.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 656-669 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kasher, R & Kempe, J 2010, Two-source extractors secure against quantum adversaries. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6302 LNCS, pp. 656-669, 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, Spain, 9/1/10. https://doi.org/10.1007/978-3-642-15369-3_49

Kasher R, Kempe J. Two-source extractors secure against quantum adversaries. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. p. 656-669. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15369-3_49

Kasher, Roy ; Kempe, Julia. / Two-source extractors secure against quantum adversaries. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. 2010. pp. 656-669 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d23c7f38023a4f4d84b5623465cff616,

title = "Two-source extractors secure against quantum adversaries",

abstract = "We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [5] two-source inner product extractor and its multi-bit variant by Dodis et al. [9]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.",

keywords = "Extractors, Quantum Information",

author = "Roy Kasher and Julia Kempe",

year = "2010",

doi = "10.1007/978-3-642-15369-3_49",

language = "English (US)",

isbn = "3642153682",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "656--669",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 ; Conference date: 01-09-2010 Through 03-09-2010",

}

TY - GEN

T1 - Two-source extractors secure against quantum adversaries

AU - Kasher, Roy

AU - Kempe, Julia

PY - 2010

Y1 - 2010

N2 - We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [5] two-source inner product extractor and its multi-bit variant by Dodis et al. [9]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.

AB - We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [5] two-source inner product extractor and its multi-bit variant by Dodis et al. [9]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.

KW - Extractors

KW - Quantum Information

UR - http://www.scopus.com/inward/record.url?scp=78149293231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149293231&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15369-3_49

DO - 10.1007/978-3-642-15369-3_49

M3 - Conference contribution

AN - SCOPUS:78149293231

SN - 3642153682

SN - 9783642153686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 656

EP - 669

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010

Y2 - 1 September 2010 through 3 September 2010

ER -

Two-source extractors secure against quantum adversaries

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this