2006 | OriginalPaper | Buchkapitel
Asymptotically Optimal Two-Round Perfectly Secure Message Transmission
verfasst von : Saurabh Agarwal, Ronald Cramer, Robbert de Haan
Erschienen in: Advances in Cryptology - CRYPTO 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The problem of perfectly secure message transmission concerns two synchronized non-faulty processors sender (
${\mathcal{S}}$
) and receiver (
${\mathcal{R}}$
) that are connected by a synchronous network of
n
≥2
t
+1 noiseless 2-way communication channels. Their goal is to communicate privately and reliably, despite the presence of an adversary that may actively corrupt at most
t
of those channels. These properties should hold information theoretically and without error.
We propose an asymptotically optimal solution for this problem. The proposed protocol consists of two communication rounds, and a total of
O
(ℓ
n
) bits are exchanged in order to transmit a message of ℓ bits. Earlier, at CRYPTO 2004, an equally optimal solution has been claimed. However, we give a counter-example showing that their result is not perfectly reliable. The flaw seems to be fundamental and non-trivial to repair. Our approach is overall entirely different, yet it also makes essential use of their neat communication efficient technique for reliably transmitting conflict graphs.
What distinguishes our approach from previous ones is a technique that allows to identify
all actively corrupted channels
, initially trading it off against privacy. A perfectly secure and reliable secret key is then distilled by privacy amplification.