曼哈顿距离的保密计算*
2019-09-10方乐笛李顺东窦家维
密码学报 2019年4期
方乐笛,李顺东,窦家维
1.陕西师范大学 计算机科学学院,西安710119
2.陕西师范大学 数学与信息科学学院,西安710119
1 引言
随着互联网、物联网和大数据技术的迅速发展与日益普及,隐私信息与机密信息极易泄露,这使得隐私保护变得尤为重要.安全多方计算(secure multiparty computation,SMC)作为隐私保护的核心技术,成为了国际密码学界的研究热点[1].安全多方计算最初于1982年由Yao[2]以百万富翁问题提出,它由两个参与者组成,之后Ben-or和Goldwasser[3]将其扩展到了多个参与者,学术界统称为安全多方计算.安全多方计算的奇妙之处就在于可以使参与者在不泄露自己隐私数据的情况下,保密地使参与者利用自己的隐私数据联合进行某种运算,从而达到合作共赢的目的,也最大限度的平衡了参与者隐私性与合作性的需求.
安全多方计算的研究在计算科学领域、密码学与信息安全中有着举足轻重的作用,是信息社会隐私保护的核心技术,其主要可分为以下几类:(1)保密的科学计算问题[4–13];(2)保密的计算几何问题[14–18];(3)保密的统计分析问题;(4)保密的数据挖掘问题[19];(5)保密的数据库查询问题;(6)其他安全多方计算问题.虽然人们已经研究了很多安全多方计算问题,并提出了这些问题的解决方案,但这些方案的效率都亟待提高,此外还有很多新的问题需要研究,曼哈顿距离问题就是需要研究的新问题。
曼哈顿距离(Manhattan distance,MD)又称出租车距离,是指两个垂直方向上的距离之和.P(x1,y1)和Q(x2,y2)之间的曼哈顿距离MD=|x1−x2| +|y1−y2|.保密计算两……
登录APP查看全文
