CN114048459A - A Preemptive Multiple Secret Sharing Method Based on Cellular Automata - Google Patents

Abstract

The invention discloses a should-first multi-secret sharing method based on a cellular automaton, and an (n, n) threshold scheme based on the cellular automaton is designed and introduced in an updating stage. So that all participants can independently execute the evolution protocol and realize the share updating according to the sum of the shares sent by other participants. The design idea firstly ensures the communication complexity, and the (n, n) threshold scheme ensures that the secret can be recovered only by combining the shares of all participants, so that at most (n-1) passive attackers cannot steal the system secret. From the perspective of cellular automata methods themselves, there is a higher computational efficiency than the current mainstream polynomial-based methods. By combining the factors, the invention forms an efficient and safe proactive secret sharing mechanism.

Description

A Preemptive Multiple Secret Sharing Method Based on Cellular Automata

technical field

The invention relates to an information security application of a computer, in particular to a scheme and a system which can be directly applied to secret sharing.

Background technique

Secret sharing can be widely used in secret management and recovery to solve the security problem caused by one or a small number of groups mastering secrets. (t,n) Threshold secret sharing divides the secret information into n meaningless sub-secrets, and the secret information can be recovered only if there are at least t secrets.

From the perspective of the secret sharing process, it mainly includes four stages: initialization stage, sharing stage, update stage and reconstruction stage. Among them, the initialization phase mainly initializes the parameters and models involved in the (t,n) threshold scheme to complete the preparation. In the sharing phase, the original secret is converted into shares and managed by the secret sharing participant team. The new share is not the same as the original secret, thus achieving the protection of the secret. In the update phase, the shares in the hands of the secret sharing participants are periodically updated to ensure that the attacker cannot obtain enough shares to recover the secret by attacking the participants in the same period. In the reconstruction phase, an appropriate number of shares are selected to restore the original secret through the shares held by the secret sharing participant team.

The initialization phase, the sharing phase and the rebuilding phase are the most basic three aspects of the above-mentioned links. The introduction of the update phase is to protect the security of the secrets in the system. Therefore, from a security point of view, the above four stages are indispensable.

From the perspective of secret sharing technology theory, it mainly includes secret sharing technology based on polynomial method, secret sharing technology based on Chinese remainder theorem, secret sharing technology based on cellular automata, etc. Among them, the secret sharing technology based on the polynomial method is the most widely studied technology, and it is also the mainstream secret sharing technology. Therefore, the secret sharing technology based on the polynomial method has been deeply studied, and the research on dynamic threshold and attacker model has appeared. The dynamic threshold research is extended to allow dynamic participation groups, dynamic thresholds, etc., while the attacker model has carried out security research from two aspects: the active attacker model and the passive attacker model. In addition, the secret sharing technology based on the polynomial method also studies the security of the shares held by the secret sharing participating groups, and proposes that the shares need to be updated periodically to achieve the purpose of security protection. In contrast, the research on secret sharing technology based on the Chinese remainder theorem and cellular automata-based secret sharing technology is obviously lagging behind, and there is much less research on related dynamic participation groups, dynamic thresholds, and attacker models. In addition, the research on the update mechanism of the secret sharing technology based on the Chinese remainder theorem and the secret sharing technology based on the cellular automata is also relatively lacking, and it is still in the theoretical research stage of the combined application of cellular automata or the Chinese remainder theorem and secret sharing.

，更新阶段能够应对被动攻击者的最佳安全阈值为

Polynomial-based secret sharing technology is the mainstream secret sharing technology. It mainly decomposes secrets into secret sharing participating groups based on the polynomial solution theory, and can quickly restore the original secret through Lagrangian method. This technology generally uses Lagrangian operations, exponential operations, large numbers and modulus operations, etc. to perform secret sharing computing processes. At present, the optimal communication complexity that can be achieved by the update mechanism in the polynomial-based secret sharing technology is:

, the optimal security threshold for passive attackers in the update phase is

和

之间，相关的先应更新机制研究尚比较少。The secret sharing technology based on the Chinese remainder theorem is mainly based on the Chinese remainder theorem theory, and uses a large number of modular remainder operations. However, secret sharing schemes based on the Chinese remainder theorem are usually difficult to construct due to the strict conditions of the modulus. At present, the communication complexity of the sharing and reconstruction phase of the secret sharing technology based on the Chinese remainder theorem is

and

However, there are still few studies on the mechanism of preemptive update.

The secret sharing technology based on cellular automata is mainly based on cellular automata theory. Researchers design one-dimensional, two-dimensional and other cellular automata structures and study and find reversible characteristics, and apply reversible cellular automata theory to secrets shared realm. However, similar to the secret sharing technology based on the Chinese remainder theorem, the current cellular automata-based secret sharing scheme still lacks a prior update mechanism, and an efficient prior update mechanism is urgently needed to make up for the secret sharing based on cellular automata Program research gaps.

SUMMARY OF THE INVENTION

The purpose of the present invention is to propose a multi-secret sharing method based on cellular automata to solve the secret update problem in the secret sharing scheme based on cellular automata,

The technical solution of the present invention to achieve the above object is that a multi-secret sharing method based on cellular automata, including: an initialization stage, initializing relevant parameters of the cellular automaton, and constructing a t -order reversible linear memorable cellular automaton (hereinafter referred to as LMCA), and then construct the evolution M of t-order LMCA;

In the sharing stage, the evolution M is calculated, divided into n secret shares different from the original k secrets, and distributed to n participants;

以及更新阶段(n,n)可逆线性可记忆元胞自动机的n-1个规则参数

，n个参与者基于手中秘密份额分别以独立且并行的方式计算n个变换份额并分发给n个参与者， n个参与者再分别将所获得的全部变换份额相加得到新份额，并删除原始的秘密份额；In the update phase, a threshold scheme of (n, n) is designed and introduced, and n participants form an n-order reversible LMCA through joint negotiation, including various parameters of the reversible LCMA in the update phase: the neighbor radius in the update phase

and the n-1 regular parameters of the update stage (n,n) reversible linear memorable cellular automaton

, n participants calculate n transformation shares in an independent and parallel manner based on the secret shares in their hands and distribute them to n participants, and n participants add all the transformation shares obtained to obtain new shares, and delete them the original secret share;

In the reconstruction stage, the original k secrets are recovered after two secret recovery processes (n, n) and (t, n).

依据手中持有的份额

在连续份额序列

中的位置i来构建初始配置序列：

，其中，

，令U为LMCA 在更新阶段构建的进化，参与者

利用该进化U来计算将要分发给n个参与者的新份额。The steps of the above-mentioned update stage include: 3a), participants

According to the shares held in hand

in consecutive share series

to build the initial configuration sequence at position i:

,in,

, let U be the evolution constructed by LMCA in the update phase, the participant

Use this evolution U to calculate the new shares to be distributed to n participants.

，其中round为更新轮数，

，且

满足

。3b), n participants negotiate or set a default random evolution number

, where round is the number of update rounds,

,and

Satisfy

.

为初始化配置进化

次，形成

阶进化

。3c), with

Configure evolution for initialization

times, form

stage evolution

.

选择最后n个配置作为新的秘密份额：3d), participants

Select the last n configurations as the new secret share:

，计算

并发布本轮的

。

,calculate

and release this round of

.

依据相同顺序将新份额

分发给参与者群组

。3e), participants

new shares in the same order

Distribute to participant groups

.

将收到的来自参与者

的新份额

，计算本轮

(1 ≤𝑗≤𝑛) 来验证份额

的正确性。3f), participants

will receive from the participant

new share of

, calculate the current round

(1 ≤𝑗≤𝑛) to verify the share

correctness.

通过求和

得到

。3g), participants

by summing

get

.

通过计算

，并发布

在本轮的

完成一轮份额更新。3h), participants

via caculation

, and publish

in this round

Complete a round of share updates.

The above reconstruction phase includes two parts. First, the (n,n) scheme of the update phase is restored, including steps:

通过计算最后一轮的

（

）来验证份额

的正确性。41a), secret sharing handler

By calculating the last round of

(

) to verify the share

correctness.

与公开参数

结合，基于初始配置

构建进化U 的逆；初始化配置进化

次能够恢复出

，其中R为更新轮次总数。41b), all the shares are correct, then the continuous shares will be

with public parameters

combined, based on initial configuration

Build the inverse of evolution U; initialize the configuration evolution

able to recover

, where R is the total number of update rounds.

持有的连续份额为

，对于(t,n)方案实施恢复，需要t个连续的份额，令

是从

中选定的t个连续份额（0 ≤𝛼≤𝑛−𝑡），其中𝛼是t个连续份额的初始位置，包括步骤：Then set up a participant group

The continuous shares held are

, for the (t,n) scheme to implement recovery, t consecutive shares are required, let

From

t consecutive shares selected in (0 ≤ 𝛼 ≤ 𝑛−𝑡), where 𝛼 is the initial position of the t consecutive shares, including steps:

可以通过

来验证份额的正确性。42a) For 1≤𝑖≤𝑛, the secret sharing handler

able to pass

to verify the correctness of the share.

结合，基于初始配置

构建 M 的逆，基于前述配置

进化

+ 𝛼次恢复出

，

进化

次恢复出

。42b) When the share is correct, connect the share with the public parameters

combined, based on initial configuration

Build the inverse of M, based on the previous configuration

evolution

+ 𝛼 times restored

,

evolution

recovered

.

；如果𝑡≤𝑘，则

，并且

。42c), if 𝑡≥𝑘, then

; if 𝑡≤𝑘, then

,and

.

The method for sharing multiple secrets in response to the present invention has outstanding substantive characteristics and remarkable progress: it can provide a more efficient and secure sharing mechanism for sharing secrets in advance. The specific performance is as follows: First, the main computational overhead of the secret sharing method based on cellular automata is composed of random number generation, XOR operation and simple addition operation, and the overall operation efficiency is very efficient.

Second, the method is analyzed and verified from the perspective of confidentiality and correct key recovery, which is more secure against passive attackers than the existing technology.

Third, compared with the current mainstream best secret sharing scheme, it has the same communication complexity.

Fourth, it can be easily transformed into a decentralized parallel execution protocol.

Description of drawings

FIG. 1 is a schematic diagram of an example of preemptive multi-secret sharing based on cellular automata of the present invention.

FIG. 2 is a schematic diagram of a first-response multi-secret sharing process based on cellular automata of the present invention.

Detailed ways

In order to make the objects, features and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and specific embodiments. Obviously, the described embodiments are some, but not all, embodiments of the present application. Based on the embodiments in the present application, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present application.

In order to clearly express the implementation of the method of the present invention, the definitions of the symbols involved are shown in the following table:

。

.

，那么对于第

个细胞的邻居可以写作

。以符号

标识为细胞

在T时刻的状态值，则有：

，One-dimensional memorable cellular automata (CA for short) is a discrete system composed of a finite number of cell states, and the state value of each cell depends on the state value of its neighbors. For a CA containing N cells, if the neighbor's radius is

, then for the

The neighbors of a cell can be written

. with symbols

identified as cells

The state value at time T is:

,

（

）。Or there is an equivalent formula:

(

).

，其状态不仅依赖于上一时刻邻居的值，还在一系列规则的控制下有不同的表现，即：

（

）。其中，半径为

的CA有

种规则，规则记为

，则有：

。因此，

。At the same time, for the state of each cell

, its state not only depends on the value of the neighbors at the previous moment, but also has different performances under the control of a series of rules, namely:

(

). where the radius is

The CAs have

rules, the rules are recorded as

, then there are:

. therefore,

.

不仅依赖于上一时刻邻居的值，还依赖于过去t-1时刻邻居的状态，那么就可以称之为可记忆元胞自动机。参考AMD Rey, Mateus J P , GR Sánchez. A secret sharing scheme based on cellular automata[J]. AppliedMathematics & Computation, 2005, 170(2):1356-1364.（以下简称Rey[1]）和Eslami Z,Ahmadabadi J Z. A verifiable multi-secret sharing scheme based on cellularautomata [J]. Information Sciences, 2010, 180(15): 2889-2894.If the state of each cell

It depends not only on the value of the neighbors at the previous moment, but also on the state of the neighbors at the past time t-1, then it can be called a memorable cellular automaton. See AMD Rey, Mateus JP , GR Sánchez. A secret sharing scheme based on cellular automata[J]. AppliedMathematics & Computation, 2005, 170(2):1356-1364. (hereinafter referred to as Rey[1]) and Eslami Z,Ahmadabadi J Z. A verifiable multi-secret sharing scheme based on cellularautomata [J]. Information Sciences, 2010, 180(15): 2889-2894.

。(hereinafter referred to as Eslami[2]) The definition in the research shows that a linear memorable cellular automaton is defined by the following formula

.

的情况下，前述线性可记忆元胞自动机可逆。其逆的线性可记忆元胞自动机满足如下表达式：And Rey[1] proved that when satisfying

In the case of , the aforementioned linear memory cellular automaton is reversible. Its inverse linear memorable cellular automaton satisfies the following expression:

。

.

（

）拆分为T个初始序列

，

，

。它们都在相同的规则

下进化。当线性元胞自动机

可逆时，

也可逆。且其逆为：Proposition 1: Initial Sequence

(

) into T initial sequences

,

,

. they are all under the same rules

Evolve down. When linear cellular automata

When reversible,

Also reversible. And its inverse is:

可逆，则其逆为：

。而对于序列

有：

。考虑到除去位置i外，其它位置都为0。因此，

。可以推出

，得证。Proof: According to the reasoning proof of Rey[1] and Eslami[2], we can know that:

Invertible, then its inverse is:

. And for the sequence

Have:

. Considering that except for position i, all other positions are 0. therefore,

. can be launched

, proved.

以及更新阶段(n,n)可逆线性可记忆元胞自动机的n-1个规则参数

，n个参与者基于手中秘密份额分别以独立且并行的方式计算n个变换份额并分发给n个参与者， n个参与者再分别将所获得的全部变换份额相加得到新份额，并删除原始的秘密份额。（4）重建阶段，经过(n,n)和(t,n)两次秘密恢复过程，恢复原始的 k个秘密。Based on the research of Rey[1] and Eslami[2], the present invention proposes a multi-secret sharing method based on cellular automata based on Proposition 1. This method allows n participants to periodically update their shares while sharing k secrets to protect the security of the shares. This method includes four stages: (1) Initialization stage, which initializes cellular automata related parameters, constructs a t -order reversible LMCA, and then builds an evolution M of t-order LMCA. (2) In the sharing stage, the evolution M is calculated, divided into n secret shares different from the original k secrets, and distributed to n participants. These n shares become new secrets in the hands of n participants, or called secret shares. (3) In the update phase, a threshold scheme of (n, n) is designed and introduced, and n participants form an n-order reversible LMCA through joint negotiation, including the parameters of the reversible LCMA in the update phase: the neighbor radius in the update phase

and the n-1 regular parameters of the update stage (n,n) reversible linear memorable cellular automaton

, n participants calculate n transformation shares in an independent and parallel manner based on the secret shares in their hands and distribute them to n participants, and n participants add all the transformation shares obtained to obtain new shares, and delete them The original secret share. (4) In the reconstruction stage, the original k secrets are recovered after two secret recovery processes (n, n) and (t, n).

The concrete and process-based implementation of each stage is shown in Figures 1 and 2, and the details are as follows.

First, the initialization phase, including steps:

1a), choose a prime p that makes the discrete logarithm problem intractable in 𝐺𝐹 (𝑝), and choose a generator g for 𝐺𝐹(𝑝)\{0}; here, where GF(p) is a mathematical finite field , GaloisField (GF), p is a prime number in parentheses, when p is a prime number, F={0, 1, 2,...p-1} The addition sum of modulo operation under mod(p) Multiplication forms a finite field, and this field is denoted GF(p). p is the size of the field. The key to the difficulty of discrete logarithms is that, taking the mathematical expression used by deffie-hellman as an example: G=g^s (mod p), the discrete logarithm problem is that it is difficult to find from known G, g, p s, the key to the difficulty of the calculation here is that p is a large prime number. Combined with the following problems, the significance of this a step is to choose such a discrete logarithmic hard problem (for example: G=g^s (mod p) used by deffie-hellman), and publishing G can verify the correctness of s , but knowing G cannot deduce s (the key secret) backwards.

GF(p) identifies the mod(p) operation, so the value is between 0 and p-1. 𝐺𝐹 (𝑝)\{0} identifies the value that removes 0, that is: the field between 1 and p-1. For example, after choosing deffie-hellman's G=g^s (mod p), GF(P) is g^s(mod p). Here g can be chosen arbitrarily, for example: 2, 3, etc., or the key of the secret sharing processor D.

的大小，使之满足

并设置

，其中

为待共享秘密的最大比特位长度，邻居半径

的上标表示初始化阶段。1b), select the neighbor radius

size to satisfy

and set

,in

is the maximum bit length of the secret to be shared, neighbor radius

The superscript of the indicates the initialization phase.

，对于

满足

，所述t-1个随机数分别作为初始t个配置的规则编码，用以推动细胞的状态变化。1c), randomly select and publish random numbers

,for

Satisfy

, the t-1 random numbers are encoded as the rules of the initial t configurations, respectively, to promote the state change of the cells.

1d), through the formula

构建t阶LMCA的进化 M，

，

是半径为

的 LMCA 的局部变换函数且规则编号是

。

Construct the evolution M of the t -order LMCA,

,

is the radius of

The local transformation function of LMCA and the rule number is

.

，设置

，并选择随机的 (𝑡−𝑘) 个长度为 N 的二进制字符串填补剩余空缺；构成

；如果

，设置

。1e), calculate the initial configuration sequence: if

,set up

, and select random (𝑡−𝑘) binary strings of length N to fill the remaining vacancies; form

;if

,set up

.

利用该进化 M 来计算将要分发给n个参与者的份额。具体步骤如下：Second, the sharing phase, let M be the evolution constructed by LMCA in the initialization phase. secret handler

Use this evolution M to calculate the shares to be distributed to n participants. Specific steps are as follows:

，且

满足

；2a), randomly select an evolution number

,and

Satisfy

;

为初始化配置进化

次，形成

阶进化 M：

；2b), with

Configure evolution for initialization

times, form

Stage evolution M:

;

，计算

，并公布

；2c), if

,calculate

, and published

;

；2e)、计算

,

和发布

。2d), setting

; 2e), calculation

,

and publish

.

要求满足条件

，主要是为了确保将要分发的配置与初始的t 个配置间无重叠。选择

作为进化次数，一方面是由于参与者数量为n，需要至少n个配置；另一方面为了确保选择的最新的n个配置与初始配置无重叠，即：在

次进化基础上再次进化n次。此外，由于𝐺𝐹 (𝑝) 的离散对数难问题，公布

不会对份额本身的信息造成泄露。而在恢复阶段，

能够起到验证的作用。最后，

是公开的参数。in,

Requirements to meet the conditions

, mainly to ensure that there is no overlap between the configuration to be distributed and the initial t configurations. choose

As the number of evolutions, on the one hand, because the number of participants is n, at least n configurations are required; on the other hand, in order to ensure that the selected latest n configurations do not overlap with the initial configuration, that is: in

On the basis of the evolution, it evolves n times again. Furthermore, due to the discrete log-hard problem of 𝐺𝐹 (𝑝), it is published

There will be no leakage of the information of the share itself. During the recovery phase,

can play a role in verification. at last,

is a public parameter.

是参与者

(1 ≤𝑖≤𝑛) 手中持有的份额，则

可以通过以下过程完成份额更新操作：Third, the update stage, assuming

is a participant

(1 ≤𝑖≤𝑛) shares held in hands, then

A share update operation can be done through the following process:

依据手中持有的份额

在连续份额序列

中的位置i来构建初始配置序列：

，其中，

，令U为LMCA 在更新阶段构建的进化，参与者

利用该进化U来计算将要分发给n个参与者的新份额；3a), participants

According to the shares held in hand

in consecutive share series

to build the initial configuration sequence at position i:

,in,

, let U be the evolution constructed by LMCA in the update phase, the participant

Use this evolution U to calculate the new shares to be distributed to n participants;

，其中round为更新轮数，

，且

满足

；3b), n participants negotiate or set a default random evolution number

, where round is the number of update rounds,

,and

Satisfy

;

为初始化配置进化

次，形成

阶进化

；3c), with

Configure evolution for initialization

times, form

stage evolution

;

选择最后n个配置作为新的秘密份额：3d), participants

Select the last n configurations as the new secret share:

，计算

并发布本轮的

,calculate

and release this round of

；

;

依据相同顺序将新份额

分发给参与者群组

；3e), participants

new shares in the same order

Distribute to participant groups

;

将收到的来自参与者

的新份额

，计算本轮

(1 ≤𝑗≤𝑛) 来验证份额

的正确性；3f), participants

will receive from the participant

new share of

, calculate the current round

(1 ≤𝑗≤𝑛) to verify the share

correctness;

通过求和

得到

；3g), participants

by summing

get

;

通过计算

，并发布

在本轮的

完成一轮份额更新。3h), participants

via caculation

, and publish

in this round

Complete a round of share updates.

Fourth, in the reconstruction stage, to restore the original k secrets, it needs to go through two secret recovery processes (n, n) and (t, n) respectively.

First, restore the (n,n) scheme of the update phase, including steps:

通过计算最后一轮的

（

）来验证份额

的正确性；41a), secret sharing handler

By calculating the last round of

(

) to verify the share

correctness;

与公开参数

结合，基于初始配置

构建进化U 的逆；初始化配置进化

次能够恢复出

，其中R为更新轮次总数；41b), all the shares are correct, then the continuous shares will be

with public parameters

combined, based on initial configuration

Build the inverse of evolution U; initialize the configuration evolution

able to recover

, where R is the total number of update rounds;

持有的连续份额为

，对于(t,n)方案实施恢复，需要t个连续的份额，令

是从

中选定的t个连续份额（0 ≤𝛼≤𝑛−𝑡），其中𝛼是t个连续份额的初始位置，包括步骤：Then set up a participant group

The continuous shares held are

, for the (t,n) scheme to implement recovery, t consecutive shares are required, let

From

t consecutive shares selected in (0 ≤ 𝛼 ≤ 𝑛−𝑡), where 𝛼 is the initial position of the t consecutive shares, including steps:

可以通过42a) For 1≤𝑖≤𝑛, the secret sharing handler

able to pass

来验证份额的正确性；

to verify the correctness of the share;

结合，基于初始配置

构建 M 的逆，基于前述配置

进化

+ 𝛼次恢复出

，

进化

次恢复出

；42b) When the share is correct, connect the share with the public parameters

combined, based on initial configuration

Build the inverse of M, based on the previous configuration

evolution

+ 𝛼 times restored

,

evolution

recovered

;

；如果𝑡≤𝑘，则

，并且

。42c), if 𝑡≥𝑘, then

; if 𝑡≤𝑘, then

,and

.

In addition, the present invention also defines the following security model for the implementation and verification of the multi-secret sharing method. In general, passive attackers are a class of honest but curious attackers who do not disrupt the normal operation of the protocol, but deliberately retain some information to achieve the goal of stealing secrets. Once an active attacker captures a node, it steals the secret data on it and vandalizes the protocol it should abide by. Compared with passive attackers, active attackers can be easily detected and eliminated once they initiate malicious behavior. Passive attackers quietly complete the stealing of secrets, which is even more harmful. The present invention mainly faces passive attackers, and designs a scheme that is more tolerant to passive attackers.

Reference [3] Hirt M, Maurer U, Lucas C. A dynamic tradeoff between active and passive corruptions in secure multi-party computation [C]//AnnualCryptology Conference. Springer, 2013: 203- 219. and Dolev S, Eldefrawy K, Lampkins J, et al. Proactive secret sharing with a dishonest majority [C]//International Conference on Security and Cryptography for Networks. Springer, 2016: 529-548. For the security definition of secret sharing scheme, the present invention defines security as correctness and Confidentiality.

，称先应秘密共享协议是安全的，当其满足以下条件：A passive attacker in the face of any probabilistic polynomial-time model with a threshold of a

, claiming that the first secret sharing protocol is secure when it satisfies the following conditions:

控制了委员会中的 a 个成员。基于该 a个成员手中的秘密份额，攻击者

一定得不到秘密，则表示系统满足保密性。Secrecy: At any time, the attacker

Controls a member of the committee. Based on the secret share in the hands of the a members, the attacker

If the secret must not be obtained, it means that the system satisfies the confidentiality.

的干扰下，选定连续秘密份额。如果恢复的秘密𝑆′与原始秘密𝑆保持一致，则是系统正确运行。Correctness: On the premise that the secret is recoverable and the attacker cannot

Under the interference of , select consecutive secret shares. If the recovered secret 𝑆' is consistent with the original secret 𝑆, then the system is functioning correctly.

Based on the above embodiments, compared with the existing mainstream solutions, the security analysis and performance analysis are as follows.

能够很好的验证份额的正确性。做到及时发现和纠正不正确的份额。因此，在任意时刻选定连续秘密份额都可以正确的恢复秘密。综上所述，在不泄露任何秘密并始终确保正确恢复秘密的前提下，本协议能够安全的抵抗最多（n-1）个被动攻击者的存在。在应对被动攻击者的安全系统中，阈值（n-1）是当前相关研究能够做到的最好水平。1. Security analysis, a (n,n) scheme is constructed in the update phase, which means that the original secret can always be recovered only by the shares in the hands of all participants. Therefore, the presence of at most (n-1) passive attackers can only gain at most (n-1) shares. This ensures that a passive attacker can never recover the secret, so that the system satisfies secrecy. Furthermore, passive attackers do not compromise the protocol of the system. At the same time, by computing and publishing

The correctness of the share can be well verified. Make timely detection and correction of incorrect shares. Therefore, the secret can be correctly recovered by selecting consecutive secret shares at any time. To sum up, under the premise of not revealing any secrets and always ensuring that the secrets are recovered correctly, this protocol can safely resist the existence of at most (n-1) passive attackers. In the security system to deal with passive attackers, the threshold (n-1) is the best level that current related research can do.

对持有的份额

计算新份额

并分发给n个参与者。该环节每个参与者

的通信复杂度为

，因此总的通信复杂度为

。如下表2. Performance analysis, the first update mechanism proposed by the present invention is in the update stage, each participant

share of holding

Calculate new shares

and distributed to n participants. Each participant in this session

The communication complexity is

, so the total communication complexity is

. The following table

shown. Among them, Maram[5] refers to Sai Krishna Deepak Maram, Fan Zhang, et al. CHURP: Dynamic-Committee Proactive Secret Sharing[C]//In Proceedings of the2019 ACM SIGSAC Conference on Computer and Communications Security (CCS '19). New York, NY, USA, 2019: 2369–2386. And Eldefrawy[6] refers to Eldefrawy K., LepointT., Leroux A. Communication-Efficient Proactive Secret Sharing for DynamicGroups with Dishonest Majorities[C]//International Conference on AppliedCryptography and Network Security(ACNS 2020). 2020:3- twenty three. It can be seen that, compared with the mainstream polynomial-based secret sharing method, the present invention has the same level of communication complexity.

In addition, the main operations of the update mechanism based on cellular automata consist of simple addition, XOR operation, and random number generation. Low time complexity.

The method for sharing multiple secrets provided by the present application has been described in detail above. In the present invention, specific examples are used to illustrate the principles and implementations of the present application. The descriptions of the above embodiments are only used to help understand the method of the present application. and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the application, there will be changes in the specific implementation and application scope. To sum up, the content of this specification should not be construed as a limits.

Claims (5)

1. a multi-secret sharing method based on cellular automata, is characterized in that comprising: In the initialization stage, the relevant parameters of the cellular automaton are initialized, a reversible linear memorable cellular automaton of order t is constructed, and then the evolution M of the cellular automaton with order t linearity and memory is constructed; In the sharing stage, the evolution M is calculated, divided into n secret shares different from the original k secrets, and distributed to n participants; In the update phase, a threshold scheme of (n,n) is designed and introduced, and n participants form an n-order reversible linear memorable cellular automaton through joint negotiation, including the parameters of the reversible linear memorable cellular automaton in the update phase : update phase neighbor radius

and the n-1 regular parameters of the update stage (n,n) reversible linear memorable cellular automaton

, n participants calculate n transformation shares in an independent and parallel manner based on the secret shares in their hands and distribute them to n participants, and n participants add all the transformation shares obtained to obtain new shares, and delete them the original secret share; In the reconstruction stage, the original k secrets are recovered after two secret recovery processes (n, n) and (t, n). 2. The multi-secret sharing method based on cellular automata according to claim 1, wherein the step of the initialization phase comprises: 1a), choose a prime p to make the discrete logarithm problem intractable in 𝐺𝐹 (𝑝), and choose a generator g for 𝐺𝐹 (𝑝)\{0}; 1b), select the neighbor radius

size to satisfy

and set

,in

is the maximum bit length of the secret to be shared, neighbor radius

The superscript indicates the initialization phase; 1c), randomly select and publish random numbers

,for

Satisfy

, the t-1 random numbers are encoded as the rules of the initial t configurations, respectively, to promote the state change of the cell; 1d), through the formula

Construct the evolution M of a linear memorable cellular automaton of order t ,

,

is the radius of

The local transformation function of the linear memorable cellular automaton of and the rule number is

; 1e), calculate the initial configuration sequence: if

,set up

, and select random (𝑡−𝑘) binary strings of length N to fill the remaining vacancies; form

;if

,set up

. 3. The multi-secret sharing method based on cellular automata according to claim 1, it is characterized in that the step of described sharing stage comprises: 2a), randomly select an evolution number

,and

Satisfy

; 2b), with

Configure evolution for initialization

times, form

stage evolution

; 2c), if

,calculate

, and published

; 2d), setting

; 2e), calculation

,

and publish

. 4. The multi-secret sharing method based on cellular automata according to claim 1, it is characterized in that the step of described update stage comprises: 3a), participants

According to the shares held in hand

in consecutive share series

to build the initial configuration sequence at position i:

,in,

, let U be the evolution constructed by a linear memorable cellular automaton in the update phase, the participant

Use this evolution U to calculate the new shares to be distributed to n participants; 3b), n participants negotiate or set a default random evolution number

, where round is the number of update rounds,

,and

Satisfy

; 3c), with

Configure evolution for initialization

times, form

stage evolution

; 3d), participants

Select the last n configurations as the new secret share:

,calculate

and release this round of

; 3e), participants

new shares in the same order

Distribute to participant groups

; 3f), participants

will receive from the participant

new share of

, calculate the current round

to verify the share

correctness; 3g), participants

by summing

get

; 3h), participants

via caculation

, and publish

in this round

Complete a round of share updates. 5. The multi-secret sharing method based on cellular automata according to claim 1, characterized in that the reconstruction phase comprises two parts, firstly, the (n,n) scheme of the update phase is restored, comprising the steps of: 41a), secret sharing handler

By calculating the last round of

(

) to verify the share

correctness; 41b), all the shares are correct, then the continuous shares will be

with public parameters

combined, based on initial configuration

Build the inverse of evolution U; initialize the configuration evolution

able to recover

, where R is the total number of update rounds; Then set up a participant group

The continuous shares held are

, for the (t,n) scheme to implement recovery, t consecutive shares are required, let

From

t consecutive shares selected in (0 ≤ 𝛼 ≤ 𝑛−𝑡), where 𝛼 is the initial position of the t consecutive shares, including steps: 42a) For 1≤𝑖≤𝑛, the secret sharing handler

able to pass

to verify the correctness of the share; 42b) When the share is correct, connect the share with the public parameters

combined, based on initial configuration

Build the inverse of M, based on the previous configuration

evolution

+ 𝛼 times restored

,

evolution

recovered

; 42c), if 𝑡≥𝑘, then

; if 𝑡≤𝑘, then

,and

.

Images