作为社会交流平台的一个重要组成部分,计算机网络通常承载着大量的敏感信息,而由于网络的开放性,如何保证这些敏感信息的安全性,如私密性和可靠性,也就自然成为了社会关注的焦点话题。当通信双方之间只有一条公开信道且攻击者计算能力无限时,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协议。