Shared and Searchable Encrypted

一、摘要

本文通过基于El-Gamal[1]的代理加密算法（proxy encryption algorithm）实现了多用户对加密数据库的上传和下载。该方案不需要用户共享密钥，可以实现用户注册和删除的透明性。

二、主要工作 （核心场景、框架或者算法）

本文首先提出了两个场景，第一个是企业用户保护商业数据的场景，第二个是个人用户保护个人医疗隐私的场景。在介绍Multi-User的方案之前需要先介绍data和keyword各自的加密方案，具体实现如下：

（一）data加密方案PE-Encryption

• 首先由可信密钥服务器生成密钥 $(G,g,q,x)$，其中 $(G,g,q)$ 作为公共参数广播，而 $x$ 作为全局唯一的主密钥由密钥服务器保存。
• 对于用户 $i$ ，密钥服务器选取素数 $x_{i1}$ ，并得到 $x_{i2}= x-x_{i1}$ ；将 $x_{i1}$ 发送给用户 $i$ ，将 $(i，x_{i2})$ 发送给服务器。
• 用户加密数据 $m$ 时，选取素数 $r$ ，根据密钥 $x_{i1}$ 对 $m$ 进行半加密，生成密文 $c^{{’}_{i(m)}=(g}r,g^{rx_{i1}}m)$ 并上传给服务器。
• 服务器根据用户id，找到对应的 $x_{i2}$，对密文 $c’$ 再进行加密得到最终的密文 $c$ ，存储在服务器中。
• 当用户 $j$ 想要获取该文件时，服务器先根据用户id找到 $x_{j2}$ 进行半解密，得到密文 $c’$ ，并发送给用户 $j$ 。

• 用户 $j$ 得到密文 $c’$ 后，根据私钥 $x_{j1}$ 解密得到最终的数据 $m$。

  
  enc-dec.png

（二）keyword加密方案KE-Encryption

与data加密方案类似，在keyword加密方案中，需要可信密钥服务器将 $(G,g,q,h,H,f)$ 进行广播，其中 $h=g^x$ ，$H$ 为哈希函数， $f$ 为伪随机函数。该方案中，将keyword经过伪随机函数计算之后的值记作 $σ$ ，将 $r+σ$ 作为El-Gamal方案的参数进行计算，并将半加密结果上传给服务器，服务器根据密文进行进一步加密后生成 $(c_1,c_2)= [h^{r+σ},H(hr)]=[h^r g^{xσ_w},H(hr)]$ 存储在服务器中。

（三）Multi-User可搜索加密方案SE-Encryption

• 可信密钥服务器将 $(G,g,q,h,H,f)$ 进行广播，并将 $x$ 作为主密钥保留。
• 用户新增时，可信密钥服务器选取用户密钥 $K_{u_i}$，并计算得到服务器密钥 $K_{s_i}$，分别发送给用户和服务器。
• 用户上传文件时，根据data和keyword的加密方案进行加密。并上传给服务器进行二次加密和存储。

multi1.png

• 用户i搜索时，根据用户i的密钥Kui以及随机素数r，生成trapdoor $T_i(w)=(t1,t2)$ ，上传给服务器。
• 服务器根据用户 $i$ 上传的trapdoor，以及用户 $i$ 的密钥 $x_{i2}$ 计算 $T=t1^{x_{i2}} t2 = g^{xσ_w}$ ,计算完成后对存储的关键字集合 $(c_1,c_2) = [h^r g^{xσ_w},H(hr)]$ 进行配对搜索，若 $c_2=H(c_1 T^{-1})$ 则配对成功，将该关键字对应的data半解密后发送给用户 $i$。
• 用户 $i$ 得到半解密的数据后，再用密钥 $K_{u_i}$ 进行完全解密。

• 用户 $i$ 的删除过程只需要服务器删除用户存储在服务器上的密钥 $x_{i2}$ 即可。

  
  multi2.png

三、优点（动机、算法、写作）

• 不需要用户共享任何密钥
• 提到了数据的增删改查，以往的方案中基本只涉及到增加和查询。

四、缺点 （算法缺陷、写作逻辑漏洞、攻击场景漏洞、工作完成度）

• 一旦发生用户和服务器共谋，整个服务器上的资料将全部泄露。
• 搜索效率低，$O(m)$，$m$为整个数据集
• 无法隐藏search pattern

五、链接

[1]【El Gamal】https://en.wikipedia.org/wiki/ElGamal_encryption