【论文阅读】【S&P】A Decentralized and Encrypted National Gun Registry

阅读了一篇论文，一个系统架构

主要内容

以枪支管理为场景，开发了一个本地管理的由端到端的加密数据库组成的去中心化系统。
运用技术：安全两方计算，安全多方计算，秘密共享，结构化加密，可搜索加密
架构：
包括，系统由一个加密的全局目录（存储序列号到县标识符的映射，解析受限的加密字典）、持有全局目录密钥份额的保管人、由地方官员P管理的加密本地数据库以及存储本地加密数据库的州服务器S组成。每个P有3个备份（用于离线查询）

协议

伴随技术进步，可使用更先进的技术对其模块实现技术进行替换。由六个子协议组成InitGlobal，InitLocal， Add,Find，Query，OfflineQuery。
协议参与者：一个服务器S，两个保管人C1,C2；多个参与者（即地方官员，数目固定，管理本地数据库的密钥，进行查询、增加记录等操作）P1~Pθ，每个参与者分别有三个备份B1,B2,B3。

InitGlobal

参与者：C1，C2，S
在S上创建一个加密字典EDX为全局目录，C1 C2各掌握部分密钥。全局目录是序列号到县标识符的映射，通过查询目录，可以根据枪支序列号找到注册所在地。

InitLocal

参与者：Pi，i∈{1,…, θ}
Pi运行该协议生成密钥Ki和空的加密数据库EDBi，并将EDBi发送给服务器S，将密钥Ki按照秘密共享分成三份分别给三个备份。

Add

参与者：本地管理人员L∈ {P1, . . . ,Pθ}，保管人C1,C2，服务器S
向系统中添加记录。
1）L将新记录(r.sn,r.cid)序列号/县标识符对上传全局目录
L利用秘密共享算法将记录对分成两份p1 p2分别给C1 C2，C1 C2使用秘密共享算法恢复全局目录密钥K和记录对 (r.sn,r.cid)，并计算出该记录对的add token，并将token依据秘密共享分成两份发送给服务器，服务器恢复该token并更新全局目录。
2）之后L为记录生成add token发送至服务器更新本地数据库。

Find

参与者：查询者Q ∈ {P1, . . . ,Pθ}，C1 ,C2,S
根据序列号sn查询全局目录得到注册所在县标识符CID。
Q将序列号SN分成两份给C1 C2。C1和C2进行安全两方运算实现以下操作：1）恢复全局目录的密钥K；2）恢复序列号SN；3）为序列号计算token；4）为序列号生成解析受限的密钥；5）将token和4）中生成密钥分成两份分别给C1 C2。C1和C2将收到的内容分别发给服务器S和查询者Q。Q恢复token和解析密钥，使用token查询全局目录EDX然后返回加密结果给Q，Q使用解析密钥进行解密，得到所在县标识符CID。

Query

参与者：查询者Q ∈ {P1, . . . ,Pθ}，被查询的本地官员L ∈ {P1, . . . ,Pθ}和服务器S
Q根据Find得到的县ID，使用布尔表达式φ对相应加密数据库进行查询
L和Q通过安全两方计算，使用L管理数据库的密钥KL为φ生成查询token，Q将token发送给服务器S,S用其查询L的数据库，返回给Q符合查询条件φ的密文记录。Q和L使用另一个安全双方计算解密记录。

OfflineQuery

参与者：Q，L的三个备份B1 B2 B3，服务器S
使用备份进行离线查询，布尔表达式为φ。
Q和三个备份使用安全多方计算进行如下操作1）恢复L的密钥；2）将密钥分成两份，分别给Q和指定备份（假设为B1）。Q和指定备份B1执行安全两方计算完成以下操作1）通过新的共享恢复密钥2）为φ计算出token，之后Q将token发送给服务器，服务器返回满足要求的加密记录集合，Q和指定备份B1使用安全两方计算进行解密。

现实模型下的协议实现

使用安全两方计算2PC和安全多方计算MPC进行计算；使用结构化加密算法对全局目录和各数据库进行加密，其中数据库使用响应隐藏数据库加密方案ΣDB= (Init, Token, Query, AddToken, Resolve)进行加密，全局目录使用解析受限的响应隐藏字典加密方案ΣDX= (Init, Token, Query, AddToken, ResKey, Resolve)加密；使用秘密共享SS =(Share, Recover) 进行密钥，token等的分配和恢复

安全性

安全性实验：
实际运行：
环境Z，敌手为A，I为腐败参与方的集合
开始：Z接受字符串z ∈ {0,1}∗为输入，并挑选参与方组成集合I发送给敌手A；A使集合I中对象腐败；之后，相应参与方运行InitGlobal，InitLocal进行初始化
初始化结束后，Z自适应选择多项式数量的命令(comm1, . . . ,commm) 形如(Pj,opj)，op为相应操作add，find，query，offlinequery。当1 ≤ j ≤ m时，Z发送commj给Pj，Pj将结果返回给Q。
最后：敌手A给Z发送任意消息，Z输出1bit信息Hybrid_(z,A) (k)
理想情况运行：用如下图所示FGR进行模拟F2PC 和FMPC的功能

理想模型下的协议实现
利用leakage profile Λ参数化该功能，用于存储和管理枪支注册系统GR = (DX,DB1, . . . ,DBθ)
理想模型的实验过程同实际运行的实验过程一样，当需要运行相应协议时，则通过下图的方式进行模拟。最后Z输出1bit信息Ideal_(z,s)^Λ (k)

安全定义

安全分析：
对协议进行泄露分析。先使用黑盒泄露分析，之后进行具体泄露分析。先证明理想情况下，在leakage profileΛ情况下的实验运行与实际情况协议运行无区别，再证明理想情况下的协议运行是安全的，从而证明系统在现实情况下是安全的。

性能

添加效率：添加记录分为添加至全局目录和本地数据库两部分，该部分的时间花费主要取决于添加值全局目录所花费的时间。
查询效率：通过全局目录识别序列号所在县仅需不到300ms。查询官方数据库的时间取决于查询选择性，即查询条件。
存储开销：加密数据库由BIEX-2Lex的加密多映射EMM以及加密数据记录组成，EMM的大小是记录数量的二次函数，加密记录的大小相比EMM可忽略不计。对于4亿对记录，全局目录大小为110GB。