Secure and reliable communication in distributed systems

本课题旨在研究大规模分布式系统中可靠、安全的通信和计算协议的设计与分析。提出了几种网络容错广播方案，以及基于异步共享存储模型的互斥算法和k-互斥算法。我们的互斥算法是Peterson的n进程算法和Peterson和Fischer的锦标赛算法的改进。我们的k-互斥算法是互斥算法的扩展。我们的算法使用多个写入器/读取器共享变量。这是一个不吸引人的特征，但算法的结构很简单。N-互斥算法不仅满足k-互斥，而且还满足k-锁定避免，提出了如何利用分层组中玩家之间的随机牌牌和计算无限窃听者来传输信息论安全比特的问题。我们还引入了语义安全的精细化定义。新定义不仅对选择明文攻击有效，而且对选择密文攻击也有效。证明了对于选择明文攻击、非自适应选择密文攻击和自适应选择密文攻击，由新定义形式化的语义安全等价于Goldwasser和Micali的不可区分性，构建了一个分布式处理系统，客户可以随时加入或离开。在PVM上实现了求解离散对数问题的一些算法。

This project is to study the design and analysis of reliable and secure protocols for communication and computation on large scale distributed systems. We proposed some fault tolerant broadcasting schemes in networks, and mutual exclusion algorithms and k-exclusion algorithms on the asynchronous shared memory model. Our mutual exclusion algorithms are improvements of the n-process algorithm by Peterson and the tournament algorithm by Peterson and Fischer. Our k-exclusion algorithms are extensions of our mutual exclusion algorithms. Our algorithms use multi-writer/reader shared variables. This is an unattractive feature, but the structures of the algorithms are simple. The n-exclusion algorithms satisfy not only k-exclusion but also k-lockout avoidance.We proposed the problem of how to transmit an information-theoretic secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. We also introduced a refined definition of semantic security. The new definition is valid against not only chosen-plaintext attacks but also chosen-ciphertext attacks. We show that semantic security formalized by the new definition is equivalent to indistinguishability, due to Goldwasser and Micali, for each of chosen-plaintext attacks, non-adaptive chosen ciphertext attacks, and adaptive chosen-ciphertext attacks.We constructed a distributed processing system where clients can join or leave whenever they want to do so. We implemented some algorithms for solving the discrete logarithm problem on PVM (Parallel Virtual Machine).