【密码学】高级密码学-2

文章目录

🍬第⑤部分由L3H_CoLin编写，有一些修改。🍬

5 可搜索对称加密（SSE）

Song, Dawn Xiaoding, David Wagner, and Adrian Perrig. “Practical techniques for searches on encrypted data.” Proceeding 2000
IEEE Symposium on Security and Privacy. S&P 2000. IEEE, 2000.

5.1 应用背景

• 数据的安全外包存储 - 利用密码算法加密明文数据，使得云平台无法获得额外信息- 解决了数据在不可信云平台上安全存储与共享的问题
• 安全的弊端 - 用户无法对数据进行关键字检索，因为加密过程完全破坏了明文数据的语义，使得云平台无法对密文数据检索- 将明文数据下载到本地，解密后再检索，这个过程开销太大不实用- 赋予云平台解密数据的能力，让云平台能够根据明文进行检索，但云平台不可信，容易导致数据泄露

  简而言之，数据的外包存储的对象都是加密数据，用户无法对数据进行检索，用户一旦想要获取含特定关键字的文件，只能下载全部密文文件，解密后再检索出文件。

5.2 SSE的应用模型

5.3 最初的SSE方案

  上述方法的不足是效率太低，对于计算出来的T’，需要和每一个密文逐一比较。
  改进方法：为具有相同关键字的可搜索密文构造隐藏的链式结构。服务器查询时只需要沿着这条链查询下去即可，检索复杂度可以减小至亚线性级。但服务器在收到对应的关键字检索请求之前不能获取任何关于该链的信息。

  除此之外，它的安全性也是不能保证的，可以通过简单的频率攻击，对关键字进行猜测。在Song的方案中，每一个关键字所对应的搜索陷门是固定的(即关键字和搜索陷门之间存在简单的一一映射的关系)。在攻击者眼中，虽然将随机数引入到可搜索加密的算法后能够保证密文的不可区分性，但是可搜索加密比常规加密多一个检索陷门(信息更多)，对于可搜索加密的安全性定义来说是远远不够的。

5.4 SSE方案

方案定义

•                                     Setup                            ⁡                                  \operatorname{Setup}                     Setup协议：   - 输入：安全参数                                                  λ                                          \lambda                           λ- 输出：私钥                                                  K                                  ⁡                                          \operatorname{K}                           K、本地状态                                                  σ                                          \sigma                           σ和加密数据库                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB，其中私钥与本地状态由客户端秘密保存，加密数据库存放在客户端
  

•                                     Update                            ⁡                                  \operatorname{Update}                     Update协议：   - 输入：客户端输入私钥                                                  K                                  ⁡                                          \operatorname{K}                           K、本地状态                                                  σ                                          \sigma                           σ、密文操作                                                  op∈(w,id)                                  ⁡                                          \operatorname{op\in(w,id)}                           op∈(w,id)；服务器输入加密数据库                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB- 输出：根据                                                  op                                  ⁡                                          \operatorname{op}                           op的值，客户端将                                                  (w,id)                                  ⁡                                          \operatorname{(w,id)}                           (w,id)对应的可搜索密文添加到                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB或从                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB中删除
  

•                                     Search                            ⁡                                  \operatorname{Search}                     Search协议：   - 输入：客户端输入私钥                                                  K                                  ⁡                                          \operatorname{K}                           K、本地状态                                                  σ                                          \sigma                           σ、要检索的关键字                                                  w                                  ⁡                                          \operatorname{w}                           w，服务端输入加密数据库                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB- 输出：服务器返回                                                  EDB                                  ⁡                                          \operatorname{EDB}                           EDB中所有与                                                  w                                  ⁡                                          \operatorname{w}                           w相匹配的检索结果
  

方案构造

5.5 SSE存在的问题

• 可搜索密文的删除问题 - 逻辑删除，易于保证安全性- 物理删除，容易破坏安全性
• 多样化检索的问题 - 模糊检索、范围检索等
• 安全性与效率的博弈 - 现有提出的SSE无法避免信息泄露- 无信息泄露的SSE，也称“隐私信息抽取”，大量地采用了“不经意”随机访问机协议，性能低下

6 可搜索公钥加密(PEKS)

6.1 PEKS的起源

  2004年，由Boneh等人针对加密邮件系统的检测问题提出，成功实现了在邮件服务器不可信的条件下以关键字检索加密邮件，而不泄露邮件和关键字信息。
  PEKS和SSE的关系，和传统公钥密码与对称密码的关系相近。PEKS具有公钥密码体制的特性，能够实现多用户之间的密文搜索。

6.2 PEKS的定义

• 初始化算法 S e t u p Setup Setup： - 输入：系统安全参数- 输出：一对公私钥
• 加密算法 P E K S PEKS PEKS： - 输入：公钥和待加密关键字- 输出：关键字可搜索密文
• 陷门生成算法 T r a p d o o r Trapdoor Trapdoor： - 输入：私钥和待检索关键字- 输出：关键字陷门
• 测试算法 T e s t Test Test： - 输入：公钥、关键字可搜索密文和关键字密文- 输出：密文与陷门是否匹配

双线性映射的另一种形式
  设群

     G 
    
   
  
    \mathbb{G} 
   
  
G和 
 
  
   
    
    
      G 
     
    
      T 
     
    
   
  
    \mathbb{G}_T 
   
  
GT​是阶为大素数 
 
  
   
   
     q 
    
   
  
    q 
   
  
q的循环乘法群，双线性映射 
 
  
   
    
    
      e 
     
    
      ^ 
     
    
   
     : 
    
   
     G 
    
   
     × 
    
   
     G 
    
   
     → 
    
    
    
      G 
     
    
      T 
     
    
   
  
    \hat{e}:\mathbb{G}×\mathbb{G}\rightarrow\mathbb{G}_T 
   
  
e^:G×G→GT​满足以下条件：

1. 双线性：对 ∀ U , V ∈ G , a , b ∈ Z q ∗ \forall U,V\in\mathbb{G},a,b\in Z^*_q ∀U,V∈G,a,b∈Zq∗​，均有 e ^ ( U a , V b ) = e ^ ( U , V ) a b ∈ G T \hat{e}(U^a,V^b)=\hat{e}(U,V)^{ab}\in\mathbb{G}_T e^(Ua,Vb)=e^(U,V)ab∈GT​成立
2. 非退化性：若 g g g为群 G \mathbb{G} G的生成元，则 e ^ ( g , g ) \hat{e}(g,g) e^(g,g)是群 G T \mathbb{G}_T GT​的生成元
3. 可计算性：对 ∀ U , V ∈ G \forall U,V\in\mathbb{G} ∀U,V∈G，可在有效时间内计算 e ^ ( U , V ) \hat{e}(U,V) e^(U,V)

6.3 PEKS实例化方案

6.4 PEKS存在的问题

• 检索效率问题 检测时需要测试每个可搜索密文，检索复杂度为线性级，效率太低。
• 安全性问题 SS-CKA安全性仅考虑了可搜索密文中关键字的语义安全，没有考虑陷门中关键字的保密性，前述方案在实际应用中需要安全信道来传递陷门。 实施关键字猜测攻击(KGA)可获得搜索关键字。其中KGA又分为离线KGA和在线KGA。离线KGA指窃听者或恶意服务器获取某一特定陷门后，穷举所有可能的关键字，依次生成密文进行测试，从而得出该陷门所含关键字；在线KGA指恶意发送方猜测所有可能的关键字，生成密文并上传，通过监听接收方的搜索结果来判断搜索关键字。

6.5 优化方案：SPCHS

起源
  2015年，带隐藏结构的可搜索公钥加密(SPCHS)被提出，它首次实现了检索复杂度只取决于包含查询关键字的可搜索密文的数量，而不是所有密文的数量，大幅度提高了检索效率。

核心思路
  同一个关键字的所有可搜索密文间具有隐藏的链式结构，链头与公共头部构成了一个隐藏的星型结构。

定义

• 初始化算法 S y s t e m S e t u p SystemSetup SystemSetup： - 输入：安全参数- 输出：系统公钥和系统私钥
• 结构初始化算法 S t r u c t u r e d I n i t a l i z a t i o n Structured Initalization StructuredInitalization： - 输入：系统公钥- 输出：隐藏结构的公有部分和私有部分
• 结构化加密算法 S t r u c t u r e d E n c r y p t i o n Structured Encryption StructuredEncryption： - 输入：系统公钥、关键字和隐藏结构的私有部分- 输出：可搜索密文(更新隐藏结构的私有部分)
• 陷门生成算法 T r a p d o o r Trapdoor Trapdoor： - 输入：系统私钥和关键字- 输出：关键字检索陷门
• 结构化检索算法 S t r u c t u r e d S e a r c h Structured Search StructuredSearch： - 输入：系统公钥、隐藏结构的公有部分、密文集合和关键字检索陷门- 输出：满足条件的密文

实例化方案

6.6 SPCHS存在的问题

• 本地私有状态问题：为了隐藏结构的生成，用户需要存储和更新私有信息。
• 仅支持关键字的精确查找，快速的模糊搜索、范围搜索、子集检索等等不能实现。
• 学术界提出的可搜索加密难以适用于数据库，两者索引的建立模式截然不同。

6.7 其他问题

如何理解可搜索加密至少泄露了1bit的信息
  在第一章的语义安全性的定义中，攻击者无法区分被加密的是

      m 
     
    
      0 
     
    
   
  
    m_0 
   
  
m0​还是 
 
  
   
    
    
      m 
     
    
      1 
     
    
   
  
    m_1 
   
  
m1​，即要求加密算法不泄露任何一比特的信息。对于可搜索加密来说，服务器需要根据检索陷门来判断哪个文件是用户所找的文件，服务器可以知道搜索陷门与对应文件标识符之间的关联关系。即：服务器在获取到关键字检索陷门之后， 可搜索密文可以被服务器区分。

  泄露的1bit信息是搜索陷门与对应文件标识符之间的关联关系。

可搜索加密必然会泄露信息，那么它还是安全的吗
  可搜索加密的安全性需要控制在一个合理的范围内，它有自己的安全性定义方式。我们只需要理解，好的可搜索加密在泄露信息之后，仍然可以证明其安全性。