隐私计算-Oblivious Transfer算法理论研究与实践

2022-12-19 17:28:05 浏览数 (1)

导读

近年来，统计分析、数据挖掘、机器学习等大数据相关技术不断发展，其应用已经渗透到各行各业的方方面面。这些技术在给人们生活带来诸多便利的同时，也造成了前所未有的隐私安全问题。因此，隐私安全保护已经越来越受到人们的关注，在法律层面，政府出台了个保法相关条例，如2021年8月13届人大会议通过的《中华人民共和国个人信息保护法》1；在技术层面，各研究机构和企业的安全计算专家也在竭尽所能的研究安全计算相关课题，并取得了突破性进展。本人近期研究的隐私安全计算Oblivious Transfer算法，又称不经意传输算法（后文简称OT算法）便是安全计算领域非常重要的算法之一，下文将详细阐述本人在OT算法的研究、优化及其应用。隐私查询及PSI应用已在微信笛卡尔平台及公司太极平台有相应的组件，示例工作流见附录。

安全计算概述

     安全计算，又称安全多方计算（MPC: Secure Multi-party Computation2），是指多个参与方在不透露各自数据的前提下，按照约定的安全计算协议，协同完成某个共同的计算任务。形式化描述为：多个参与方$C_1$，$C_2$，$C_3$ $...$ $C_n$拥有的数据分别为$x_1$，$x_2$，$x_3$ $...$ $x_n$，在安全协议$SP$的约束下，协同完成函数$f(x_1,x_2,x_3...x_n)$的计算。

     安全多方计算起源于1982年姚期智的百万富翁问题（Yao's Millionaires' problem3），这个问题讨论了两个百万富翁，Alice和Bob，他们有兴趣知道他们中谁更富有，但是不透露他们的实际财富。百万富翁问题是密码学中的一个重要问题，其解决方案被应用于电子商务和数据挖掘中。多方安全计算方法大体上可以分为两类，一类是基于噪音的，以差分隐私(Differential Privacy)为代表；另一类是基于密码学的，将原数据编码或者加密，使得人们很难从加密后的数据还原出原始数据，这类主要包括：同态加密(HE: Homomorphic Encryption)、不经意传输(OT: Oblivious Transfer)、混淆电路(GC: Garbled Circuit)、密钥共享(SS: Secret Sharing)等。安全多方计算是电子选举、门限签名以及电子拍卖等诸多应用的密码学基础4。

OT算法研究

     OT是一种密码学协议5，是混淆电路6背后的密码学思想，其解决的问题是：假设A有n份数据$x_1$，$x_2$，$x_3$ $...$ $x_n$，B想知道其中的一个$x_i$($i in 1cdots n$)，通过OT协议，B获得了$x_i$，但不知道$x_j$($j neq i$)，同时A不知道$i$。OT算法的形式有1-out-of-n和k-out-of-n，在实际应用中，OT算法的实现方式有多种，比较经典的有基于离散对数的、以及基于RSA原理的实现。

1-out-of-n OT算法

     1-out-of-n OT协议可以被定义为1-out-of-2 OT协议的自然泛化。以下详细介绍基于RSA的实现方式，在1-out-of-n OT协议7中，发送方A有n个消息$x_1$，$x_2$，$x_3$ $...$ $x_n$，接收方B有一个选择$i$($i in 1cdots n$)，接收方希望收到$x_i$，而发送方不知道$i$，同时发送方希望保证接收方能且仅能收到n个消息中的一个，即$x_i$，但接收方不知道$x_j$($j neq i$)。详细步骤可以用RSA加密实现如下：

  • A生成一对RSA公钥私钥对，同时生成n个随机字符串$r_1$，$r_2$，$r_3$ $...$ $r_n$
  • A将公钥pubKey发送给B，并将n个随机字符串发送给B
  • B生成一个随机数y，用pubKey加密随机数y，得到encryptedY，再和选择数据$x_i$对应的随机字符串$r_i$做异或操作，得到encryptedYOp
  • B将加密后的encryptedYOp发送给A
  • A遍历$x_1$，$x_2$，$x_3$ $...$ $x_n$，对于$x_j$($j in 1cdots n$)，用$r_j$与encryptedYOp异或再用私钥priKey解密，得到$decryptedY_j$，再和$x_j$异或得到$decryptedM_j$
  • A将$decryptedM_0$, $decryptedM_1$, ... , $decryptedM_n$发送给B
  • B用自己的随机数y与得到的$decryptedM_0$, $decryptedM_1$, ... , $decryptedM_n$分别进行异或，得到自己想要的值$m_i$($m_i = x_i$)，其他的$m_j$($j neq i$)都是乱码
基于RSA的1-out-of-n OT实现原理基于RSA的1-out-of-n OT实现原理

k-out-of-n OT算法

     在k-out-of-n OT协议中810，发送方A有n个消息$X1$，$X_2$，$X_3$ $...$ $X_n$，接收方B有k个不同的选择$s_i$($s_i in 1cdots n, i in 1cdots k$)，接收方希望收到$X{si}$，而发送方不知道$s_i$，同时发送方希望保证接收方能且仅能收到n个消息中的k个，即$X{s_i}$，但接收方不知道$X_j$($j neq s_i$)。详细步骤可以用RSA加密实现如下：

  • A生成一对RSA公钥私钥对，同时生成n个随机字符串$R_1$，$R_2$，$R_3$ $...$ $R_n$
  • A将公钥pubKey发送给B，并将n个随机字符串发送给B
  • B生成k个随机数$Y1$, $Y_2$...$Y_k$, 用pubKey分别加密随机数$Y_1$, $Y_2$...$Y_k$，得到$encryptedY_1$, $encryptedY_2$, ..., $encryptedY_k$, 再分别和选择数据$X{si}$对应的随机字符串$R{s_i}$做异或操作，得到$encryptedYOp_1$, $encryptedYOp_2$, ..., $encryptedYOp_k$
  • B将加密后的$encryptedYOp_1$, $encryptedYOp_2$, ..., $encryptedYOp_k$发送给A
  • A遍历$encryptedY1$, $encryptedY_2$, ..., $encryptedY_k$，对于$encryptedY_i$($i in 1cdots k$)，与$X_1$，$X_2$，$X_3$ $...$ $X_n$对应的$R_j$异或再用私钥priKey解密，得到$decryptedY{sij}$，再和$X_j$异或得到$decryptedM{s_ij}$, 共$k times n$条数据
  • A将$k times n$条数据$decryptedM_{s_ij}$发送给B
  • B遍历发送过来的$k times n$条数据，用自己的随机数$Y_1$, $Y_2$...$Y_k$分别进行异或，得到自己想要k条数据，其他的$(k - 1) times n$条数据都是乱码
基于RSA的k-out-of-n OT实现原理基于RSA的k-out-of-n OT实现原理

OT算法优化研究

  上述OT算法中1-out-of-n模式中，接收端加密环节时间复杂度是，发送端解密环节时间复杂度是，此模式下已经达到了最优复杂度。而k-out-of-n模式却存在些许不足。

现有OT算法的不足

  在k-out-of-n OT算法模式中，接收端加密环节时间复杂度是$O(1)$，发送端解密环节时间复杂度是$O(n)$，此模式下已经达到了最优复杂度。而k-out-of-n模式却存在些许不足。现有OT算法的不足     在k-out-of-n OT算法模式中，OT算法接收方和发送方在加解密环节存在以下不足之处：

  • 发送方解密时需要遍历$k times n$次，并生成$k times n$条数据发给接收方，即时间复杂度和空间复杂度均为$O(k times n)$
  • 接收方接受到$k times n$条数据后，要遍历$k times n$次，得到$k times n$条消息，其中k条是自己想要的数据，其他$(k - 1) times n$条数据是乱码，时间复杂度和空间复杂度同样为$O(k times n)$k值限制非安全模式优化（v1）     现有OT算法中，对于k-out-of-n模式，接收者需要从发送者的n条消息中获取k条，但是发送者在解密环节以及接收者从接收到的数据还原想要的数据时时间和空间复杂度都过高，观察k-out-of-n的实现原理不难发现，其关键问题在于对于接收方发送的每一条加密数据，发送方都要像1-out-of-n的实现方式一样遍历一遍其拥有的n条数据，本人从接收方加密数据开始研究，提出以下优化解决方案：

前置约定

  • A为发送方，拥有$n$条数据$X_1$，$X_2$，$X_3$ $...$ $X_n$，以及生成的与其对应的n个随机字符串$R_1$，$R_2$，$R_3$ $...$ $R_n$， 公钥pubKey，私钥priKey；
  • B为接收方，有A的n条数据的k个选择，即长度为k的索引不同的向量$s_1$，$s_2$，$s_3$ $...$ $s_k$，其中$s_i in 1 cdots n$，以及随机字符串$y$，$y$用A的公钥pubKey加密后为$ey$。

算法优化推导

  • B加密之后要传给A的数据，其中$R{s_i}^-$是$R{si}$的逻辑取反，$k$是发送方A用来限制接收方B获取数据条数的。 $$begin{aligned} ey R{s1}R{s2}R{s3}...R{sk} (1) ey^- R{s1}^-R{s2}^-R{s3}^-...R{s_k}^- (2) k (3) end{aligned}$$
  • A解密阶段，遍历每一个数据，对于数据$Xi， i in 1 cdots n$，$R{i}$是对应的随机字符串，$R{i}^-$是$R{i}$的逻辑取反。 $$begin{aligned} (ey R{s_1}R{s2}R{s3}...R{sk}) times R_i^-_undefined&=ey times R_i^- R{s_1}R{s2}R{s3}...R{sk}R_i^- &=ey times R_i^- R{s1}R{s2}R{s3}...R{sj}R_i^-...R{s_k} (4)

(ey^- R{s_1}^-R{s2}^-R{s3}^-...R{s_k}^-) times R_i

&=ey^- times Ri R{s1}^-R{s2}^-R{s3}^-...R{s_k}^-R_i

&=ey^- times Ri R{s1}^-R{s2}^-R{s3}^-...R{sj}^-R_i...R{s_k}^- (5)

end{aligned}$$

     如果X_i是B想要的数据，即$i in s_1 cdots s_k$，假设$s_j = i$，则有

$$begin{aligned}

R_{s_j}R_i^- &= 0 (6)

R_{s_j}^-R_i &= 0 (7)

ey times Ri^- R{s1}R{s2}R{s3}...R{sj}R_i^-...R{s_k} &= ey times R_i^- (8)

ey^- times Ri R{s1}^-R{s2}^-R{s3}^-...R{sj}^-R_i...R{s_k}^- &= ey^- times R_i (9)

end{aligned}$$

     公式(8)和(9)做或操作，则有

$$begin{aligned}

ey times R_i^- ey^- times R_i &= ey ⊕ R_i (10)

end{aligned}$$

     由公式(10)再和$R_{s_i}$做异或操作，则有

$$begin{aligned}

ey ⊕ R_i ⊕ R_i &= ey (11)

end{aligned}$$

     由公式(11)能得到B加密$y$后的值$ey$，A再用自己的私钥priKey解密$ey$得到$y_i$，当且仅当X_i是B想要的数据，即$i in s_1 cdots s_k$时，$y_i = y$，A再用解密后$y_i$与自己的数据做异或操作$y_i ⊕ X_i$，并将$y_1 ⊕ X_1, y_2 ⊕ X_2, y_3 ⊕ X_3, ..., y_n ⊕ X_n$这n条数据发送给B。

     B收到A的n条数据后，遍历每一条数据，对于$y_i ⊕ X_i$，用自己的随机字符串$y$与之再进行异或操作，当X_i是B想要的数据，即$i in s_1 cdots s_k$时，$y_i = y$时，则有

$$begin{aligned}

y_i ⊕ X_i ⊕ y &= y ⊕ y⊕ X_i

&= X_i (12)

end{aligned}$$

     通过以上公式推导，B最终得到$n$条数据中，只有自己想要的那$k$条数据是A的原始数据，其他$n-k$条数据都是随机乱码，本次优在保证获得正确结果的前提下，时间和空间复杂度都下降了很多，主要优化了以下几点：

  1. 接收方B从原来的发送$k$条数据变成了发送$3$条数据，空间复杂度从$O(k)$降到了$O(1)$；
  2. 发送方A在解密数据时只需要遍历$n$条数据，并产生$n$条数据发送给接收方B，时间和空间复杂度均从$O(k times n)$降到了$O(n)$；
  3. 接收方B获取数据时只需要遍历$n$次，并产出$n$条数据，时间和空间复杂度均从$O(k times n)$降到了$O(n)$。k值限制安全模式优化（v2）     上述k-out-of-n OT算法优化方案$v1$版从发送方和接收方交互环节中做了很大程度的优化，使得时间和空间复杂度降低显著。但是从上述接收方加密后的数据发给发送方的数据中的$k$值是直接传的，接收方如果是恶意的，可以修改算法源码篡改$k$值，从而绕过发送方对接收方请求数据量的限制，即上述优化存在$k$值限制非安全问题。

     通过对公式(1)和(2)进行拆分，可分别得到

$$begin{aligned}

ey R{s_1}R{s2}R{s3}...R{sk} &= (ey R{s1})(ey R{s2})(ey R{s3})...(ey R{s_k}) (13)

ey^- R{s_1}^-R{s2}^-R{s3}^-...R{sk}^- &= (ey^- R{s1}^-)(ey^- R{s2}^-)(ey^- R{s3}^-)...(ey^- R{s_k}^-) (14)

end{aligned}$$

     通过公式(13)和(14)的因式分解，可以将分解数据$(ey R{s_1})$, $(ey R{s2})$, $(ey R{s3})$...$(ey R{sk})$以及$(ey^- R{s1}^-)$, $(ey^- R{s2}^-)$, $(ey^- R{s3}^-)$...$(ey^- R{s_k}^-)$共$2k$条数据发送给A，A收到数据后可以通过加密数据条数除以2来限制接收方请求数据条数，其他步骤和$v1$版优化方案一样，这样不仅降低了时间和空间复杂度，还保证了$k$值限制安全性。

基于k-out-of-n OT 变体实现PSI

前置约定

  • A为Guest方，拥有$m$条数据$X_1$，$X_2$，$X_3$ $...$ $X_m$，以及生成的与其对应的m个信息摘要$XR_1$，$XR_2$，$XR_3$ $...$ $XR_m$， 对称密钥$symKey$, 对称加密函数$symEnc$；
  • B为Host方，拥有$n$条数据$Y_1$，$Y_2$，$Y_3$ $...$ $Y_n$，以及生成的与其对应的n个信息摘要$YR_1$，$YR_2$，$YR_3$ $...$ $YR_n$；
  • A与B的交集为$Z{s_1}$，$Z{s2}$，$Z{s3}$ $...$ $Z{s_k}$，其中$s_k le min(m,n) $。

算法优化推导

  • A运算加密之后要传给B的数据，其中$XRi$表示第$i$个数据的信息摘要，$symKey$是A发给B的对称密钥。 $$begin{aligned} coXor&= XR_1⊕XR_2⊕XR_3...XR_m (15) E_i&= coXor⊕XR_i symEnc(XR_i, symKey) &= XR_1⊕XR_2⊕XR_3 ... XR_m⊕XR_i symEnc(XR_i, symKey) &= XR_1⊕XR_2 ... ⊕XR{i-1}⊕XR_{i 1} ... XR_m symEnc(XR_i, symKey) (16) &symKey (17) end{aligned}$$
  • B从A收到$coXor, E_i, symKey$后，遍历每一条数据，对于$YR_j$，有 $$begin{aligned} F_i&= coXor⊕YR_j symEnc(YR_j, symKey) &= XR_1⊕XR_2⊕XR_3 ... XR_m⊕YR_j symEnc(YR_j, symKey) (18) end{aligned}$$
  • 对于公式（18），当且仅当$XRi = YR_j$时，有以下公式 $$begin{aligned} F_i&= XR_1⊕XR_2⊕XR_3 ... XR_m⊕YR_j symEnc(YR_j, symKey) &= XR_1⊕XR_2 ... ⊕XR{i-1}⊕XR{i 1} ... XR_m symEnc(YR_j, symKey) &= XR_1⊕XR_2 ... ⊕XR{i-1}⊕XR_{i 1} ... XR_m symEnc(XR_i, symKey) &= E_i (19) end{aligned}$$
  • B将$E1, E_2, E_3 ... E_m$与得到的$F_1, F_2, F_3 ... F_n$进行求交，根据以上公式推导，当且仅当$XR_i = YR_j$时，有$E_i = E_j$，由以上过程便可得到双方交集数据$Z{s1}$，$Z{s2}$，$Z{s3}$ $...$ $Z{s_k}$，而不会泄漏除交集之外的任何其他数据。OT算法应用     基于优化后的k-out-of-n 模式的OT算法，开发了离线OT算法服务端和客户端应用，可以应用于双方大规模隐私数据查询，同时基于改进扩展的k-out-of-n OT开发了安全样本对齐组件，与现有最优的方案相比有较大的性能提升。大规模隐私数据查询离线OT算法服务端     OT算法服务端基于Spark大数据计算框架，使用研究优化的k-out-of-n OT算法，为多个客户端同时提供大规模隐私数据查询，OT算法服务端设置参数如下： | 参数名 | 参数描述 | 参数类型 | | :--- | :---: | ---: | | tdw源数据路径 | 指定tdw库表和分区， 格式为tdw://db/table/partition | string | | 获取源数据sql| 源数据sql， 格式为select * from _table where xxx=yyy| string | | 服务器url路径 | 指定tdw库表和分区， 格式为tdw://db/table/partition | string | | 源数据key | 源数据key，如uin | string | | 源数据限制数 | 限制服务端数据量 | long | | 源数据限制维度 | 限制服务端数据字段数 | long | | 客户端限制数 | 限制同时请求的客户端数目 | long | | 每次请求限制数 | 限制每个客户端每次请求数据量 | long | | 服务器rpc端口 | 服务器rpc端口，默认9001 | int | | 保持服务运行 | 是否保持rpc服务运行，为下次请求提供服务 | boolean | | 服务停止延时 | 服务停止延时秒数，关闭保持服务运行有效 | long | | 是否缓存数据 | 是否缓存数据 | boolean | | 缓存超时时间 | 缓存超时时间，格式：2h、2m、2s | string | | 大数据模式 | 是否大数据模式，建议客户端携带数据量较大时开启 | boolean |离线OT算法客户端     OT算法客户端同样是基于Spark大数据计算框架，使用研究优化的k-out-of-n 模式的OT算法库，在满足OT算法服务端约定条件下，多个OT算法客户端可同时像一个服务端查询大批量数据，OT算法客户端设置参数如下： | 参数名 | 参数描述 | 参数类型 | | :--- | :---: | ---: | | tdw客户端数据库 | 指定tdw数据库 | string | | tdw源数据表| 指定tdw源数据表| string | | tdw输出结果表 | 指定tdw输出结果表| string | | 源数据key | 源数据key，如uin | string | | tdw源数据标签名 | tdw源数据标签名，数据为0或1 | string | | rpc服务url路径 | 指定tdw库表和分区， 格式为tdw://db/table/partition | string | | tdw中间数据库 | tdw中间结果数据库 | long | | 中间结果通过tdw | 中间结果是否通过tdw | boolean | | 大数据模式 | 是否大数据模式，建议客户端携带数据量较大时开启 | boolean | 运行效率      在OT服务端数据量为185万，200个维度，客户端数据量为556万的规模下，3个OT算法客户端同时请求一个OT算法服务端，运行效果如下图所示，时间均在10分钟左右。

     其中OT算法客户端想要的数据就是OT算法服务端对应的数据，其他数据除了数据key（uin）以外其他都是NULL。

安全样本对齐

     安全样本对齐，又称隐私集合求交（Private Set Intersection, PSI），是指多方（一般是两方）在进行样本对齐的过程中，各方不会获取其他方除交集之外的任何信息。安全样本对齐的实现方案有多种，如基于Blind RSA的、基于1-out-2 OT设计的不经意伪随机函数（Oblivious Pseudorandom Functions, OPRF）协议来实现的等。已有方案中性能最好的是基于1-out-2 OT实现的，但其通信复杂度依然较高。

     本文基于改进的k-out-of-n OT进行扩展，应用于安全样本对齐，性能比现有的OT-PSI算法有显著提升。

性能对比

| 实验id |1（v1版） | 2（v1版） | 3（v1版） |4 （v2版）

| :--- | :---: | :---: | :---: |

| guest数据量 | 100万 | 100万 | 100万 | 1000万 |

| host数据量 | 100万 | 500万 | 1000万 | 1000万 |

| k-out-of-n OT运行时间 | 2分22秒 | 3分15秒 | 6分52秒 | 7分06秒 |

| PowerFL OT运行时间 | 3分04秒 | 7分02秒 | 14分45秒 | 16分41秒 |

| k-out-of-n OT资源配置 | num-executors:1,

executor-mem:10g | num-executors:1,

executor-mem:10g | num-executors:1,

executor-mem:10g | num-executors:4,

executor-mem:10g |

| PowerFL OT资源配置 | num-executors:1,

executor-mem:10g | num-executors:2,

executor-mem:10g | num-executors:4,

executor-mem:10g | num-executors:4,

executor-mem:10g |

     根据以上性能对比可以看出：对于v1版在非平衡场景下（即在两方ID数量相差悬殊的情况下），其性能比PowerFL框架现有的OT-PSI算法要快好几倍；在平衡场景下（即两方ID数量相当的情况下），性能与现有的OT-PSI算法一样。因实际业务场景大多是非平衡场景，所以v1版基于 k-out-of-n OT 的PSI算法的实际应用价值很大。v2版做了进一步的性能优化，使得在平衡场景下，其性能比现有的OT-PSI快1倍，非平衡场景性能和数据相差量成正比，即数据量相差越大，性能越好。

参考文献

<small>

  1. http://www.npc.gov.cn/npc/c30834/202108/a8c4e3672c74491a80b53a172bb753fe.shtml

</small>

  1. https://en.wikipedia.org/wiki/Secure_multi-party_computation
  2. https://en.wikipedia.org/wiki/Yao's_Millionaires'_problem
  3. https://baike.baidu.com/item/安全多方计算/6217146
  4. https://en.wikipedia.org/wiki/Oblivious_transfer
  5. Bellare, Mihir et al. “Foundations of garbled circuits.” Proceedings of the 2012 ACM conference on Computer and communications security (2012): n. pag.
  6. Orrù, M., Orsini, E., & Scholl, P. (2016). Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection. IACR Cryptol. ePrint Arch., 2016, 933.
  7. Chu, C., & Tzeng, W. (2005). Efficient k-Out-of-n Oblivious Transfer Schemes with Adaptive and Non-adaptive Queries. Public Key Cryptography.
  8. Chou, J., Wu, C., & Chen, Y. (2011). A Novel k-out-of-n Oblivious Transfer Protocol from Bilinear Pairing. IACR Cryptol. ePrint Arch., 2011, 150.
  9. Lai, J., Mu, Y., Guo, F., Chen, R., & Ma, S. (2018). Efficient k-out-of-n oblivious transfer scheme with the ideal communication cost. Theor. Comput. Sci., 714, 15-26.
数据挖掘 数据库 大数据 sql hadoop

0 人点赞