License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2023.1
URN: urn:nbn:de:0030-drops-183297
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18329/
Resch, Nicolas ;
Yuan, Chen
Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate
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).
BibTeX - Entry
@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.dagstuhl.de/opus/volltexte/2023/18329},
URN = {urn:nbn:de:0030-drops-183297},
doi = {10.4230/LIPIcs.ITC.2023.1},
annote = {Keywords: Secure transmission, Information theoretical secure, MDS codes}
}
|
Keywords: |
|
Secure transmission, Information theoretical secure, MDS codes |
|
Collection: |
|
4th Conference on Information-Theoretic Cryptography (ITC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.07.2023 |
