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

多方计算的安全性、容错性、高效性

• 批准号: 13680390
• 负责人: IGARASHI Yoshihide
• 金额: $ 2.11万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680390/
• 关键词: asynchronous shared memory; distributed algorithm; distributed system; group mutual exclusion; information security; k-exclusion; multi-party computation; mutual exclusion; 分散システム; 情報セキュリティ; 非同期共有メモリ; 相互排他問題; k-排他問題; 情報セキュティ; _<k->排他問題

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.

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

项目成果

Masataka Takamura: "A Simplification of the Bakery algorithm based on bounded tickets for the mutual exclusion problem"電子情報通信学会技術研究報告. 101・376. 61-68 (2001)

Masataka Takamura：“基于互斥问题的有界票据的 Bakery 算法的简化”IEICE 技术报告 101・376 (2001)。

Masataka Takamura: "Group mutual exclusion algorithms based on ticket orders"Lecture Notes in Computer Science. 2697. 232-241 (2003)

高村正孝：《基于票单的分组互斥算法》计算机科学讲义。

Tom Altman: "A turn function scheme realized in the asynchronous single-writer/multi-reader shared memory model"Lecture Notes in Computer Science. 2906. 454-463 (2003)

Tom Altman：“在异步单写入器/多读取器共享内存模型中实现的轮函数方案”计算机科学讲义。

M.Takamura, Y.Igarashi: "Simple mutual exclusion algorithms based on bounded tickets on the asynchronous shared memory model"The 8th International Conference on Computing and Combinatrics, Singapore, Lecture Notes in Computer Science(Springer-Verlag). Vol

M.Takamura、Y.Igarashi：“基于异步共享内存模型上的有界票据的简单互斥算法”第八届国际计算与组合学会议，新加坡，计算机科学讲义（Springer-Verlag）。

Tom Altman: "Fast and dependable communication in hyper-rings"Lecture Notes in Computer Science. 2387. 350-359 (2002)

Tom Altman：“超环中快速可靠的通信”计算机科学讲义。