# Hierachical Threshold Secret Sharing
Unlike normal threshold secret sharing where all shares have equal "weight" and any $t+1$ out of $n$ shares can be used to reconstruct the private key, in hierarchical threshold secret sharing, participants in the secret sharing are split into different "levels" and shares at a higher level are more important in the reconstruction threshold than shares at a lower level. This type of secret sharing has been studied extensively since the seminal work of [Tassa](https://link.springer.com/chapter/10.1007/978-3-540-24638-1_26), and since then many variants of hierarchical threhsold secret sharing have been introduced. In particular, we provide a simple adaptation of [Pedersen-VSS](https://link.springer.com/chapter/10.1007/3-540-46416-6_47) below for a $(t,n)$ secret sharing where one of the shares is further sub-shared under a $(t',n')$ secret sharing, such that the secret sharing is linear, and adaptable for use as a subprotocol in an existing [DKG](https://link.springer.com/article/10.1007/s00145-006-0347-3) and [TSS](https://eprint.iacr.org/2019/114.pdf) scheme. Wlog, we assume that the $n^{th}$ share in the $(t,n)$ sharing is sub-shared.

#### $HTSS-(t,n,t',n')$
- Dealer $D$ performs a secret sharing of a secret $z$
- D chooses 2 random polynomials $A(z),A'(z)$ over $\mathbb{Z}_q$ of degree $t$: $A(z)=a_0+a_1z+...+a_tz^t,A'_i(z)=a'_0+a'_1z+...+a'_tz^t.$ such that $z=a_0=A(0)$
$D$ broadcasts $C_{k}=g^{a_k}h^{a'_k}\bmod{p}$ for $k=0,...,t$. $D$ computes the shares $s_i=A(i),s'_i=A'(i)\bmod{q}$ for $i=1,2,3,n-1$ and sends $s_i,s'_i$ to party $P_i$
- D also chooses 2 random polynomials $B(z),B'(z)$ over $\mathbb{Z}_q$ of degree $t'$: $B(z)=b_0+b_1z+...+b_tz^{t'},B'(z)=b'_0+b'_1z+...+b'_tz^{t'}$ such that $b_0=A(n)$ and $b'_0=A'(n)$.
$D$ broadcasts $C'_{k'}=g^{b_{k'}}h^{b'_{k'}}\bmod{p}$ for $k'=0,...,t'$. $D$ computes the shares $u=B(i),u'_i=B'(i)\bmod{q}$ for $j=1,2,3,n'-1$ and sends $u_j,u'_j$ to party $P_j$
- Each party $P_i$ verifies the shares he received from D by checking if:
$g^{s_i}h^{s'_i}=\displaystyle\prod^t_{k=0}(C_k)^{i^k}\bmod{p}$
- Each party $P_j$ verifies the shares he received from D by checking if:
$g^{u_i}h^{u'_i}=\displaystyle\prod^t'_{k'=0}(C'_{k'})^{i^{k'}}\bmod{p}$
- All parties $P_i,P_j$ also verify that $b_0=A(n)$ and $b'_0=A'(n)$ by checking if:
$C'_0=\displaystyle\prod^t_{k=0}(C_k)^{n^k}\bmod{p}$
- If a check fails for $P_i$ or $P_j$, they broadcast a *complaint* against D.
- D then reveals the share for $P_i$ or $P_j$, and if it does not pass the check D is disqualified.
- **Correctness**
- For any set $\mathcal{R}$ of $t+1$ parties $P_i$, $z=\sum_{i\in\mathcal{R}}\gamma_i.s_i\bmod{q}$, where $\gamma_i$ is the appropriate Lagrangian coefficients for $\mathcal{R}$
- For any set $\mathcal{R'}$ of $t$ parties $P_i$ and $t'+1$ parties $P_j$, $z=\sum_{i\in\mathcal{R'}}\gamma_i.s_i+\gamma_n.\sum_{j\in\mathcal{R'}}\gamma'_j.u_j\bmod{q}$ where $\gamma_i$ and $\gamma'_j$ are appropriate Lagrangian coefficients for $\mathcal{R'}$
- Note that since the reconstruction of the secret from the shares is a linear mapping, the HTSS scheme is linear
- **Secrecy**
- No information on $z$ can be learned by an adversary who does not satisfy the specified $(t,n,t',n')$ access structure. We consider an adversary who corrupts the maximal non-qualified set $M$, which is $t$ parties in $P_i$ and $t$ parties in $P_j$. For any $z'\in\mathbb{Z}_q$, we can use $\{z',s_i\}, i\in M$ to interpolate $\bar{A}$, a polynomial of degree $t$, and evaluate $\bar{b}_0=\bar{A}(n)$. We can then use $\{\bar{b}_0,s_j\}, j\in M$ to interpolate $\bar{B}$, a polynomial of degree $t'$. So there always exists a set of two polynomials, $\bar{A},\bar{B}$ for any $z'\in \mathbb{Z}_q$ that include the shares in the maximal non-qualified set, so it is not possible for the adversary to find $z$.