An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.
An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.
Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).
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.)
Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secret s correctly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition called Q3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S | and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).
The problem of secure message transmission (SMT), due to its importance in both \npractice and theory, has been studied extensively. Given a communication network in \nwhich a sender S and a receiver R are indirectly connected by unreliable and distrusted \nchannels, the aim of SMT is to enable messages to be transmitted from S to R with a \nreasonably high level of privacy and reliability. SMT must be achieved in the presence \nof a Byzantine adversary who has unlimited computational power and can corrupt the \ntransmission. In the general adversary model, the adversary is characterized by an \nadversary structure. We study two diff�erent measures of security: perfect (PSMT) and \nalmost perfect (APSMT). Moreover, reliable (but not private) message transmission (RMT) are considered as a specifi�c part of SMT. In this thesis, we study RMT, APSMT \nand PSMT in two di�fferent network settings: point-to-point and multicast. \nTo prepare the study of SMT in these two network settings, we present some ideas \nand observations on secret sharing schemes (SSSs), generalized linear codes and critical \npaths. First, we prove that the error-correcting capability of an almost perfect SSS is \nthe same as a perfect SSS. Next, we regard general access structures as linear codes, \nand introduce some new properties that allow us to construct pseudo-basis for efficient \nPSMT protocol design. In addition, we de�fine adversary structures over "critical paths", \nand observe their properties. Having these new developments, the contributions on SMT \nin the aforementioned two network settings can be presented as follows. \nThe results on SMT in point-to-point networks are obtained in three aspects. First, \nwe show a Guessing Attack on some existing PSMT protocols. This attack is critically \nimportant to the design of PSMT protocols in asymmetric networks. Second, we determine necessary and sufficient conditions for di�fferent levels of RMT and APSMT. \nIn particular, by applying the result on almost perfect SSS, we show that relaxing the \nrequirement of privacy does not weaken the minimal network connectivity. Our �final \ncontribution in the point-to-point model is to give the �first ever efficient, constant round \nPSMT protocols in the general adversary model. These protocols are designed using \nlinear codes and critical paths, and they signifi�cantly improve some previous results in \nterms of communication complexity and round complexity. \nRegarding SMT in multicast networks, we solve a problem that has been open for \nover a decade. That is, we show the necessary and sufficient conditions for all levels of \nSMT in di�fferent adversary models. First, we give an Extended Characterization of the \nnetwork graphs based on our observation on the eavesdropping and separating activities \nof the adversary. Next, we determine the necessary and sufficient conditions for SMT \nin the general adversary model with the new Extended Characterization. Finally, we \napply the results to the threshold adversary model to completely solve the problem of \nSMT in general multicast network graphs.
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), 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).