| Secure multi-party computation solution to Yao's millionaires' problem based on set-inclusion |
| |
| 作者姓名： | LI Shundong DAI Yiqi YOU Qiyou |
| |
| 作者单位： | Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China,Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China,Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China |
| |
| 基金项目： | 国家自然科学基金，中国博士后科学基金 |
| |
| 摘 要： | Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaires' problem have high computational complexity or communication complexity. In this study, based on the 1-out-of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation paradigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.
|
| 关 键 词： | secure multi-party computation Yao's millionaires' problem 1-out-of-m oblivious transfer set-inclusion problem. |
Secure multi-party computation solution to Yao's millionaires' problem based on set-inclusion |
| |
| LI Shundong,DAI Yiqi,YOU Qiyou.Secure multi-party computation solution to Yao''s millionaires'' problem based on set-inclusion[J].Progress in Natural Science,2005,15(9):851-856. |
| |
| Authors: | LI Shundong DAI Yiqi YOU Qiyou |
| |
| Institution: | Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China |
| |
| Abstract: | Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaires' problem have high computational complexity or communication complexity. In this study, based on the 1-out-of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation paradigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols. |
| |
| Keywords: | secure multi-party computation Yao's millionaires' problem 1-out-of-m oblivious transfer set-inclusion problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
