Publicly Verifiable Delegation of Set Intersection

摘要：

　　We study the verifiable delegation of set intersection in the model of authenticated data structures,where a weak client in storage and computation stores its dataset composed of some sets into a powerful server.The client can issue update and set intersection query over outsourced data.The server returns the result and a proof of its correctness.Our scheme allows any entity to publicly verify the correctness of set intersection query,and requires no secret key.Based on characteristic polynomials of sets,our authenticated data structure firstly provides a practical and specific method for set intersection through polynomial evaluations.It achieves optimal verification and proof complexity,as well as optimal update complexity without bearing any extra space overhead.The overhead for computing actual answer and proofs is reduced significantly in contrast with previous methods based on bilinear-map accumulators.The intersection query comes up in keyword search,database queries and other applications.Indeed,our scheme can be effectively used in such scenarios.The security of our constructions is based on co-Computational Diffie-Hellman assumption.

关键词： Verifiable computation Authenticated data structures Set intersection Data outsourcing

作者: Tingting Wang Yanqin Zhu Xizhao Luo

作者单位: Soochow University Suzhou,China

会议类型: 国际会议

会议名称: 2014 International Conference on Cloud Computing and Internet of Things (CCIOT)(2014年第一届云计算和物联网国际会议)

会议地点: 长春

会议语种:英文

页码: 26-30

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