基于字符串排序的高效保密数据库查询

来源：软件学报杂志2018年第7期北京时间：

作者：李顺东,亢佳,杨晓艺,窦家维

单位：李顺东，陕西师范大学 计算机科学学院, 陕西 西安 71006211,亢佳，陕西师范大学 计算机科学学院, 陕西 西安 71006202,杨晓艺，陕西师范大学 计算机科学学院, 陕西 西安 71006203,窦家维，陕西师范大学 数学与信息科学学院, 陕西 西安 71006204

摘要：安全多方计算是近年来国际密码学界研究的热点问题之一，是信息社会隐私保护的核心技术.保密地将字符串按照字典序排序问题是一个全新的安全多方计算问题，在信息安全领域有重要的实际意义和广泛的应用前景.它不仅可以提高保密数据库查询的效率，还可以解决大数据情况下的百万富翁问题.为了保密地判断两个字符串按照字典序排序的位置关系，首先设计了一种新的编码方法和一种基于ElGamal加密算法的云外包计算下的同态加密方案，在此基础上提出了一个高效、简单的协议，并对协议进行了正确性和安全性分析，同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题协议应用于解决百万富翁问题，从根本上解决了大数据情况下的百万富翁问题.

关键词：密码学;安全多方计算;字符串排序;数据库保密查询;同态加密;百万富翁问题

基金资助：国家自然科学基金（61272435）