Adaptive versus non-adaptive strategies in the quantum setting
with applications

D 2016

Adaptive versus non-adaptive strategies in the quantum setting with applications

DUPONT DUPUIS, Frédéric; Serge FEHR; Philippe LAMONTAGNE a Louis SALVAIL

Základní údaje

Originální název

Adaptive versus non-adaptive strategies in the quantum setting with applications

Autoři

DUPONT DUPUIS, Frédéric; Serge FEHR; Philippe LAMONTAGNE a Louis SALVAIL

Vydání

Santa Barbara, CA, Proceedings of CRYPTO 2016, od s. 33-59, 27 s. 2016

Nakladatel

Springer Berlin Heidelberg

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00088206

Organizační jednotka

Fakulta informatiky

ISBN

978-3-662-53014-6

ISSN

DOI

https://doi.org/10.1007/978-3-662-53015-3_2

UT WoS

000416105000002

EID Scopus

2-s2.0-84979587358

Klíčová slova anglicky

quantum cryptography

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 5. 2020 19:27, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We prove a general relation between adaptive and non-adaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its “information content”. Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to non-adaptive attacks. We demonstrate the usefulness of this methodology with two examples. The first is a quantum bit commitment scheme based on 1-bit cut-and-choose. Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for two-party computation, this implies the universality of 1-bit cut-and-choose, and thus solves the main open problem of [9]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al. It was originally suggested as an unconditionally secure scheme, back when this was thought to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model. In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a non-adaptive version, which can be done by means of known techniques, and applying our main result.

Návaznosti

GAP202/12/1142, projekt VaV

Název: Slabé zdroje entanglementu a náhodnosti

Investor: Grantová agentura ČR, Weak sources of entanglement and randomness

Citovat

DUPONT DUPUIS, Frédéric; Serge FEHR; Philippe LAMONTAGNE a Louis SALVAIL. Adaptive versus non-adaptive strategies in the quantum setting with applications. Online. In Robshaw, Matthew and Katz, Jonathan. Proceedings of CRYPTO 2016. Santa Barbara, CA: Springer Berlin Heidelberg, 2016, s. 33-59. ISBN 978-3-662-53014-6. Dostupné z: https://doi.org/10.1007/978-3-662-53015-3_2.

@inproceedings{1355997,
   author = {Dupont Dupuis, Frédéric and Fehr, Serge and Lamontagne, Philippe and Salvail, Louis},
   address = {Santa Barbara, CA},
   booktitle = {Proceedings of CRYPTO 2016},
   doi = {https://doi.org/10.1007/978-3-662-53015-3_2},
   editor = {Robshaw, Matthew and Katz, Jonathan},
   keywords = {quantum cryptography},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Santa Barbara, CA},
   isbn = {978-3-662-53014-6},
   pages = {33-59},
   publisher = {Springer Berlin Heidelberg},
   title = {Adaptive versus non-adaptive strategies in the quantum setting with applications},
   year = {2016}
}

TY  - CONF
ID  - 1355997
AU  - Dupont Dupuis, Frédéric - Fehr, Serge - Lamontagne, Philippe - Salvail, Louis
PY  - 2016
TI  - Adaptive versus non-adaptive strategies in the quantum setting with applications
PB  - Springer Berlin Heidelberg
CY  - Santa Barbara, CA
SN  - 9783662530146
KW  - quantum cryptography
N2  - We prove a general relation between adaptive and non-adaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its “information content”. Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to non-adaptive attacks. We demonstrate the usefulness of this methodology with two examples. The first is a quantum bit commitment scheme based on 1-bit cut-and-choose. Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for two-party computation, this implies the universality of 1-bit cut-and-choose, and thus solves the main open problem of [9]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al. It was originally suggested as an unconditionally secure scheme, back when this was thought to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model. In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a non-adaptive version, which can be done by means of known techniques, and applying our main result.
ER  -

DUPONT DUPUIS, Frédéric; Serge FEHR; Philippe LAMONTAGNE a Louis SALVAIL. Adaptive versus non-adaptive strategies in the quantum setting with applications. Online. In Robshaw, Matthew and Katz, Jonathan. \textit{Proceedings of CRYPTO 2016}. Santa Barbara, CA: Springer Berlin Heidelberg, 2016, s.~33-59. ISBN~978-3-662-53014-6. Dostupné z: https://doi.org/10.1007/978-3-662-53015-3\_{}2.

Přehled o publikaci