﻿ 基于格的可验证秘密共享方案
 计算机系统应用  2020, Vol. 29 Issue (1): 225-230 PDF

1. 中国电子科技集团公司第三十二研究所, 上海 201808;
2. 中国科学技术大学 计算机科学与技术学院, 合肥 230026

Verifiable Secret Sharing Scheme Based on Lattice Cryptography
PENG Yong1, SHAO Pei-Nan1, LI Xiang1, BAI Jian-Feng2, MENG Ke-Ju2
1. The 32nd Research Institute of China Electronics Technology Group Corporation, Shanghai 201808, China;
2. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
Foundation item: Construction Fund of Shanghai Science and Technology Commission (17DZ2251400)
Abstract: Verifiable Secret Sharing (VSS) is an important cryptographic primitive in distributed computing. The most of pervious VSS almost depended on the commitments which was established under the computational assumption of discrete algorithm problem which had been proofed unsecure. So a quantum-resistant VSS scheme which can be applied in secret sharing schemes implemented by different methods is called for. In this study, we analyze the existing verifiable sharing schemes. In order to solve the flaws in the existing schemes, we propose a new scheme with the applicability to secret sharing implemented by lattice cryptography. In addition, it has higher verification efficiency compared to past schemes and resistance so far to cryptanalysis by quantum algorithms.
Key words: Verifiable Secret Sharing (VSS)     discrete algorithm     quantum attack     Lattice cryptography     Lattice problem

1 概述

1)秘密分发过程中, 子份额持有者验证从秘密持有者获得子份额的完整性和正确性.

2)秘密恢复过程中, 秘密恢复者验证从其他子份额持有者那获得的子份额的正确性和完整性.

2 基础知识 2.1 秘密共享

2.2 格

[18] $m$ 维欧式空间 ${\mathbb{Z}^m}$ $n$ 个线性无关向量组 ${{\bf{b}}_1},{{\bf{b}}_2}, \cdots ,{{\bf{b}}_n}$ 的整系数线性组合, 即:

 ${\bf{L}}({\bf{B}}) = \left\{ {\sum\limits_{i = 1}^n {{x_i}} {{\bf{b}}_i}:{x_i} \in \mathbb{Z},i = 1, \cdots ,n} \right\}$

$\gamma$ -近似最短向量问题(SVP- $\gamma$ ): 给定格 ${\bf L}$ , 找一个非零格向量 $v$ , 满足对任意格中的非零向量 ${\bf{u}} \in {\bf{L}}$ , $\parallel {\bf{v}}\parallel \le \gamma \parallel {\bf{u}}\parallel$ .

2.3 Ajtai单向函数[19]

3 方案构造

3.1 符号

3.2 可验证秘密共享方案

 $f(x) = {a_0} + {a_1}x + \cdots +{a_{t - 1}}{x^{t - 1}}od p$

(1) 秘密持有者计算 ${s_i} = f({x_i})$ 并且随机从 ${\{ 0,1\} ^m}$ 中选择 ${t_i}$ , 将 $({s_i},{t_i})$ 一起发送给子份额持有者 ${P_i}$ . 注意到如果 ${s_i} \ne {s_j}$ ${t_i} \ne {t_j}$ , 那么 ${s_i} \oplus {t_i}$ 一定不等于 ${s_i} \oplus {t_j}$ .

(2) 秘密持有者公开矩阵A, ${F_{\bf A}}({s_i} \oplus {t_i})$ $s_i'$ 的值, 其中 $s_i' = {s_i} \oplus {t_i}$ .

(3) 子份额持有者 ${P_i}$ 收到 $({s_i},{t_i})$ 后, 首先要对自己接收到的子份额进行验证:

 ${F_{\bf A}}({s_i} \oplus {t_i}) = {\bf{A}}({s_i} \oplus {t_i})od q$

(1) 子份额持有者之间互相验证对方子份额的合法性, 具体操作如下:

 ${F_{\bf A}}\left(\sum {(s_j')} \right) = \sum {{F_{\bf A}}({s_j} \oplus {t_j})} od q,j \in [k]$

 ${F_{\bf A}}(s_j') = A({s_j} \oplus {t_j})od q,j \in [k]$

(2) 参与秘密恢复的子份额持有者互相交换信息 $s_i$ 并用所得到这些子份额采用Shamir秘密共享的方式去恢复秘密.

 $s = \sum\limits_{i = 1}^k {{s_i}\prod\limits_{1 \le j \le k,j \ne i} {\frac{{{x_j}}}{{{x_j} - {x_i}}}} } od p$

 $\sum {{F_{\bf A}}({s_i} \oplus {t_i})} = {F_{\bf A}}\left(\sum {({s_i} \oplus {t_i})} \right)od q$

 \begin{aligned} \sum\limits_{i = 1}^k {{F_{\bf A}}({s_i} \oplus {t_i})} & = \sum\limits_{i = 1}^k {{\bf A}({s_i} \oplus {t_i})} \\ & = \sum\limits_{i = 1}^k {({\alpha _1}, \cdots ,{\alpha _m})({s_i} \oplus {t_i})} od q \end{aligned}

 \begin{aligned} \sum\limits_{i = 1}^{{k}} {\left( {{\alpha _1}{\delta _{{i_1}}} + \cdots + {\alpha _m}{\delta _{{i_m}}}} \right)} & = \sum\limits_{i = 1}^{\rm{k}} {\sum\limits_{j = 1}^m {{\alpha _j}} } {\delta _{{i_j}}} \\ & = {\bf A}\sum\limits_{i = 1}^k {\left( {{\delta _{{i_1}}}, \cdots ,{\delta _{{i_m}}}} \right)} od \,q \end{aligned}

4 分析

4.1 效率分析

 $\sigma = \frac{s}{{{{\max }_{i \in P}}\left( {{s_i}} \right)}}$

(1) 验证子份额时所要通信的轮数.

(2) 子份额持有者用于验证子份额合法性所需的通信数据量.

(3) 子份额持有者验证子份额合法性所要做出的运算量.

 $mn\log q + n\log q \approx {m^2} = {\log ^2}p$

4.2 安全性分析

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 1979 International Workshop on Managing Requirements Knowledge. New York, NY, USA. 1979. 313–318. [3] 李新超, 钟卫东, 刘明明, 等. 基于秘密共享的SM4算法S盒实现方案. 计算机工程, 2018, 44(11): 148-153. [4] 王俞力, 杜伟章. 向量空间上无可信中心的动态多秘密共享方案. 计算机工程, 2017, 43(7): 163-169. DOI:10.3969/j.issn.1000-3428.2017.07.027 [5] 顾为玉, 苗付友, 何晓婷. 基于二元对称多项式的公平秘密共享方案. 计算机工程与应用, 2016, 52(13): 38-42, 109. DOI:10.3778/j.issn.1002-8331.1601-0192 [6] 张红军, 刘珂, 牟占生. 基于格的门限秘密共享算法. 计算机工程, 2016, 42(6): 139-143, 150. DOI:10.3969/j.issn.1000-3428.2016.06.024 [7] 梁建武, 刘晓书, 程资. 基于图态和中国剩余定理的量子秘密共享方案. 通信学报, 2018, 39(10): 72-78. DOI:10.11959/j.issn.1000-436x.2018220 [8] 彭巧, 田有亮. 基于多线性Diffie-Hellman问题的秘密共享方案. 电子学报, 2017, 45(1): 200-205. DOI:10.3969/j.issn.0372-2112.2017.01.027 [9] Chor B, Goldwasser S, Micali S, et al. Verifiable secret sharing and achieving simultaneity in the presence of faults. Proceedings of the 26th Annual Symposium on Foundations of Computer Science. Portland, OR, USA. 1985. 383–395. [10] Feldman P. A practical scheme for non-interactive verifiable secret sharing. Proceedings of the 28th Annual Symposium on Foundations of Computer Science. Los Angeles, CA, USA. 1987. 427–438. [11] Stadler M. Publicly verifiable secret sharing. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Saragossa, Spain. 1996. 190–199. [12] Fitzi M, Garay J, Gollakota S, et al. Round-optimal and efficient verifiable secret sharing. Proceedings of the 3rd Theory of Cryptography Conference. New York, NY, USA. 2006. 329–342. [13] Patra A, Choudhary A, Rabin T, et al. The round complexity of verifiable secret sharing revisited. Proceedings of the 29th Annual International Cryptology Conference. Santa Barbara, CA, USA. 2009. 487–504. [14] Kumaresan R, Patra A, Rangan C P. The round complexity of verifiable secret sharing: The statistical case. Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. Singapore. 2010. 431–447. [15] Pedersen TP. Non-interactive and information-theoretic secure verifiable secret sharing. Proceedings of the Annual International Cryptology Conference. Santa Barbara, CA, USA. 1992. 129–140. [16] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303-332. DOI:10.1137/S0036144598347011 [17] Beimel A. Secret-sharing schemes: A survey. Proceedings of the 3rd International Conference on Coding and Cryptology. Qingdao, China. 2011. 11–46. [18] 王小云, 刘明洁. 格密码学研究. 密码学报, 2014, 1(1): 13-27. [19] Ajtai M. Generating hard instances of lattice problems extended abstract. Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing. Philadelphia, PA, USA. 1996. 99–108. [20] Schoenmakers B. A simple publicly verifiable secret sharing scheme and its application to electronic voting. Proceedings of the 19th Annual International Cryptology Conference. Santa Barbara, CA, USA. 1999. 148–164.