前言

为什么提出？

解决在加密数据库上的高效检索（要practical，不能只停留在学术层面）。

解决了什么问题？

本篇文章定义了两种威胁：

第一种是内部攻击，比如对于不可信的DBA/管理员用户，其偷偷窃取/窃听数据所存在的威胁
第二种是敌手通过某种手段拿下整个application以及DBMS的控制权，保证目前状态下的数据隐私问题

怎么做的？

通过SQL查询，在用户和DBMS中间加了一层proxy server来对用户查询的SQL进行一定的处理，最终将需要查询的数据透明返回给查询用户，其系统架构如下：

为解决以上两种问题，本文提出三种解决措施：

SQL-aware encryption strategy

根据SQL语句有清晰结构的特点，让CryptDB能够对加密数据库执行简单的SQL操作

adjustable query-based encryption

避免信息泄露，对于不同的查询，CryptDB在运行态对其分析处理，并提出了洋葱加密

chain encryption keys to user passwords

访问控制，在威胁二下将密钥成串连接起来，未登陆用户的密钥无法被获取，即使DBMS和application全都妥协也无法解密数据

Queries over Encrypted Data

:::info
该部分内容适用于Threat 1下的场景，即DBMS和administrator是不可信的。
:::
CryptDB中的proxy server拥有一个密钥MK，数据库表，目前所有列对应的所有加密层，加密用户数据以及辅助表。因此对于DBMS来说，表是匿名的（因为表名、列名、值都做了加密处理）。在加密数据上的query可分为以下四个步骤：

application发出query，proxy拦截后重写query，使用MK加密对应列名和表，并把query中的常量值以最合适的方式加密处理
proxy先检查DBMS是否需要给密钥来调整encryption layer，如果是的话，发送密钥并通过UDF来触发UPDATE调整对应列的encryption layer
proxy将query发出，DBMS通过标准SQL查询（对于aggregate可能需要用到UDF）
DBMS将数据发送，proxy解密并返回给application

SQL-aware Encryption

为了满足SQL的多种操作，CryptDB提供了多种加密层，下面逐一介绍：

Random（RND）：该加密层是一种满足IND-CPA安全的probabilistic方案（即对于相同的输入，其输出是不同的）。它在CryptDB中安全性最高，但RND不允许在密文上进行任何计算。RND的构造一般使用分组加密算法，多使用带有初始化随机向量IV的AES。
Deterministic（DET）：该加密层是确定性方案（两个相同的输入对应一个共同的输出），安全性相对较低。因此可以在该加密层上执行相等比较运算，即可以在query中实现谓词的equality、join、GROUP BY、COUNT、DISTINCT操作。DET的构造一般为使用了CMC模式的AES（没有初始化随机向量IV的参与）。
Order-preserving Encryption（OPE）：即保序加密，对于任意的x<y，其OPEK(x)<OPEK(y)，它的安全性比DET还要低。根据其特性，对于任意谓词c1、c2，计算其OPEK(c1)，OPEK(c2)，即可查询在区间[c1, c2]之间的值。因此可以用来操作ORDER BY、 MIN、MAX、SORT等操作。
Homomorphic encryption（HOM）：即同态加密，满足IND-CPA的probabilistic方案，支持在密文上执行运算。CryptDB是用了Paillier，实现了两个同态后的密文相乘的结果与两个相加后的密文同态结果（HOMK(x)·HOMK(y)=HOMK(x+y)）。可支持加运算。
Join（JOIN和OPE-JOIN）：在需要多表查询时会用到join，因此在跨表时可以与DET一同协作，也可以与OPE一同协作（即对join后的结果判断DET或者OPE排序）。
Word search（SEARCH）：用来支持模糊查询，即LIKE。其使用了Song（SE开山之作）的方案来对需要执行的列进行加密运算，通过将column中的值分割为若干不重复的关键词逐个加密，当query中的predicate与column中的某个关键词对应上了，则说明这个就是目标结果。但这种方式也有缺点，即它使用了Song的以关键词为单位的加密，则必然不支持非完整关键词的检索（比如要搜索的词为hello的一半->%llo%，这种时候就没法完成模糊搜索），也不支持正则表达式搜索，功能性差。

Adjustable Query-based Encryption

背景：假设一种场景，在数据库中的某一列从未被application查询过（或者无需进行查询），那么使用上面提到了RND即可满足加密需求；另外如果有一列仅需要执行equality check，则使用DET即可满足需求。但可惜的是，我们无法预先知道查询集，因此需要一种可自适应的方案来动态调整加密策略。
CryptDB提出了一种解决方案，洋葱加密。对于上面提到的加密策略，每个加密策略是洋葱加密的一层，当需要完成多种需求时，加密层就会像洋葱一样一层一层包裹起来；当需要调整时，也可将某一层加密像洋葱一样剥离开来。

正如上图所示，最外层的RND和HOM提供了最高的安全性，其中包含的DET、OPE等则提供了功能性。

那么实际中洋葱加密是怎么运作的呢？

首先，对于每个洋葱加密层，其最开始使用的都是安全性最高的加密策略（比如RND用于equality check和order，HOM用于add，SEARCH用于search等）。
当proxy收到SQL查询时，首先它会根据谓词来确定其应当执行在哪个洋葱加密层上。
如果谓词所需要的执行层目前存在，则直接发送到DBMS server上执行相关操作，否则剥离当前洋葱层（通过proxy给DBMS server发送密钥来实现）。

另外，洋葱层的解密（应当等同于剥离操作）是完全在DBMS上完成的，通过proxy server发出UDF来实现，这里属于实现细节，不做过多阐述。

Executing over Encrypted Data

:::info
该部分即讨论已到所需执行操作的洋葱层，不考虑自适应性“剥洋葱“相关事宜
:::
步骤进行到这一步其实已经非常清晰了，目前DBMS server存在的数据是”自适应性”处理后的加密数据。如果此时需要执行相关SQL操作，proxy只需通过UDF向DBMS server查询即可完成相关操作。这里简要介绍一下读、写两种操作：

读操作

由于SQL是一种结构化很强的语句，所以对于查询语句例如SELECT ID FROM Employees WHERE Name = ‘Alice’，解析器会解析到这是一条对Name列的equality check，所以首先会先将Name列对应加密后的列解密处理（这一步由proxy server调用UDF完成，即解密RND层），并将解密后的列对应到之前的表中。此时的表中ID列仍是加密处理的，Name列可以通过对DET处理后的Alice进行比较处理，得到ID列的密文和其初始置换向量。最终通过初始置换向量解密密文得到ID。

写操作

在前面的处理中，写操作是与读操作一样的。但对于列增情况则有例外。