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

Lecture notes in computer science

Cryptanalysis of Secure Message Transmission Protocols with Feedback

Qiushi Yang, Yvo Desmedt

Published Jan 1, 2010• 15 citations
Publisher
DOI
10.1007/978-3-642-14496-7_14

Related papers

Human Perfectly Secure Message Transmission Protocols and Their Applications

Stelios Erotokritou, Yvo Desmedt

Lecture notes in computer science•Jan 1, 2012•4 citations

Towards Optimal and Efficient Perfectly Secure Message Transmission

Matthias Fitzi, Matthew Franklin, Juan A. Garay +1 more

Springer eBooks•May 16, 2007•80 citations

Cryptanalysis of Secure Message Transmission Protocols with Feedback.

Qiushi Yang, Yvo Desmedt

Abstract. In the context of secure point-to-point message transmission in networks with minimal connectivity, previous studies showed that feedbacks from the receiver to the sender can be used to reduce the requirements of network connectivity. We observe that the way how feedbacks were used in previous work does not guarantee perfect privacy to the transmitted message, when the adversary performs a Guessing Attack. In this paper, we shall describe our new Guessing Attack to some existing protocols (in fact, we are the first to point out a flaw in the protocols of Desmedt-Wang’s Eurocrypt’02 paper and of Patra-Shankar-Choudhary-Srinathan-Rangan’s CANS’07 paper), and propose a scheme defending against a general adversary structure. In addition, we also show how to achieve almost perfectly secure message transmission with feedbacks when perfect reliability or perfect privacy is not strictly required.

•Jan 1, 2009•0 citations

Secure Capacity Region for Erasure Broadcast Channels with Feedback

László Czap, Vinod M. Prabhakaran, Suhas N. Diggavi +1 more

We formulate and study a cryptographic problem relevant to wireless: a sender, Alice, wants to transmit private messages to two receivers, Bob and Calvin, using unreliable wireless broadcast transmissions and short public feedback from Bob and Calvin. We ask, at what rates can we broadcast the private messages if we also provide (information-theoretic) unconditional security guarantees that Bob and Calvin do not learn each-other's message? We characterize the largest transmission rates to the two receivers, for any protocol that provides unconditional security guarantees. We design a protocol that operates at any rate-pair within the above region, uses very simple interactions and operations, and is robust to misbehaving users.

arXiv:1110.5741•Oct 26, 2011•2 citations

The design and analysis of real-world cryptographic protocols

Samuel M. Scott

•Jan 1, 2018•0 citations

New results on secure message transmission

Reihaneh Safavi–Naini, Mohammed Ashraful Alam Tuhin

In the Secure Message Transmission (SMT) problem two nodes in a network want to communicate securely (both privately and reliably), given that some of the nodes in the network are corrupted by an adaptive byzantine adversary with unlimited computational power. A SMT protocol uses multiple paths between the sender S and a receiver R to guarantee privacy and reliability of the message transmission. Privacy means that the adversary learns no information about the transmitted secret, whereas reliability means that the receiver always receives the message sent by the sender. S and R are connected by n disjoint paths where a subset of which (at most t in case of a threshold adversary) can be corrupted by an adversary. Efficiency parameters of a SMT protocol are the number of rounds (number of interactions between S and R ), communication complexity, and computational complexity. An (e, δ)-SMT protocol bounds the adversary's success probability of breaking privacy and reliability to e and δ, respectively. A SMT protocol for a given number of rounds is optimal if its transmission rate (amount of communication per one bit of message) matches the lower bound for that number of rounds. Optimal protocols have been constructed for a restricted set of parameters. It has been proved that secure SMT is possible if and only if n ≥ 2t + 1, where t is the number of paths corrupted by the adversary. This thesis describes a number of contributions to the study of SMT problem. First, we improve the system parameter of a previously introduced wire virtualization method for constructing optimal protocols using two component protocols. Using the improved wire virtualization method we present the first optimal 1-round (0, δ)-SMT protocol for higher connectivity. Then we introduce a modular approach for constructing SMT protocols using two or more modules. Using this approach we design an optimal 1-round (0, δ)-SMT protocol for the minimum connectivity, which has higher reliability than any comparable protocol. We also design a similar protocol for higher connectivity improving the reliability of the protocol presented in the first part of this thesis. Constructing secure and efficient (in communication) SMT protocols against a threshold adversary has been extensively researched. However less is known about SMT problem for a generalized adversary who can corrupt one out of a set of possible subsets. In this part of the thesis, we focus on 1-round (0, δ)-SMT protocols against a generalized adversary. These protocols are especially attractive because of their possible practical applications. Finally, we introduce a new security definition by presenting an alternative privacy definition, which is based on guessing advantage of the adversary, to construct more efficient (in communication) protocols. Our motivation is that if the received message is long enough and has sufficient entropy, then it can be used as a secret key. We give the relationship between the new security definition and the known one, and revisit bounds on connectivity and transmission rates of SMT protocols under the new definition. We also give constructions for a 1-round and a 3-round protocol, secure under the new definition, that are optimal. The contributions made in this thesis add to the research on the secure message transmission problem and show new directions for future research.

•Jan 1, 2012•0 citations
Abstract. In the context of secure point-to-point message transmission in networks with minimal connectivity, previous studies showed that feedbacks from the receiver to the sender can be used to reduce the requirements of network connectivity. We observe that the way how feedbacks were used in previous work does not guarantee perfect privacy to the transmitted message, when the adversary performs a Guessing Attack. In this paper, we shall describe our new Guessing Attack to some existing protocols (in fact, we are the first to point out a flaw in the protocols of Desmedt-Wang’s Eurocrypt’02 paper and of Patra-Shankar-Choudhary-Srinathan-Rangan’s CANS’07 paper), and propose a scheme defending against a general adversary structure. In addition, we also show how to achieve almost perfectly secure message transmission with feedbacks when perfect reliability or perfect privacy is not strictly required.
We formulate and study a cryptographic problem relevant to wireless: a sender, Alice, wants to transmit private messages to two receivers, Bob and Calvin, using unreliable wireless broadcast transmissions and short public feedback from Bob and Calvin. We ask, at what rates can we broadcast the private messages if we also provide (information-theoretic) unconditional security guarantees that Bob and Calvin do not learn each-other's message? We characterize the largest transmission rates to the two receivers, for any protocol that provides unconditional security guarantees. We design a protocol that operates at any rate-pair within the above region, uses very simple interactions and operations, and is robust to misbehaving users.
In the Secure Message Transmission (SMT) problem two nodes in a network want to communicate securely (both privately and reliably), given that some of the nodes in the network are corrupted by an adaptive byzantine adversary with unlimited computational power. A SMT protocol uses multiple paths between the sender S and a receiver R to guarantee privacy and reliability of the message transmission. Privacy means that the adversary learns no information about the transmitted secret, whereas reliability means that the receiver always receives the message sent by the sender. S and R are connected by n disjoint paths where a subset of which (at most t in case of a threshold adversary) can be corrupted by an adversary. Efficiency parameters of a SMT protocol are the number of rounds (number of interactions between S and R ), communication complexity, and computational complexity. An (e, δ)-SMT protocol bounds the adversary's success probability of breaking privacy and reliability to e and δ, respectively. A SMT protocol for a given number of rounds is optimal if its transmission rate (amount of communication per one bit of message) matches the lower bound for that number of rounds. Optimal protocols have been constructed for a restricted set of parameters. It has been proved that secure SMT is possible if and only if n ≥ 2t + 1, where t is the number of paths corrupted by the adversary. This thesis describes a number of contributions to the study of SMT problem. First, we improve the system parameter of a previously introduced wire virtualization method for constructing optimal protocols using two component protocols. Using the improved wire virtualization method we present the first optimal 1-round (0, δ)-SMT protocol for higher connectivity. Then we introduce a modular approach for constructing SMT protocols using two or more modules. Using this approach we design an optimal 1-round (0, δ)-SMT protocol for the minimum connectivity, which has higher reliability than any comparable protocol. We also design a similar protocol for higher connectivity improving the reliability of the protocol presented in the first part of this thesis. Constructing secure and efficient (in communication) SMT protocols against a threshold adversary has been extensively researched. However less is known about SMT problem for a generalized adversary who can corrupt one out of a set of possible subsets. In this part of the thesis, we focus on 1-round (0, δ)-SMT protocols against a generalized adversary. These protocols are especially attractive because of their possible practical applications. Finally, we introduce a new security definition by presenting an alternative privacy definition, which is based on guessing advantage of the adversary, to construct more efficient (in communication) protocols. Our motivation is that if the received message is long enough and has sufficient entropy, then it can be used as a secret key. We give the relationship between the new security definition and the known one, and revisit bounds on connectivity and transmission rates of SMT protocols under the new definition. We also give constructions for a 1-round and a 3-round protocol, secure under the new definition, that are optimal. The contributions made in this thesis add to the research on the secure message transmission problem and show new directions for future research.