基于多变量多项式的门限函数秘密分享方案*

林昌露, 罗景龙, 张胜元, 王华雄

1. 福建师范大学 数学与统计学院, 福州 350117

2. 福建省网络安全与密码技术重点实验室(福建师范大学), 福州 350007

3. 鹏城实验室 人工智能研究中心, 深圳 518055

4. 新加坡南洋理工大学 物理与数学学院, 新加坡 308232

5. 网络空间与信息安全重庆市重点实验室, 重庆 400065

6. 桂林电子科技大学 广西可信软件重点实验室, 桂林 541004

1 引言

1979 年, Shamir[1]和Blakly[2]分别独立提出秘密分享的概念并给出了具体构造方案, 他们的方案被称为(t,n)-门限秘密分享方案. 在(t,n)-门限秘密分享方案中, 通常包括1 个分发者和n个参与者, 在秘密的分发阶段分发者将秘密分为n个子秘密发送给相应的参与者; 在重构阶段任意大于t个参与者合作可以重构出秘密, 任意t个或者少于t个参与者则得不到关于秘密的任何信息. 秘密分享在密码学和分布式计算中有许多应用, 如拜占庭协议[3]、安全多方计算[4–6]、门限密码学[7,8]等.

Chor 等人[9]最早考虑了用户私密信息存取问题中的一种场景, 即用户想要从服务器管理的数据库中恢复某一信息, 同时服务器不知道用户恢复信息的内容, 将解决此类问题的模型称之为私密信息检索(Private information retrieval, PIR) 协议, 并用通信复杂度表示PIR 协议中用户和服务器之间传输信息的总量, 用于衡量协议的传输效率.

为了降低私密信息存取协议的通信复杂度, Boyle 等人[10]在2015 年欧密会上提出了函数秘密分享(Function Secret Sharing, FSS) 的概念. 通过设计高效的FSS 方案, 并将其转换为具有同级别通信复杂度的私密信息存取协议, 从而……