Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theory and Decision

A Simple Model of Secure Public Communication

Hannu Vartiainen

Published Dec 3, 2007• 3 citations
Publisher
DOI
10.1007/s11238-007-9089-4

Related papers

A Theory of Secure Communication

Björn Tackmann

•Jan 1, 2014•4 citations

Secure Message Transmission With Small Public Discussion

Juan A. Garay, Clint Givens, Rafail Ostrovsky

In the problem of secure message transmission in the public discussion model (SMT-PD), a sender wants to send a message$M_{{\cal S}}\in\{0,1\}^{\ell}$to a receiver privately and reliably. Sender and receiver are connected by$n$channels, also known as simple wires, up to$t<n$of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multiparty computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel. In this paper, we present the first SMT-PD protocol with sublinear (i.e., logarithmic in$\ell$, the message length) communication on the public channel. In addition, the protocol incurs a simple-wire communication complexity of$O({\ell n}/{n-t})$, which, as we also show, is optimal. By contrast, the best known bounds in both public and simple channels were linear. Furthermore, our protocol has an optimal round complexity of (3, 2), meaning three rounds, two of which must invoke the public channel. Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten on average through amortization. In other words, if sender and receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the naïve solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel; it is possible to limit the total number of uses of the public channel to two, no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is the best possible.)

IEEE Transactions on Information Theory•Feb 20, 2014•2 citations

On secure multiparty sampling for more than two parties

Manoj Prabhakaran, Vinod M. Prabhakaran

We investigate secure multi-party sampling problems involving more than two parties. In the public discussion model, we give a simple characterization of the distributions that can be sampled without any setup. In a model which allows private point-to-point communication, we reduce the problem of characterizing distributions that can be securely sampled using pairwise setups to the problem of characterizing distributions that can be sampled without any setups.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•13 citations

Secure Message Transmission by Public Discussion: A Brief Survey

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Lecture notes in computer science•Jan 1, 2011•10 citations

Unconditionally secure communications over fading channels

Michael A. Tope, J.C. McEachen

In this paper, we propose a novel method for two communicates to exchange a secret over a public wireless fading channel. Unlike conventional computationally secure public key methods, this technique is information theoretic and unconditionally secure provided that a component of the reciprocal channel fading over time between the two communicates is statistically independent with the channel fading from either communicate to the eavesdropper. This technique may be particularly well suited to secure tactical mobile communications. A simple protocol suitable for a lognormal shadowed fading channel is described and its key exchange rate is derived.

•Nov 13, 2002•79 citations

Secure communication in minimal connectivity models

Matthew Franklin, Rebecca N. Wright

Lecture notes in computer science•Jan 1, 1998•40 citations
In the problem of secure message transmission in the public discussion model (SMT-PD), a sender wants to send a messageMS∈{0,1}ℓM_{{\cal S}}\in\{0,1\}^{\ell}MS​∈{0,1}ℓto a receiver privately and reliably. Sender and receiver are connected bynnnchannels, also known as simple wires, up tot<nt<nt<nof which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multiparty computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel. In this paper, we present the first SMT-PD protocol with sublinear (i.e., logarithmic inℓ\ellℓ, the message length) communication on the public channel. In addition, the protocol incurs a simple-wire communication complexity ofO(ℓn/n−t)O({\ell n}/{n-t})O(ℓn/n−t), which, as we also show, is optimal. By contrast, the best known bounds in both public and simple channels were linear. Furthermore, our protocol has an optimal round complexity of (3, 2), meaning three rounds, two of which must invoke the public channel. Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten on average through amortization. In other words, if sender and receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the naïve solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel; it is possible to limit the total number of uses of the public channel to two, no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is the best possible.)
In this paper, we propose a novel method for two communicates to exchange a secret over a public wireless fading channel. Unlike conventional computationally secure public key methods, this technique is information theoretic and unconditionally secure provided that a component of the reciprocal channel fading over time between the two communicates is statistically independent with the channel fading from either communicate to the eavesdropper. This technique may be particularly well suited to secure tactical mobile communications. A simple protocol suitable for a lognormal shadowed fading channel is described and its key exchange rate is derived.