Security, Fault-tolerance, Efficiency of Multi-party Computation

我们得到的主要结果如下：(1)我们形式化了如何在分层组中玩家之间使用随机发牌传输信息理论上安全的比特的问题。然后我们针对该问题设计了协议，并针对每个协议给出了足够的条件，成功地构建了玩家和窃听者手牌大小的密钥交换生成树。(2)通过给出一种连接一对给定节点的节点不相交路径的显式构造算法，证明了N个节点的超环的节点连通性与其度相等。(3)分析了异步多写/读共享内存模型上k-exclusion问题的两种算法及其正确性。我们给出了每个算法等待时间的上界。(4)给出了一些提高求解最小生成树并行算法效率的结果。我们还表明，对于密集图，我们可以在EWEW PRAM上实现0（log n）时间。(5)针对异步单写/多读共享内存模型上的互斥问题，提出了两种基于有界票证的简单算法。(6)通过异步分布式计算，定义了一个基于事件间时间关系的回合函数。我们提出了一种可以在单写/多读共享内存模型中实现的turn函数算法。(7)提出了一种加速群k不相容问题的Vidyasankar算法的方法。(8)针对群体互斥问题，提出了两种基于票序的算法。

The main results which we obtained are as follows :(1)We formalized the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups. Then we designed protocols for the problem, and for each protocol we gave sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players an the eavesdropper.(2)We proved that the node connectivity of a hyper-ring with N nodes is equal to its degree by presenting an algorithm for the explicit construction of node-disjoint paths connecting a pair of given nodes.(3)We analyzed two algorithms for the k-exclusion problem on the asynchronous multi-writer/reader shared memory model and their correctness. We gave an upper bound on waiting time for each algorithm.(4)We gave some results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. We also show that for dense graphs we can achieve 0(log n) time on EWEW PRAM.(5)We prepared two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model.(6)We defined a turn function based on a temporal relation among events by asynchronous distributed computing. We proposed an algorithm for the turn function that can be implemented in the single-writer/multi-reader shared memory model.(7)We proposed a method to accelerate Vidyasankar's algorithm for the group k-exclusion problem.(8)We proposed two algorithms based on ticket orders for the group mutual exclusion problem.