Verifiably Randomized Quick-sort Protocols In the Presence of Malicious Adversaries

摘要：

The sorting protocols are applied extensively in the real-world (say, a key to the auto-partitions problem and the kth-ranked element problem). This paper studies random quick-sort protocols in the presence of malicious adversaries and makes the following twofold contributions. ·In the first fold, a new notion which we call verifiably randomized quick-sort protocols is introduced and formalized. ·In the second fold, an efficient implementation of the primitive from homomorphic commitment schemes is proposed and analyzed. We show that our implementation is provably secure assuming that the underlying homomorphic commitment scheme is statistically hiding and computationally binding in the common reference model.

作者: Huafei Zhu

作者单位: Institute for Infocomm Research, A*STAR, Singapore

会议类型: 国际会议

会议名称: Second International Symposium on Information Science and Engineering(第二届信息科学与工程国际会议)

会议地点: 上海

会议语种:英文

页码: 359-362

在线出版日期: 2009-12-26（万方平台首次上网日期，不代表论文的发表时间）