【论文阅读】【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。