【作者】 石竑松；

【导师】 秦志光；

【作者基本信息】 电子科技大学 ， 计算机应用技术， 2010， 博士

【摘要】 作为社会交流平台的一个重要组成部分,计算机网络通常承载着大量的敏感信息,而由于网络的开放性,如何保证这些敏感信息的安全性,如私密性和可靠性,也就自然成为了社会关注的焦点话题。当通信双方之间只有一条公开信道且攻击者计算能力无限时,Shannon的研究表明,为了实现完善保密性,通信双方必须预先共享一个不短于明文消息长度的密钥。而在实际应用中,这种需求未免有些过于苛刻了。为此,安全消息传输(SMT)协议从两个方面对Shannon模型进行了弱化:一方面,若通信双方存在多条( )信道,且攻击者只能虏获其中的一部分( )时,即使(通信双方)预先未共享任何密钥也能实现完善保密的目标;另一方面,若通信双方只有一条公开认证信道,但攻击者计算能力有限(如概率多项式时间算法)且某些困难性猜想成立时,通信双方也可能在未共享任何密钥的前提下实现足够安全的保密目标。这两种情况分别对应了信息论安全和计算上安全的消息传输协议问题。自提出以来,这两个问题均得到了密码学界的广泛研究。不过细心分析可以发现,对这两个问题的研究还远未达到完美的状态,特别是在高效协议设计以及复杂度下界证明方面仍留有很大的想象空间。为此,本文同时从计算上安全和信息论安全这两个角度研究了高效SMT协议的构造和通信复杂度下界证明问题,并取得了以下原创性成果:(1)在计算上安全的消息传输协议方面,本文主要考虑如何提高可证安全伪随机生成器算法的效率。为此,本文研究了如何将标准的DDH(Diffie-Hellman判定困难性)假定由二变量推广至多变量的情形;并以此为基础,在模为素数的素阶子群及RSA合数的二次剩余类子群上分别构造了一个伪随机生成器算法。这两个算法在每个指数长度为比特的模幂运算下分别能输出比特和比特。通过与目前已知最好的算法在同一具体安全级别上的比较发现,我们的第一个算法是目前基于标准假定下最快的;而第二个算法也是改进前的(Goldreich-Rosen)算法的两倍快。本文后续研究都是针对信息论安全的消息传输协议展开的。(2)为了回答Garay和Ostrovsky提出的一个开放问题,本文证明了任何公开讨论信道模型下的SMT协议(即SMT-PD)都需要进行三轮通信,且其中两轮需要使用公开讨论信道;并给出了一个通信轮数最优的SMT-PD协议。该协议是计算上有效的,且当消息长度满足一定条件时,通信复杂度接近最优。(3)通过降低安全性要求,分析了如何设计具有最优通信复杂度的1-轮概率SMT协议的问题。首先,针对条件(其中)和分别设计了一个概率SMT协议以分别实现最优的传输率和。这些协议都能实现完善的保密性,但有很小的失败概率。其次,通过采用一个类似于加密方案语义安全性的私密性定义,还在条件下设计了一个具有最优传输率的1-轮概率SMT协议。该协议完全可靠,但攻击者有可能获得一些秘密信息。(4)由于SMT标准模型假定可用信道中有些是完全保密且没有任何噪音的,因此在一个攻击气氛弥漫的网络中可能不太合理。为此提出了敌手信道模型,不仅允许攻击者能完全控制一些信道,还允许她通过引入噪音来篡改其它信道中的部分消息。在新模型中设计了一个轮复杂性最优的SMT协议。相比于标准模型下的协议,该协议只增加了一些很小的计算和通信开销。(5)提出了一个被称为“多信道密钥扩展”的新问题(KEoW)以研究如何在多条信道上将一个共享的弱密钥扩展为一个任意长的强密钥。证明了KEoW问题在即使只存在一条未虏获信道的情况下都是可以解决的,不过当被虏获的信道数多于一半时,KEoW协议无法实现完善可靠性。利用该问题与SMT问题的关系还分析了KEoW协议的通信复杂性,同时还证明了带初始弱密钥的SMT协议的通信复杂性实际上得不到显著的改善。最后证明了当存在初始弱密钥时无需公开讨论信道就可实现条件下的SMT协议。更多还原

【Abstract】 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.更多还原