权重型n选1不经意传输协议_张辰旭.pdf

第 30 卷 第 4 期北京电子科技学院学报2022 年 12 月Vol.30 No.4Journal of Beijing Electronic Science and Technology InstituteDec.2022权重型 n 选 1 不经意传输协议张辰旭 张艳硕 张黎仙北京电子科技学院,北京市 100070摘 要:不经意传输协议(Oblivious Transfer Protocol,简称 OT 协议)是一种可保护双方隐私的通信协议,能使通信双方通过选择模糊化的方式传送消息。在现在越来越复杂的网络环境中,用户的实际应用需求越来越多样化,一般的 n 选 1 不经意传输协议已经很难满足我们多样化的需求。因此,在本文中我们基于 Diffie-Hellman 假设提出了权重型 n 选 1 不经意传输协议,该协议可以根据接收者的实际需求设置相应的权重来获取秘密消息,离散对数和随机预言机保证了该协议的安全性。同时这种形式的通信代价并不会因此而提高,相反还会优于一般的 n 选 1 不经意传输协议,因此它能够在保证自身通信代价的同时,满足我们在复杂网络环境中的多样化需求。最后,我们还进行了权重型 n 选 1 不经意传输方案的编程实现和相关测试,证明了权重型 n 选 1 不经意传输在未来应用方面的可能性。关键词:不经意传输;权重型;n 选 1;方案中图分类号:TN918 文献标识码:A文章编号:1672-464X(2022)4-24-39 基金项目:2020 年教育部新工科项目“新工科背景下数学课程群的教学改革与实践”、“信息安全”国家级一流本科专业建设点和国家重点研发计划基金资助项目(项目编号:2017YFB0801803)作者简介:张辰旭(2000-),男,本科在读,信息安全专业。E-mail:1367552349 张艳硕(1979-),男,博士,副教授,硕导,通信作者,从事密码数学理论和区块链技术研究。E-mail:zhang_yanshuo 张黎仙(2000-),女,学士,主要研究方向为密码理论及其应用。E-mail:1134562105 1 引言 不经意传输协议1,是一种可保护双方隐私的通信协议,它在一个消息集合中以一种不经意的方式来“秘密”获取部分消息。不经意传输协议保证了接收者在不知道发送者隐私的情况下获取秘密消息,同时保证了接收者自身的隐私不被发送者知道,因此不经意传输协议可以作为单独的协议应用到数字产品交易、电子选举方案等诸多信息交易中,还可以作为密码模块应用到众多安全多方计算当中。不经意传输的概念最初由 Rabin2在 1981年提出,从此以后不经意传输协议逐渐成为了密码学的一个重要组成部分,随着学者研究的不断深入,诸多的不经意传输协议相继问世。具体可分为以下 4 类:1 选 1 不经意传输协议2-3、2 选1 不经意传输协议4、n 选 1 不经意传输协议5、n 选 k 不经意传输协议6-7。在 Rabin 之后,Even8提出了一个 2 选 1 不经意传输协议,后来 Brassard5将 2 选 1 不经意传输协议推广到了 n 选 1 不经意传输协议,即发送者发送 n 条消息,接收者仅能获取其中的 1 条消息,并且发送者不知道接收者选择的是哪条消息。Naor 和 Pinkas9基于 Diffie-Hellman 假设提第 30 卷权重型 n 选 1 不经意传输协议 出了第一个 n 选 1 不经意传输协议,同时它也是一个可复用的 n 选 1 不经意传输协议。在本文中,我们提出了权重型不经意传输协议的概念,并对经典的 n 选 1 不经意传输协议Naor 方案进行了研究分析,将接收者以固定概率接收发送者消息进行了改进,新的方案可以根据接收者的实际需求设置相应的权重进行获取。而这种形式也满足了我们在复杂网络环境中的多样化需求,更好地适应目前复杂网络环境中不经意传输协议的信息传输需求。2 不经意传输协议简介 不经意传输的概念由 Rabin2在 1981 年提出后,不经意传输协议逐渐成为了密码学的一个重要组成部分,随着学者研究的不断深入,诸多的不经意传输协议相继问世。按照功能具体分为以下 4 类经典不经意传输协议:1 选 1 不经意传输协议2-3、2 选 1 不经意传输协议4、n 选 1不经 意 传 输 协 议5、n 选 k 不 经 意 传 输 协议6-7。具体介绍如下:(1)1 选 1 不经意传输协议:发送方将一条消息传送给接收方,接收方有 1/2 的概率接收成功,而发送方不知道接收方是否接收成功;(2)2 选 1 不经意传输协议:信息的发送方持有的消息集合包含两个秘密信息,接收方可以且仅可以成功恢复其中一条秘密信息,同时发送方并不知道他成功恢复的是哪一条秘密消息;(3)n 选 1 不经意传输协议:信息的发送方持有的消息集合包含 n 个秘密信息,而接收方在协议执行完毕后只能成功恢复其中一个秘密信息,同时发送方并不知道他成功恢复的是哪一条秘密消息;(4)n 选 k 不经意传输协议:信息的发送方持有的消息集合包含 n 个秘密信息,而接收方在协议执行完毕后只能成功恢复其中 k 个秘密信息,同时发送方并不知道他成功恢复的是哪 k 条秘密消息。对于一般性的不经意传输协议,要考虑三个性质:(1)正确性:只要发送方和接收方均遵守协议,那么执行完协议后接收方可以得到他想要的信息;(2)发送发的安全性:执行完协议后,接收方得不到除了他选择外的其他任何秘密消息;(3)接收方的安全性:执行完协议后,发送方不会知道他的选择。3 n 选 1 不经意传输协议 本节将重点介绍 n 选 1 不经意传输协议的发展历程和最新进展以及两个经典的 n 选 1 不经意传输协议方案。我们首先介绍一般的 n 选 1 不经意传输协议。Brassard5在 2 选 1 不经意传输协议的基础上推广到了 n 选 1 不经意传输协议,其具体概念为:发送方有 n 个消息 s1,s2,sn,接收方通过选择 i 1,2,n 的值来获得消息 si,但却不知道其他的秘密消息 sj(j i),或者这些 sj(j i)的组合消息,同时发送方也不知道接收方具体的选择 i,即获取的是哪一条消息。在独立的 n 选 1 不经意传输协议被设计出来之前,要实现 n 选 1 不经意传输协议的功能就要通过多次执行 2 选 1 不经意传输协议来实现,因此这些不同形式的不经意传输协议之间是可以相互转化的,但是这样的协议构造往往会造成很高的通信代价,因此人们将研究 n 选 1 不经意传输协议的主要精力放在了直接设计独立的 n选 1 不经意传输协议。Naor 和 Pinkas9提出了第一个独立的 n 选1 不经意传输协议,该协议是一个基于 Diffie-Hellman 假设并且可复用的 n 选1 不经意传输协议,大大减少了为实现 n 选 1 不经意传输功能而多次执行 2 选 1 不经意传输协议的通信代价;后来 Tzeng10基于 Diffie-Hellman 假设也提出了一个 n 选 1 的不经意传输协议,它没有初始化阶52北京电子科技学院学报2022 年段,但它的传输阶段效率还不如 Naor 的协议;2006 年叶君曜11等人基于门限思想提出了一个可复用的 n 选 1 的不经意传输协议;2008 年,张京良12等人对 Naor 方案进行了改进并应用到群签名当中;2015 年,Shin-Yan Chiou13等人提出了一种基于离散对数问题(DLP)的代理签名 n 选 1 的不经意传输方案,它结合了代理签名和不经意签名的优点,满足了两种签名的安全特性,由于该协议提供了收件人选择的模糊性,它非常适用于电子投票应用;2019 年,邱錫彦和陈俊名14两人首先提出了一种基于不经意传输的n 选 1 不经意传输签名方案,不仅满足了完整性、不可伪造性、隐私性的安全要求,而且还满足了选择限制和非重复性的要求,使得这种方案非常适合于多选电子投票的应用,并在手机上实现了该方案,使用户能够安全、方便地进行投票;在一些车联网(VANET)技术的特征匹配中,用户的隐私泄露问题已经严重威胁到人身安全并造成了相当大的经济损失,2020 年 WangXianmin15等人构建了一个高效的 OT 协议,被采用来给出一个带有平等测试的 PSI 协议,VANET 的两方可以获得他们的特征集的交集,而这种交集之外的任何信息都是不可用的。因此,内部攻击者无法从双方的特征匹配中获得任何有用的信息,双方也无法获得对方的额外数据;2020 年 3 月,WahaballaAbubaker16等人提出了一个安全的 n 选 1 不经意传输协议,该协议具有隐藏的访问控制和基于确定性有限自动机(DFA)的功能加密的外包解密(HACOT-DFA),可以应用在车辆传感器中,传感器的数据被处理并以记录的形式存储在车载传感器数据库中,这些记录可以被其他车辆或路边单位访问和共享,目的是提高道路安全。然而,这些记录可能包含非常敏感的信息,如车辆的识别码和位置,这些信息需要特别的保护,而该协议就确保了车辆用户的隐私和保密性;2020 年 6 月,WangXiaotian17等人在 ECDH 的假设下,设计了一种新型的 n 选 1 不经意传输协议。该协议可以在恶意模式下安全实现,在 n 个输入值中选择其中的 1 个。在此假设下定义了 RAND 函数,并给出了安全定义,构建了发送方和接收方的安全交互模式。最后分析了该协议的正确性,并给出了安全证明。该协议具有常数级的交互复杂度,计算和通信复杂度只与 n 线性有关;2020 年 8 月,Nibedita Kundu18等人利用多变量公钥密码学(MPKC)的 OT 协议的构造,提出了一个 2 选 1 的不经意传输协议,而我们可以进行 n 次的复用以实现 n 选 1 不经意传输的功能,该方案的安全性是在多变量二次方(MQ)问题的硬度下实现的,该设计是第一个基于 MPKC 的后量子 OT 协议;2020 年 9 月,Shanshan Zhang19-20利用格上不经意传输协议的特点,设计了一个使用决策性Diffie-Hellman 假设和混淆不可区分的基于 LWE的 n 选 1 不经意传输协议,该协议主要的工具包括基于 LWE 的双模式密码系统和安全的不可区分性混淆,保证了该 n 选 1 不经意传输协议的安全性;2021 年 5 月,Saeid Esmaeilzade21等人采用了非对称同态加密的概念,使用了一些著名的同态加密方案(如 RSA、Paillier 和 NTRU)来实例化他们的结构,以获得具体的不经意传输协议,提出了一个通用的结构来建立简单而高效的 n 选 1 不经意传输协议,该协议的通用结构在通用可组合框架中是安全的;2021 年 11 月,Wang Ping22等人在量子信道的帮助下,设计了一种新型的计算安全的量子 n 选 1 不经意传输(QOT)协议,其最低假设要求是:单向函数的存在。独立的 n 选 1 不经意传输协议虽然在降低了通信代价的同时,实现了相应的通信功能,但这种功能是不完善的,因为它没有考虑到接收方的实际需求,因此我们给出了权重型 n 选 1 不经意传输协议的定义和性质,并在下一节提出了具体的设计方案,下面我们介绍几种经典的 n 选 1不经意传输协议。3.1 Naor 方案本节对 Naor7的 n 选 1 不经意传输协议进62第 30 卷权重型 n 选 1 不经意传输协议 行描述,具体过程如下:初始化:Alice 选择随机数 C1,C2,CN-1和 r,并计算(Ci)r和 gr的值。Bob 可以获得 C1,C2,CN-1和 gr的值。其中 1 i N-1,g 为Zq的生成元。传 输 阶 段:Alice 的 输 入 为(M0,M1,MN-1)。Bob 的输入为 0,N-1(他选择获取 M)。(1)Bob 选择 k Zq,并设置 PK=gk。如果 0,将计算 PK0=C/PK,并向 Alice 发送 PK0,并且已经可以计算解密密钥(gr)k=(PK)r;(2)Alice计 算(PK0)r,(PKi)r