In 2012, De Cristofaro et al. proposed a protocol to calculate the Private Set Intersection and Union cardinality(PSI-CA and PSU-CA). This protocol's security is based on the famous DDH assumption. Since its publication, it has gained lots of popularity because of its efficiency(linear complexity in computation and communication) and concision. So far, it's still considered one of the most efficient PSI-CA protocols and the most cited(more than 170 citations) PSI-CA paper based on the Google Scholar search. However, when we tried to implement this protocol, we couldn't get the correct result of the test data. Since the original paper lacks of experimental results to verify the protocol's correctness, we looked deeper into the protocol and found out it made a fundamental mistake. Needless to say, its correctness analysis and security proof are also wrong. In this paper, we will point out this PSI-CA protocol's mistakes, and provide the correct version of this protocol as well as the PSI protocol developed from this protocol. We also present a new security proof and some experimental results of the corrected protocol.
翻译:在2012年,De Cristfardo等人提出了计算私密交界和联合核心(PSI-CA和PSU-CA)的协议。这项协议的安全性以著名的DDH假设为基础。自其出版以来,由于效率(计算和通信的线性复杂性)和精确性,它赢得了很多人的欢迎。到目前为止,它仍然被认为是PSI-CA协议中最有效的协议之一,也是根据谷歌学者搜索而引用最多的(超过170次引用)PSI-CA文件。然而,当我们试图执行这项协议时,我们无法从测试数据中获得正确的结果。由于最初的文件缺乏核查协议正确性的实验结果,我们更深入地研究了协议,发现它犯了根本性错误。不用说,它的正确性分析和安全证据也是错误的。在这份文件中,我们将指出PSI-CA协议的错误,并提供该议定书的正确版本以及根据这项协议制定的PSI协议。我们还提交了一份新的安全证据和经更正的议定书的一些实验性结果。