# Multiparty secret sharing based on hidden multipliers

Vitaly Roman’kov

111The study was carried out within the framework of the state contract of the
Sobolev Institute of Mathematics (project no. 0314-2019-0004).

Sobolev Institute of Mathematics of RAS (Omsk Branch), Omsk, Russia

<EMAIL_ADDRESS>
Abstract:

Secret sharing schemes based on the idea of hidden multipliers in encryption
are proposed. As a platform, one can use both multiplicative groups of finite
fields and groups of invertible elements of commutative rings, in particular,
multiplicative groups of residue rings. We propose two versions of the secret
sharing scheme and a version of ($k,n$)-thrested scheme. For a given $n$, the
dealer can choose any $k.$ The main feature of the proposed schemes is that
the shares of secrets are distributed once and can be used multiple times.
This property distinguishes the proposed schemes from the secret sharing
schemes known in the literature. The proposed schemes are semantically secure.
The same message can be transmitted in different forms. From the transferred
secret $c$ it is impossible to determine which of the two given secrets
$m_{1}$ or $m_{2}$ was transferred. For concreteness, we give some numerical
examples.

Keywords: cryptography, multiparty, secret sharing, ($k,n$)-thrested scheme,
hidden multipliers.

##  1\. Introduction

Sharing secrets was introduced in 1979 by Shamir [1] and Blakely [2]. Since
then, many applications have emerged for several different types of
cryptographic protocols. At the same time, research on some of the major open
problems in secret sharing has led to the development of a rich mathematical
theory related to combinatorics, information theory, algebra, and other
fields. A secret sharing scheme involves a dealer who holds a secret. This
dealer distributes pieces of its secret (called shares) to a set of
participants. Only qualified participant groups that form the schema’s access
structure can recover a complete secret using the shared resources available
to them, and therefore only they can read the transmitted message.

This paper discusses the unconditionally secure committed secret sharing
schemes. These are the schemes in which the unqualified sets of participants
cannot obtain any partial information about the transmitted message. The
reader is referred to [3] for an introduction to secret sharing. See also
survey [4] and papers [5] – [12] for some secret sharing schemes.

The main goal of this article is to build schemes that provide for the reuse
of once distributed secret resources. This is possible only in cases where the
allocated secret shares are not revealed when the complete secret is built on
their basis. It should also be possible to add, remove or replace qualified
group members without changing their shares of the secret. These properties
show the advantages of the proposed scheme in comparison with the known secret
distribution schemes. The proposed schemas are semantically secure. The same
message can be transmitted in different forms. From the transferred secret $c$
it is impossible to determine which of the two given secrets $m_{1}$ or
$m_{2}$ was transferred.

For example, in Shamir’s scheme the secret is a polynomial function $f(x).$ If
$n$ is the degree of $f(x)$, then for its restoration it is required to know
$f(x_{i})$’s at $n$ different points $x_{1},\ldots,x_{n}.$ Therefore, any
subset of at least $n$ members (provided that their at least $n$ points are
different) will be qualified. Any subset of $m\leq n-1$ members is
unqualified. However, once the secret is recovered, it becomes known to all
participants and cannot be reused.

We propose schemes such that the initial distribution of shares of the secret
between all participants in the process is carried out either using a secure
communication channel, or using the protocol of secret key transfer over an
open communication channel. The entire further process is carried out over an
public network.

If $m\leq n$ then an ($m,n$)-threshold scheme is one with $n$ total
participants and in which any $m$ participants can combine their shares and
recover the secret but not fewer than $m$. The number $m$ is called the
threshold. It is a secure secret sharing scheme if given less than the
threshold there is no chance to recover the secret. Using our approach, we
also propose an ($m,n$)-scheme for arbitrary parameters $m,n;m\leq n.$ For a
given $n$, the dealer can choose any $m$ without redistributing shares. This
scheme is monotone, i.e., any set of $k\geq m$ participants is qualified.

Notation: $\mathbb{Z}$ – set of integer numbers,
$\mathbb{Z}_{n}=\mathbb{Z}/n\mathbb{Z}$ – residue ring, $\mathbb{N}$ – set of
nonnegative integer numbers, $\mathbb{N}_{k}=\\{1,\ldots,k\\}.$

##  2\. Construction of fields with prescribed orders of subgroups of
multiplicative groups

The main idea behind the corresponding algorithm is the following statement.

######  Proposition 1.

([13], Fact 4.59). Let $n\geq 3$ be an odd integer, and suppose that $n=1+rq$,
where $q$ is an odd prime and $r$ is even positive integer. Suppose further
that $r<q$.

  * •

If there exists an integer $a$ satisfying $a^{n-1}\equiv 1(\bmod\,n)$ and
gcd($a^{r}-1,n$) = $1$, then $n$ is prime.

  * •

If $n$ is prime, the probability that a randomly selected base $a,1\leq a\leq
n-1$, satisfies $a^{n-1}\equiv 1(\bmod\,n)$ and gcd($a^{r}-1,n$) = $1$ is
$\frac{q-1}{q}$.

Maurer’s algorithm for generating provable primes (Algorithm 4.62 in [13])
recursively generates an odd prime $n$, and then chooses random even integers
$r,r<q$, until $n=1+rq$ can be proven prime using for some base $a$. By
proposition 1 the proportion of such bases is $1-1/q$ for prime $n$. On the
other hand, if $n$ is composite, then most bases $a$ will fail to satisfy the
condition $a^{n-1}\equiv 1(\bmod\,n)$.

Let’s describe this algorithm.

  1. (1)

We start with an odd prime $q=q_{1}$.

  2. (2)

Let’s choose an even $r$ at random:

$q\leq r\leq 4q+2.$

  3. (3)

Consider

$n=qr+1,\,q\leq r\leq 4q+2.$

  4. (4)

Choose randomly the number $a=a_{1}$ within $1<a<n-1$ and check the
fulfillment of conditions from proposition 1. If $a=a_{1}$ does not satisfy
these conditions, then we take another random number $a=a_{2}$. So we repeat a
sufficient number of times: $a=a_{1},a_{2},\ldots,a_{k}$ until we find a
suitable value $a$.

If you succeed in doing this, then $n$ is prime. We put $q=q_{2}=n$ and repeat
the construction starting from first step. We do this until don’t get a big
enough prime.

If, with a large number of trials for $a$, it was not possible to execute the
conditions of proposition 1, then we change $r$ and repeat everything again.

Suppose that the constructed number $n$ is indeed prime. Let us ask ourselves
what is the probability of finding the number $a$ with the given properties
from proposition 1. First, note that the condition $a^{n-1}=1(\bmod\,n)$ will
be automatically satisfied by Fermat’s Little Theorem. In this case (for prime
$n$) the second condition gcd($a^{n-1/q}-1,n)=1$ $\sim$ gcd$(a^{r}-1,n)=1$ is
satisfied if and only if $a^{r}\neq 1(\bmod\,n)$. In the field
$\mathbb{F}_{n}$, the equation $x^{r}=1$ has at most $r$ roots, one of which
is equal to $1$, and the second $n-1$. Therefore, on the interval $1<a<n-1$,
there are at most $r-2$ numbers $r$ for which $a^{r}=1$ in the field
$\mathbb{F}_{n}.$ This means that the probability of choosing such $a$ is no
more than $\frac{r-2}{n-3}\sim\frac{r}{qr}=\frac{1}{q}$.

Note also that the thus constructed prime $n$ will be is greater than $q^{2}$
because $q\leq r$ and $n=qr+1$. When sequential construction of primes
$q_{1},q_{2},\ldots$ they grow no less than quadratically.

Let’s ask another question: how realistic is it to find prime number $n=qr+1$
under the indicated constraints $q\leq r\leq 4q+2$, choosing an even $r$.

First of all, note that , by the famous Dirichlet theorem, the progression
$n=2qt+1$ ($t=0,1,2,3,\ldots$) contains infinitely many prime numbers. We are
interested in primes $n$ of the indicated form with possible small parameters
$t=1,2,\ldots$. If the generalized Riemann hypothesis is true, then the
smallest prime number in the indicated sequence does not exceed
$c(\varepsilon)q^{2+\varepsilon}$ for any $\varepsilon>0$ ($c(\varepsilon$ is
a constant, depending on $\varepsilon$). Calculation experience shows that
primes in the specified sequence occur quite often and close to its beginning.
Note also that, according to the theory known numbers to Cramer’s hypothesis
$p_{n+1}-p_{n}=0(\ln^{2}p_{n})$ (here $p_{n}$ denotes the $n$th prime number
in order). Roughly the same follows from the generalized Riemann hypothesis.

Suppose we need to construct a prime $p$ such that $p-1=r$ and $r$ is
divisible by the product of $n+1$ pairwise coprime numbers $d$ and
$t=\prod_{i=1}^{n}t_{i},$ i.e., $r=dtr^{\prime}$. This can be effectively done
by the process just described, by choosing the parameter $r$ dividing to $dt$
and $r^{\prime}$ dividing to $q$. Then we obtain the prime number $p=1+r$ and
build the finite field $\mathbb{F}_{p}$ of order $p.$ We can assume that
$d=t-1$ which is coprime with any number $t_{i}$. The order $p-1$ of the
multiplicative group $\mathbb{F}_{p}^{\ast}$ divides to $r$.

Therefore $\mathbb{F}_{p}^{\ast}$ contains $n$ cyclic subroups $T_{i}$ =
gp($u_{i}$), where $|u_{i}|=t_{i},i=1,\ldots,n,$ and subgroup $F$ = gp($f$) of
order $d$. Let $g$ generates $\mathbb{F}_{p}^{\ast}$. The elements $u_{i}$ are
efficiently computable by the formula $u_{j}=g^{\frac{r}{t_{j}}}$. The element
$f$ is computed as $f=g^{\frac{r}{d}}.$

Of course, there is another way to find the prime number $p$ for which $p-1$
is divisible by the product $dt$, as above. We select the even numbers
$r^{\prime}$ in a certain interval and check the simplicity of the number
$p=1+drr^{\prime}$ using well-known tests (for example, the Miller-Rabin test
(see [13]). The check goes on until a simple $p$ is obtained. This method is
effective and often used in practical cryptography.

The indicated method of constructing the subgroups $T_{i},i=1,\ldots,n$ and
$F$, as above, is obviously extended to residue rings, in particular, to rings
of the form $\mathbb{Z}_{n},n=pq$, where $p$ and $q$ are different primes. In
this case, we can construct the primes $p$ and $q$ with the desired sets of
divisors for the numbers $p-1$ and $q-1$, and then use them in our
construction. See [14], [16] or [17] for details.

##  3\. Version of encryption with hidden factors

The main idea used to construct a new secret sharing protocol is the
encryption scheme proposed in the works of the author [14] and [16]. Let $p$
and $q$ are two large different prime numbers and $n=pq$. Encryption platform
- multiplicative group $\mathbb{Z}_{n}^{\ast}$ of a residual ring
$\mathbb{Z}_{n}$, in which two subgroups $F$ and $H$ of coprime exponents
exp($F$) $=k$ and exp($H$) $=l$ are defined. Recall that, the exponent of a
group is defined as the least common multiple of the orders of all elements of
the group. The subgroup $F$ serves as the message space, and $H$ is the space
of hidden multipliers. Both of these subgroups $F$ and $H$ are publicly
available. The numbers $k$ and $l$ are private. Alice, the owner of the
system, computes the number $l^{\prime}$ such that $ll^{\prime}=1(\bmod\,k).$
It follows, that $f^{ll^{\prime}}=f$ for any element $f\in F.$ The numbers $l$
and $l^{\prime}$ are private.

Suppose Bob wants to send a message to Alice, who is the organizer of the
system. Alice will receive and decrypt this message. The algorithm works as
follows:

  1. (1)

Bob encodes the message as $f\in F$, chooses $h\in H$ at random and sends
$c=hf$ to Alice.

  2. (2)

Alice computes

$c^{ll^{\prime}}=(h^{l})^{l^{\prime}}f^{ll^{\prime}}=f.$

The secrecy of the proposed scheme is based on the intractability of
calculating the order of an element in a finite field. See [14], [16] or [17].

Similar encryption is also possible on the multiplicative group
$\mathbb{F}_{p^{r}}^{\ast}$ of any finite field $\mathbb{F}_{p^{r}}$. Here we
give a toy example for the scheme.

######  Example 2.

Let $p=8317,$ then $p-1=8316=2^{2}\cdot 3^{3}\cdot 7\cdot 11=108\cdot 77.$
Then $\mathbb{F}_{p}^{\ast}$ = gp($3$). In the group $\mathbb{F}_{p}^{\ast}$,
Alice takes two elements: $f=3^{77}=3113$ and $h=3^{108}=4610$, and defines
two subgroups: $F=$ gp($f$) and $H=$ gp($h$) of coprime exponents
$108=2^{2}\cdot 3^{3}$ and $77=7\cdot 11$ respectively. She also computes
$77^{-1}=101(\bmod\,108)$, more exactly: $77\cdot 101=7777=1+108\cdot 72.$
Then for any $m\in F$ one has $m^{108}=1$ and $m^{7777}=m.$ For any $u\in H$
one has $u^{77}=1.$

Suppose Bob wants to send the message $m=f^{i}$ ($i\in\mathbb{Z}$) to Alice.
He chooses $u=h^{j}$ ($j\in\mathbb{Z}$) and sends $c=um.$ Alice computes as
follows:

$c^{7777}=(u^{77})^{101}m(m^{108})^{72}=m.$

######  Remark 3.

Of course, one can use as a platform the multiplicative group $K^{\ast}$ of
any commutative associative ring $K$ with unity, provided that large subgroups
of coprime exponents can be chosen in $K$, and the problem of calculating the
order of an element is intractable. One of the advantages of this system over
the original RSA version is its semantic secrecy. See [14], [16] or [17] for
details.

##  4\. Multiparty secret sharing protocol description

Let ${\mathcal{A}}$ be the system which is organized and managed by Alice. Let
$\\{B_{1},\ldots,B_{n}\\}$ be the set of users in ${\mathcal{A}}.$

Version 1

When setting up the system ${\mathcal{A}}$, Alice takes a set of pairwise
coprime positive integers $t_{1},\ldots,t_{n}$. Let $t=\prod_{i=1}^{n}t_{i}$.
Alice also defines $d=t-1$ or $d=t+1.$ Then Alice chooses a large prime finite
field $\mathbb{F}_{p},\,p-1=r,$ where $r=dtr^{\prime},$ for some
$r^{\prime}\in\mathbb{N}$, while simultaneously defining the set of subgroups
$T_{i}=$ gp($u_{i}$) ($i=1,\ldots,n$) and $F=$ gp($f$) of the multiplicative
group $\mathbb{F}_{p}^{\ast}$ of the corresponding orders $t_{1},\ldots,t_{n}$
and $d$, respectively. The corresponding algorithm has been given in Section
2. The prime $p$ and consequently field $\mathbb{F}_{p}$ are public. The
subgroups $T_{1},\ldots,T_{n},F$ and their corresponding orders
$t_{1},\ldots,t_{n},d$ are private. Let $H=\prod_{i=1}^{n}T_{i}$. The subgroup
$F$ serves as the space of possible secrets, and $H$ is the space of hidden
multipliers.

Then Alice distributes the numbers (shares) $t_{1},\ldots,t_{n}$ among the
users $B_{1},\ldots,B_{n}$ of ${\mathcal{A}}$ corresponding to their indexes.
Each user $B_{i}$ receives the share $t_{i}.$ This distribution is carried out
either over a secure communication channel, or is transmitted in encrypted
form over an open channel. These shares are for future reuse.

Let $m\in F$ be a message that Alice wants to send to some (qualified) set of
users of the system $B(m)=B_{i_{1}}\cup\ldots\cup B_{i_{w}},1\leq
i_{1}<\ldots<i_{w}\leq n.$ Alice acts as follows:

  1. (1)

Alice randomly selects nontrivial elements $v_{i_{j}}\in
T_{i_{j}},\,j=1,\ldots,w.$ Then she computes $c=\prod_{j=1}^{w}v_{i_{j}}\cdot
m^{t/\prod_{j=1}^{w}t_{i_{j}}}$. She sends $c$ to the coalition $B(m).$

  2. (2)

Members of the coalition $B(m)$ sequentially raise the obtained element $c$ to
the power $t_{j}$ for $j=1,\ldots,w.$ In the case $d=t-1$, they get element

$m^{t}=m^{d+1}=m.$

If $d=t+1$, they get

$m^{t}=m^{d-1}=m^{-1}$

and compute $m.$

Obviously, Alice can send the message $m$ to any possible coalition of users
in this way. Any unqualified coalition will not be able to reveal the message
$m$ in some natural way. If this coalition does not contain the user
$B_{i_{j}}$ it cannot remove the factor $v_{i_{j}}$ and obtain also $m^{t}.$

This scheme is not monotonous. Moreover, interference with the disclosure of a
secret by any member outside the qualified coalition results in an incorrect
secret.

Let us illustrate this scheme with an example. We use the notation introduced
above.

######  Example 4.

Let $p=6091,p-1=6090=2\cdot 3\cdot 5\cdot 29\cdot
7,t_{1}=2,t_{2}=3,t_{3}=5,d=29,t=30.$ Then $\mathbb{F}_{p}=$ gp($2$),
$u-1=2^{3045}=3045,u_{2}=2^{2030}=4247,u_{3}=2^{1218}=5842,f=2^{210}=2901.$
The qualified coalition is $B_{1}\cup B_{2}\cup B_{3}$.

Alice takes $v_{1}=u_{1}=3045,v_{2}=u_{2}^{2}=1558,v_{3}=u_{3}^{2}=1091.$ She
chooses the message $m=f^{3}=2^{630}=5948$ and sends
$c=v_{1}v_{2}v_{3}m=2^{4081}=808.$ The coalition recovers the message as
$c^{t}=m.$

Version 2.

This version can be used to decrease $d$ (while decreasing $p$). Let $d$ be a
sufficiently large positive integer. Alice choose the number $t_{1}$ which is
coprime to $d$ and computes $t_{1}^{\prime}$ such that
$t_{1}t_{1}^{\prime}=1(\bmod\,d).$ Note that $t_{i}^{\prime}$ is also coprime
to $d.$ Then Alice takes a random $t_{2}$ coprime to $d$ and computes
$t_{2}^{\prime}$ such that $t_{2}t_{2}^{\prime}=1(\bmod\,d)$ with the
constraint that $t_{2}t_{2}^{\prime}$ is coprime to $t_{1}t_{1}^{\prime}$.
Alice continues this process and gets a set of elements
$\tilde{t}_{i}=t_{i}t_{i}^{\prime}$ for $i=1,\ldots,n,$ all of whose members
are pairwise coprime and coprime to $d$.

Now Alice takes as above the prime finite field
$\mathbb{F}_{p},\,p-1=r,r=dtr^{\prime},t=\prod_{i=1}^{n}t_{i}.$ while
simultaneously defining the set of subgroups $T_{i}=$ gp($u_{i}$)
($i=1,\ldots,n$) and $F=$ gp($f$) of the multiplicative group
$\mathbb{F}_{p}^{\ast}$ of orders $t_{1},\ldots,t_{n}$ and $d$, respectively.
The corresponding algorithm has been given in Section 2. The prime $p$ and
consequently field $\mathbb{F}_{p}$ are public. The subgroups
$T_{1},\ldots,T_{n},F$ and their corresponding orders $t_{1},\ldots,t_{n},d$
are private. Let $H=\prod_{i=1}^{n}T_{i}$. The subgroup $F$ serves as the
space of possible secrets, and $H$ is the space of hidden multipliers.

Then Alice distributes the numbers (shares)
$\tilde{t}_{1},\ldots,\tilde{t}_{n}$ among the users of ${\mathcal{A}}$
corresponding to their indexes. Each user $B_{i}$ receives the share
$\tilde{t}_{i}.$ This distribution is carried out either over a secure
communication channel, or is transmitted in encrypted form over an open
channel. These shares are for future reuse.

Let $m\in H$ be a message that Alice wants to send to some (qualified) set of
users of the system $B(m)=B_{i_{1}}\cup\ldots\cup B_{i_{w}},1\leq
i_{1}<\ldots<i_{w}\leq n.$ Alice acts as follows:

  1. (1)

Alice randomly selects nontrivial elements $v_{i_{j}}\in
T_{i_{j}},\,j=1,\ldots,w.$ Then she computes $c=\prod_{j=1}^{w}v_{i_{j}}\cdot
m$. She sends $c$ to the coalition $B(m).$

  2. (2)

Members of the coalition $B(m)$ sequentially raise the element $c$ and
elements successively received from it to the power $\tilde{t}_{j}$ for
$j=1,\ldots,w.$

The first step gives the element

$c_{i_{1}}=v_{i_{2}}^{\tilde{t}_{i_{1}}}\cdots
v_{i_{w}}^{\tilde{t}_{i_{1}}}\cdot m.$

This means that the first factor has been removed from the record. The rest of
the factors before $m$ retained their orders, since these orders are coprime
to $\tilde{t}_{i_{1}}$. Continuing the process, they sequentially remove all
factors except $m$, which remains unchanged for all exponentiations. As a
result, they get the element $m$.

Unlike version 1, this version is monotonous. Any coalition containing a
qualified coalition also reveals the secret. This is due to the fact that each
raising to the power, which is a share of the secret, does not change the
multiplier $m$. Exactly one coalition reveals the correct secret. In this
case, the coalition is not obliged to know whether it is qualified in this
case.

We give a toy example for the second version of the scheme.

######  Example 5.

Let us choose as a platform the multiplicative group $\mathbb{Z}_{n}^{\ast}$
of the modular ring $\mathbb{Z}_{n},n=pq,$ where $p=8317$ is a prime number
from Example 2, and $q=31.$ Then $n=257827.$

First, Alice solves the system of congruences:

$\begin{cases}f_{1}\equiv 3113(\bmod\,p),\\\ f_{1}\equiv
1(\bmod\,q).\end{cases}$

By the Chinese Remainder Theorem she gets $f_{1}\equiv 77966(\bmod\,n).$ The
exponent of $f_{1}\in\mathbb{Z}_{n}^{\ast}$ is equal to $108$ (the exponent of
$f\in\mathbb{F}_{p}^{\ast}$; see Example 2). The subgroup $F=$
gp($f_{1}$)$\in\mathbb{Z}_{n}^{\ast}$ is the message space.

In the similar way Alice solves the system:

$\begin{cases}h_{1}\equiv 4610(\bmod\,p),\\\ h_{1}\equiv
1(\bmod\,q).\end{cases}$

She finds a solution $h_{1}=71146(\bmod\,n)$. Therefore
$h_{1}\in\mathbb{Z}_{n}^{\ast}$ has the exponent $77$ (the exponent of
$h\in\mathbb{F}_{p}^{\ast}$; see Example 2). Then $77\cdot 101=7777\equiv
1(\bmod\,108).$ The first share of the secret is $t_{1}=7777.$ For each $m\in
F$, $m^{t_{1}}=m$ is fulfilled. For each $u_{1}\in$gp($h_{1}$) we get
$u_{1}^{t_{1}}=1.$

Element $16\in\mathbb{F}_{q}^{\ast}$ has exponent $5$. Congruences

$\begin{cases}h_{2}\equiv 1(\bmod\,p),\\\ h_{2}\equiv
16(\bmod\,q).\end{cases}$

have a solution $h_{2}=99805$. Then $h_{2}\in\mathbb{Z}_{n}^{\ast}$ has the
exponent $5$. Since $325=5\cdot 65\equiv 1(\bmod\,108)$ the number $t_{2}=325$
will be the second share of the secret. For each $m\in F$ one has
$m^{t_{2}}=m.$ For each $u_{2}\in$gp($h_{2}$) we get $u_{2}^{t_{2}}=1.$

Let the qualified coalition consists of two users $B_{1}$ and $B_{2}$, that
have two shares of the secret $t_{1}$ and $t_{2}$ respectively.

Suppose Alice wants to send the message $m=f^{i}$ ($i\in\mathbb{Z}$) to the
qualified coalition $B_{1}\cup B_{2}$. She chooses $u_{1}=h_{1}^{s_{1}}$ and
$u_{2}=h_{2}^{s_{2}}\,(1\leq s_{1},s_{2}\leq 107)$. Then Alice sends
$c=u_{1}u_{2}m$ to $B_{1}\cup B_{2}$. The coalition computes as follows:

$c^{t_{1}}=u_{1}^{t_{1}}\cdot u_{2}^{t_{1}}\cdot m^{t_{1}}=u_{2}^{t_{1}}\cdot
m;$ $(u_{2}^{t_{1}}\cdot m)^{t_{2}}=(u_{2}^{t_{2}})^{t_{1}}\cdot m^{t_{2}}=m.$

##  5\.  ($k,n$) - thrested scheme

This proposition bases on the version 2 of the multiparty sharing protocol
described in Section 4. Let us prove a preliminary statement.

######  Lemma 6.

Let $n\in\mathbb{N}.$ For any $k\in\mathbb{N}_{n}$, there exists a set
$T(k)=\\{t_{0},t_{1},\ldots,t_{l_{k}}\\}$, which can be represented as a union
of $n$ subsets $T_{j}(k)$ ($j=1,\ldots,n$) such that the union of any $k$
subsets coincides with $T(k)$, and the union of a smaller number is strictly
less than $T(k)$.

###### Proof.

Induction by $k$. The statement is true for $k=1$, when one can define
$T_{j}=t_{0}$ for any $j$. Assume that the statement is true for $k-1$ and
$T(k-1)=\\{t_{0},\ldots,t_{l_{k-1}}\\}.$

We enumerate all subsets of the set $\mathbb{N}_{n}$, consisting of the $k-1$
element: $V_{1},\ldots,V_{\binom{n}{k-1}}$. Then we take elements
$t_{l_{k-1}+1},\ldots,t_{l_{k-1}+\binom{n}{k}}$ and include each
$t_{l_{k-1}+i}$ into all $V_{j}$ except $V_{i}$. Therefore we can set
$T(k)=\\{t_{0},t_{1},\ldots,t_{l_{k}}\\}$, where
$l_{k}=1+\binom{n}{1}+\ldots+\binom{n}{k}$, satisfying the required condition.

∎

Note that for the indicated construction $T_{1}\subset T(2)\subset\ldots T(n)$
and $T(n)=2^{n}-1.$

Let ${\mathcal{A}}$ be the system which is organized and managed by Alice. Let
$\\{B_{1},\ldots,B_{n}\\}$ be the set of users in ${\mathcal{A}}.$

For $s=2^{n}-1$, Alice takes a set of pairwise coprime positive integers
$T=\\{t_{1},\ldots,t_{s}\\}\cup\\{d\\}$. Let $t=\prod_{i=1}^{s}t_{i}.$ Then
Alice chooses a large prime finite field $\mathbb{F}_{p},\,p-1=r,$ where
$r=dtr^{\prime},$ for some $r^{\prime}\in\mathbb{N}$, while simultaneously
defining the set of subgroups $W_{i}=$ gp($w_{i}$) ($i=1,\ldots,s$) and $F=$
gp($f$) of the multiplicative group $\mathbb{F}_{p}^{\ast}$ of the
corresponding orders $t_{1},\ldots,t_{s}$ and $d$, respectively.

By Lemma 1, Alice defines a representation of the set $T$ in the form of a
union of subsets $T(n)_{i}$ for $i=1,\ldots,n.$ Each $T(n)_{i}$ is the union
of ascending sets $T(1)_{i}\subset T(2)_{i}\ldots\subset T(n)_{i}.$ For each
$j\in\mathbb{N}_{n}$, Alice computes $\bar{t}_{i}=\prod_{i\in T(n)_{j}}t_{i}$.
Then she computes the shares $\tilde{t}_{j}=\bar{t}_{j}\bar{t}_{j}^{-}$, where
$\bar{t}_{j}^{-}=\bar{t}_{j}^{-1}(\bmod\,d).$

Then Alice distributes the shares $\tilde{t}_{j}$ among the participants
according to the indices. Each participant $B_{j}$ receives the share
$\tilde{t}_{j}$.

We suppose that Alice wants to develop an ($k,n$) secret sharing scheme. In
each subgroup $W_{i}$, where $i\leq l_{m}$, Alice chooses a nontrivial element
$g_{i}$. Then she computes

$c=\prod_{i\in T(m)}g_{i}\cdot k$

and sends this element to all participants.

Let $C$ be a coalition, consisting of $z\geq k$ members. Coalition members
consistently raise $c$ to exponents equal to their shares. Since the product
of all their shares is divisible by any value $t_{i}$ for $i\leq l_{k}$, the
result is the shared secret $m$. This does not happen if the coalition has
fewer than $k$ members. Hence, it is a ($k,n$) secret sharing scheme.

Properties and security

The semantic secrecy of the above schemes is based on the difficult
solvability of the problem of calculating the exponent of an element in the
platform under consideration (finite field or commutative associative ring
with unity, in particular, residue ring). Indeed, let there be two secrets
$m_{1}$ and $m_{2}$, one of which is transmitted in the form $c=tm$, where $t$
and $m$ have coprime orders. If the attacker can calculate the exponents of
the elements, he will calculate $e_{i}=$exp($m_{i}$) and $e_{i}^{\prime}=$
exp($c^{-1}m_{i}$) for $i=1,2.$ Then he compares the sets of prime divisors
for two pairs $e_{1},e_{1}^{\prime}$ and $e_{2},e_{2}^{\prime}$. Only in the
pair corresponding to the transmitted secret, such a set for $e_{i}^{\prime}$
does not contain prime divisors of $e_{i}$.

If the problem of calculating the exponent of a protocol platform element is
intractable, then this scheme is semantically secret.

In the case of the field $\mathbb{F}_{p}$, to calculate the orders of the
elements of the group $\mathbb{F}_{p}^{\ast}$, it is sufficient to know the
primary decomposition of the number $p-1$ (see [13]). The ability to solve the
problem of calculating the order of an element of the group
$\mathbb{Z}_{n}^{\ast},n=pq$ ($p,q$ are different primes) gives an algorithm
for calculating transmitted messages, that is, it solves the RSA problem (see
[14]).

There is very little public data in the proposed schemes. In the case of the
field $\mathbb{F}_{p}$, only its order $p$ is known, but the primary
decomposition of the number $p-1$ is unknown. In the case of the residue ring
$\mathbb{Z}_{n}$, only the module $n$ is known.

Conclusions.

In this paper, we have studied two versions of a new secret sharing scheme
based on hidden multipliers in finite fields or commutative associative rings,
in particular, residue rings. We also propose a ($k,n$) - thrested scheme,
where $k$ is chosen by the dealer for each session without any additional
allocations. The main feature of the proposed schemes is that the shares of
secrets are distributed once and can be used multiple times. Our schemas are
secure against passive attacks and semantically secure under assumption that
the problem of calculation the exponent of element of a protocol platform is
intractible. It is also easy to see that the version 2 of the sharing scheme
is monotonic, but the version 1 is not. The size of each share of the secret
is equal to the size of the secret, since they are platform elements.

## References

  * [1] Shamir, A. How to share a secret. Commun. ACM 1979, 22, 612–613.
  * [2] Blakley, G.R. Safeguarding Cryptographic Keys. In Proceedings of the 1979 International Workshop on Managing Requirements Knowledge (MARK), New York, NY, USA, 4–7 June 1979; pp. 313–317.
  * [3] D.R. Stinson. An explication of secret sharing schemes. Designs, Codes Cryptography 1992, 2, 357–390.
  * [4] A. Beimel. Secret-sharing schemes: A survey. In Proceedings of the International Conference on Coding and Cryptology, Qingdao, China, 30 May-3 June 2011; Springer: Berlin/Heidelberg, Germany, 2011; pp. 11–46.
  * [5] S. Calkavur, P. Sole, and A. Bonnecaze. A New Secret Sharing Scheme Based on Polynomials over Finite Fields. Mathematics 2020, 8, 1200.
  * [6] C. Ding, D. Kohel, S. Ling. Secret sharing with a class of ternary codes. Theor. Comp. Sci. 2000, 246, 285–298.
  * [7] E.D. Karnin, J.W. Greene, M.E. Hellman. On secret sharing systems. IEEE Trans. Inf. Theory 1983, 29, 35–41.
  * [8] K. Okada, K. Kurosawa. MDS Secret Sharing Scheme Secure Against Cheaters. IEEE Trans. Inf. Theory 2000, 46, 1078–1081.
  * [9] J. Piepryzk, X.M. Zhang. Ideal Threshold Schemes from MDS Codes. In Information Security and Cryptology-Proc. of ICISC 2002 (Lecture Notes in Computer Science); Springer: Berlin, Germany, 2003; Volume 1172, pp. 67–78.
  * [10] A. Renvall, C. Ding. The access structure of some secret sharing schemes. In Information Security and Privacy (Lecture Notes in Computer Science); Springer: Berlin, Germany, 1996; Volume 1172, pp. 67–78.
  * [11] H.M. Sun, S.P. Shieh. Construction of dynamic threshold schemes. Electron. Lett. 1994, 30, 2023–2026.
  * [12] S. Hwang, C.A. Chang. A dynamic secret sharing scheme with cheater detection. In Lecture Notes in Computer Science 1172, ACISP’96; Springer: Berlin, Germany, 1993; pp. 136–146.
  * [13] A.J. Menezes, P.C. van Oorschot, S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1996.
  * [14] V.A. Roman’kov. New probabilistic public-key encryption based on the RSA cryptosystem. Groups, Complexity, Cryptology, 2015, 7, 153–156.
  * [15] V.A. Roman’kov. Introduction to cryptography. Moscow: Forum, 2012 (In Russian).
  * [16] V.A. Roman’kov. A semantically sequre public-key cryptosystem based on RSA. Prikl. Diskr. Mat., 2015, 3(29), 32–40.
  * [17] V.A. Roman’kov. Algebraic cryptology. Dostoevsky Omsk State University Press, Omsk, 2020, (In Russian).