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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Almost Secure (1-Round, n-Channel) Message Transmission Scheme

Kaoru Kurosawa, Kazuhiro SUZUKI

Published Jan 1, 2009• 22 citations
Publisher

Abstract

It is known that perfectly secure (1-round, n-channel) message transmission (MT) schemes exist if and only if n ≥ 3t + 1, where t is the number of channels that the adversary can corrupt. Then does there exist an almost secure MT scheme for n = 2t + 1 ? In this paper, we first sum up a number flaws of the previous almost secure MT scheme presented at Crypto 2004*. We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure (1-round, n-channel) MT schemes for n =2t + 1.

DOI
10.1587/transfun.e92.a.105

Related papers

Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme.

Kaoru Kurosawa, Kazuhiro Suzuki

Abstract. In the model of perfectly secure message transmission schemes (PSMTs), there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.

•Jan 1, 2008•0 citations

Truly Efficient 222-Round Perfectly Secure Message Transmission Scheme

Kaoru Kurosawa, Kazuhiro Suzuki

In the model of perfectly secure message transmission (PSMT) schemes, there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer, and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.

IEEE Transactions on Information Theory•Oct 27, 2009•34 citations

Round-Efficient Perfectly Secure Message Transmission Scheme Against General Adversary.

Kaoru Kurosawa

In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are n channels between a sender and a receiver, and they share no key. An infinitely powerful adversary A can corrupt (observe and forge) the messages sent through some subset of n channels. For non-threshold adversaries called Q 2, Kumar et al. showed a many round PSMT (Ashwin Kumar et al. On perfectly secure communication over arbitrary networks. PODC 2002, pp. 193---202, 2002). In this paper, we show round efficient PSMTs against Q 2-adevrsaries. We first give a 3-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a 2-round PSMT which is inefficient in general. (However, it is efficient for some special case.)

•Jan 1, 2010•3 citations

Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Nicolas Resch, Chen Yuan

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).

Leibniz international proceedings in informatics•Jan 1, 2023•1 citation

Efficient Almost Secure 1-Round Message Transmission Schemes for 3t+1 Channels

Toshinori Araki, Wakaha Ogata

In the model, a sender S wants to send a message to a receiver R secretly and reliably in r-round. They do not share any information like keys, but there are n independent communication channels between S and R, and an adversary A can observe and/or substitute the data which goes through some channels (but not all). In this paper, we propose almost secure (1-round, 3t+1 -channel) MTSs which have following two properties where t is the number of channels A can observe and/or forge. (1) The running time of message decryption algorithm is polynomial in n. (2) Communication cost is smaller than the previous MTSs, if the message is large to some degree.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2010•0 citations

Efficient Protocols for Perfectly Secure Message Transmission With Applications to Secure Network Coding

Gabriele Spini, Gilles Zémor

In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.

IEEE Transactions on Information Theory•May 13, 2020•4 citations
It is known that perfectly secure (1-round, n-channel) message transmission (MT) schemes exist if and only if n ≥ 3t + 1, where t is the number of channels that the adversary can corrupt. Then does there exist an almost secure MT scheme for n = 2t + 1 ? In this paper, we first sum up a number flaws of the previous almost secure MT scheme presented at Crypto 2004*. We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure (1-round, n-channel) MT schemes for n =2t + 1.
Abstract. In the model of perfectly secure message transmission schemes (PSMTs), there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.
In the model of perfectly secure message transmission (PSMT) schemes, there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer, and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.
In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are n channels between a sender and a receiver, and they share no key. An infinitely powerful adversary A can corrupt (observe and forge) the messages sent through some subset of n channels. For non-threshold adversaries called Q 2, Kumar et al. showed a many round PSMT (Ashwin Kumar et al. On perfectly secure communication over arbitrary networks. PODC 2002, pp. 193---202, 2002). In this paper, we show round efficient PSMTs against Q 2-adevrsaries. We first give a 3-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a 2-round PSMT which is inefficient in general. (However, it is efficient for some special case.)
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).
In the model, a sender S wants to send a message to a receiver R secretly and reliably in r-round. They do not share any information like keys, but there are n independent communication channels between S and R, and an adversary A can observe and/or substitute the data which goes through some channels (but not all). In this paper, we propose almost secure (1-round, 3t+1 -channel) MTSs which have following two properties where t is the number of channels A can observe and/or forge. (1) The running time of message decryption algorithm is polynomial in n. (2) Communication cost is smaller than the previous MTSs, if the message is large to some degree.
In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.