Research On Some Problems Of Provable Secure Message Transmission Protocols

As an important part of the infrastructure of social communication, computer networks usually carry a large amount of sensitive information. For the public accessibility of the transmission system, the problem of guaranteeing the security, e.g., privacy and reliability, has been becoming a hot topic of social life. When the adversary is computationally unbounded and only one public channel is available to the communicants, Shannon's result on achieving perfect security shows that a uniformly random key, not shorter than the corresponding plaintext, has to be shared initially. Obviously, this inconvenient requirement sets up a barrier to the extensive application of cryptography.To break the deadlock, the study on secure message transmission protocols selects to weaken Shannon's model in two ways: On the one hand, provided that there are multiple (say ) channels available and only part of them (say ) could be corrupted by a (computationally unbounded) adversary, reasonable (or even perfect) privacy and reliability might be realized even no random key is shared initially. On the other hand, in the scenario that only one authenticated channel is available, reasonable security is also achievable as long as the potential adversary is of limited computability (e.g., probabilistic-polynomial-time computability) and some hardness assumptions holds. The two considerations correspond respectively to the two problems of secure message transmission (SMT) with information-theoretical and computational security. Though both of the two problems have been extensively studied in the last decades, a careful analysis will find out that the research on SMT is still far from complete, especially the problems of constructing practically efficient SMT protocols and proving complexity bounds of them.For this reason, we consider how to improve the efficiency, and prove the lower bounds of communication complexity of SMT protocols in this thesis. The main results we achieved are listed as follows.(1) On computationally secure message transmission problem, we mainly consider how to improve the efficiency of probable pseudorandom generators. We first generalize the standard two-variable DDH (Decisional Diffie-Hellman hardness) assumption to multi-variable case, then present two pseudorandom generators under the prime order subgroup modulo a prime and the subgroup of quadratic residue modulo a RSA composite respectively, which can respectively output or bits when the exponent is -bit long. Under the same concrete security level, our first generator is one of the fastest generators under standard assumptions, while the second construction is also twice faster than the original (Goldreich-Rosen) algorithm.The rest of the research mainly focuses on information theoretically secure message transmission protocols.(2) To answer the open question raised by Garay and Ostrovsky on the round complexity of secure message transmission by public discussion (SMT-PD) protocols, we prove that any SMT-PD protocol should be at least 3-round totally, and two of them must invoke the public discussion channel. Then we present a round optimal SMT-PD protocol, which is computationally efficient and almost optimal in communication complexity when the message is long enough.(3) By weakening the requirement of security, we consider the problem of constructing communication-optimal 1-round Almost SMT protocols. For each of the two conditions of (where ) and , we present one Almost SMT protocols to achieve optimal transmission rate ( and respectively). Both of the two protocols are perfectly private and probabilistically reliable. Then, by adopting a privacy definition similar to the notion of semantic security of encryption schemes, we construct a 1-round SMT protocol under the condition of to achieve optimal transmission rate (that is ). The protocol is perfectly reliable though its privacy is weaker than perfect SMT protocols.(4) The standard model of SMT, assuming some of the available channels are completely secure and no noise, won't work any more when all the available channels may be affected by the adversarial actions. We suggest a new model (called the adversarial channel model) to capture the scenario where the adversary can not only fully control some channels but also partially modify the other channels by introducing adversarial noises. A round-optimal SMT protocol under the new model is presented, which only involves a little more computation and communication complexity in comparing with SMT protocols under the standard model. (5) We finally formalize a new problem, called Key Expansion over Wires (KEoW), to fulfill the requirement of expanding a weak key to a much longer and stronger key over multiple wires. The problem, as we prove in this thesis, is solvable when only one of the available channels is uncorrupted. We then bound the communication complexity of KEoW protocols by analyzing the relation between KEoW and SMT protocols, while we prove that the communication complexity of SMT protocols with initial weak keys cannot be reduced substantially. Finally, we prove that, even without the help of public discussion channel , the SMT protocols under condition is constructible when a weak key is shared initially.