5 Search Results for "Salvail, Louis"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.7
Quantum Protocols for Rabin Oblivious Transfer

Authors: Erika Andersson, Akshay Bansal, James T. Peat, Jamie Sikora, and Jiawei Wu

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Rabin oblivious transfer is the cryptographic task where Alice wishes to receive a bit from Bob but it may get lost with probability 1/2. In this work, we provide protocol designs which yield quantum protocols with improved security. Moreover, we provide a constant lower bound on any quantum protocol for Rabin oblivious transfer. To quantify the security of this task with asymmetric cheating definitions, we introduce the notion of cheating advantage which may be of independent interest in the study of other asymmetric cryptographic primitives.
Cite as

Erika Andersson, Akshay Bansal, James T. Peat, Jamie Sikora, and Jiawei Wu. Quantum Protocols for Rabin Oblivious Transfer. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andersson_et_al:LIPIcs.FSTTCS.2025.7,
  author =	{Andersson, Erika and Bansal, Akshay and Peat, James T. and Sikora, Jamie and Wu, Jiawei},
  title =	{{Quantum Protocols for Rabin Oblivious Transfer}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.7},
  URN =		{urn:nbn:de:0030-drops-250866},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.7},
  annote =	{Keywords: quantum cryptography, oblivious transfer, information-theoretic security}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.2
Powerful Primitives in the Bounded Quantum Storage Model

Authors: Mohammed Barhoush and Louis Salvail

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide the following contributions in this model: 1) We build one-time programs and utilize them to construct CCA1-secure symmetric key encryption and message authentication codes. These schemes require no quantum memory from honest users, yet they provide information-theoretic security against adversaries with arbitrarily large quantum memories, as long as the transmission length is suitably large. 2) We introduce the notion of k-time program broadcast which is a form of program encryption that allows multiple users to each learn a single evaluation of the encrypted program, while preventing any one user from learning more than k evaluations of the program. We build this primitive unconditionally and employ it to construct CCA1-secure asymmetric key encryption, encryption tokens, signatures, and signature tokens. All these schemes are information-theoretically secure against adversaries with roughly e^√m quantum memory where m is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.
Cite as

Mohammed Barhoush and Louis Salvail. Powerful Primitives in the Bounded Quantum Storage Model. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barhoush_et_al:LIPIcs.ITC.2025.2,
  author =	{Barhoush, Mohammed and Salvail, Louis},
  title =	{{Powerful Primitives in the Bounded Quantum Storage Model}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.2},
  URN =		{urn:nbn:de:0030-drops-243523},
  doi =		{10.4230/LIPIcs.ITC.2025.2},
  annote =	{Keywords: Quantum Cryptography, Bounded Quantum Storage Model, Information-Theoretic Security}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.4
Practical Relativistic Zero-Knowledge for NP

Authors: Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear.
Cite as

Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang. Practical Relativistic Zero-Knowledge for NP. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{crepeau_et_al:LIPIcs.ITC.2020.4,
  author =	{Cr\'{e}peau, Claude and Massenet, Arnaud Y. and Salvail, Louis and Stinchcombe, Lucas Shigeru and Yang, Nan},
  title =	{{Practical Relativistic Zero-Knowledge for NP}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.4},
  URN =		{urn:nbn:de:0030-drops-121091},
  doi =		{10.4230/LIPIcs.ITC.2020.4},
  annote =	{Keywords: Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.4
The RGB No-Signalling Game

Authors: Xavier Coiteux-Roy and Claude Crépeau

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Introducing the simplest of all No-Signalling Games: the RGB Game where two verifiers interrogate two provers, Alice and Bob, far enough from each other that communication between them is too slow to be possible. Each prover may be independently queried one of three possible colours: Red, Green or Blue. Let a be the colour announced to Alice and b be announced to Bob. To win the game they must reply colours x (resp. y) such that a != x != y != b. This work focuses on this new game mainly as a pedagogical tool for its simplicity but also because it triggered us to introduce a new set of definitions for reductions among multi-party probability distributions and related non-locality classes. We show that a particular winning strategy for the RGB Game is equivalent to the PR-Box of Popescu-Rohrlich and thus No-Signalling. Moreover, we use this example to define No-Signalling in a new useful way, as the intersection of two natural classes of multi-party probability distributions called one-way signalling. We exhibit a quantum strategy able to beat the classical local maximum winning probability of 8/9 shifting it up to 11/12. Optimality of this quantum strategy is demonstrated using the standard tool of semidefinite programming.
Cite as

Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{coiteuxroy_et_al:LIPIcs.TQC.2019.4,
  author =	{Coiteux-Roy, Xavier and Cr\'{e}peau, Claude},
  title =	{{The RGB No-Signalling Game}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.4},
  URN =		{urn:nbn:de:0030-drops-103965},
  doi =		{10.4230/LIPIcs.TQC.2019.4},
  annote =	{Keywords: No-Signalling, Quantum Entanglement, Non-Locality, Bell inequality, Semidefinite Programming, Non-locality Hierarchy}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.3
Provably Secure Key Establishment Against Quantum Adversaries

Authors: Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.
Cite as

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably Secure Key Establishment Against Quantum Adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belovs_et_al:LIPIcs.TQC.2017.3,
  author =	{Belovs, Aleksandrs and Brassard, Gilles and H{\o}yer, Peter and Kaplan, Marc and Laplante, Sophie and Salvail, Louis},
  title =	{{Provably Secure Key Establishment Against Quantum Adversaries}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.3},
  URN =		{urn:nbn:de:0030-drops-85816},
  doi =		{10.4230/LIPIcs.TQC.2017.3},
  annote =	{Keywords: Merkle puzzles, Key establishment schemes, Quantum cryptography, Adversary method, Average-case analysis}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2020
  • 1 2019
  • 1 2018

  • Refine by Author
  • 3 Salvail, Louis
  • 2 Crépeau, Claude
  • 1 Andersson, Erika
  • 1 Bansal, Akshay
  • 1 Barhoush, Mohammed
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Quantum information theory
  • 1 Security and privacy → Cryptography
  • 1 Security and privacy → Information-theoretic techniques

  • Refine by Keyword
  • 2 Non-Locality
  • 2 Quantum Entanglement
  • 1 3-COLorability
  • 1 Adversary method
  • 1 Average-case analysis
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact