# An Efficient Lattice-Based Secret Sharing Construction

Rachid El Bansarkhani, Mohammed Meziani

► To cite this version:

Rachid El Bansarkhani, Mohammed Meziani. An Efficient Lattice-Based Secret Sharing Construction. 6th International Workshop on Information Security Theory and Practice (WISTP), Jun 2012, Egham, United Kingdom. pp.160-168, 10.1007/978-3-642-30955-7_14. hal-01534304

HAL Id: hal-01534304

https://inria.hal.science/hal-01534304

Submitted on 7 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Efficient Lattice-based Secret Sharing Construction

Rachid El Bansarkhani¹ and Mohammed Meziani²

¹ Technische Universität Darmstadt
Fachbereich Informatik
Kryptographie und Computeralgebra,
Hochschulstraße 10, 64289 Darmstadt, Germany
elbansarkhani@cdc.informatik.tu-darmstadt.de

² CASED – Center for Advanced Security Research Darmstadt,
Mornewegstrasse 32, 64293 Darmstadt, Germany
mohammed.meziani@cased.de

**Abstract.**

This paper presents a new construction of a lattice-based verifiable secret sharing scheme. Our proposal is based on lattices and the usage of linear hash functions to enable each participant to verify its received secret share. The security of this scheme relies on the hardness of some well known approximation problems in lattices such as $n$-approximate SVP. Different to protocols proposed by Pedersen this scheme uses efficient matrix vector operations instead of exponentiation to verify the secret shares.

**Keywords:** Secret Sharing, Lattice-based Cryptography, Shortest Vector Problem, Hash Functions.

## 1 Introduction

It is known from [12] that quantum algorithms could break most of number-theory based cryptosystems used in practice (e.g., RSA, DL). Indeed, such algorithms can solve both the factoring problem and the discrete log problem in finite fields and on elliptic curves in polynomial time. It may therefore be desirable to design new cryptographic primitives, such as public-key cryptosystems and secret sharing schemes, whose security depends upon problems that are not vulnerable to quantum attacks. Lattice-based systems offer a promising alternative to number-theoretic ones, and they are believed to be secure against quantum attacks since their security is based on lattice problems that in their general form are well-known NP-hard. In addition to post-quantum security, they are easy to implement and utilize only basic operations.

Motivated by the need for protecting cryptographic keys by more than one party, secret sharing schemes were first introduced independently in 1979 by Shamir [11] and Blakley [3]. The Shamir's proposal relies on polynomials
with $n$ coefficients where $n$ is the number of parties involved to reconstruct the coefficients of polynomials with degrees at most $n-1$. Blakley, instead, makes use of the fact that different hyperplanes can intersect in one point. And a certain amount of these hyperplanes is only required to specify that point. Since then several other secret sharing schemes have been developed, for example those that are based on the Chinese Remainder Theorem ([7] and [2]) or hybrid constructions [8] using the discrete logarithm problem for verification. Our construction follows a new simple approach since it uses only simple operations from linear algebra. Compared to the previous schemes it recovers a vector rather than a single value. Furthermore, the verification of the secret shares as well as the secret vector can be done via lattice-based hash functions whose security is reducible to some NP-hard problems in lattices. Previous schemes, instead, rely on the discrete logarithm problem for the verification. The main idea behind our scheme is to recover a basismatrix at first which is then required to compute the secret vector that in turn could be used as a secret key for the lattice-based LWE encryption scheme [10]. Secret sharing systems can be found in many real applications such as secure multi-party computations [4], e-voting [14], and sensor networks [6]. In the basic model of secret sharing we differ at least two major protocols: the distribution protocol in which the dealer forwards the secret shares to the participants, and the combination or reconstruction protocol in which the secret is recovered by pooling the shares of a qualified subset of the participants.

A system is called a $(t, n)$ threshold secret sharing scheme with $t \le n$, when at least $t$ participants are required to recover the secret key, where $n$ is the number of participants obtaining a secret share from the dealer. We present a $(n, n)$ secret sharing scheme based on the difficulty to solve $n^c$-approximate SVP in lattices for some constant $c$.

# 2 Preliminaries

The following briefly introduces the definitions and notations used in the present paper.

## 2.1 Notations

The following notations and definitions will be used throughout the rest of the paper.

* $|x|$ is the length in bits of a string $x$.

* The Hamming weight of a string $x$ is the number of its non-null coordinates and denoted by $wt(x)$.

* $[v_1, \dots, v_n]$ is the matrix composed by the column vectors $v_1, v_2, \dots, v_n$.

* By $t_1 = (t_1^{(1)}, \dots, t_1^{(n)})$ we denote a vector consisting of $n$ elements, where $t_j^{(i)}$ identifies the $i$-th element of the vector $t_j$.
★ For a finite set $S$, we denote by $x \stackrel{\$}{\leftarrow} S$ the experiment of uniformly choosing an element $x$ from $S$ and assigning it to $x$.

★ With $[r]$ we round a real number $r$ up to the next integer.

★ $x^\top$ is the transpose of a vector $x$.

★ $\mathrm{rot}(x)$ cyclically rotates the vector $x$, e.g. $\mathrm{rot}((1, 2, 3, 4)) = (4, 1, 2, 3)$.

## 2.2 Basics on lattices

A lattice $L$ is a discrete abelian subgroup of $\mathbb{R}^m$. A basis $B = [b_1, \dots, b_n] \in \mathbb{R}^{m \times n}$ for the lattice $L$ consists of $d \le n$ linearly independent vectors $b_i$ with $\mathcal{L}(B) = \{\sum_{i=1}^n t_i b_i \mid t_1, \dots, t_n \in \mathbb{Z}\} \subset \mathbb{R}^m$, i.e. $\mathcal{L}$ is the set of all integer combinations of the vectors in $B$. The minimum distance of a lattice $\mathcal{L}(B)$, denoted $\lambda(\mathcal{L}(B))$, is the minimum distance between any two distinct lattice points, and equals the length of a nonzero shortest lattice vector.

$$ \lambda(\mathcal{L}(B)) = \min\{\|x\| : x \in \mathcal{L}(B)\} \quad (1) $$

**Definition 1. (Shortest Vector Problem - SVP)**

Let $\mathcal{L}(B) \subset \mathbb{R}^n$ be a $d$-dimensional lattice and $B \in \mathbb{Z}^{n \times d}$ the corresponding basis matrix. An input to SVP is a lattice basis $B$ and the goal is to find a vector $x$ in $\mathcal{L}(B)$ such that $\|x\| = \lambda(\mathcal{L}(B))$

**Definition 2. (Approximate Shortest Vector Problem - $\gamma$-SVP)**

Let $\mathcal{L}(B) \subset \mathbb{R}^n$ be a $d$-dimensional lattice and $B \in \mathbb{Z}^{n \times d}$ the corresponding basis matrix. An input to SVP is a lattice basis $B$ and the goal is to find a vector $x$ in $\mathcal{L}(B)$ such that $\|x\| = \gamma \cdot \lambda(\mathcal{L}(B))$

# 3 Our Construction

In this section, we present a non-interactive verifiable lattice-based secret sharing protocol that requires all parties to participate with their shares in order to recover a secret, while at the same time enabling them to verify their secret share. In this scheme, a dealer selects different vectors of length $n$ and weight $m > 1$ and produces secret shares of length $n$, where $n$ is a positive integer. A higher weight is chosen in order to prevent the participants to get information about the basis vectors from their secret shares, because the secret share is a linear combination of the private basis vectors.

## 3.1 Description

This scheme works in non-interactive manner, meaning that each participant can verify its own secret share without communicating with other participants. It consists of two steps: the distribution and combination phase. On the other hand, its security relies on the hardness of solving SVP in lattices. Furthermore, it is very fast as it uses only matrix-vector multiplication to recover the secret.
The principle of our proposal is the following: the dealer generates a private lattice basis $B \in \mathbb{Z}^{n \times n}$ with low orthogonal defect and selects linearly independent vectors $\lambda_i \in \{x \in \mathbb{F}_2^n : wt(x) = m > 1\}$ and publishes them together with the hashed (encrypted) secret and basis vectors. The dealer also reveals the vector $v \in \mathbb{Z}^n$ which is needed to compute the secret as $s := B \cdot v$. Here a linear hash function is used, such as Ajtai's hash function [1] or more efficient ones proposed by Lyubashevsky and Micciancio [5] or Peikert and Rosen [9], to enable each participant to verify its secret share in a non-interactive manner. It is also possible to take a semi-homomorphic lattice-based encryption scheme with additive property to achieve the same results. As next step, the dealer secretly distributes the vectors $c_i = B \cdot \lambda_i$ to each participant $P_i$. By doing so, n participants would be able to recover the private basis and compute the secret. In what follows, we describe the distribution and combination phase in details.

## Distribution phase

1. $D$ chooses a private lattice Basis $B$ and selects linearly independent binary vectors $\lambda_i$ of length $n$ and weight $m > 1$. Then he computes the secret shares $c_i = B \cdot \lambda_i$ and secretly forwards them to the participants.

2. Upon receipt of the own secret share, each participant $P$ checks the hash value, in particular he verifies whether the hash value of its secret share can be written as a linear combination of the hashed basis vectors, i.e., $H(c_i) \stackrel{?}{=} \sum \lambda_{ij} \cdot H(b_j)$, since the $\lambda_i$ and $H(b_j)$ as well as the secret generating vector $v$ are public. If the hash value is valid, the participant sends its acknowledgment to the dealer back.

Since many hash functions are fed with binary strings of a special length we can hash each component of the received vector without losing the linearity of the hash function. In this way we obtain for every input vector a matrix as hash value.

## Combination phase

The combination phase involves three steps to recover the secret:

1. n participants $P_{k_1}, \dots, P_{k_n}$ secretly send their received secret shares $c_{k_1}, \dots, c_{k_n}$ to the combiner. These secret shares $c_{k_1}, \dots, c_{k_n}$ can be represented as square matrix of size $n \times n$, i.e., $C = [c_{k_1}, \dots, c_{k_n}]$. Then the combiner solves the following equations for the unknown vectors $a_{k_1}, \dots, a_{k_n}$, where $e_i$ denotes the i-th n-dimension unit vector:

$$e_i = [\lambda_{k_1}, \dots, \lambda_{k_n}] \cdot (a_{k_1}^{(i)}, \dots, a_{k_n}^{(i)})^T, \quad 1 \le i \le n \quad (2)$$

We then obtain a matrix $A = [a_{k_1}, \dots, a_{k_n}]$ in order to compute the private lattice basis $B$. The following equation shows that the private Basis can be
<figure><img src="image_2.png" /><figcaption>Fig. 1. Distribution Phase</figcaption></figure>

expressed as a function of the matrices C and A:

$$
\begin{align}
B &= [c_{k_1}, \dots, c_{k_n}] \cdot [a_{k_1}, \dots, a_{k_n}]^\top \nonumber \\
  &= [b_1, \dots, b_n] \cdot [\lambda_{k_1}, \dots, \lambda_{k_n}] \cdot [a_{k_1}, \dots, a_{k_n}]^\top \tag{3} \\
  &= [b_1, \dots, b_n] \cdot [e_1, \dots, e_n] \nonumber
\end{align}
$$

2. The combiner computes the secret by simple matrix vector multiplication.

$$
s = B \cdot v, \tag{4}
$$

The secret is then sent via a secure communication channel to each partici-
pant back.

3. The participants can then verify the secret produced by the combiner. To this end, the participant compares the hash of the received value with the hashed secret provided by the dealer which is also publicly available.

**Example:** n=4, wt = 3

$$
[\lambda_1, \dots, \lambda_4] = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{pmatrix}, [b_1, \dots, b_4] = \begin{pmatrix} 7 & 9 & 8 & 4 \\ 6 & 3 & 3 & 0 \\ 5 & 9 & 0 & 5 \\ 4 & 4 & 2 & 3 \end{pmatrix}, \\
[c_1, \dots, c_4] = \begin{pmatrix} 15 & 22 & 10 & 12 \\ 17 & 16 & 13 & 7 \\ 18 & 21 & 11 & 9 \\ 15 & 16 & 5 & 8 \end{pmatrix}
$$
<figure><img src="image_3.png" /><figcaption>Fig. 2. Combination Phase</figcaption></figure>

3.2 Security and Performance

The security of our construction is based on the underlying hash function which
is used for hiding the basis vectors as well as the secret. It is also possible
to use any encryption function instead, which however needs to satisfy the
additive property. The security of Ajtai's hash function (see Algorithm 1) or
more efficient ones constructed by Lyubashevsky and Micciancio [5] or Peik-
ert and Rosen [9] can be reduced to the hardness of solving approximate n<sup>c</sup>-SVP.

<caption>**Algorithm 1** Calculate A hash function following Ajtai's construction</caption>

1. **Parameters:** integers $n, k, p, d \ge 1$ with $n > \frac{k \cdot \log(p)}{\log(d)}$
2. **Key:** a matrix $B$ chosen uniformly from $\mathbb{Z}_p^{k \times n}$
3. **Hash function:** $f_A : \{0, \dots, d-1\}^n \to \mathbb{Z}_p^k$ given by $f_A(x) = A \cdot x \bmod p$

As already mentioned above many hash functions are fed with a binary input
string and produce a vector. Since we operate on n dimensional vector spaces
we would have to hash each component of a vector leading to a n x n-matrix as
a hash value without affecting the additive property. In the distribution phase every participant verifies its secret share. The needed number of operations and transferred bits of each protocol step are depicted in the following tables. When $Z^n$ is replaced by $Z_q^n$, the bit size of each vector component is bounded by $\log(q)$ and the solution is unique if the determinant of $[\lambda_{k_1}, \dots, \lambda_{k_n}]$ is coprime to q as shown in [13].

<table><caption>**Table 1.** Theoretical performance in the distribution phase</caption><thead><tr><th></th><th>Dealer</th><th>Participant</th></tr></thead><tbody><tr><td>Computation (bops)</td><td>$n^2 m \cdot \log(q)$</td><td>$\frac{n^2 \cdot \log(q)}{\log(p)}$</td></tr><tr><td>Communication (bits)</td><td>$n \cdot \log(q)$</td><td>1</td></tr></tbody></table>

<table><caption>**Table 2.** Theoretical performance in the combination phase</caption><thead><tr><th></th><th>Participants</th><th>Combiner</th></tr></thead><tbody><tr><td>Computation (bops)</td><td></td><td>$n^2 \cdot (n^2 + n^{0.373} + \log(q))$</td></tr><tr><td>Communication (bits)</td><td>$n^2 \cdot (\log(q) + 1)$</td><td>$n \cdot \log(q)$</td></tr></tbody></table>

In a $(n, n)$ scheme the dealer can efficiently generate $n$ linearly independent vectors having length $n$ by setting the weight to $n-1$. If we use the vectors $\lambda_i = (\sum_{j=1}^n e_j) - e_i$ for $1 \le i \le n$ it can easily be shown that these vectors form a base due to the fact that each vector represents a vertex in a $n$-dimensional hypercube. These vertices are on different axial planes perpendicular to each other. So any checks in terms of linearly independence can be neglected.

**Example:** $n = 6$, $wt = 5$

$$[\lambda_1, \dots, \lambda_6] = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{pmatrix}$$
From linear algebra we know that fewer than *n* participants cannot recover the private basis and thus get no information about the secret *s* because the secret satisfies equation (4). It is also possible to show that no unit vector can be computed in the first step of the combination phase when the number of participants is less than *n*. So any private basis vector remains hidden. This advantageous side effect comes from the fact that *n* − 1 of the chosen vectors $\lambda_k$ span a (*n* − 1)-dimensional hyperplane connecting the *n* − 1 vertices and the origin in a hypercube. So every unit vector is outside the hyperplane.

Our secret sharing scheme has been implemented on a 2.5 GHz Intel Core i5-2520M, running Linux (Ubuntu 11.04) 32 Bit. The performance results of the implementation are reported in Table 3.

<table><caption>**Table 3.** Performance of the secret sharing scheme</caption><thead><tr><th>Number of users (dimension)</th><th>Distribution timing (sec)</th><th>Combination timing (sec)</th><th>Verification timing (sec)</th></tr></thead><tbody><tr><td>n=128</td><td>0.005864</td><td>0.006625</td><td>0.000085</td></tr><tr><td>n=256</td><td>0.035171</td><td>0.042033</td><td>0.00023</td></tr><tr><td>n=512</td><td>0.195757</td><td>0.273959</td><td>0.000676</td></tr><tr><td>n=1024</td><td>1.212575</td><td>1.922552</td><td>0.002577</td></tr></tbody></table>

This scheme can easily be extended to a protocol where at most *n* out of $\binom{n}{m}$ participants are required to recover the secret. By this means, the chosen weight would maximize the binomial coefficient and therefore the number of potential secret share holders. This is the case when *m* equals to $\lceil \frac{n}{2} \rceil$. To this end, the dealer selects all possible vectors with weight $wt = \lceil \frac{n}{2} \rceil$ and computes the corresponding secret shares. But the reconstruction of the secret is computational infeasible for less than $\lceil \frac{n}{2} \rceil + 1$ parties because fewer than $\lceil \frac{n}{2} \rceil + 1$ of the selected vectors cannot span a $(\lceil \frac{n}{2} \rceil + 1)$-dimensional subspace and with the same argument as above no unit vector can be computed. However, every participant can determine which other secret share holder could involve for the purpose of computing the secret since $\lambda_i$ of all participants are publicly available. As *n* vectors form the basis matrix *B*, which is not necessarily consisting of linearly independent vectors, it is required to know at least $\lceil \frac{n}{2} \rceil$ vectors in order to recover all basis vectors. One method is to use cyclic rotations of $\frac{n}{2}$ basis vectors.

**Example:**

1. Dimension: $n = 100, (n = 1024)$

2. Weight: $n - 2 = 98, (1022)$

3. Nr. of participants: $\binom{n}{n-2} = \frac{n \cdot (n-1)}{2} = 4950, (523776)$

4. Min. number of participants to recover the secret: $n - 1 = 99, (1023)$

5. Max. number of participants to recover the secret: $n = 100, (1024)$

6. $B = [b_1, \dots, b_{n-1}, \text{rot}(b_{n-1})]$
4 Conclusion

In this work we present a new and efficient construction of a secret sharing
scheme by making use of a lattice based hash function for the protection of
the secret. Every secret share holder is enabled to verify its share due to the
linearity of the employed hash function. We showed that breaking this scheme
by attacking the hash function is at least as hard as solving approximate SVP.
We also showed that in the (n,n)-scheme all parties have to participate in order
to recover the secret. In addition, it is computationally infeasible for less than
n participants to compute the basis matrix and hence the secret. Furthermore,
our scheme can be extended into n out of (n/2) secret sharing scheme in order
to increase the number of potential secret share holders.
References

1. M. Ajtai. Generating hard instances of lattice problems (extended abstract). In *In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing*, pages 99–108. ACM, 1996.

2. C Asmuth and J Bloom. A modular approach to key safeguarding. *IEEE Transactions on Information Theory*, 29(2):208–210, 1983.

3. G. R. Blakley. Safeguarding cryptographic keys. In *Proceedings of the National Computer Conference*, pages 313–317. American Federation of Information Processing Societies, 1979.

4. Ronald Cramer and Ueli Maurer. General secure multi-party computation from any linear secret-sharing scheme. pages 316–334. Springer-Verlag, 2000.

5. Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In *In ICALP (2)*, pages 144–155. Springer, 2006.

6. Ajay Mahimkar. Securedav: A secure data aggregation and verification protocol for sensor networks. In *In Proceedings of the IEEE Global Telecommunications Conference*, pages 2175–2179, 2004.

7. Maurice Mignotte. How to share a secret. In *Cryptography*, volume 149 of *Lecture Notes in Computer Science*, pages 371–375. Springer Berlin / Heidelberg, 1983.

8. Torben Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In *Advances in Cryptology CRYPTO 91*, volume 576 of *Lecture Notes in Computer Science*, pages 129–140. Springer Berlin / Heidelberg, 1992.

9. Chris Peikert and Alon Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In *In TCC*, pages 145–166. Springer, 2006.

10. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. *J. ACM*, 56(6):34:1–34:40, 2009.

11. Adi Shamir. How to share a secret. *Commun. ACM*, 22:612–613, November 1979.

12. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. *SIAM J. Comput.*, 26:1484–1509, 1997.

13. Henry J. Stephen Smith. On systems of linear indeterminate equations and congruences. *Philosophical Transactions of the Royal Society of London*, 151:pp. 293–326, 1861.

14. Sorin and Iftene. General secret sharing based on the chinese remainder theorem with applications in e-voting. *Electronic Notes in Theoretical Computer Science*, 186(0):67 – 84, 2007.