4 Search Results for "Fehr, Serge"

Document
DOI: 10.4230/LIPIcs.ITC.2023.1
Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Authors: Nicolas Resch and Chen Yuan

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via n parallel two-way channels, and Alice holds an 𝓁 symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls t of the channels, where n = 2t+1. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice’s secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice’s secret, regardless of Eve’s corruptions; and (b) private, i.e., Eve may not learn anything about Alice’s secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret 𝓁 is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an 𝓁 symbol secret to Bob by transmitting at most 2(1+o_{𝓁→∞}(1))n𝓁 symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that 2n𝓁 symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).
Cite as

Nicolas Resch and Chen Yuan. Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{resch_et_al:LIPIcs.ITC.2023.1,
  author =	{Resch, Nicolas and Yuan, Chen},
  title =	{{Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.1},
  URN =		{urn:nbn:de:0030-drops-183297},
  doi =		{10.4230/LIPIcs.ITC.2023.1},
  annote =	{Keywords: Secure transmission, Information theoretical secure, MDS codes}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.24
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case

Authors: Harry Buhrman, Serge Fehr, and Christian Schaffner

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value < 1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game G has a non-signaling value v_{ns}(G) < 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n. Stronger than that, we prove that the probability of winning more than (v_{ns}(G) + delta) * n parallel repetitions is exponentially small in n (for any delta > 0). Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.
Cite as

Harry Buhrman, Serge Fehr, and Christian Schaffner. On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 24-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2014.24,
  author =	{Buhrman, Harry and Fehr, Serge and Schaffner, Christian},
  title =	{{On the Parallel Repetition of Multi-Player Games: The No-Signaling Case}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{24--35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.24},
  URN =		{urn:nbn:de:0030-drops-48034},
  doi =		{10.4230/LIPIcs.TQC.2014.24},
  annote =	{Keywords: Parallel repetition, non-signaling value, multi-player non-local games}
}
Document
DOI: 10.4230/DagRep.3.9.59
Quantum Cryptanalysis (Dagstuhl Seminar 13371)

Authors: Serge Fehr, Michele Mosca, Martin Rötteler, and Rainer Steinwandt

Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13371 "Quantum Cryptanalysis". In the first part, the motivation and organizational aspects of this meeting are outlined. Thereafter, abstracts for the presentations are provided (sorted alphabetically by last name of the presenter)
Cite as

Serge Fehr, Michele Mosca, Martin Rötteler, and Rainer Steinwandt. Quantum Cryptanalysis (Dagstuhl Seminar 13371). In Dagstuhl Reports, Volume 3, Issue 9, pp. 59-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{fehr_et_al:DagRep.3.9.59,
  author =	{Fehr, Serge and Mosca, Michele and R\"{o}tteler, Martin and Steinwandt, Rainer},
  title =	{{Quantum Cryptanalysis (Dagstuhl Seminar 13371)}},
  pages =	{59--73},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{9},
  editor =	{Fehr, Serge and Mosca, Michele and R\"{o}tteler, Martin and Steinwandt, Rainer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.9.59},
  URN =		{urn:nbn:de:0030-drops-43575},
  doi =		{10.4230/DagRep.3.9.59},
  annote =	{Keywords: security of cryptographic schemes, quantum algorithms, computational hardness assumptions}
}
Document
DOI: 10.4230/DagRep.1.9.58
Quantum Cryptanalysis (Dagstuhl Seminar 11381)

Authors: Serge Fehr, Michele Mosca, Martin Rötteler, and Rainer Steinwandt

Published in: Dagstuhl Reports, Volume 1, Issue 9 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11381 ``Quantum Cryptanalysis''. The first section gives an overview of the meeting, including organizational aspects. Subsequently abstracts of presentations at the meeting are provided (in alphabetical order).
Cite as

Serge Fehr, Michele Mosca, Martin Rötteler, and Rainer Steinwandt. Quantum Cryptanalysis (Dagstuhl Seminar 11381). In Dagstuhl Reports, Volume 1, Issue 9, pp. 58-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{fehr_et_al:DagRep.1.9.58,
  author =	{Fehr, Serge and Mosca, Michele and R\"{o}tteler, Martin and Steinwandt, Rainer},
  title =	{{Quantum Cryptanalysis (Dagstuhl Seminar 11381)}},
  pages =	{58--75},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{9},
  editor =	{Fehr, Serge and Mosca, Michele and R\"{o}tteler, Martin and Steinwandt, Rainer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.9.58},
  URN =		{urn:nbn:de:0030-drops-33675},
  doi =		{10.4230/DagRep.1.9.58},
  annote =	{Keywords: Security of cryptographic schemes, quantum algorithms, computational hardness assumptions}
}
  • Refine by Author
  • 3 Fehr, Serge
  • 2 Mosca, Michele
  • 2 Rötteler, Martin
  • 2 Steinwandt, Rainer
  • 1 Buhrman, Harry
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Mathematical foundations of cryptography

  • Refine by Keyword
  • 2 computational hardness assumptions
  • 2 quantum algorithms
  • 1 Information theoretical secure
  • 1 MDS codes
  • 1 Parallel repetition
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2014
  • 1 2011
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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