﻿ 基于多项式插值的门限函数秘密分享方案
 计算机系统应用  2020, Vol. 29 Issue (5): 29-35 PDF

1. 福建师范大学 数学与信息学院, 福州 350117;
2. 福建师范大学 福建省网络安全与密码技术重点实验室, 福州 350007

Threshold Function Secret Sharing Scheme Based on Polynomial Interpolation
LUO Jing-Long, LIN Chang-Lu, LI Chao-Zhen, ZHANG Jian
College of Mathematics and informatics, Fujian Normal University, Fuzhou 350117, China;
Fujian Provincial Key Lab of Network Security & Cryptology, Fujian Normal University, Fuzhou 350007, China
Foundation item: National Natural Science Foundation of China (U1705264, 61572132); Natural Science Foundation of Fujian Province, China (2019J01275)
Abstract: Since the existing function secret sharing schemes require all participants to join in the reconstruction phase. Therefore, it cannot be flexibly applied to real-world scenarios. A function secret sharing scheme with thresholds is constructed in this study using polynomial techniques. According to the security model of function secret sharing, we proved that the proposed scheme has security in the sense of information theory. In addition, this study analyzes the function secret sharing scheme proposed by Yuan et al., and expounds the reason why their scheme does not satisfy the security of function secret sharing. Finally, a comprehensive comparison between the newly constructed scheme and the existing function secret sharing scheme is found. We note that the newly constructed scheme has higher level of security and higher efficiency through the comprehensive comparison.
Key words: secret sharing     function secret sharing     private information retrieval     polynomial interpolation     security analysis

1979年, Shamir[1] 和Blakley[2]分别独立提出了秘密分享(Secret Sharing, SS)概念并基于不同数学工具构造了相应方案. 秘密分享一般包含一个发送者和多个参与者, 在秘密分发阶段发送者将秘密值分成多个子秘密, 并将每个子秘密安全地发送给对应的参与者. 在重构阶段满足条件的参与者集合中的参与者合作重构出秘密值, 不满足条件的参与者集合中的参与者则不能得到关于秘密值的任何信息. 作为重要的密码技术, 秘密分享自提出以来一直受到研究者的持续关注.

1 相关概念

1)分发阶段: 发送者D从有限域 $G{F_q}$ 中随机均匀地选取 $r - 1$ 个值 ${a_1}, \cdots ,{a_{r - 1}}$ , 生成 $r - 1$ 次多项式 $f(x) = s +$ ${a_1}x + \cdots + {a_{r - 1}}{x^{r - 1}}$ , 发送者D计算 ${s_i} = f({{\textit{z}}_i})$ $(i = 1, \cdots ,n)$ , 并将 ${s_i}$ 安全地发送给每位参与者 ${P_i}$ .

2)重构阶段: 对任意r个参与者 $\{ {P_{{i_1}}}, \cdots ,{P_{{i_r}}}\} \subseteq \{ {P_1}, \cdots ,$ ${P_n}\}$ , 他们利用公开值 ${{\textit{z}}_1}, \cdots ,{{\textit{z}}_n}$ 计算值插值系数 ${c_{{i_h}}} =$ $\displaystyle\prod\limits_{h' = 1,h' \ne h}^r {\dfrac{{ - {{\textit{z}}_{{i_{h'}}}}}}{{{{\textit{z}}_{{i_h}}} - {{\textit{z}}_{{i_{h'}}}}}}}$ , 并通过多项式插值公式重构出秘密 $s = \displaystyle\sum\limits_{h = 1}^r {{c_{{i_h}}}} \cdot {s_{{i_h}}}$ .

(1) $Gen({1^\lambda },f) \to ({k_1}, \cdots ,{k_n})$ : 输入安全参数和秘密函数, 输出n个子函数 ${k_1}, \cdots ,{k_n}$ .

(2) $Eval(i,{k_i},{x_0}) \to {y_i}$ : 任意的 ${x_0} \in {D_f}$ , 参与者 ${P_i}(i =$ $1, \cdots ,n)$ 输入 $(i,{k_i},{x_0})$ , 输出值 ${y_i}$ .

(3) $Dec({y_{{i_1}}}, \cdots ,{y_{{i_r}}}) \to f({x_0})$ : 输入 $({y_{{i_1}}}, \cdots ,{y_{{i_r}}})$ , 输出秘密函数在点 ${x_0}$ 处的函数值 $f({x_0})$ .

t-安全: 若存在受贿参与者集合 $T \subseteq \{ {P_1}, \cdots ,{P_n}\}$ $|T| = t$ , 则不可区分性实验 $\prod$ 可描述如下:

1)敌手 ${\cal{A}}$ 输入安全参数1λ输出(f0,f1), 满足 ${D_{{f_0}}} = {D_{{f_1}}}$ , 并将产生的(f0,f1)发送给挑战者 ${\cal{C}}$ .

2) 挑战者 ${\cal{C}}$ 收到(f0,f1)后, 随机地选取挑战值 $c \in \{ 0,1\}$ , 执行子函数生成算法输入 ${f_c}$ , 输出 $(k_1^c, \cdots ,k_n^c)$ , 并将 ${{\rm{\{ }}k_i^c{\rm{\} }}_{i \in T}}$ 发送给 ${\cal{A}}$ .

3) 敌手 ${\cal{A}}$ 收到 ${{\rm{\{ }}k_i^c{\rm{\} }}_{i \in T}}$ 后根据自己所掌握的信息给出关于挑战值 $c$ 的猜测 $\hat c$ .

$Adv({1^\lambda },A,T) = Pr [\hat c = c] - \dfrac{1}{2}$ 表示敌手 ${\cal{A}}$ 在上述实验 $\prod$ 中猜对挑战值 $c$ 的概率与 ${\cal{A}}$ 在不知道任何信息下随机猜测猜对c的概率的之差.

2 门限FSS方案TFSS(Gen, Eval, Dec)

2.1 TFSS(Gen, Eval, Dec)

(1) $Gen({1^\lambda },{f_{a,b}}) \to ({k_1}, \cdots ,{k_n})$

① 将 $a \in {\{ 0,1\} ^l}$ 转换为二进制进行表示, 则a = $({a_1}, \cdots ,{a_l})$ , 其中 ${a_j} \in \{ 0,1\} (j = 1, \cdots ,l)$ .

② 令 $b = \displaystyle\prod\limits_{j = 1}^l {{b_j}}$ , 其中 ${b_j} \in G{F_q}$ .

③ 发送者D $G{F_q}$ 中随机均匀的选取 $lt$ 个值 ${r_{j,1}}, \cdots ,{r_{j,t}}(j = 1, \cdots ,l)$ , 并产生 $2l$ 个关于z $2t$ 次多项式 $\left\{ {\begin{array}{*{20}{l}}{{g_j}({\textit{z}}) = ({a_j} + {r_{j,1}} \cdot {\textit{z}} + \cdots + {r_{j,t}} \cdot {{\textit{z}}^t}) \cdot ({b_j} + {r_{j,1}} \cdot {\textit{z}} + \cdots + {r_{j,t}} \cdot {{\textit{z}}^t})}\\{{{\hat g}_j}({\textit{z}}) = (1 - ({a_j} + {r_{j,1}} \cdot {\textit{z}} + \cdots + {r_{j,t}} \cdot {{\textit{z}}^t})) \cdot ({b_j} + {r_{j,1}} \cdot {\textit{z}} + \cdots + {r_{j,t}} \cdot {{\textit{z}}^t})}\end{array}} \right.$ .

D使用公开值 ${{\textit{z}}_1}, \cdots ,{{\textit{z}}_n}$ 计算 ${g_{j,i}} = {g_j}({{\textit{z}}_i}),{\hat g_{j,i}} = {\hat g_j}({{\textit{z}}_i})$ , 并生成 ${k_i} = ({g_{1,i}}, \cdots ,{g_{l,i}};{\hat g_{1,i}}, \cdots ,{\hat g_{l,i}})$ .

⑤ 输出 $({k_1}, \cdots ,{k_n})$ .

(2) $Eval(i,{k_i},{x_0}) \to {y_i}$

① 对于任意的 ${x_0} \in {\{ 0,1\} ^l}$ , 将 ${x_0}$ 用二进制表示为 ${x_0} = (x_1^0, \cdots ,x_l^0)$ .

${P_i}$ 计算 ${y_i} = \displaystyle\prod\limits_{j = 1}^l {(x_j^0 \cdot {g_{j,i}} + (1 - x_j^0)(1 - {{\hat g}_{j,i}}))}$ .

③ 输出 ${y_i}$ .

(3) $Dec({y_{{i_1}}}, \cdots ,{y_{{i_r}}}) \to y$

① 参与者 ${P_{{i_h}}}(h = 1, \cdots ,r)$ 通过公开值 ${{\textit{z}}_1}, \cdots ,{{\textit{z}}_n}$ 计算 ${c_{{i_h}}} = \displaystyle\prod\limits_{h' = 1,h' \ne r}^r {\frac{{ - {{\textit{z}}_{{i_{h'}}}}}}{{{{\textit{z}}_{{i_h}}} - {{\textit{z}}_{{i_{h'}}}}}}}$ .

② 输出 $y = \displaystyle\sum\nolimits_{h = 1}^r {{c_{{i_h}}} \cdot {y_{{i_h}}}}$ .

 $\left\{ {\begin{array}{*{20}{l}} \!\!\!\!{{g_j}({\textit{z}}) \!=\! ({a_j}\! +\! {r_{j,1}} \!\cdot \!{\textit{z}} \!+\! \cdots \!+ {r_{j,t}} \!\cdot\! {{\textit{z}}^t}) \!\cdot\! ({b_j} + {r_{j,1}} \cdot {\textit{z}} + \cdots + {r_{j,t}} \cdot {{\textit{z}}^t})}\\ \!\!\!\!{{{\hat g}_j}({\textit{z}}) \!\!=\!\! (1 \!-\! ({a_j} \!+\! {r_{j,1}}\! \cdot\! {\textit{z}} \!+\! \cdots \!\!+\! {r_{j,t}}\! \cdot\! {{\textit{z}}^t})) \!\cdot\! ({b_j} \!+\! {r_{j,1}} \cdot {\textit{z}} \!+\! \cdots \!+\! {r_{j,t}} \!\cdot\! {{\textit{z}}^t})} \end{array}} \right.\!\!\!$

 $\begin{array}{l} y = f(0) = \displaystyle\sum\limits_{h = 1}^r {{c_{{i_h}}}} \cdot {y_{{i_h}}} = \displaystyle\prod\limits_{j = 1}^l {x_j^0 \cdot {g_j}(0) + (1 - x_j^0) \cdot {{\hat g}_j}(0)} \\ \;\;\;\; = \displaystyle\prod\limits_{j = 1}^l {x_j^0 \cdot {a_j} \cdot {b_j} + (1 - x_j^0) \cdot (1 - {a_j}} ) \cdot {b_j}, \\ \end{array}$

2.2 TFSS方案的安全性分析

(1) 敌手 ${\cal{A}}$ 输入安全参数1λ输出 $({f_{{a^0},{b^0}}},{f_{{a^1},{b^1}}})$ , 满足 ${a^0},{a^1} \in {\{ 0,1\} ^l},{b^0},{b^1} \in {\{ 0,1\} ^m}$ , 并将 $({f_{{a^0},{b^0}}},{f_{{a^1},{b^1}}})$ 发送给挑战者 ${\cal{C}}$ .

(2) 挑战者 ${\cal{C}}$ 收到 $({f_{{a^0},{b^0}}},{f_{{a^1},{b^1}}})$ 后, 随机地产生挑战值 $c \in \{ 0,1\}$ , 执行子函数生成算法输入 ${f_{{a^c},{b^c}}}$ , 输出 $(k_1^c, \cdots ,k_n^c)$ , 并将 ${{\rm{\{ }}k_i^c{\rm{\} }}_{i \in T}}$ 发送给敌手 ${\cal{A}}$ .

(3) 敌手 ${\cal{A}}$ 收到 ${{\rm{\{ }}k_i^c{\rm{\} }}_{i \in T}}$ 后, 根据自己所掌握的信息给出一个关于挑战值 $c$ 的猜测 $\hat c$ .

 $\left\{ \begin{array}{l} \!\!\!\!\!g_{j,u}^c \!=\! (a_j^c \!+\! {r_{j,1}} \cdot {{\textit{z}}_u} \!+\! \cdots \!+\! {r_{j,t}} \cdot {\textit{z}}_u^t) \cdot (b_j^c \!+\! {r_{j,1}} \!\cdot\! {{\textit{z}}_u} \!+\! \cdots \!+\! {r_{j,t}} \!\cdot\! {\textit{z}}_u^t)\\ \!\!\!\!\!\hat g_{j,u}^c \!\!=\!\! (\!1 \!-\! (a_j^c \!+\! {r_{j,1}} \!\cdot\! {{\textit{z}}_u} \!+\!\! \cdots \!\!+\! {r_{j,t}}\! \cdot\! {\textit{z}}_u^t)) \cdot (b_j^c \!+\!\! {r_{j,1}} \!\cdot\! {{\textit{z}}_u} \!+\!\! \cdots \!\!+\! {r_{j,t}}\! \cdot\! {\textit{z}}_u^t) \end{array} \right.\!\!\!\!$

 $\begin{array}{l} \underbrace {\left( {\begin{array}{*{20}{c}} {b_1^c}&{b_1^c}& \cdots &{b_1^c} \\ {b_2^c}&{b_2^c}& \cdots &{b_2^c} \\ \vdots & \vdots &{}& \vdots \\ {b_l^c}&{b_l^c}& \cdots &{b_l^c} \end{array}} \right)}_B + \underbrace {\left( {\begin{array}{*{20}{c}} {{r_{1,1}}}&{{r_{1,2}}}& \cdots &{{r_{1,t}}} \\ {{r_{2,1}}}&{{r_{2,2}}}& \cdots &{{r_{2,t}}} \\ \vdots & \vdots &{}& \vdots \\ {{r_{l,1}}}&{{r_{l,2}}}& \cdots &{{r_{l,t}}} \end{array}} \right)}_R\underbrace {\left( {\begin{array}{*{20}{c}} {{{\textit{z}}_1}}&{{{\textit{z}}_2}}& \cdots &{{{\textit{z}}_t}} \\ {{{\textit{z}}_1}^2}&{{{\textit{z}}_2}^2}& \cdots &{{{\textit{z}}_t}^2} \\ \vdots & \vdots &{}& \vdots \\ {{{\textit{z}}_1}^t}&{{{\textit{z}}_2}^t}& \cdots &{{{\textit{z}}_t}^t} \end{array}} \right)}_Z = \underbrace {\left( {\begin{array}{*{20}{c}} {{w_{1,1}}}&{{w_{1,2}}}& \cdots &{{w_{1,t}}} \\ {{w_{2,1}}}&{{w_{2,2}}}& \cdots &{{w_{2,t}}} \\ \vdots & \vdots &{}& \vdots \\ {{w_{l,1}}}&{{w_{l,2}}}& \cdots &{{w_{l,t}}} \end{array}} \right)}_W \\ \end{array}$

 $\left\{ \begin{array}{l} \!\!\!\!\!g_{j,u}^c \!=\! (a_j^c \!+\! {r_{j,1}} \cdot {{\textit{z}}_u} \!+\! \cdots \!+\! {r_{j,t}} \cdot {\textit{z}}_u^t) \cdot (b_j^c \!+\! {r_{j,1}} \cdot {{\textit{z}}_u} \!+\! \cdots \!+\! {r_{j,t}} \cdot {\textit{z}}_u^t)\\ \!\!\!\!\!\hat g_{j,u}^c \!\!=\! (\!1 \!\!-\! (a_j^c \!+\! {r_{j,1}}\! \cdot \!{{\textit{z}}_u} \!+\!\! \cdots \!\!+\! {r_{j,t}}\! \cdot\! {\textit{z}}_u^t)) \cdot (b_j^c \!+\! {r_{j,1}}\! \cdot\! {{\textit{z}}_u} \!+\!\! \cdots \!\!+\! {r_{j,t}}\! \cdot\! {\textit{z}}_u^t) \end{array} \right.\!\!\!\!$

2.3 TFSS方案的通信复杂度分析

3 文献[11]的方案及其分析

3.1 文献[11]的方案

3.2 安全性分析

1) 参与者 ${P_i}(i = 1, \cdots ,n)$ , 通过 ${k_i}$ 计算秘密函数 ${f_{a,b}}$ b的值.

2) 任意两个参与者(不妨设为 ${P_1},{P_2}$ )联合通过 ${k_1},{k_2}$ 计算出秘密函数 ${f_{a,b}}$ .

3.3 通信复杂度分析

4 TFSS方案与现有FSS方案的比较

5 结语

 [1] Shamir A. How to share a secret. Communications of the ACM, 1979, 22(11): 612-613. DOI:10.1145/359168.359176 [2] Blakley GR. Safeguarding cryptographic keys. Proceedings of the AFIPS 1979 National Computer Conference. Montvale, NJ, USA. 1979. 313–317. [3] Chor B, Kushilevitz E, Goldreich O, et al. Private information retrieval. Journal of the ACM, 1998, 45(6): 965-981. DOI:10.1145/293347.293350 [4] Ostrovsky R, Shoup V. Private information storage (extended abstract). Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. New York, NY, USA. 1997. 294–303. [5] Gilboa N, Ishai Y. Distributed point functions and their applications. Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. Copenhagen, Denmark. 2014. 640–658. [6] Boyle E, Gilboa N, Ishai Y. Function secret sharing. Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Sofia, Bulgaria. 2015. 337–367. [7] Boyle E, Couteau G, Gilboa N, et al. Homomorphic secret sharing: Optimizations and applications. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, TX, USA. 2017. 2105–2122. [8] Plantard T, Susilo W, Zhang ZF. Fully homomorphic encryption using hidden ideal lattice. IEEE Transactions on Information Forensics and Security, 2013, 8(12): 2127-2137. DOI:10.1109/TIFS.2013.2287732 [9] Boyle E, Gilboa N, Ishai Y. Function secret sharing: Improvements and extensions. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Vienna, Austria. 2016. 1292–1303. [10] Håstad J, Impagliazzo R, Levin LA, et al. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 1999, 28(4): 1364-1396. DOI:10.1137/s0097539793244708 [11] Yuan DZ, He MX, Zeng SK, et al. (t, p)-threshold point function secret sharing scheme based on polynomial interpolation and its application. Proceedings of 2016 IEEE/ACM 9th International Conference on Utility and Cloud Computing. Shanghai, China. 2016. 269–275. [12] Bellare M. A note on negligible functions. Journal of Cryptology, 2002, 15(4): 271-284. DOI:10.1007/s00145-002-0116-x