# A Survey on Perfectly-Secure Verifiable Secret-Sharing

Anirudh Chandramouli111International Institute of Information Technology,
Bangalore India. Email<EMAIL_ADDRESS>Ashish
Choudhury222International Institute of Information Technology, Bangalore
India. Email<EMAIL_ADDRESS>This research is an outcome of the
R & D work undertaken in the project under the Visvesvaraya PhD Scheme of
Ministry of Electronics & Information Technology, Government of India, being
implemented by Digital India Corporation (formerly Media Lab Asia). Arpita
Patra333Indian Institute of Science, Bangalore India. Email:
<EMAIL_ADDRESS>Arpita Patra would like to acknowledge financial support
from SERB MATRICS (Theoretical Sciences) Grant 2020 and Google India AI/ML
Research Award 2020.

###### Abstract

Verifiable Secret-Sharing (VSS) is a fundamental primitive in secure
distributed computing. It is used as a building block in several distributed
computing tasks, such as Byzantine agreement and secure multi-party
computation. In this article, we consider VSS schemes with perfect security,
tolerating computationally unbounded adversaries. We comprehensively survey
the existing perfectly-secure VSS schemes in three different communication
settings, namely synchronous, asynchronous and hybrid setting and provide full
details of the existing schemes in these settings. The aim of this survey is
to provide a clear knowledge and foundation to researchers who are interested
in knowing and extending the state-of-the-art perfectly-secure VSS schemes.

##  1 Introduction

A central concept in cryptographic protocols is that of Secret Sharing (SS)
[55, 14]. Consider a set $\mathcal{P}=\\{P_{1},\ldots,P_{n}\\}$ of mutually
distrusting parties, where the distrust is modeled by a centralized adversary,
who can control up to $t$ parties. Then a SS scheme allows a designated dealer
$\mathsf{D}\in\mathcal{P}$ to share a secret $s$ among $\mathcal{P}$, by
providing each $P_{i}$ a share of the secret $s$. The sharing is done in such
a way that the adversary controlling any subset of at most $t$ share-holders
fails to learn anything about $s$, while any subset of at least $t+1$ share-
holders can jointly recover $s$. In a SS scheme, it is assumed that all the
parties including the ones under the adversary’s control follow the protocol
instructions correctly (thus, the adversary is assumed to only eavesdrop the
computation and communication of the parties under its control). VSS [18]
extends the notion of SS to the more powerful malicious/active adversarial
model, where the adversary can completely dictate the behaviour of the parties
under its control during a protocol execution. Moreover, $\mathsf{D}$ is
allowed to be potentially corrupted. A VSS scheme consists of a sharing phase
and a reconstruction phase, each implemented by a publicly-known protocol.
During the sharing phase, $\mathsf{D}$ shares its secret in a verifiable
fashion, which is later reconstructed during the reconstruction phase. If
$\mathsf{D}$ is honest, then the privacy of its secret is maintained during
the sharing phase and the shared secret is later robustly reconstructed,
irrespective of the behaviour of the corrupt parties. The interesting property
of VSS is the verifiability property, which guarantees that even if
$\mathsf{D}$ is corrupt, it has “consistently/correctly” shared some value
among the parties and the same value is later reconstructed. One can interpret
VSS as a distributed commitment, where, during the sharing phase, $\mathsf{D}$
publicly commits to a private input (known only to $\mathsf{D}$) and later
during the reconstruction phase, the committed value is reconstructed publicly
(even if $\mathsf{D}$ does not cooperate). Due to its central importance in
secure distributed-computing tasks, such as secure multi-party computation
(MPC) [12, 54] and Byzantine agreement (BA) [30], VSS has been studied in
various settings, based on the following categorizations.

  * $\bullet$

Conditional vs Unconditional Security: If the adversary is computationally
bounded (where it is allowed to perform only polynomial amount of
computations), then the notion of security achieved is
conditional/cryptographic [53, 5, 6], whereas unconditionally-secure VSS
provides security even against a computationally unbounded adversary.
Unconditionally-secure VSS can be further categorized as perfectly-secure
where all security guarantees are achieved in an error-free fashion [12], and
statistically-secure where a negligible error is allowed [54, 25, 40].

  * $\bullet$

Type of Communication: Here we have three categories. The synchronous model
assumes that the parties are synchronized through a global clock and there are
strict (publicly-known) upper bounds on the message delays [12, 54, 33, 32,
39, 3]. The second category is the asynchronous model [11, 13, 7, 49, 50, 24],
where the parties are not synchronized and where the messages can be
arbitrarily (but finitely) delayed. A major challenge in the asynchronous
model is that a slow sender party (whose messages are delayed) cannot be
distinguished from a corrupt sender who does not send messages at all. Due to
this inherent phenomenon, asynchronous VSS (AVSS) protocols are more
complicated than their synchronous counter-parts. The third category is the
hybrid communication setting [51], which is a mix of the synchronous and
asynchronous models. Namely, the protocol starts with a few initial
synchronous rounds, followed by a completely asynchronous execution. The main
motivation for considering a hybrid setting is to “bridge” the feasibility and
efficiency gaps between completely synchronous and completely asynchronous
protocols.

  * $\bullet$

Corruption Capacity: Most of the works on VSS assume a threshold adversary
which can corrupt any subset of $t$ parties. A non-threshold adversary [26,
46, 22, 23] is a more generalized adversary, where the corruption capacity of
adversary is specified by a publicly-known adversary structure, which is a
collection of potentially corrupt subsets of parties. During the protocol
execution, the adversary can choose any subset from the collection for
corruption.

##### Our Contributions and Paper Organization

We provide a comprehensive survey of all the existing perfectly-secure VSS
schemes tolerating a threshold adversary. We cover three communication
settings, namely synchronous, asynchronous and hybrid. These schemes are
designed over a period of three decades. The nuances, subtleties and
foundational ideas involved in these works need a holistic and unified
treatment, which is the focus of this work. This survey is structured to
provide an easy digest of the perfectly-secure VSS schemes. Through this
survey, we hope to provide a clear knowledge and foundation to researchers who
are interested in knowing and extending the state-of-the-art perfectly-secure
VSS schemes. The survey is divided into three parts, each dealing with a
separate communication model. We do not survey SS schemes and their share
sizes, for which the interested readers are referred to the survey by Beimel
[10].

Part I : Synchronous Communication Setting

##  2 Preliminaries and Definitions

Throughout part I, we consider a synchronous communication setting, where the
parties in $\mathcal{P}$ are connected by pair-wise private and authentic
channels. The distrust in the system is modelled by a computationally
unbounded adversary $\mathsf{Adv}$, who can corrupt at most $t$ parties during
the execution of a protocol in a malicious/Byzantine fashion and force them to
behave in any arbitrary manner. The parties under the control of
$\mathsf{Adv}$ are called corrupt/malicious, while the parties not under
$\mathsf{Adv}$’s control are called honest. We assume a static adversary, who
decides the set of corrupt parties at the beginning of a protocol. However,
following [41] the protocols discussed can be proved to be secure even against
an adaptive adversary, who can corrupt parties as the protocol proceeds.

We also assume the presence of a broadcast channel, which allows any
designated party to send some message identically to all the parties. A
protocol in the synchronous setting operates as a sequence of rounds. In each
round, a party can (privately) send messages to other parties and broadcast a
message. Moreover in a given round, each party can simultaneously use the
broadcast channel. The messages sent or broadcast by a party is determined by
its input, random coins and the messages received from other parties in
previous rounds. The view of a party during a protocol execution consists of
its inputs, random coins and all the messages received by the party throughout
the protocol execution. The view of $\mathsf{Adv}$ is the collection of the
views of the corrupt parties.

##### Structure of a VSS Scheme.

Following [33], VSS schemes can be structured into two phases. A sharing phase
executed by a protocol $\mathsf{Sh}$, followed by a reconstruction phase
executed by a protocol $\mathsf{Rec}$. While the goal of $\mathsf{Sh}$ is to
share a secret held by a designated dealer $\mathsf{D}\in\mathcal{P}$, the aim
of $\mathsf{Rec}$ is to reconstruct back the shared secret. Specifically,
during $\mathsf{Sh}$, the input of $\mathsf{D}$ is some secret
$s\in\mathcal{S}$, where $\mathcal{S}$ is some publicly-known secret-space
which is the set of all possible $\mathsf{D}$’s secrets. Additionally, the
parties may have random inputs for the protocol. Let $\mathsf{view}_{i}$
denote the view of $P_{i}$ at the end of $\mathsf{Sh}$. Based on
$\mathsf{view}_{i}$, each $P_{i}$ outputs a share $s_{i}$, as determined by
$\mathsf{Sh}$.

During $\mathsf{Rec}$, each $P_{i}$ reveals a subset of $\mathsf{view}_{i}$,
as per $\mathsf{Rec}$. The parties then apply a reconstruction function on the
revealed views, as per $\mathsf{Rec}$ and reconstruct some output. Following
[39], we say that round-complexity of $\mathsf{Sh}$ (resp. $\mathsf{Rec}$) is
$(R,R^{\prime})$, if $\mathsf{Sh}$ (resp. $\mathsf{Rec}$) involves total $R$
rounds and among these $R$ rounds, the broadcast channel is used for
$R^{\prime}$ rounds. By communication complexity of a protocol, we mean the
total number of bits communicated by the honest parties in the protocol.

###  2.1 Definitions

A $t\mbox{-out-of-}n$ secret-sharing (SS) scheme is a pair of functions
$(\mathsf{G},\mathsf{R})$. While $\mathsf{G}$ is probabilistic, $\mathsf{R}$
is deterministic. Function $\mathsf{G}$ generates shares for the input secret,
while $\mathsf{R}$ maps the shares back to the secret. The shares are
generated in such a way that the probability distribution of any set of $t$
shares is independent of the secret, while any set of $t+1$ shares uniquely
determines the secret.

######  Definition 2.1 ($t\mbox{-out-of-}n$ secret-sharing [34]).

It is a pair of algorithms $(\mathsf{G},\mathsf{R})$, such that:

  * –

Syntax: The share-generation function $\mathsf{G}$ takes input a secret $s$
and some randomness $q$ and outputs a vector of $n$ shares
$(s_{1},\ldots,s_{n})$. The recovery function $\mathsf{R}$ takes input a set
of $t+1$ shares corresponding to $t+1$ indices
$\\{i_{1},\ldots,i_{t+1}\\}\subset\\{1,\ldots,n\\}$ and outputs a value.

  * –

Correctness: For any $s\in\mathcal{S}$ and any vector $(s_{1},\ldots,s_{n})$
where $(s_{1},\ldots,s_{n})=\mathsf{G}(s,q)$ for some randomness $q$, the
condition $\mathsf{R}(s_{i_{1}},\ldots,s_{i_{t+1}})=s$ holds for any subset
$\\{i_{1},\ldots,i_{t+1}\\}\subset\\{1,\ldots,n\\}$.

  * –

Privacy: For any subset of $t$ indices, the probability distribution of the
shares corresponding to these indices is independent of the underlying secret.
That is, for any $I=\\{i_{1},\ldots,i_{t}\\}\subset\\{1,\ldots,n\\}$, let
$g_{I}(s)\stackrel{{\scriptstyle def}}{{=}}(s_{i_{1}},\ldots,s_{i_{t}})$,
where $(s_{1},\ldots,s_{n})=\mathsf{G}(s,q)$ for some randomness $q$. Then we
require that for every index-set $I$ where $|I|=t$, the random variables
$g_{I}(s)$ and $g_{I}(s^{\prime})$ are identically distributed, for every
$s,s^{\prime}\in\mathcal{S}$, where $s\neq s^{\prime}$.

######  Definition 2.2.

Let $\Pi=(\Pi_{\mathsf{G}},\Pi_{\mathsf{R}})$ be a $t\mbox{-out-of-}n$ secret-
sharing scheme. Then we say that a value $s$ is secret-shared among
$\mathcal{P}$ as per $\Pi$, if there exists some randomness $q$ such that
$(s_{1},\ldots,s_{n})=\Pi_{\mathsf{G}}(s,q)$ and each honest party
$P_{i}\in\mathcal{P}$ has the share $s_{i}$.

In the literature, two types of VSS schemes have been considered. The type-I
VSS schemes are “weaker” compared to the type-II VSS schemes. Namely, in type-
II VSS, it is guaranteed that the dealer’s secret is secret-shared as per the
semantics of some specified secret-sharing scheme444In Type-I VSS, the
underlying secret need not be secret-shared as per the semantics of any
$t\mbox{-out-of-}n$ SS scheme. (for instance, say Shamir’s SS [55]). While
type-I VSS is sufficient to study VSS as a stand-alone primitive (for
instance, to study the round complexity of VSS [32] or to design a BA protocol
[16]), type-II VSS schemes are desirable when VSS is used as a primitive in
secure MPC protocols [39, 4, 3].

######  Definition 2.3 (Type-I VSS [33]).

Let $(\mathsf{Sh},\mathsf{Rec})$ be a pair of protocols for the parties in
$\mathcal{P}$, where a designated dealer $\mathsf{D}\in\mathcal{P}$ has some
private input $s\in\mathcal{S}$ for the protocol $\mathsf{Sh}$. Then
$(\mathsf{Sh},\mathsf{Rec})$ is called a Type-I perfectly-secure VSS scheme,
if the following requirements hold.

  * –

Privacy: If $\mathsf{D}$ is honest, then the view of $\mathsf{Adv}$ during
$\mathsf{Sh}$ is distributed independent of $s$.

  * –

Correctness: If $\mathsf{D}$ is honest, then all honest parties output $s$ at
the end of $\mathsf{Rec}$.

  * –

Strong Commitment: Even if $\mathsf{D}$ is corrupt, in any execution of
$\mathsf{Sh}$, the joint view of the honest parties defines a unique value
$s^{\star}\in\mathcal{S}$ (which could be different from $s$), such that all
honest parties output $s^{\star}$ at the end of $\mathsf{Rec}$, irrespective
of the behaviour of $\mathsf{Adv}$.

######  Definition 2.4 (Type-II VSS [34]).

Let $\Pi=(\Pi_{\mathsf{G}},\Pi_{\mathsf{R}})$ be a $t\mbox{-out-of-}n$ SS
scheme. Then $(\mathsf{Sh},\mathsf{Rec})$ is called a Type-II perfectly-secure
VSS scheme with respect to $\Pi$, if the following requirements hold.

  * –

Privacy: If $\mathsf{D}$ is honest, then the view of $\mathsf{Adv}$ during
$\mathsf{Sh}$ is distributed independent of $s$.

  * –

Correctness: If $\mathsf{D}$ is honest, then at the end of $\mathsf{Sh}$, the
value $s$ is secret-shared among $\mathcal{P}$ as per $\Pi$ (see Definition
2.2). Moreover, all honest parties output $s$ at the end of $\mathsf{Rec}$.

  * –

Strong Commitment: Even if $\mathsf{D}$ is corrupt, in any execution of
$\mathsf{Sh}$ the joint view of the honest parties defines some value
$s^{\star}\in\mathcal{S}$, such that $s^{\star}$ is secret-shared among
$\mathcal{P}$ as per $\Pi$ (see Definition 2.2). Moreover, all honest parties
output $s^{\star}$ at the end of $\mathsf{Rec}$.

##### Alternative Definition of VSS

Definition 2.3-2.4 are called “property-based” definition, where we enumerate
a list of desired security goals. One can instead follow other definitional
frameworks such as the the ideal-world/real-world paradigm of Canetti [17] or
the constructive-cryptography paradigm of Liu-Zhang and Maurer [42]. Proving
the security of VSS schemes as per these paradigm brings in additional
technicalities in the proofs. Since our main goal is to survey the existing
VSS protocols, we will stick to the property-based definitions, which are easy
to follow.

###  2.2 Properties of Polynomials Over a Finite Field

Let $\mathbb{F}$ be a finite field where $|\mathbb{F}|>n$ with
$\alpha_{1},\ldots,\alpha_{n}$ be distinct non-zero elements of $\mathbb{F}$.
A degree-$d$ univariate polynomial over $\mathbb{F}$ is of the form
$f(x)=a_{0}+\ldots+a_{d}x^{d}$, where $a_{i}\in\mathbb{F}$. A
degree-$(\ell,m)$ bivariate polynomial over $\mathbb{F}$ is of the form
$F(x,y)=\displaystyle\sum_{i,j=0}^{i=\ell,j=m}r_{ij}x^{i}y^{j}$, where
$r_{ij}\in\mathbb{F}$. The polynomials $f_{i}(x)\stackrel{{\scriptstyle
def}}{{=}}F(x,\alpha_{i})$ and $g_{i}(y)\stackrel{{\scriptstyle
def}}{{=}}F(\alpha_{i},y)$ are called the $i^{th}$ row and column-polynomial
respectively of $F(x,y)$ as evaluating $f_{i}(x)$ and $g_{i}(y)$ at
$x=\alpha_{1},\ldots,\alpha_{n}$ and at $y=\alpha_{1},\ldots,\alpha_{n}$
respectively results in an $n\times n$ matrix of points on $F(x,y)$ (see Fig
1). Note that $f_{i}(\alpha_{j})=g_{j}(\alpha_{i})=F(\alpha_{j},\alpha_{i})$
holds for all $\alpha_{i},\alpha_{j}$. We say a degree-$m$ polynomial
$F_{i}(x)$ (resp. a degree-$\ell$ polynomial $G_{i}(y)$), where
$i\in\\{1,\ldots,n\\}$, lies on a degree-$(\ell,m)$ bivariate polynomial
$F(x,y)$, if $F(x,\alpha_{i})=F_{i}(x)$ (resp. $F(\alpha_{i},y)=G_{i}(y)$)
holds. $F(x,y)$ is called symmetric, if $r_{ij}=r_{ji}$ holds, implying
$F(\alpha_{j},\alpha_{i})=F(\alpha_{i},\alpha_{j})$ and
$F(x,\alpha_{i})=F(\alpha_{i},x)$.

######  Definition 2.5 ($d$-sharing [28, 8]).

A value $s\in\mathbb{F}$ is said to be $d$-shared, if there exists a
degree-$d$ polynomial, say $q(\cdot)$, with $q(0)=s$, such that each (honest)
$P_{i}\in\mathcal{P}$ holds its share $s_{i}\stackrel{{\scriptstyle
def}}{{=}}q(\alpha_{i})$ (we interchangeably use the term shares of $s$ and
shares of the polynomial $q(\cdot)$ to denote the values $q(\alpha_{i})$). The
vector of shares of $s$ corresponding to the (honest) parties in $\mathcal{P}$
is denoted as $[s]_{d}$. A set of values
$S=(s^{(1)},\ldots,s^{(L)})\in\mathbb{F}^{L}$ is said to be $d$-shared, if
each $s^{(i)}\in S$ is $d$-shared.

####  2.2.1 Properties of Univariate Polynomials Over $\mathbb{F}$

Most of the type-II VSS schemes are with respect to the Shamir’s $t\mbox{-out-
of-}n$ SS scheme $(\mathsf{Sha}_{\mathsf{G}},\mathsf{Sha}_{\mathsf{R}})$ [55].
Algorithm $\mathsf{Sha}_{\mathsf{G}}$ takes input a secret $s\in\mathbb{F}$.
To compute the shares, it picks a Shamir-sharing polynomial $q(\cdot)$
randomly from the set $\mathcal{P}^{s,t}$ of all degree-$t$ univariate
polynomials over $\mathbb{F}$ whose constant term is $s$. The output of
$\mathsf{Sha}_{\mathsf{G}}$ is $(s_{1},\ldots,s_{n})$, where
$s_{i}=q(\alpha_{i})$. Since $q(\cdot)$ is chosen randomly, the probability
distribution of the $t$ shares learnt by $\mathsf{Adv}$ will be independent of
the underlying secret. Formally:

######  Lemma 2.6 ([4]).

For any set of distinct non-zero elements
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$, any pair of values
$s,s^{\prime}\in\mathbb{F}$, any subset $I\subset\\{1,\ldots,n\\}$ where
$|I|=\ell\leq t$, and every $\vec{y}\in\mathbb{F}^{\ell}$, it holds that:

$\underset{f(x)\in_{r}\mathcal{P}^{s,t}}{\mbox{Pr}}\Big{[}\vec{y}=(\\{f(\alpha_{i})\\}_{i\in
I})\Big{]}=\underset{g(x)\in_{r}\mathcal{P}^{s^{\prime},t}}{\mbox{Pr}}\Big{[}\vec{y}=(\\{g(\alpha_{i})\\}_{I\in
I})\Big{]},$

where $f(x)$ and $g(x)$ are chosen randomly (denoted by the notation
$\in_{r}$) from $\mathcal{P}^{s,t}$ and $\mathcal{P}^{s^{\prime},t}$,
respectively.

Let $(s_{1},\ldots,s_{n})$ be a vector of Shamir-shares for $s$, generated by
$\mathsf{Sha}_{\mathsf{G}}$. Moreover, let $I\subset\\{1,\ldots,n\\}$, where
$|I|=t+1$. Then $\mathsf{Sha}_{\mathsf{R}}$ takes input the shares
$\\{s_{i}\\}_{i\in I}$ and outputs $s$ by interpolating the unique degree-$t$
Shamir-sharing polynomial passing through the points
$\\{(\alpha_{i},s_{i})\\}_{i\in I}$.

##### Relationship Between $d$-sharing and Reed-Solomon (RS) Codes

Let $s$ be $d$-shared through a polynomial $q(\cdot)$ and let
$(s_{1},\ldots,s_{n})$ be the vector of shares. Moreover, let $W$ be a subset
of these shares, such that it is ensured that at most $r$ shares in $W$ are
incorrect (the exact identity of the incorrect shares are not known). The goal
is to error-correct the incorrect shares in $W$ and correctly reconstruct back
the polynomial $q(\cdot)$. Coding-theory [47] says that this is possible if
and only if $|W|\geq d+2r+1$ and the corresponding algorithm is denoted by
$\mathsf{RS}\mbox{-}\mathsf{Dec}(d,r,W)$. There are several well-known
efficient instantiations of $\mathsf{RS}\mbox{-}\mathsf{Dec}$, such as the
Berlekamp-Welch algorithm [44].

####  2.2.2 Properties of Bivariate Polynomials Over $\mathbb{F}$

There always exists a unique degree-$d$ univariate polynomial, passing through
$d+1$ distinct points. A generalization of this result for bivariate
polynomials is that if there are “sufficiently many” univariate polynomials
which are “pair-wise consistent”, then together they lie on a unique bivariate
polynomial. Formally:

######  Lemma 2.7 (Pair-wise Consistency Lemma [16, 50, 4]).

Let $\\{f_{i_{1}}(x),\ldots,f_{i_{q}}(x)\\}$ and
$\\{g_{j_{1}}(y),\ldots,\allowbreak g_{j_{r}}(y)\\}$ be degree-$\ell$ and
degree-$m$ polynomials respectively where $q\geq m+1,r\geq\ell+1$ and where
$i_{1},\ldots,i_{q},j_{1},\ldots,j_{r}\in\\{1,\ldots,n\\}$. Moreover, let for
every $i\in\\{i_{1},\ldots,i_{q}\\}$ and every $j\in\\{j_{1},\ldots,j_{r}\\}$,
the condition $f_{i}(\alpha_{j})=g_{j}(\alpha_{i})$ holds. Then there exists a
unique degree-$(\ell,m)$ bivariate polynomial ${F}^{\star}(x,y)$, such that
the polynomials $f_{i_{1}}(x),\ldots,f_{i_{q}}(x)$ and
$g_{j_{1}}(y),\ldots,g_{j_{r}}(y)$ lie on ${F}^{\star}(x,y)$.

In type-II VSS schemes based on Shamir’s SS scheme, $\mathsf{D}$ on having
input $s$ first picks a random degree-$t$ Shamir-sharing polynomial
$q(\cdot)\in\mathcal{P}^{s,t}$ and then embeds $q(\cdot)$ into a random
degree-$(t,t)$ bivariate polynomial $F(x,y)$ at $x=0$. Each $P_{i}$ then
receives $f_{i}(x)=F(x,\alpha_{i})$ and $g_{i}(y)=F(\alpha_{i},y)$ from
$\mathsf{D}$. Similar to Shamir SS, $\mathsf{Adv}$ by learning at most $t$ row
and column-polynomials, does not learn $s$. Intuitively, this is because
$(t+1)^{2}$ distinct values are required to uniquely determine $F(x,y)$, but
$\mathsf{Adv}$ learns at most $t^{2}+2t$ distinct values. In fact, it can be
shown that for every two degree-$t$ polynomials $q_{1}(\cdot),q_{2}(\cdot)$
such that $q_{1}(\alpha_{i})=q_{2}(\alpha_{i})=f_{i}(0)$ holds for every
$P_{i}\in\mathcal{C}$ (where $\mathcal{C}$ is the set of corrupt parties), the
distribution of the polynomials
$\\{f_{i}(x),g_{i}(y)\\}_{P_{i}\in\mathcal{C}}$ when $F(x,y)$ is chosen based
on $q_{1}(\cdot)$, is identical to the distribution when $F(x,y)$ is chosen
based on $q_{2}(\cdot)$. Formally:

######  Lemma 2.8 ([4]).

Let $\mathcal{C}\subset\mathcal{P}$ where $|\mathcal{C}|\leq t$, and let
$q_{1}(\cdot)\neq q_{2}(\cdot)$ be degree-$t$ polynomials where
$q_{1}(\alpha_{i})=q_{2}(\alpha_{i})$ holds for all $P_{i}\in\mathcal{C}$.
Then the probability distributions
$\Big{\\{}\\{F(x,\alpha_{i}),F(\alpha_{i},y)\\}_{P_{i}\in\mathcal{C}}\Big{\\}}$
and
$\Big{\\{}\\{F^{\prime}(x,\alpha_{i}),F^{\prime}(\alpha_{i},y)\\}_{P_{i}\in\mathcal{C}}\Big{\\}}$
are identical, where $F(x,y)\neq F^{\prime}(x,y)$ are different degree-$(t,t)$
bivariate polynomials, chosen at random, under the constraints that
$F(0,y)=q_{1}(\cdot)$ and $F^{\prime}(0,y)=q_{2}(\cdot)$ holds.

##  3 Lower Bounds

In any perfectly-secure VSS scheme, the joint view of the honest parties
should uniquely determine the dealer’s secret. Otherwise the correctness
property will be violated if the corrupt parties produce incorrect view during
the reconstruction phase. Since there can be only $n-t$ honest parties, to
satisfy the privacy property, the condition $n-t>t$ should necessarily hold,
as otherwise the view of the adversary will not be independent of the dealer’s
secret. We actually need a stricter necessary condition of $n>3t$ to hold for
any perfectly-secure VSS scheme, as stated in the following theorem.

######  Theorem 3.1 ([29]).

Let $\Pi=(\mathsf{Sh},\mathsf{Rec})$ be a perfectly-secure VSS scheme. Then
$n>3t$ holds.

Theorem 3.1 is first proved formally by Dolev, Dwork, Waarts and Yung in [29]
by relating VSS with the problem of $1$-way perfectly-secure message
transmission (1-way PSMT) [29]. In the 1-way PSMT problem, there is a sender S
and a receiver R, such that there are $n$ disjoint uni-directional
communication channels $Ch_{1},\ldots,Ch_{n}$ from S to R (i.e. only S can
send messages to R along these channels). At most $t$ out of these channels
can be controlled by a computationally unbounded malicious/Byzantine adversary
in any arbitrary fashion. The goal is to design a protocol, which allows S to
send some input message $m$ reliably (i.e. R should be able to receive $m$
without any error) and privately (i.e. view of the adversary should be
independent of $m$) to R. In [29], it is shown that a 1-way PSMT protocol
exists only if $n>3t$. Moreover, if there exists a perfectly-secure VSS scheme
$(\mathsf{Sh},\mathsf{Rec})$ with $n\leq 3t$, then one can design a $1$-way
PSMT protocol with $n\leq 3t$, which is a contradiction. On a very high level,
the reduction from $1$-way PSMT to VSS can be shown as follows: S on having a
message $m$, acts as a dealer and runs an instance of $\mathsf{Sh}$ with input
$m$ by playing the role of the parties $P_{1},\ldots,P_{n}$ as per the
protocol $\mathsf{Sh}$. Let $\mathsf{view}_{i}$ be the view generated for
$P_{i}$, which S communicates to R over $Ch_{i}$. Let R receives
$\mathsf{view}^{\prime}_{i}$ over $Ch_{i}$, where
$\mathsf{view}^{\prime}_{i}=\mathsf{view}_{i}$ if $Ch_{i}$ is not under
adversary’s control. To recover $m$, R applies the reconstruction function as
per $\mathsf{Rec}$ on
$(\mathsf{view}^{\prime}_{1},\ldots,\mathsf{view}^{\prime}_{n})$. It is easy
to see that the correctness of the VSS scheme implies that R correctly
recovers $m$, while the privacy of the VSS scheme guarantees that the view of
any adversary controlling at most $t$ channels remains independent of $m$.

An alternative argument for the requirement of $n>3t$ for perfect VSS follows
from its reduction to a perfectly-secure reliable-broadcast (RB) protocol over
the pair-wise channels, for which $n>3t$ is required [52]. This is elaborated
further later in the context of usage of a broadcast channel for designing VSS
protocols (the paragraph entitled ”On the Usage of Broadcast Channel” after
Lemma 3.4 and Footnote 5).

##### The Round Complexity of VSS

In Genarro, Ishai, Kushilevitz and Rabin [33], the round-complexity of a VSS
scheme is defined to be the number of rounds in the sharing phase, as all
(perfectly-secure) VSS schemes adhere to a single-round reconstruction. The
interplay between the round-complexity of perfectly-secure VSS and resilience
bounds is stated below.

######  Theorem 3.2 ([33]).

Let $R\geq 1$ be a positive integer and let $R^{\prime}\leq R$. Then:

  * $\bullet$

If $R=1$, then there exists no perfectly-secure VSS scheme with
$(R,R^{\prime})$ rounds in the sharing phase if either $t>1$ (irrespective of
the value of $n$) or if ($t=1$ and $n\leq 4$).

  * $\bullet$

If $R=2$, then perfectly-secure VSS with $(R,R^{\prime})$ rounds in sharing
phase is possible only if $n>4t$.

  * $\bullet$

If $R\geq 3$, then perfectly-secure VSS with $(R,R^{\prime})$ rounds in
sharing phase is possible only if $n>3t$.

We give a very high level overview of the proof of Theorem 3.2. We focus only
on $2$ and $R$-round sharing phase VSS schemes where $R\geq 3$, as one can use
standard hybrid arguments to derive the bounds related to VSS schemes with
$1$-round sharing phase (see for instance [48]). The lower bound for $2$-round
VSS schemes (namely $n>4t$) is derived by relating VSS to the secure multi-
cast (SM) problem. In the SM problem, there exists a designated sender
$\mathsf{S}\in\mathcal{P}$ with some private message $m$ and a designated
receiving set $\mathcal{R}\subseteq\mathcal{P}$, where
$\mathsf{S}\in\mathcal{R}$ and where $|\mathcal{R}|>2$. The goal is to design
a protocol which allows $\mathsf{S}$ to send its message identically to all
the parties only in $\mathcal{R}$, even in the presence of an adversary who
can control any $t$ parties, possibly including $\mathsf{S}$. Moreover, if all
the parties in $\mathcal{R}$ are honest, then the view of the adversary should
be independent of $m$. Genarro et al. [33] establishes the following
relationship between VSS and SM.

######  Lemma 3.3 ([33]).

Let $(\mathsf{Sh},\mathsf{Rec})$ be a VSS scheme with a $k$-round sharing
phase where $k\geq 2$. Then there exists a $k$-round SM protocol.

The proof of Lemma 3.3 proceeds in two steps.

  * –

It is first shown that for any $R$-round protocol $\Pi$, there exists an
$R$-round protocol $\Pi^{\prime}$ with the same security guarantees as $\Pi$,
such that all the messages in rounds $2,\ldots,R$ of $\Pi^{\prime}$ are
broadcast messages. The idea is to let each $P_{i}$ exchange a “sufficiently-
large” random pad with every $P_{j}$ apriori during the first round. Then in
any subsequent round of $\Pi$, if $P_{i}$ is supposed to privately send
$v_{ij}$ to $P_{j}$, then in $\Pi^{\prime}$, party $P_{i}$ instead broadcasts
$v_{ij}$ being masked with appropriate pad, exchanged with $P_{j}$. Since
$P_{j}$ is supposed to hold the same pad, it can unmask the broadcasted value
and recover $v_{ij}$ and process it as per $\Pi$.

  * –

Let $(\mathsf{Sh},\mathsf{Rec})$ be a VSS scheme where $\mathsf{Sh}$ requires
$k$ rounds such that $k\geq 2$. Using the previous implication, we can assume
that all the messages during the final round of $\mathsf{Sh}$ are broadcast
messages. Using $(\mathsf{Sh},\mathsf{Rec})$, one can get a $k$-round SM
protocol as follows: the parties invoke an instance of $\mathsf{Sh}$, with
$\mathsf{S}$ playing the role of $\mathsf{D}$ with input $m$. In the final
round, apart from the messages broadcasted by the parties as part of
$\mathsf{Sh}$, every party $P_{i}$ privately sends its entire view of the
first $k-1$ rounds during $\mathsf{Sh}$ to every party in $\mathcal{R}$. Based
on this, every party in $\mathcal{R}$ will get the view of all the parties in
$\mathcal{P}$ for all the $k$ rounds of $\mathsf{Sh}$. Intuitively, this also
gives every (honest) party in $\mathcal{R}$ the share of every (honest) party
from $\mathsf{Sh}$. Every party in $\mathcal{R}$ then applies the
reconstruction function on the $n$ extrapolated views as per $\mathsf{Rec}$
and outputs the result. It is easy to see that the correctness of the VSS
implies that if $\mathsf{S}$ is honest, then all the honest parties in
$\mathcal{R}$ obtains $m$. Moreover, the privacy of the VSS scheme implies
that if $\mathcal{R}$ contains only honest parties, then the view of the
adversary remains independent of $m$. Finally, the strong commitment of the
VSS guarantees that even if $\mathsf{S}$ is corrupt, all honest parties in
$\mathcal{R}$ obtain the same output.

Next, Genarro et al. [33] shows the impossibility of any $2$-round SM protocol
with $n\leq 4t$.

######  Lemma 3.4.

There exists no $2$-round SM protocol where $n\leq 4t$.

By a standard player-partitioning argument [43], Lemma 3.4 reduces to showing
the impossibility of any $2$-round SM protocol with $n=4$ and $t=1$. At a
high-level, the player-partitioning argument goes as follows: if there exists
a $2$-round SM protocol $\Pi$ with $n=4t$, then one can also design a
$2$-round SM protocol $\Pi^{\prime}$ for $4$ parties, where each of the $4$
parties in $\Pi^{\prime}$ plays the role of a disjoint set of $t$ parties as
per $\Pi$. However, one can show that there does not exist any $2$-round SM
protocol with $n=4$ and $t=1$, thus ruling out the existence of any $2$-round
SM protocol with $n\leq 4t$. We refer the interested readers to [33] for the
proof of non-existence of any $2$-round SM protocol with $n=4$ and $t=1$. Now
combining Lemma 3.3 with Lemma 3.4, we get that there exists no VSS scheme
with $n\leq 4t$ and a $2$-round sharing phase. Since $n>3t$ is necessary for
any VSS scheme, this automatically implies that a VSS scheme with $3$ or more
rounds of sharing phase will necessarily require $n>3t$.

##### On the Usage of Broadcast Channel

All synchronous VSS schemes assume the existence of a broadcast channel.
However, this is just a simplifying abstraction, as the parties can “emulate”
the effect of a broadcast channel by executing a perfectly-secure reliable-
broadcast (RB) protocol over the pair-wise channels, provided $n>3t$ holds
[52]. RB protocols with guaranteed termination in the presence of
malicious/Byzantine adversaries require $\Omega(t)$ rounds of communication
[31], while the RB protocols with probabilistic termination guarantees require
$\mathcal{O}(1)$ expected number of rounds [30, 38] where the constants are
high. Given the fact that the usage of broadcast channel is an “expensive
resource”, a natural question is whether one can design a VSS scheme with a
constant number of rounds in the sharing phase and which does not require the
usage of broadcast channel in any of these rounds. Unfortunately, the answer
is no. This is because such a VSS scheme will imply the existence of a strict
constant round RB protocol with guaranteed termination in the presence of a
malicious adversary (the message to be broadcast by the sender can be shared
using the VSS scheme with sender playing the role of the dealer, followed by
reconstructing the shared message), which is impossible as per the result
of555This reduction from RB to VSS is another way to argue the necessity of
the $n>3t$ condition for VSS, since the necessary condition for RB is $n>3t$
[52]. [31]. Hence the best that one can hope for is to design VSS schemes
which invoke the broadcast channel only in a fewer rounds.

##  4 Upper Bounds

We now discuss the optimality of the bounds in Theorem 3.2 by presenting VSS
schemes with various round-complexities. The sharing phase of these schemes
are summarized in Table 1 and their reconstruction phase require one round.
The prefix in the names of the schemes denotes the number of rounds in the
sharing phase. In the table, $\mathbb{G}$ denotes a finite group and RSS
stands for replicated secret-sharing [37] (see Section 4.1.4). The
$\mathsf{3AKP\mbox{-}VSS}$ scheme has some special properties, compared to
$\mathsf{3FGGRS\mbox{-}VSS},\mathsf{3KKK\mbox{-}VSS}$ schemes, which are
useful for designing round-optimal perfectly-secure MPC protocols (see Section
4.1.7).

Scheme | $n$ | Round Complexity | Type | Sharing Semantic | Algebraic Structure | Communication Complexity
---|---|---|---|---|---|---
$\mathsf{7BGW\mbox{-}VSS}$ [12] | $n>3t$ | $(7,5)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log{|\mathbb{F}|}))$
$\mathsf{5BGW\mbox{-}VSS}$ [33] | $n>3t$ | $(5,3)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log{|\mathbb{F}|}))$
$\mathsf{4GIKR\mbox{-}VSS}$ [33] | $n>3t$ | $(4,3)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log{|\mathbb{F}|}))$
$\mathsf{3GIKR\mbox{-}VSS}$ [33] | $n>3t$ | $(3,2)$ | Type-II | RSS | $\mathbb{G}$ | $\mathcal{O}(n\cdot{n\choose t}\log{|\mathbb{G}|}+\mathcal{BC}(n\cdot{n\choose t}\log{|\mathbb{G}|}))$
$\mathsf{3FGGRS\mbox{-}VSS}$ [32] | $n>3t$ | $(3,2)$ | Type-I | Not Applicable | $\mathbb{F}$ | $\mathcal{O}(n^{3}\log{|\mathbb{F}|}+\mathcal{BC}(n^{3}\log{|\mathbb{F}|}))$
$\mathsf{3KKK\mbox{-}VSS}$ [39] | $n>3t$ | $(3,1)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{3}\log{|\mathbb{F}|}+\mathcal{BC}(n^{3}\log{|\mathbb{F}|}))$
$\mathsf{3AKP\mbox{-}VSS}$ [3] | $n>3t$ | $(3,2)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{3}\log{|\mathbb{F}|}+\mathcal{BC}(n^{3}\log{|\mathbb{F}|}))$
$\mathsf{2GIKR\mbox{-}VSS}$ [33] | $n>4t$ | $(2,1)$ | Type-II | Shamir | $\mathbb{F}$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log{|\mathbb{F}|}))$
$\mathsf{1GIKR\mbox{-}VSS}$ [33] | $n=5,t=1$ | $(1,0)$ | Type-I | Not Applicable | $\mathbb{F}$ | $\mathcal{O}(n\log{|\mathbb{F}|})$

Table 1: Summary of the sharing phase of the perfectly-secure VSS schemes,
with $\mathcal{BC}$ denoting communication over the broadcast channel.

###  4.1 VSS Schemes with $n>3t$

We start with perfectly-secure VSS schemes with $n>3t$. While presenting these
schemes, we use the following simplifying conventions. If in a protocol a
party is expecting some message from a sender party and if it either receives
no message or semantically/syntactically incorrect message, then the receiving
party substitutes some default value and proceeds with the steps of the
protocol. Similarly, if the dealer is publicly identified to be cheating then
the parties discard the dealer and terminate the protocol execution with a
default sharing of $0$.

####  4.1.1 The $\mathsf{7BGW\mbox{-}VSS}$ Scheme

The scheme (Fig 2) consists of the protocols
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ and
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$. Protocol
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ is actually a simplified version
of the original protocol, taken from [36]. To share $s$, the dealer
$\mathsf{D}$ picks a random degree-$t$ Shamir-sharing polynomial $q(\cdot)$
and the goal is to ensure that $\mathsf{D}$ verifiably distributes the Shamir-
shares of $s$ as per $q(\cdot)$. Later, during
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$, the parties exchange these
Shamir-shares and reconstruct $q(\cdot)$ by error-correcting up to $t$
incorrect shares using the algorithm $\mathsf{RS}\mbox{-}\mathsf{Dec}$. The
verifiability in $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ ensures that
even if $\mathsf{D}$ is corrupt, the shares distributed by $\mathsf{D}$ to the
(honest) parties are as per some degree-$t$ Shamir-sharing polynomial, say
$q^{\star}(\cdot)$, thus ensuring that $s^{\star}\stackrel{{\scriptstyle
def}}{{=}}q^{\star}(0)$ is $t$-shared. Moreover, the same $s^{\star}$ is
reconstructed during $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$. This
ensures that the scheme is of type-II.

To prove that $\mathsf{D}$ is sharing its secret using a degree-$t$ polynomial
$q(\cdot)$, the dealer $\mathsf{D}$ embeds $q(\cdot)$ in a random
degree-$(t,t)$ bivariate polynomial $F(x,y)$. As shown in Fig 1, there are two
approaches to do this embedding. The polynomial $q(\cdot)$ could be either
embedded at $x=0$ (the approach shown in part (a)) or it could be embedded at
$y=0$ (the approach shown in part (b)). For our description, we follow the
first approach. The dealer then distributes distinct row and column-
polynomials to respective parties. If $\mathsf{D}$ is honest, then this
distribution of information maintains the privacy of dealer’s secret (follows
from Lemma 2.8). Also, if $\mathsf{D}$ is honest, then constant term of the
individual row-polynomials actually constitute the Shamir-shares of $s$, as
they constitute distinct points on $q(\cdot)$. However, a potentially corrupt
$\mathsf{D}$ may distribute polynomials, which may not be derived from a
single degree-$(t,t)$ bivariate polynomial. Hence, the parties interact to
verify if $\mathsf{D}$ has distributed “consistent” row and column-
polynomials, without revealing any additional information about $s$.

$[s]_{t}$(a)$f_{j}(x)$$\Rightarrow$$g_{i}(y)$$\Downarrow$$\Downarrow$$q(\cdot)$$F(\alpha_{1},\alpha_{1})$$\ldots$$F(\alpha_{i},\alpha_{1})$$\ldots$$F(\alpha_{n},\alpha_{1})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{j})$$\ldots$$F(\alpha_{i},\alpha_{j})$$\ldots$$F(\alpha_{n},\alpha_{j})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{n})$$\ldots$$F(\alpha_{i},\alpha_{n})$$\ldots$$F(\alpha_{n},\alpha_{n})$$\Rightarrow$
. . . $\Rightarrow$ . . . $\Rightarrow$$f_{1}(0)$ . . . $f_{j}(0)$ . . .
$f_{n}(0)$$[s]_{t}$(b)$f_{j}(x)$$\Leftarrow$$g_{i}(y)$$\Downarrow$$\Leftarrow$$q(\cdot)$$F(\alpha_{1},\alpha_{1})$$\ldots$$F(\alpha_{i},\alpha_{1})$$\ldots$$F(\alpha_{n},\alpha_{1})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{j})$$\ldots$$F(\alpha_{i},\alpha_{j})$$\ldots$$F(\alpha_{n},\alpha_{j})$
. . . . . . . . . . . . . . .
$F(\alpha_{1},\alpha_{n})$$\ldots$$F(\alpha_{i},\alpha_{n})$$\ldots$$F(\alpha_{n},\alpha_{n})$$\Downarrow$$\Downarrow$$\Downarrow$$\Downarrow$$\Downarrow$$g_{1}(0)$$\ldots$$g_{i}(0)$$\ldots$$g_{n}(0)$
Figure 1: Pictorial depiction of the values on the degree-$(t,t)$ polynomial
$F(x,y)$ distributed by $\mathsf{D}$ and how they constitute $[s]_{t}$. The
value highlighted in the yellow color denotes a common value held by every
pair of parties $(P_{i},P_{j})$. In the first approach, the Shamir-sharing
polynomial $q(\cdot)$ is set as $F(0,y)$ and the Shamir-shares are the
constant terms of the individual row-polynomials. In the second approach,
$q(\cdot)$ is set as $F(x,0)$ and the Shamir-shares are the constant terms of
the individual column-polynomials.

Every pair of parties $P_{i},P_{j}$ upon receiving the polynomials
$f_{i}(x),g_{i}(y)$ and $f_{j}(x),g_{j}(y)$ respectively, interact and check
if $f_{i}(\alpha_{j})=g_{j}(\alpha_{i})$ and
$f_{j}(\alpha_{i})=g_{i}(\alpha_{j})$ holds. If the checks pass for all the
pairs of (honest) parties, then from Lemma 2.7, it follows that $\mathsf{D}$
has distributed consistent row (and column-polynomials) to the parties.
However, if the checks do not pass, then either $\mathsf{D}$ has distributed
inconsistent polynomials or the parties have not exchanged the correct common
values. In this case, the parties interact publicly with $\mathsf{D}$ to
resolve these inconsistencies. The details follow.

Every $P_{i}$ upon receiving the supposedly common values on its column
polynomial prepares a complaint-list $L_{i}$, which includes all the parties
$P_{j}$ whose received value is inconsistent with $P_{i}$’s column-polynomial
(this is interpreted as if there is a dispute between $P_{i}$ and $P_{j}$). If
there is a dispute between $P_{i}$ and $P_{j}$, then at least one of the three
parties $\mathsf{D},P_{i},P_{j}$ is corrupt. Each party then broadcasts its
complaint-list. In response, for every dispute reported by a party, the dealer
$\mathsf{D}$ makes public its version of the disputed value, namely the
corresponding value on its bivariate polynomial. This is followed by the
first-stage accusations against the dealer. Namely, a party publicly “accuses”
$\mathsf{D}$, if the party is in dispute with more than $t$ parties or if it
finds $\mathsf{D}$ making public a value, which is not consistent with its
column-polynomial. In response, $\mathsf{D}$ makes public the row and column-
polynomials of such accusing parties. However, care has to taken to ensure
that these broadcasted polynomials are consistent with the polynomials of the
parties who have not yet accused $\mathsf{D}$. This is done through the
second-stage of public accusations against the dealer, where a party (who has
not yet accused $\mathsf{D}$) publicly accuses $\mathsf{D}$, if it finds any
inconsistency between the row and column-polynomials held by the party and the
polynomials which were made public by $\mathsf{D}$.

An honest $\mathsf{D}$ always respond correctly against any accusation or
dispute. Moreover, there will be at most $t$ accusations against $\mathsf{D}$.
Consequently, if the parties find $\mathsf{D}$ not responding to any
accusation/dispute or if more than $t$ parties accuse $\mathsf{D}$, then
$\mathsf{D}$ is corrupt and hence the parties discard $\mathsf{D}$. If
$\mathsf{D}$ is honest, then all the values which are made public correspond
to corrupt parties (already known to $\mathsf{Adv}$) and hence does not
violate privacy. On the other hand, if $\mathsf{D}$ is corrupt but not
discarded, then it ensures that the polynomials of all honest parties are
consistent.  Sharing Phase: Protocol
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ $\bullet$ Round I (sending
polynomials) — the dealer does the following:  – On having the input
$s\in\mathbb{F}$, pick a random degree-$t$ Shamir-sharing polynomial
$q(\cdot)$, such that $q(0)=s$ holds. Then pick a random degree-$(t,t)$
bivariate polynomial $F(x,y)$, such that $F(0,y)=q(\cdot)$ holds. – For
$i=1,\ldots,n$, send the polynomials $f_{i}(x)\stackrel{{\scriptstyle
def}}{{=}}F(x,\alpha_{i})$ and $g_{i}(y)\stackrel{{\scriptstyle
def}}{{=}}F(\alpha_{i},y)$ to party $P_{i}$. $\bullet$ Round II (pair-wise
consistency checks) — each party $P_{i}$ does the following:  – On receiving
degree-$t$ polynomials $f_{i}(x),g_{i}(y)$ from $\mathsf{D}$, send
$f_{ij}\stackrel{{\scriptstyle def}}{{=}}f_{i}(\alpha_{j})$ to $P_{j}$, for
$j=1,\ldots,n$. $\bullet$ Round III (broadcast complaints) — each party
$P_{i}$ does the following:  – Initialize a complaint-list $L_{i}$ to
$\emptyset$. For $j=1,\ldots,n$, include $P_{j}$ to $L_{i}$, if $f_{ji}\neq
g_{i}(\alpha_{j})$. Broadcast $L_{i}$. $\bullet$ Round IV (resolving
complaints) — the dealer does the following:  – For $i=1,\ldots,n$, if $P_{i}$
has broadcast $L_{i}\neq\emptyset$, then for every $P_{j}\in L_{i}$, broadcast
the value $F(\alpha_{i},\alpha_{j})$. $\bullet$ Round V (first-stage
accusations) — each party $P_{i}$ does the following:  – Broadcast the message
$(P_{i},\texttt{accuse},\mathsf{D})$, if any of the following conditions hold.
1. $|L_{i}|>t$ or if $P_{i}\in L_{i}$; 2. If $\exists k\in\\{1,\ldots,n\\}$,
such that $P_{i}\in L_{k}$ and $F(\alpha_{k},\alpha_{i})\neq
f_{i}(\alpha_{k})$; 3. If for any $P_{j}\in L_{i}$, the condition
$F(\alpha_{i},\alpha_{j})\neq g_{i}(\alpha_{j})$ holds. $\bullet$ Round VI
(resolving first-stage accusations) — the dealer does the following:  – For
every $P_{i}$ who has broadcast $(P_{i},\texttt{accuse},\mathsf{D})$,
broadcast the degree-$t$ polynomials $f_{i}(x)$ and $g_{i}(y)$. $\bullet$
Round VII (second-stage accusations) — each party $P_{i}$ does the following:
– Broadcast the message $(P_{i},\texttt{accuse},\mathsf{D})$ if there exists
any $j\in\\{1,\ldots,n\\}$ such that $\mathsf{D}$ has broadcast degree-$t$
polynomials $f_{j}(x),g_{j}(y)$ and either $f_{j}(\alpha_{i})\neq
g_{i}(\alpha_{j})$ or $g_{j}(\alpha_{i})\neq f_{i}(\alpha_{j})$ holds.
$\bullet$ Output decision — each party $P_{i}$ does the following:  – If more
than $t$ parties $P_{j}$ broadcast $(P_{j},\texttt{accuse},\mathsf{D})$
throughout the protocol, then discard $\mathsf{D}$. – Else output the
share666If $\mathsf{D}$ has broadcast new polynomials $f_{i}(x),g_{i}(y)$ for
$P_{i}$ during Round VI, then consider these new polynomials.
$s_{i}=f_{i}(0)$.
Reconstruction Phase: Protocol $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$
Each party $P_{i}$ sends the share $s_{i}$ to every party
$P_{j}\in\mathcal{P}$. Let $W_{i}$ be the set of shares received by $P_{i}$
from the parties. Party $P_{i}$ executes
$\mathsf{RS}\mbox{-}\mathsf{Dec}(t,t,W_{i})$ to reconstruct $s$.

Figure 2: The perfectly-secure VSS scheme of Ben-Or, Goldwasser and Wigderson
[12].

Since the idea of bivariate polynomials has been used in all the followup
works on perfectly-secure VSS, we give a very high level overview of the proof
of the properties of $\mathsf{7BGW\mbox{-}VSS}$ scheme.

######  Theorem 4.1.

Protocols
$(\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh},\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec})$
constitute a Type-II perfectly-secure VSS scheme with respect to Shamir’s
$t\mbox{-out-of-}n$ secret-sharing scheme. The protocol incurs a communication
of $\mathcal{O}(n^{2}\log{|\mathbb{F}|})$ bits over the point-to-point
channels and broadcast of $\mathcal{O}(n^{2}\log{|\mathbb{F}|})$ bits.

###### Proof.

If $\mathsf{D}$ is honest, then $f_{i}(\alpha_{j})=g_{j}(\alpha_{i})$ and
$f_{j}(\alpha_{i})=g_{i}(\alpha_{j})$ holds for every pair of parties
$(P_{i},P_{j})$. Consequently, no honest $P_{j}$ will be present in the list
$L_{i}$ of any honest $P_{i}$. Moreover, $\mathsf{D}$ honestly resolves the
first-stage accusations as well as second-stage accusations and consequently,
no honest party accuses and discards $\mathsf{D}$. Hence $s$ will be
$t$-shared through the degree-$t$ polynomial $q(\cdot)$. Moreover, during
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$, the honest parties correctly
reconstruct $q(\cdot)$ and hence $s$. This follows from the properties of
$\mathsf{RS}\mbox{-}\mathsf{Dec}$ and the fact that $q(\cdot)$ is a degree-$t$
polynomial and at most $t$ corrupt parties can send incorrect shares. Hence,
the correctness property is guaranteed.

Let $\mathcal{C}$ be the set of corrupt parties. If $\mathsf{D}$ is honest,
then throughout $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, the view of
$\mathsf{Adv}$ consists of $\\{f_{i}(x),g_{i}(y)\\}_{P_{i}\in\mathcal{C}}$.
Moreover, no honest party accuses $\mathsf{D}$ and hence all the information
which $\mathsf{D}$ makes public can be derived from
$\\{f_{i}(x),g_{i}(y)\\}_{P_{i}\in\mathcal{C}}$. Now since these polynomials
are derived from $F(x,y)$, which is a randomly chosen polynomial embedding
$q(\cdot)$, it follows from Lemma 2.8 that the view of $\mathsf{Adv}$ is
distributed independently of $s$, thus guaranteeing privacy.

For strong commitment we have to consider a corrupt $\mathsf{D}$. If the
honest parties discard $\mathsf{D}$, then clearly the value
$s^{\star}\stackrel{{\scriptstyle def}}{{=}}0$ will be $t$-shared and the same
value $0$ gets reconstructed during
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$. On the other hand, consider
the case when the honest parties do not discard $\mathsf{D}$ during
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$. In this case we claim that the
row and column-polynomials of all the honest parties are derived from a single
degree-$(t,t)$ bivariate polynomial, say ${F}^{\star}(x,y)$, which we call as
$\mathsf{D}$’s committed bivariate polynomial. Consequently,
$s^{\star}\stackrel{{\scriptstyle def}}{{=}}{F}^{\star}(0,0)$ will be
$t$-shared through the Shamir-sharing polynomial
$q^{\star}(\cdot)\stackrel{{\scriptstyle def}}{{=}}{F}^{\star}(0,y)$ and
$s^{\star}$ gets reconstructed during
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$.

To prove the claim, we first note that there are at least $n-t\geq 2t+1$
parties who do not broadcast an accuse message against $\mathsf{D}$ (as
otherwise $\mathsf{D}$ is discarded). Let $\mathcal{H}$ be the set of honest
parties among these $n-t$ parties. It is easy to see that $|\mathcal{H}|\geq
n-2t\geq t+1$. The parties in $\mathcal{H}$ receive degree-$t$ row and column-
polynomials from $\mathsf{D}$. Moreover, for every
$P_{i},P_{j}\in\mathcal{H}$, their row and column-polynomials are pair-wise
consistent (as otherwise either $P_{i}$ or $P_{j}$ would broadcast an accuse
message against $\mathsf{D}$). It then follows from Lemma 2.7 that the row and
column-polynomials of all the parties in $\mathcal{H}$ lie on a single
degree-$(t,t)$ bivariate polynomial, say ${F}^{\star}(x,y)$. Next consider any
honest party $P_{j}\not\in\mathcal{H}$, who broadcasts an accuse message
against $\mathsf{D}$ and corresponding to which $\mathsf{D}$ makes public the
row and column-polynomials of $P_{j}$. To complete the proof of the claim, we
need to show that these polynomials also lie on ${F}^{\star}(x,y)$. We show it
for the row-polynomial of $P_{j}$ and a similar argument can be used for the
column-polynomial as well. So let $f_{j}(x)$ be the degree-$t$ row-polynomial
broadcast by $\mathsf{D}$ for $P_{j}$. It follows that
$f_{j}(\alpha_{i})=g_{i}(\alpha_{j})$ holds for every $P_{i}\in\mathcal{H}$,
where $g_{i}(y)$ is the degree-$t$ column polynomial held by $P_{i}$
(otherwise $P_{i}$ would have broadcast an accuse message against
$\mathsf{D}$). Now $g_{i}(y)={F}^{\star}(\alpha_{i},y)$ holds. Moreover, since
$|\mathcal{H}|\geq t+1$, the distinct points
$\\{(\alpha_{j},g_{i}(\alpha_{j}))\\}_{P_{i}\in\mathcal{H}}$ uniquely
determine the degree-$t$ polynomial ${F}^{\star}(x,\alpha_{j})$. This implies
that $f_{j}(x)={F}^{\star}(x,\alpha_{j})$, as two different degree-$t$
polynomials can have at most $t$ common points.

In the protocol, $\mathsf{D}$ sends two degree-$t$ polynomials to each party
and every pair of parties exchange $2$ common values, which requires a
communication of $\mathcal{O}(n^{2})$ field elements. There could be at most
$t$ parties corresponding to which $\mathsf{D}$ makes public their polynomials
and this requires a broadcast of $\mathcal{O}(n^{2})$ field elements. ∎

####  4.1.2 A $5$-round Version of
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$

Protocol $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ follows the “share-
complaint-resolve” paradigm, where $\mathsf{D}$ first distributes the
information on its bivariate polynomial, followed by parties complaining about
any “inconsistency”, which is followed by $\mathsf{D}$ resolving these
inconsistencies. At the end, either all (honest) parties held consistent
polynomials derived from a single degree-$(t,t)$ bivariate polynomial or
$\mathsf{D}$ is discarded. The “complaint” and “resolve” phases of
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ occupied five rounds. In
Gennaro, Ishai, Kushilevitz and Rabin [33], the authors proposed a round-
reducing technique, which collapses these phases to three rounds, thus
reducing the overall number of rounds to five. The modified protocol
$\mathsf{5BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ is presented in Fig 3.

The high level idea of $\mathsf{5BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ is as
follows. In $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, during the third
round, $P_{i}$ broadcasts only the identity of the parties with which it has a
dispute (through $L_{i}$), followed by $\mathsf{D}$ making the corresponding
disputed values public during Round IV, which is further followed by $P_{i}$
accusing $\mathsf{D}$ during Round V, if $P_{i}$ finds $\mathsf{D}$’s version
to mis-match with $P_{i}$’s version. Let us call $P_{i}$ to be unhappy, if it
accuses $\mathsf{D}$ during Round V. The round-reducing technique of [33]
enables to identify the set of unhappy parties $\mathcal{UH}$ by the end of
Round IV as follows. During Round III, apart from broadcasting the list of
disputed parties, party $P_{i}$ also makes public its version of the
corresponding disputed values. In response, both $\mathsf{D}$ and the
corresponding complainee party makes public their respective version of the
disputed value. Now based on whether $\mathsf{D}$’s version matches the
complainant’s version or complainee’s version, the parties can identify the
set $\mathcal{UH}$.

In $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, once $\mathcal{UH}$ is
identified, $\mathsf{D}$ makes public the polynomials of the parties in
$\mathcal{UH}$ during Round VI. And to verify if $\mathsf{D}$ made public the
correct polynomials, during Round VII, the parties not in $\mathcal{UH}$ raise
accusations against $\mathsf{D}$, if they find any inconsistency between the
polynomials held by them and the polynomials made public by $\mathsf{D}$. The
round-reducing technique of [33] collapses these two rounds into a single
round. Namely, once $\mathcal{UH}$ is decided, $\mathsf{D}$ makes public the
row-polynomials of these parties. In parallel, the parties not in
$\mathcal{UH}$ make public the corresponding supposedly common values on these
row-polynomials. Now to check if $\mathsf{D}$ broadcasted correct row-
polynomials, one just has to verify whether each broadcasted row-polynomial is
pair-wise consistent with at least $2t+1$ corresponding values, broadcasted by
the parties not in $\mathcal{UH}$.  $\bullet$ Round I — $\mathsf{D}$ picks
$F(x,y)$ as in $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ and distributes
$f_{i}(x),g_{i}(y)$ lying on $F(x,y)$ to each $P_{i}$. $\bullet$ Round II — As
in $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, each $P_{i}$ upon receiving
$f_{i}(x),g_{i}(y)$ from $\mathsf{D}$, sends $f_{ij}=f_{i}(\alpha_{j})$ to
$P_{j}$. $\bullet$ Round III — each party $P_{i}$ does the following:  – For
every $P_{j}\in\mathcal{P}$ where $f_{ji}\neq g_{i}(\alpha_{j})$, broadcast
$(\texttt{complaint},i,j,g_{i}(\alpha_{j}))$. $\bullet$ Round IV (making
disputed values public) — the dealer and each party $P_{j}$ does the
following:  – If $P_{i}$ broadcasts
$(\texttt{complaint},i,j,g_{i}(\alpha_{j}))$, then $\mathsf{D}$ and $P_{j}$
broadcasts $F(\alpha_{i},\alpha_{j})$ and $f_{j}(\alpha_{i})$ respectively.
$\bullet$ Local computation (deciding unhappy parties) — each party $P_{k}$
does the following:  – Initialize a set of unhappy parties $\mathcal{UH}$ to
$\emptyset$. – For every pair of parties $(P_{i},P_{j})$, such that $P_{i}$
has broadcast $(\texttt{complaint},i,j,g_{i}(\alpha_{j}))$, $\mathsf{D}$ has
broadcast $F(\alpha_{i},\alpha_{j})$ and $P_{j}$ has broadcast
$f_{j}(\alpha_{i})$, do the following.  – If $g_{i}(\alpha_{j})\neq
F(\alpha_{i},\alpha_{j})$, then include $P_{i}$ to $\mathcal{UH}$. – If
$f_{j}(\alpha_{i})\neq F(\alpha_{i},\alpha_{j})$, then include $P_{j}$ to
$\mathcal{UH}$. – If $|\mathcal{UH}|>t$, then discard $\mathsf{D}$. $\bullet$
Round V (resolving unhappy parties) — the dealer and each
$P_{j}\not\in\mathcal{UH}$ does the following:  – For every
$P_{i}\in\mathcal{UH}$, the dealer $\mathsf{D}$ broadcasts degree-$t$
polynomial $f_{i}(x)$. – For every $P_{i}\in\mathcal{UH}$, party $P_{j}$
broadcasts $g_{j}(\alpha_{i})$. $\bullet$ Output decision — each party $P_{k}$
does the following:  – If there exists any $P_{i}\in\mathcal{UH}$ for which
$\mathsf{D}$ broadcasts $f_{i}(x)$ and at most $2t$ parties
$P_{j}\not\in\mathcal{UH}$ broadcast $g_{j}(\alpha_{i})$ values where
$f_{i}(\alpha_{j})=g_{j}(\alpha_{i})$ holds, then discard $\mathsf{D}$. – Else
output the share $f_{k}(0)$.

Figure 3: A simplified $5$-round version of
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ due to Genarro, Ishai,
Kushilevitz and Rabin [33].

####  4.1.3 The $4$-round $\mathsf{4GIKR\mbox{-}VSS}$ Scheme

Genarro et al [33] proposed another round-reducing technique to reduce the
number of rounds of $\mathsf{5BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ by one. The
modified protocol $\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ is presented
in Fig 4. The idea is to ensure that the set $\mathcal{UH}$ is decided by the
end of Round III, even though this might look like an impossible task. This is
because $\mathcal{UH}$ can be decided during Round IV, only after the results
of pair-wise consistency checks are available during Round III. The key-
observation of [33] is that the parties can “initiate” the pair-wise
consistency checks from Round I itself. More specifically, every $P_{i},P_{j}$
exchange random pads privately during the Round I, independently of
$\mathsf{D}$’s distribution of the polynomials. During the second round,
$P_{i},P_{j}$ can then broadcast a masked version of the supposedly common
values on their polynomials, using the exchanged pads as the masks. If
$\mathsf{D},P_{i}$ and $P_{j}$ are honest, then the masked version of the
common values will be the same and nothing about the common values will be
learnt, as the corresponding masks will be private. By comparing the masked
versions of the common values, the parties publicly learn about the results of
pair-wise consistency checks by the end of the Round II.  $\bullet$ Round I
(sending polynomials and exchanging random pads) – $\mathsf{D}$ picks $F(x,y)$
as in $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ and distributes
$f_{i}(x),g_{i}(y)$ lying on $F(x,y)$ to each $P_{i}$. – Each
$P_{i}\in\mathcal{P}$ picks a random pad $r_{ij}\in\mathbb{F}$ corresponding
to every $P_{j}\in\mathcal{P}$ and sends $r_{ij}$ to $P_{j}$. $\bullet$ Round
II (broadcasting common values in a masked fashion) — each $P_{i}$ does the
following:  – Broadcast $a_{ij}\stackrel{{\scriptstyle
def}}{{=}}f_{i}(\alpha_{j})+r_{ij}$ and $b_{ij}\stackrel{{\scriptstyle
def}}{{=}}g_{i}(\alpha_{j})+r^{\prime}_{ji}$, where $r^{\prime}_{ji}$ is the
pad, received from $P_{j}$. $\bullet$ Round III (making disputed values
public) — for all $P_{i},P_{j}$ where $a_{ij}\neq b_{ji}$, party $P_{i},P_{j}$
and $\mathsf{D}$ does the following:  – $\mathsf{D}$ broadcasts
$F(\alpha_{j},\alpha_{i})$; $P_{i}$ broadcasts $f_{i}(\alpha_{j})$ and $P_{j}$
broadcasts $g_{j}(\alpha_{i})$. $\bullet$ Local computation (deciding unhappy
parties) — each party $P_{k}$ does the following:  – Initialize a set of
unhappy parties $\mathcal{UH}$ to $\emptyset$. For every $(P_{i},P_{j})$ where
$a_{ij}\neq b_{ji}$ and where $P_{i}$ has broadcast $f_{i}(\alpha_{j})$,
$\mathsf{D}$ has broadcast $F(\alpha_{j},\alpha_{i})$ and $P_{j}$ has
broadcast $g_{j}(\alpha_{i})$, do the following.  – If $f_{i}(\alpha_{j})\neq
F(\alpha_{j},\alpha_{i})$, then include $P_{i}$ to $\mathcal{UH}$. – If
$g_{j}(\alpha_{i})\neq F(\alpha_{j},\alpha_{i})$, then include $P_{j}$ to
$\mathcal{UH}$. – If $|\mathcal{UH}|>t$, then discard $\mathsf{D}$. $\bullet$
Round IV (resolving unhappy parties) — the dealer and each
$P_{j}\not\in\mathcal{UH}$ does the following:  – For every
$P_{i}\in\mathcal{UH}$, $\mathsf{D}$ broadcasts degree-$t$ polynomial
$f_{i}(x)$ and $P_{j}$ broadcasts $g_{j}(\alpha_{i})$. $\bullet$ Output
decision — each party $P_{k}$ does the following:  – If there exists any
$P_{i}\in\mathcal{UH}$ for which $\mathsf{D}$ broadcasts $f_{i}(x)$ and at
most $2t$ parties $P_{j}\not\in\mathcal{UH}$ broadcast $g_{j}(\alpha_{i})$
values where $f_{i}(\alpha_{j})=g_{j}(\alpha_{i})$ holds, then discard
$\mathsf{D}$. – Else output the share $f_{k}(0)$.

Figure 4: A $4$-round sharing phase protocol due to Genarro, Ishai,
Kushilevitz and Rabin [33].

####  4.1.4 The $3$-round $\mathsf{3GIKR\mbox{-}VSS}$ Scheme

We now present the $\mathsf{3GIKR\mbox{-}VSS}$ scheme from [33], which has a
round-optimal sharing phase, namely a 3-round sharing phase. However, the
protocol is inefficient, as it requires an exponential (in $n$ and $t$) amount
of computation and communication. The computations in
$\mathsf{3GIKR\mbox{-}VSS}$ scheme are done over a finite group
$(\mathbb{G},+)$. We first explain $t\mbox{-out-of-}n$ replicated secret-
sharing (RSS) [37]. Let $K\stackrel{{\scriptstyle def}}{{=}}{n\choose t}$ and
$A_{1},\ldots,A_{K}$ denote the set of all possible subsets of $\mathcal{P}$
of size $t$. For $k=1,\ldots,K$, let $\mathcal{G}_{k}=\mathcal{P}\setminus
A_{k}$. It is easy to see that in each $\mathcal{G}_{k}$, the majority of the
parties are honest. To share $s\in\mathbb{G}$, the share-generation algorithm
of RSS outputs $(v^{(1)},\ldots,v^{(K)})\in\mathbb{G}^{K}$, where
$v^{(1)},\ldots,v^{(K)}$ are random elements, such that
$v^{(1)}+\ldots+v^{(K)}=s$ holds. The share $s_{i}$ for $P_{i}$ is defined as
$s_{i}\stackrel{{\scriptstyle
def}}{{=}}\\{v^{(j)}\\}_{P_{i}\in\mathcal{G}_{j}}$. Any $t$-sized subset of
$(s_{1},\ldots,s_{n})$ will have at least one “missing” element from
$v^{(1)},\ldots,v^{(K)}$, say $v^{(l)}$, whose probability distribution will
be independent of $s$, thus ensuring privacy. On the other hand, any
$(t+1)$-sized subset of $(s_{1},\ldots,s_{n})$ will have all values
$v^{(1)},\ldots,v^{(K)}$ which can be added to reconstruct back $s$, thus
ensuring correctness. We say that $s\in\mathbb{G}$ is RSS-shared, if it is
secret-shared as per $t\mbox{-out-of-}n$ RSS. That is, if there exist
$v^{(1)},\ldots,v^{(K)}$ where $s=v^{(1)}+\ldots+v^{(K)}$, with all the
parties in $\mathcal{G}_{k}$ holding $v^{(k)}$.

Scheme $\mathsf{3GIKR\mbox{-}VSS}$ is presented in Fig 5. The sharing protocol
$\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ verifiably generates a
replicated secret-sharing of dealer’s secret, maintaining its privacy if
$\mathsf{D}$ is honest. The verifiability ensures that even if $\mathsf{D}$ is
corrupt, there exists some value which has been shared as per RSS by
$\mathsf{D}$. The reconstruction protocol
$\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Rec}$ allows the parties to
reconstruct the RSS-shared value of $\mathsf{D}$. During
$\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, $\mathsf{D}$ generates a
vector of values $(v^{(1)},\ldots,v^{(K)})$ as per the share-generation
algorithm of RSS and sends $v^{(k)}$ to all the parties in $\mathcal{G}_{k}$.
If $\mathsf{D}$ is honest, then this ensures the privacy of $s$. This is
because if $\mathsf{Adv}$ corrupts the parties in $A_{k}$, then it will not
know $v^{(k)}$. To ensure that a potentially corrupt $\mathsf{D}$ has
distributed the same $v_{k}$ to all the (honest) parties in $\mathcal{G}_{k}$,
each pair of parties in $\mathcal{G}_{k}$ privately exchange their respective
copies of $v^{(k)}$ and publicly raise a complaint if they find any
inconsistency. To resolve any complaint raised for $\mathcal{G}_{k}$,
$\mathsf{D}$ makes public the value $v^{(k)}$ for $\mathcal{G}_{k}$, thus
ensuring that all the parties in $\mathcal{G}_{k}$ have the same $v^{(k)}$.
Notice that this does not violate privacy, since if any inconsistency is
reported for $\mathcal{G}_{k}$, then either $\mathsf{D}$ is corrupt or
$\mathcal{G}_{k}$ consists of at least one corrupt party and so adversary
already knows $v^{(k)}$.

The above process will require four rounds, which can be collapsed to three,
based on the idea of pre-exchanging pair-wise random pads. During
$\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Rec}$, the goal of each $P_{i}$ is
to correctly obtain $v^{(1)},\ldots,v^{(K)}$. If $P_{i}\in\mathcal{G}_{k}$,
then it already has $v^{(k)}$. However, if $P_{i}\not\in\mathcal{G}_{k}$, then
every party in $\mathcal{G}_{k}$ sends $v^{(k)}$ to $P_{i}$, who applies the
majority rule to filter out the correct $v^{(k)}$.  Sharing Phase: Protocol
$\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ $\bullet$ Round I (distributing
shares and exchanging random pads): Let $K={n\choose t}$ and
$A_{1},\ldots,A_{K}$ denote the set of all possible subsets of $\mathcal{P}$
of size $t$ and let $\mathcal{G}_{k}=\mathcal{P}\setminus A_{k}$.  –
$\mathsf{D}$ on having the input $s\in\mathbb{G}$, randomly selects
$v^{(1)},\ldots,v^{(K)}\in\mathbb{G}$ such that $s=v^{(1)}+\ldots+v^{(K)}$
holds. It then sends $v^{(k)}$ to every party $P_{i}\in\mathcal{G}_{k}$, for
$k=1,\ldots,K$. – For $k=1,\ldots,K$, each $P_{i}\in\mathcal{G}_{k}$ sends a
randomly chosen pad $r^{(k)}_{ij}\in\mathbb{G}$ to every
$P_{j}\in\mathcal{G}_{k}$ where $i<j$. $\bullet$ Round II (pair-wise
consistency check within each group) – For $k=1,\ldots,K$, each pair of
parties $P_{i},P_{j}\in\mathcal{G}_{k}$ with $i<j$ do the following:  –
$P_{i}$ broadcasts $a^{(k)}_{ij}=v^{(k)}_{i}+r^{(k)}_{ij}$, where
$v^{(k)}_{i}$ denotes the version of $v^{(k)}$ received by $P_{i}$ from
$\mathsf{D}$. – $P_{j}$ broadcasts
$a^{(k)}_{ji}=v^{(k)}_{j}+r^{\prime(k)}_{ij}$, where $v^{(k)}_{j}$ denotes the
version of $v^{(k)}$ received by $P_{j}$ from $\mathsf{D}$ and
$r^{\prime(k)}_{ij}$ denotes the pad received by $P_{j}$ from $P_{i}$.
$\bullet$ Round III (resolving conflicts) – For $k=1,\ldots,K$, if there
exists $P_{i},P_{j}\in\mathcal{G}_{k}$ such that $a^{(k)}_{ij}\neq
a^{(k)}_{ji}$, then $\mathsf{D}$ broadcasts the value $v^{(k)}$. $\bullet$
Output determination — each party $P_{i}$ does the following:  – If $\exists
k\in\\{1,\ldots,K\\}$ where $P_{i}\in\mathcal{G}_{k}$ such that $\mathsf{D}$
broadcast $v^{(k)}$, then set $v^{(k)}_{i}$ to $v^{(k)}$. – Output the share
$s_{i}\stackrel{{\scriptstyle
def}}{{=}}\\{v^{(k)}_{i}\\}_{P_{i}\in\mathcal{G}_{k}}$.
Reconstruction Phase: Protocol $\mathsf{3GIKR\mbox{-}VSS}\mbox{-}\mathsf{Rec}$
Each party $P_{i}\in\mathcal{P}$ does the following:  – $\forall
k\in\\{1,\ldots,K\\}$, such that $P_{i}\in\mathcal{G}_{k}$, send $v^{(k)}_{i}$
to every party in $\mathcal{P}\setminus\mathcal{G}_{k}$. – $\forall
k\in\\{1,\ldots,K\\}$ where $P_{i}\not\in\mathcal{G}_{k}$, set $v^{(k)}$ to be
the value $v^{(k)}_{j}$ received from at least $t+1$ parties
$P_{j}\in\mathcal{G}_{k}$. – Output
$s=\displaystyle\sum_{\mathcal{G}_{k}:P_{i}\in\mathcal{G}_{k}}v^{(k)}_{i}+\displaystyle\sum_{\mathcal{G}_{k}:P_{i}\not\in\mathcal{G}_{k}}v^{(k)}$.

Figure 5: The $3$-round $\mathsf{3GIKR\mbox{-}VSS}$ scheme due to Genarro,
Ishai, Kushilevitz and Rabin [33].

####  4.1.5 The $3$-round $\mathsf{3FGGRS\mbox{-}VSS}$ Scheme

The $\mathsf{4GIKR\mbox{-}VSS}$ protocol comes closest in terms of the number
of rounds to obtain a round optimal and efficient VSS scheme. Round IV of
$\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ consists of $\mathsf{D}$ making
public the polynomials of the unhappy parties. Fitzi et al. [32] observed that
the elimination of Round IV results in a primitive that satisfies a weaker
commitment property, where the reconstructed value may be some predefined
default value, when the dealer is corrupt. This primitive is called weak
verifiable secret sharing (WSS) [54] and is used as a building block to
construct a VSS scheme. We next present the required background and the WSS
scheme of [32].

######  Definition 4.2 ($(n,t)$-WSS [54]).

Let $(\mathsf{Sh},\mathsf{Rec})$ be a pair of protocols where
$\mathsf{D}\in\mathcal{P}$ has a private input $s\in\mathcal{S}$ for
$\mathsf{Sh}$. Then $(\mathsf{Sh},\mathsf{Rec})$ is a perfectly-secure
$(n,t)$-WSS scheme, if the following hold.

  * –

Privacy and Correctness: Same as in VSS.

  * –

Weak Commitment: Even if $\mathsf{D}$ is corrupt, in any execution of
$\mathsf{Sh}$ the joint view of the honest parties defines a unique value
$s^{\star}\in\mathcal{S}$ (which could be different from $s$), such that each
honest party outputs either $s^{\star}$ or some default value $\perp$ at the
end of $\mathsf{Rec}$, irrespective of $\mathsf{Adv}$.

The WSS scheme $\mathsf{3FGGRS\mbox{-}WSS}$ of Fitzi et al. [32] is given in
Fig. 6. Protocol $\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ is the same
as $\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$, except that the parties do
not execute Round IV. Consequently, the parties in $\mathcal{UH}$ will not
posses their shares. Hence, during
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$, only the happy parties
(who are not in $\mathcal{UH}$) participate by broadcasting their respective
polynomials. To verify that correct polynomials are broadcasted, the pair-wise
consistency of these polynomials is checked. The polynomials which are not
found to be pair-wise consistent with “sufficiently many” polynomials are not
considered. If the parties are left with at least $n-t$ polynomials, then they
are used to reconstruct back $\mathsf{D}$’s committed Shamir-sharing
polynomial, else the parties output $\bot$. The idea is that if the parties
are left with $n-t$ polynomials, then they lie on the same degree-$(t,t)$
bivariate polynomial as committed by $\mathsf{D}$ to honest happy parties
during the sharing phase, as among these polynomials, at least $t+1$ belong to
the honest parties who are happy.

For an honest $\mathsf{D}$, no honest party will be in $\mathcal{UH}$ and
hence all honest parties will have their respective shares of $\mathsf{D}$’s
Shamir-sharing polynomial. Moreover, if any corrupt party produces an
incorrect polynomial during the reconstruction phase, then it will be ignored
due to the pair-wise consistency checks. Thus $\mathsf{3FGGRS\mbox{-}WSS}$
achieves the properties of a type-II VSS, for an honest $\mathsf{D}$. However
if $\mathsf{D}$ is corrupt, then up to $t$ honest parties may belong to
$\mathcal{UH}$. Moreover, during the reconstruction phase, even if a single
corrupt party produces incorrect polynomials, then the parties reconstruct
$\bot$. And this prevents $\mathsf{3FGGRS\mbox{-}WSS}$ from being a VSS
scheme.  Sharing Phase: Protocol
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ $\bullet$ The parties
execute the first $3$ rounds of
$\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$. Let $\mathcal{UH}$ be the set
of unhappy parties and let $\mathcal{W}\stackrel{{\scriptstyle
def}}{{=}}\mathcal{P}\setminus\mathcal{UH}$ be the set of happy parties. If
$|\mathcal{UH}|>t$, then discard $\mathsf{D}$.
Reconstruction Phase: Protocol
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$ $\bullet$ Revealing private
information: each $P_{i}\in\mathcal{W}$ broadcasts $f_{i}(x)$ and $g_{i}(y)$.
$\bullet$ Consistency check and output decision — each party $P_{i}$ does the
following: – Construct a consistency graph $G$ over the set of parties
$\mathcal{W}$ with an edge between $P_{j}$ and $P_{k}$ if and only if
$f_{j}(\alpha_{k})=g_{k}(\alpha_{j})$ and
$g_{j}(\alpha_{k})=f_{k}(\alpha_{j})$. – Remove $P_{j}$ from $G$, if it has
degree less than $n-t$ in $G$. Repeat till no more nodes can be removed from
$G$. Redefine $\mathcal{W}$ to be the set of parties, whose corresponding
nodes remain in $G$. – If $|\mathcal{W}|<n-t$ then output a default value
$\perp$. Else interpolate a degree-$t$ polynomial $q(\cdot)$ through the
points $\\{(\alpha_{j},f_{j}(0))\\}_{P_{j}\in\mathcal{W}}$ and output
$q(\cdot),s=q(0)$.

Figure 6: The 3-round $\mathsf{3FGGRS\mbox{-}WSS}$ scheme due to Fitzi, Garay,
Gollakota, Rangan and Srinathan [32].

##### Sharing and Reconstructing Polynomial Using $\mathsf{3FGGRS\mbox{-}WSS}$

One can interpret $\mathsf{D}$’s computation in
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ as if $\mathsf{D}$ wants to
share the degree-$t$ Shamir-sharing polynomial ${F}^{\star}(0,y)$. If
$\mathsf{D}$ is not discarded, then each (honest) $P_{j}\in\mathcal{W}$
receives the share ${F}^{\star}(0,\alpha_{j})$ from $\mathsf{D}$ through its
degree-$t$ row-polynomial ${F}^{\star}(x,\alpha_{j})$. Here ${F}^{\star}(x,y)$
is the degree-$(t,t)$ bivariate polynomial committed by $\mathsf{D}$ to the
honest parties in $\mathcal{W}$, which is the same as $F(x,y)$ for an honest
$\mathsf{D}$. If $\mathsf{D}$ is honest, then adversary learns at most $t$
shares lying on $F(0,y)$ and hence its view will be independent of $F(0,0)$.
Similarly, the computations during
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$ can be interpreted as if
the parties publicly try to reconstruct a degree-$t$ Shamir-sharing polynomial
${F}^{\star}$(0, y), which has been shared by $\mathsf{D}$ during
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$. If $\mathsf{D}$ is honest,
then the parties robustly reconstruct the shared polynomial. Else, the parties
either reconstruct the shared polynomial or output $\bot$. Hence we propose
the following notations for $\mathsf{3FGGRS\mbox{-}WSS}$, which later
simplifies the presentation of $\mathsf{3FGGRS\mbox{-}VSS}$.

######  Notation 4.3 (Notations for using $\mathsf{3FGGRS\mbox{-}WSS}$).

We use the following notations.

  * $\bullet$

We say that party $P_{j}\in\mathcal{P}$ shares a degree-$t$ polynomial
$r(\cdot)$ held by $P_{j}$, to denote that $P_{j}$ plays the role of
$\mathsf{D}$ and invokes an instance of
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ by selecting $r(\cdot)$ as
its Shamir-sharing polynomial and all the parties participate in this
instance.

  * $\bullet$

We say that $P_{i}$ receives a wss-share $r_{ji}$ from $P_{j}$, to denote that
in Round I of the $\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ instance
invoked by $P_{j}$, $P_{i}$ receives a degree-$t$ row-polynomial from $P_{j}$,
whose constant term is $r_{ji}$. If $P_{j}$ is not discarded during the
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ instance, then the wss-
shares $r_{ji}$ of all the honest parties in $\mathcal{W}$ lie on a unique
degree-$t$ Shamir-sharing polynomial held by $P_{j}$.

  * $\bullet$

Let $r(\cdot)$ be a degree-$t$ polynomial shared by $P_{j}$ through an
instance of $\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$. We say that the
parties try to reconstruct $P_{j}$’s shared polynomial, to denote that the
parties execute the corresponding instance of
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$, which either outputs
$r(\cdot)$ or $\bot$.

##### From WSS to VSS

The sharing-phase protocol of $\mathsf{3FGGRS\mbox{-}VSS}$ (see Fig. 7) is the
same as the first three rounds of
$\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$ with the following twist. The
random pads $r_{ji}$ used by $P_{j}$ to verify the pair-wise consistency of
its row-polynomial with the other parties’ column-polynomials are “tied
together” by letting these pads lie on a random degree-$t$ blinding-polynomial
$r_{j}(\cdot)$, which is shared by $P_{j}$ (see Notation 4.3). For pair-wise
consistency, $P_{j}$ makes public the polynomial $A_{j}(\cdot)$, which is a
masked version of its row-polynomial and its blinding-polynomial, while every
$P_{i}$ makes public the supposedly common value on its column-polynomial,
blinded with the wss-share of $P_{j}$’s blinding-polynomial. This new way of
performing pair-wise consistency checks achieves the same “goals” as earlier.
Moreover, privacy is maintained for an honest $\mathsf{D}$, as for every
honest $P_{j}$, the adversary obtains at most $t$ wss-shares of $P_{j}$’s
blinding-polynomial, which are randomly distributed. The set of happy parties
for the VSS is identified based on the results of pair-wise consistency and
conflict-resolutions, as done in
$\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$. Moreover, the parties also
ensure that for every happy party $P_{j}$ for the VSS, there is an overlap of
at least $n-t$ between the set of happy parties for the VSS and the set of
happy parties for $P_{j}$’s WSS-sharing instance. This is crucial for ensuring
the strong commitment property during the reconstruction phase.

Let ${F}^{\star}(x,y)$ be the degree-$(t,t)$ bivariate polynomial, committed
by $\mathsf{D}$ during the sharing phase. During the reconstruction phase,
instead of asking the happy parties to make their row-polynomials public, the
parties reconstruct their blinding-polynomials (by executing instances of
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$), which are then unmasked
from the corresponding $A_{j}(\cdot)$ polynomials to get back the row-
polynomials of the happy parties. For the honest happy parties $P_{j}$, robust
reconstruction of their blinding-polynomials is always guaranteed, thus
ensuring that their row-polynomials ${F}^{\star}(x,\alpha_{j})$ are robustly
reconstructed. If the reconstruction of $P_{j}$’s blinding-polynomial fails,
then $P_{j}$ is corrupt and hence can be safely discarded from consideration.
However, if $P_{j}$ is corrupt and the parties reconstruct a degree-$t$
polynomial during the corresponding
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$ instance, then the weak
commitment property of the WSS ensures that reconstructed polynomial is the
correct blinding-polynomial. Hence unmasking it from $A_{j}(\cdot)$ will
return back the row-polynomial ${F}^{\star}(x,\alpha_{j})$. This is because
there are at least $n-t$ parties, which belong to the happy set of both the
VSS instance, as well as $P_{j}$’s WSS instance. Among these $n-t$ common
happy-parties, at least $t+1$ are honest. And the wss-shares received by these
honest parties $P_{k}$ from $P_{j}$ uniquely define $P_{j}$’s blinding-
polynomial $r_{j}(\cdot)$, while evaluations of the column-polynomials of the
same honest-parties $P_{k}$ at $y=\alpha_{j}$ uniquely determine the
degree-$t$ row-polynomial ${F}^{\star}(x,\alpha_{j})$. Moreover, during the
sharing phase these honest parties $P_{k}$ collectively ensured that
$A_{j}(\cdot)={F}^{\star}(x,\alpha_{j})+r_{j}(\cdot)$ holds, as otherwise they
do not belong to the happy set of $P_{j}$’s WSS instance.

Sharing Phase: Protocol $\mathsf{3FGGRS\mbox{-}VSS}_{\mathsf{Sh}}$ $\bullet$
Round I (sending polynomials and exchanging random pads): – $\mathsf{D}$ picks
$F(x,y)$ and distributes $f_{i}(x),g_{i}(y)$ lying on $F(x,y)$ to each
$P_{i}$. – Each party $P_{i}\in\mathcal{P}$ (including $\mathsf{D}$) picks a
random degree-$t$ blinding-polynomial $r_{i}(\cdot)$ and shares it through an
instance $\mathsf{WSS}{-}\mathsf{Sh}_{i}$ of
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$. $\bullet$ Round II
(broadcasting common values in a masked fashion) — each $P_{i}$ does the
following: – Broadcast the degree-$t$ polynomial
$A_{i}(\cdot)\stackrel{{\scriptstyle def}}{{=}}f_{i}(x)+r_{i}(\cdot)$. –
Broadcast $b_{ij}\stackrel{{\scriptstyle
def}}{{=}}g_{i}(\alpha_{j})+r^{\prime}_{ji}$, where $r^{\prime}_{ji}$ denotes
the wss-share received from $P_{j}$ during $\mathsf{WSS}{-}\mathsf{Sh}_{j}$. –
For every $k\in\\{1,\ldots,n\\}$, concurrently execute Round II of the
instance $\mathsf{WSS}{-}\mathsf{Sh}_{k}$. $\bullet$ Round III:  – (making
disputed values public) — for all $P_{i},P_{j}$ where $A_{i}(\alpha_{j})\neq
b_{ji}$, dealer $\mathsf{D}$ broadcasts $F(\alpha_{j},\alpha_{i})$, party
$P_{i}$ broadcasts $f_{i}(\alpha_{j})$ and party $P_{j}$ broadcasts
$g_{j}(\alpha_{i})$. – For every $k\in\\{1,\ldots,n\\}$, the parties
concurrently execute Round III of the instance
$\mathsf{WSS}{-}\mathsf{Sh}_{k}$. $\bullet$ Local computation at the end of
Round III — each party $P_{k}$ does the following:  – Initialize a set
$\mathcal{UH}$ of unhappy parties. For every $P_{i},P_{j}$ where
$A_{i}(\alpha_{j})\neq b_{ji}$, do the following.  – Include
$P_{i}\in\mathcal{UH}$ (resp. $P_{j}\in\mathcal{UH}$), if
$F(\alpha_{j},\alpha_{i})\neq f_{i}(\alpha_{j})$ (resp.
$F(\alpha_{j},\alpha_{i})\neq g_{j}(\alpha_{i})$) holds. Let
$\mathcal{V}\stackrel{{\scriptstyle
def}}{{=}}\mathcal{P}\setminus\mathcal{UH}$ be the set of happy parties. – For
$j\in\\{1,\ldots,n\\}$, let $\mathcal{W}_{j}$ denote the set of happy parties
during the instance $\mathsf{WSS}{-}\mathsf{Sh}_{j}$. Remove $P_{i}$ from
$\mathcal{W}_{j}$, if during Round II, $A_{j}(\alpha_{i})\neq b_{ij}$ holds. –
For every $P_{j}\in\mathcal{V}$, if $|\mathcal{V}\cap\mathcal{W}_{j}|<n-t$,
then remove $P_{j}$ from $\mathcal{V}$. Repeat this step till no more parties
can be removed from $\mathcal{V}$. If $|\mathcal{V}|<n-t$, then discard
$\mathsf{D}$.
Reconstruction Phase: Protocol $\mathsf{3FGGRS\mbox{-}VSS}_{\mathsf{Rec}}$
$\bullet$ Reconstructing the blinding-polynomials:  – $\forall
P_{j}\in\mathcal{V}$, the parties try to reconstruct $P_{j}$’s blinding-
polynomial by participating in an instance $\mathsf{WSS}{-}\mathsf{Rec}_{j}$
of $\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Rec}}$. $P_{j}$ is removed from
$\mathcal{V}$ if $\bot$ is the output during
$\mathsf{WSS}{-}\mathsf{Rec}_{j}$. $\bullet$ Output decision — each party
$P_{i}$ does the following:  – For each $P_{j}\in\mathcal{V}$, compute
$f_{j}(x)=A_{j}(x)-r_{j}(\cdot)$, where $r_{j}(\cdot)$ is reconstructed during
$\mathsf{WSS}{-}\mathsf{Rec}_{j}$. Interpolate a degree-$t$ polynomial
$q(\cdot)$ through $\\{(\alpha_{j},f_{j}(0))\\}_{P_{j}\in\mathcal{V}}$. Output
$s=q(0)$.

Figure 7: The 3-round $\mathsf{3FGGRS\mbox{-}VSS}$ scheme due to Fitzi, Garay,
Gollakota, Rangan and Srinathan [32].

####  4.1.6 The $3$-round $\mathsf{3KKK\mbox{-}VSS}$ Scheme

The $\mathsf{3FGGRS\mbox{-}VSS}$ scheme is a Type-I VSS, because if
$\mathsf{D}$ is corrupt, then only the honest parties in $\mathcal{V}$ get
their shares. Moreover, it makes use of the broadcast channel during two of
the rounds of the sharing phase, which is not optimal (the optimal is one
round). The $\mathsf{3KKK\mbox{-}VSS}$ scheme due to Katz et al. [39]
rectifies both these problems.

The optimal broadcast-channel usage must first be rectified for
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}\mathsf{Sh}$. The modified construction
$\mathsf{3KKK\mbox{-}WSS}\mbox{-}\mathsf{Sh}$ (see Fig 8) is based on the
observation that during Round II of
$\mathsf{3FGGRS\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$ (which is the same as Round
II of $\mathsf{4GIKR\mbox{-}VSS}\mbox{-}\mathsf{Sh}$), there is no need to
publicly perform the pair-wise consistency checks over masked values. Instead,
parties can first privately perform the pair-wise consistency checks over
unmasked values and later publicly announce the results during the third
round. However, we also need to add a provision for the dealer to resolve any
potential conflicts during the third round itself. For this, during the second
round, every $P_{i},P_{j}$ privately exchange their supposedly common values
and also the random pads. Additionally, the pads are also “registered” with
the dealer. Later during the third round, upon a disagreement between $P_{i}$
and $P_{j}$, they broadcast their respective common values and their
respective random pads, else they broadcast their appropriately masked common
values. In parallel, dealer either broadcasts the common value in a masked
fashion if the pads it received from $P_{i},P_{j}$ are same, else it just
broadcasts the common value. The secrecy of the common values is maintained if
$P_{i}$, $P_{j}$ and the dealer are honest. On the other hand, if dealer is
corrupt and if there is a disagreement between honest $P_{i},P_{j}$ , then the
dealer can “take side” with at most one of them during the third round.

$\bullet$ Round I (sending polynomials and exchanging random pads): –
$\mathsf{D}$ distributes $f_{i}(x),g_{i}(y)$ lying on $F(x,y)$ to each
$P_{i}$. In parallel, each $P_{i}$ sends a random pad $r_{ij}$ to $P_{j}$ and
additionally the pad-list $\\{r_{ij}\\}_{P_{j}\in\mathcal{P}}$ to
$\mathsf{D}$. $\bullet$ Round II (exchanging common values and confirming pad)
— each $P_{i}$ does the following: – Send $a_{ij}=f_{i}(\alpha_{j})$ and
$b_{ij}=g_{i}(\alpha_{j})$ to $P_{j}$. – Send
$\\{r^{\prime}_{ji}\\}_{P_{j}\in\mathcal{P}}$ to $\mathsf{D}$, where
$r^{\prime}_{ji}$ denotes the pad received from $P_{j}$ during Round I.
$\bullet$ Round III (complaint and resolution) — each party $P_{i}$ does the
following:  – For $j\in\\{1,\ldots,n\\}$, let $a^{\prime}_{ji}$ and
$b^{\prime}_{ji}$ be the values received from $P_{j}$ during Round II.  – If
$b^{\prime}_{ji}\neq f_{i}(\alpha_{j})$, broadcast
$(j,\texttt{disagree}\mbox{-}\texttt{row},f_{i}(\alpha_{j}),r_{ij})$, else
broadcast $(j,\texttt{agree}\mbox{-}\texttt{row},f_{i}(\alpha_{j})+r_{ij})$. –
If $a^{\prime}_{ji}\neq g_{i}(\alpha_{j})$, broadcast
$(j,\texttt{disagree}\mbox{-}\texttt{column},g_{i}(\alpha_{j}),r^{\prime}_{ji})$,
else broadcast $(j,\texttt{agree}\mbox{-}\texttt{column},\allowbreak
g_{i}(\alpha_{j})+r^{\prime}_{ji})$. – If $P_{i}=\mathsf{D}$, then for every
ordered pair of parties $(P_{j},P_{k})$, additionally do the following.  – Let
$r_{jk}^{(1)}$ and $r_{jk}^{(2)}$ be the pads received from $P_{j}$ and
$P_{k}$ respectively during Round I and Round II. If $r_{jk}^{(1)}\neq
r_{jk}^{(2)}$, then broadcast $((j,k),\texttt{NEQ},F(\alpha_{k},\alpha_{j}))$,
else broadcast $((j,k),\texttt{EQ},F(\alpha_{k},\alpha_{j})+r_{jk}^{(1)})$.
$\bullet$ Local computation (identifying unhappy parties) — each party $P_{k}$
does the following:  – Initialize a set of unhappy parties $\mathcal{UH}$ to
$\emptyset$. For every $P_{i},P_{j}$ such that $P_{i}$ broadcasts
$(j,\texttt{disagree}\mbox{-}\texttt{row},\allowbreak
f_{i}(\alpha_{j}),r_{ij})$ and $P_{j}$ broadcasts
$(i,\texttt{disagree}\mbox{-}\texttt{column},g_{j}(\alpha_{j}),r^{\prime}_{ij})$
where $r_{ij}=r^{\prime}_{ij}$, do the following.  – Include $P_{i}$ to
$\mathcal{UH}$, if one of the following holds.  – During Round III,
$\mathsf{D}$ broadcasts $((i,j),\texttt{NEQ},d_{ij})$, such that $d_{ij}\neq
f_{i}(\alpha_{j})$. – During Round III, $\mathsf{D}$ broadcasts
$((i,j),\texttt{EQ},d_{ij})$, such that $d_{ij}\neq f_{i}(\alpha_{j})+r_{ij}$.
– Include $P_{j}$ to $\mathcal{UH}$, if one of the following holds.  – During
Round III, $\mathsf{D}$ broadcasts $((i,j),\texttt{NEQ},d_{ij})$, such that
$d_{ij}\neq g_{j}(\alpha_{i})$. – During Round III, $\mathsf{D}$ broadcasts
$((i,j),\texttt{EQ},d_{ij})$, such that $d_{ij}\neq
g_{j}(\alpha_{i})+r^{\prime}_{ij}$. – If $|\mathcal{UH}|>t$, then discard
$\mathsf{D}$. Else let $\mathcal{W}=\mathcal{P}\setminus\mathcal{UH}$ be the
set of happy parties.

Figure 8: The $3$-round $\mathsf{3KKK\mbox{-}WSS}\mbox{-}\mathsf{Sh}$ protocol
due to Katz, Koo and Kumaresan [39].

##### From $\mathsf{3KKK\mbox{-}WSS}$ to $\mathsf{3KKK\mbox{-}VSS}$

The notion of sharing and reconstructing degree-$t$ polynomials (as per
Notation 4.3) is applicable even for $\mathsf{3KKK\mbox{-}WSS}$. Replacing
$\mathsf{3FGGRS\mbox{-}WSS}$ with $\mathsf{3KKK\mbox{-}WSS}$ in the
$\mathsf{3FGGRS\mbox{-}VSS}$ readily provides a VSS scheme with the optimal
usage of the broadcast channel. However, the resultant VSS need not be of
Type-II if $\mathsf{D}$ is corrupt, as the unhappy honest parties may not get
their shares. Hence $\mathsf{3KKK\mbox{-}VSS}$ deploys an additional trick to
get rid of this problem.

Let $P_{i}$ be an unhappy party during
$\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ and let ${F}^{\star}(x,y)$
be $\mathsf{D}$’s committed bivariate polynomial. Note that each happy $P_{j}$
broadcasts a masking $A_{j}(\cdot)$ of ${F}^{\star}(x,\alpha_{j})$. If $P_{i}$
is happy in $\mathsf{WSS}{-}\mathsf{Sh}_{j}$, then $P_{i}$ can compute the
point ${F}^{\star}(\alpha_{i},\alpha_{j})$ on its supposedly column-polynomial
${F}^{\star}(\alpha_{i},y)$ by unmasking the wss-share $r^{\prime}_{ji}$
computed during $\mathsf{WSS}{-}\mathsf{Sh}_{j}$ from $A_{j}(\alpha_{i})$.
Hence if there is a set $\mathcal{SS}_{i}$ of at least $t+1$ happy parties
$P_{j}$, who keep $P_{i}$ happy during $\mathsf{WSS}{-}\mathsf{Sh}_{j}$
instances, then $P_{i}$ can compute $t+1$ distinct points on
${F}^{\star}(\alpha_{i},y)$ and hence get ${F}^{\star}(\alpha_{i},y)$.
However, it is not clear how to extend the above approach to enable $P_{i}$
obtain its row-polynomial ${F}^{\star}(x,\alpha_{i})$, which is required for
$P_{i}$ to obtain its share of $\mathsf{D}$’s Shamir-sharing polynomial
${F}^{\star}(0,y)$. The way-out is to let $\mathsf{D}$ use a symmetric
bivariate polynomial, which ensures that
${F}^{\star}(x,\alpha_{i})={F}^{\star}(\alpha_{i},y)$ holds.

The above idea requires broadcast during the second and third round. To ensure
the optimal usage of the broadcast channel, the technique used in
$\mathsf{3KKK\mbox{-}WSS}\mbox{-}\mathsf{Sh}$ is deployed, along with
postponing the broadcast of masked row-polynomials to the third round.
However, this brings additional challenges to filter out the parties from
$\mathcal{W}_{j}$ sets for the individual WSS instances. For example, a
corrupt $\mathsf{D}$ can distribute pair-wise inconsistent polynomials in such
a way that the masked polynomial $A_{j}(\cdot)$ broadcast by an honest happy
party $P_{j}$ is inconsistent with the corresponding masked value broadcast by
an honest unhappy party $P_{i}$, even though $P_{i}$ belongs to
$\mathcal{W}_{j}$ during $\mathsf{WSS}{-}\mathsf{Sh}_{j}$. Simply removing
$P_{i}$ from $\mathcal{W}_{j}$ in this case (as done in
$\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$) might end up resulting in
$P_{i}$ being removed from the $\mathcal{W}_{j}$ sets of every honest happy
party. And this may lead to $\mathcal{SS}_{i}$ set of size less than $t+1$. To
prevent this, apart from pair-wise consistency checks of masked row-
polynomials, the parties also carefully consider the results of private pair-
wise consistency checks performed during the second round, whose results are
public during the third round (see Fig. 9). We stress that even though each
party obtains a single polynomial from $\mathsf{D}$, it is treated both as row
as well as column-polynomial to perform the pair-wise consistency checks.
Accordingly, if $P_{i}$ finds a “negative” result for the private pair-wise
consistency check with $P_{j}$, then it broadcasts both disagree-row and
disagree-column messages against $P_{j}$. Else it broadcasts just an agree-
column message for $P_{j}$; the agree-row message for $P_{j}$ is assumed to be
implicitly present in the latter case. The reconstruction phase of
$\mathsf{3KKK\mbox{-}VSS}$ scheme is the same as $\mathsf{7BGW\mbox{-}VSS}$.

Sharing Phase: Protocol $\mathsf{3KKK\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$
$\bullet$ Round I (sending polynomials and exchanging random pads): –
$\mathsf{D}$ embeds its Shamir-sharing polynomial $q(\cdot)$ in a random
degree-$(t,t)$ symmetric bivariate polynomial $F(x,y)$ at $x=0$ and sends only
the row-polynomial $f_{i}(x)=F(x,\alpha_{i})$ to party $P_{i}$. – Each party
$P_{i}\in\mathcal{P}$ (including $\mathsf{D}$) picks a random degree-$t$
blinding polynomial $r_{i}(\cdot)$ and shares it through an instance
$\mathsf{WSS}{-}\mathsf{Sh}_{i}$ of
$\mathsf{3KKK\mbox{-}WSS}\mbox{-}{\mathsf{Sh}}$. In addition, $P_{i}$ sends
the polynomial $r_{i}(\cdot)$ to $\mathsf{D}$. $\bullet$ Round II (exchanging
common values and confirming pad) — each $P_{i}$ does the following: – For
$j=1,\ldots,n$, send $a_{ij}=f_{i}(\alpha_{j})$ to $P_{j}$. Send
$\\{r^{\prime}_{ji}\\}_{j=1,\ldots,n}$ to $\mathsf{D}$, where
$r^{\prime}_{ji}$ is the wss-share received from $P_{j}$ during Round I of
$\mathsf{WSS}{-}\mathsf{Sh}_{j}$. – For $j=1,\ldots,n$ execute Round II of the
instance $\mathsf{WSS}{-}\mathsf{Sh}_{j}$. $\bullet$ Round III (complaint and
resolution) — each party $P_{i}$ does the following:  – Broadcast the
degree-$t$ polynomial $A_{i}(\cdot)=f_{i}(x)+r_{i}(\cdot)$. – For
$j\in\\{1,\ldots,n\\}$, let $a^{\prime}_{ji}$ be the value received from
$P_{j}$ during Round II.  – If $a^{\prime}_{ji}\neq f_{i}(\alpha_{j})$, then
broadcast $(j,\texttt{disagree}\mbox{-}\texttt{row},f_{i}(\alpha_{j}),r_{ij})$
and
$(j,\texttt{disagree}\mbox{-}\texttt{column},f_{i}(\alpha_{j}),r^{\prime}_{ji})$.
– Else broadcast
$(j,\texttt{agree}\mbox{-}\texttt{column},f_{i}(\alpha_{j})+r^{\prime}_{ji})$.
– If $P_{i}=\mathsf{D}$, then for every ordered pair of parties
$(P_{j},P_{k})$, additionally do the following.  – Let $r_{jk}^{(1)}$ and
$r_{jk}^{(2)}$ be the pads received from $P_{j}$ and $P_{k}$ respectively
during Round I and Round II. If $r_{jk}^{(1)}\neq r_{jk}^{(2)}$, then
broadcast $((j,k),\texttt{NEQ},F(\alpha_{k},\alpha_{j}))$, else broadcast
$((j,k),\texttt{EQ},F(\alpha_{k},\alpha_{j})+r_{jk}^{(1)})$. – For every
$j\in\\{1,\ldots,n\\}$, concurrently execute Round III of
$\mathsf{WSS}{-}\mathsf{Sh}_{j}$. $\bullet$ Local computation at the end of
Round III — each party $P_{k}$ does the following:  – Initialize a set of
unhappy parties $\mathcal{UH}$ to $\emptyset$. For every $P_{i},P_{j}$ such
that $P_{i}$ broadcasts $(j,\texttt{disagree}\mbox{-}\texttt{row},\allowbreak
f_{i}(\alpha_{j}),r_{ij})$ and $P_{j}$ broadcasts
$(i,\texttt{disagree}\mbox{-}\texttt{column},f_{j}(\alpha_{i}),r^{\prime}_{ij})$
where $r_{ij}=r^{\prime}_{ij}$, do the following.  – Include $P_{i}$ to
$\mathcal{UH}$, if one of the following holds.  – During Round III,
$\mathsf{D}$ broadcasts $((i,j),\texttt{NEQ},d_{ij})$, such that $d_{ij}\neq
f_{i}(\alpha_{j})$. – During Round III, $\mathsf{D}$ broadcasts
$((i,j),\texttt{EQ},d_{ij})$, such that $d_{ij}\neq f_{i}(\alpha_{j})+r_{ij}$.
– Include $P_{j}$ to $\mathcal{UH}$, if one of the following holds.  – During
Round III, $\mathsf{D}$ broadcasts $((i,j),\texttt{NEQ},d_{ij})$, such that
$d_{ij}\neq f_{j}(\alpha_{i})$. – During Round III, $\mathsf{D}$ broadcasts
$((i,j),\texttt{EQ},d_{ij})$, such that $d_{ij}\neq
f_{j}(\alpha_{i})+r^{\prime}_{ij}$. – Let
$\mathcal{V}=\mathcal{P}\setminus\mathcal{UH}$ be the set of happy parties and
for every $P_{j}\in\mathcal{V}$, let $\mathcal{W}_{j}$ be the set of happy
parties during $\mathsf{WSS}{-}\mathsf{Sh}_{j}$. Remove $P_{j}$ from
$\mathcal{V}$, if any of the following holds:  – $|\mathcal{W}_{j}|<n-t$. –
$\exists i\in\\{1,\ldots,n\\}:P_{j}$ broadcasts
$(i,\texttt{disagree}\mbox{-}\texttt{row},f_{j}(\alpha_{i}),r_{ji})$ where
$A_{j}(\alpha_{i})\neq f_{j}(\alpha_{i})+r_{ji}$. – For every
$P_{j}\in\mathcal{V}$, remove $P_{i}$ from $\mathcal{W}_{j}$, if any of the
following holds.  – $P_{i}$ broadcasts
$(j,\texttt{agree}\mbox{-}\texttt{column},y)$ such that $A_{j}(\alpha_{i})\neq
y$. – $P_{j}$ broadcasts
$(i,\texttt{disagree}\mbox{-}\texttt{row},f_{j}(\alpha_{i}),r_{ji})$ and
$P_{i}$ broadcasts either $(j,\texttt{agree}\mbox{-}\texttt{column},\star)$ or
$(j,\allowbreak\texttt{disagree}\mbox{-}\texttt{column},\star,r^{\prime}_{ji})$,
where $r^{\prime}_{ji}\neq r_{ji}$. – Remove $P_{j}$ from $\mathcal{V}$ if
$|\mathcal{V}\cap\mathcal{W}_{j}|<n-t$. Repeat, till no more parties can be
removed from $\mathcal{V}$. – If $|\mathcal{V}|<n-t$, then discard
$\mathsf{D}$. $\bullet$ Computing shares — each party $P_{i}\in\mathcal{P}$
does the following:  – If $P_{i}\in\mathcal{V}$, then output the share
$f_{i}(0)$. Else recompute $f_{i}(x)$ as follows and output the share
$f_{i}(0)$.  – Add $P_{j}$ to $\mathcal{SS}_{i}$, if $P_{j}\in\mathcal{V}$ and
$P_{i}\in\mathcal{W}_{j}$. Interpolate
$\\{(\alpha_{j},A_{j}(\alpha_{i})-r^{\prime}_{ji})\\}_{P_{j}\in\mathcal{SS}_{i}}$
to compute $f_{i}(x)$.

Figure 9: The $3$-round sharing-phase protocol due to Katz, Koo and Kumaresan
[39].

####  4.1.7 The $3$-round $\mathsf{3AKP\mbox{-}VSS}$ Scheme

In Applebaum, Kachlon and Patra [3], it is shown that $4$ rounds are necessary
and sufficient for securely computing any $n$-party degree-$2$ functionality
with perfect security and optimal resilience of $t<n/3$. To design their
$4$-round MPC protocol, they rely on a $3$-round Type-II perfectly-secure VSS
which should ensure that if $\mathsf{D}$ is not discarded at the end of
sharing phase, then one of the following holds for every honest party $P_{i}$
at the end of Round II.

  * $\bullet$

$P_{i}$ holds its tentative Shamir-share of the underlying secret;

  * $\bullet$

$P_{i}$ holds at least $t+1$ tentative shares of its Shamir-share, which we
call as sub-shares.

Moreover, it is also required that at the end of Round III, either the
tentative share or the tentative sub-shares should turn out to be correct (the
exact case need not be known to $P_{i}$ at the end of Round II). The
$\mathsf{3FGGRS\mbox{-}VSS}$ does not satisfy the above requirements, as it is
not a Type-II VSS. The $\mathsf{3KKK\mbox{-}VSS}$ scheme also fails because if
$P_{i}\not\in\mathcal{V}$, then it obtains its sub-shares through
$\mathcal{SS}_{i}$ only at the end of Round III. Hence in Applebaum et al.
[3], a new 3-round VSS scheme (see Fig 10) is presented, satisfying the above
requirements. The scheme is obtained by tweaking the
$\mathsf{3FGGRS\mbox{-}VSS}$ scheme and by borrowing the idea of symmetric
bivariate polynomial from the $\mathsf{3KKK\mbox{-}VSS}$ scheme. The
reconstruction phase of the scheme is same as
$\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$.  Sharing Phase: Protocol
$\mathsf{3AKP\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ $\bullet$ Round I: Same as
Round I of $\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$, except that
$\mathsf{D}$ uses a random degree-$(t,t)$ symmetric bivariate polynomial
$F(x,y)$ and distributes only the row-polynomial $f_{i}(x)=F(x,\alpha_{i})$ to
every $P_{i}$. $\bullet$ Round II: Same as Round II of
$\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$, except that
$b_{ij}\stackrel{{\scriptstyle def}}{{=}}f_{i}(\alpha_{j})+r^{\prime}_{ji}$.
Moreover, every party $P_{i}$ sets $s_{i}\stackrel{{\scriptstyle
def}}{{=}}f_{i}(0)$ as its tentative Shamir-share and
$\\{A_{j}(\alpha_{i})-r^{\prime}_{ji}\\}_{P_{j}\in\mathcal{P}}$ as its
tentative sub-shares. $\bullet$ Round III: Same as Round III of
$\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$, except that for every
$P_{i},P_{j}$ where $A_{i}(\alpha_{j})\neq b_{ji}$, party $P_{i}$ broadcasts
$(f_{i}(\alpha_{j}),r_{ij})$, party $P_{j}$ broadcasts
$(f_{j}(\alpha_{i}),r^{\prime}_{ij})$ and $\mathsf{D}$ broadcasts
$F(\alpha_{j},\alpha_{i})$. $\bullet$ Local computation at the end of Round
III — each party $P_{k}$ does the following:  – Compute the sets
$\mathcal{UH}$ and $\mathcal{V}$ as in
$\mathsf{3FGGRS\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$, based on every
$P_{i},P_{j}$ for which $A_{i}(\alpha_{j})\neq b_{ji}$. – Remove $P_{i}$ from
$\mathcal{W}_{j}$, if $A_{j}(\alpha_{i})\neq b_{ij}$ during Round II and
$r_{ji}\neq r^{\prime}_{ji}$ during Round III. – Remove $P_{j}$ from
$\mathcal{V}$ if there exists some $i\in\\{1,\ldots,n\\}$, such that $P_{j}$
broadcasts $(f_{j}(\alpha_{i}),r_{ji})$ during Round III and
$A_{j}(\alpha_{i})\neq f_{j}(\alpha_{i})+r_{j}(\alpha_{i})$. – Remove $P_{j}$
from $\mathcal{V}$, if $|\mathcal{V}\cap\mathcal{W}_{j}|<n-t$. Repeat, till no
more parties can be removed from $\mathcal{V}$. If $|\mathcal{V}|<n-t$, then
discard $\mathsf{D}$. $\bullet$ Computing shares — each party
$P_{i}\in\mathcal{P}$: compute the shares as in the protocol
$\mathsf{3KKK\mbox{-}VSS}_{\mathsf{Sh}}$.

Figure 10: The $3$-round sharing-phase protocol due to Applebaum, Kachlon and
Patra [3].

###  4.2 VSS Scheme with $n>4t$

We present a perfectly-secure VSS scheme with $n>4t$ and a $2$-round sharing
phase due to Genarro et al. [33]. We first present a data structure called
$(n,t)$-$\mathsf{star}$ (which we often call as just $\mathsf{star}$).

######  Definition 4.4 ($(n,t)$-$\mathsf{star}$ [11]).

Let $G$ be an undirected graph over $\mathcal{P}$. Then a pair of subsets of
nodes $(\mathcal{C},\mathcal{D})$ where
$\mathcal{C}\subseteq\mathcal{D}\subseteq\mathcal{P}$ is called an
$(n,t)$-$\mathsf{star}$, if all the following hold.

  * –

$|\mathcal{C}|\geq n-2t$ and $|\mathcal{D}|\geq n-t$.

  * –

For every $P_{i}\in\mathcal{C}$ and every $P_{j}\in\mathcal{D}$, the edge
$(P_{i},P_{j})$ is present in $G$.

Ben-Or et al. [11] presents an efficient algorithm for checking the presence
of a $\mathsf{star}$. Whenever the input graph contains a clique of size at
least $n-t$, then the algorithm outputs a $\mathsf{star}$.

Protocol $\mathsf{2GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ is based on a
simplification of the asynchronous VSS scheme of Ben-Or et al. [11], adapted
to the synchronous setting (see Section 6.1). As done in the earlier
protocols, $\mathsf{D}$ distributes row and column-polynomials to the
respective parties. The goal is then to verify if the row and column-
polynomials of all (honest) parties are derived from a single degree-$(t,t)$
bivariate polynomial. However, since $n>4t$ (compared to $n>3t$ in the earlier
protocols), the above verification task is significantly simplified. For
simplicity, we first explain an inefficient verification, followed by the
actual efficient method used in the protocol.

Once the parties receive their respective polynomials, they perform the pair-
wise consistency checks (based on the idea of using random pads). The parties
next construct a consistency-graph $G$ over $\mathcal{P}$, where there exists
an edge between a pair of parties if no dispute is reported between them. The
parties next check for the presence of a clique of size $n-t$ in $G$, which is
bound to exist if $\mathsf{D}$ is honest. If no clique is obtained then
clearly $\mathsf{D}$ is corrupt and hence discarded. If a clique $\mathcal{C}$
of size $n-t$ is obtained, then the polynomials of the honest parties in
$\mathcal{C}$ are pair-wise consistent and lie on a single degree-$(t,t)$
bivariate polynomial, say ${F}^{\star}(x,y)$. However, there could be up to
$t$ (honest) parties outside $\mathcal{C}$ and the goal is to let each such
“outsider” $P_{i}\not\in\mathcal{C}$ obtain its degree-$t$ row-polynomial
${F}^{\star}(x,\alpha_{i})$. The crucial observation here is that since
$n>4t$, achieving this goal does not require any additional interaction. That
is, each $P_{i}\not\in\mathcal{C}$ considers the set of $n-t\geq 3t+1$
$g_{ji}$ values, received from the parties $P_{j}\in\mathcal{C}$ as part of
the pair-wise consistency test. Among these $g_{ji}$ values, at least $2t+1$
are sent by the honest parties $P_{j}\in\mathcal{C}$, which uniquely define
${F}^{\star}(x,\alpha_{i})$. Since ${F}^{\star}(x,\alpha_{i})$ is a degree-$t$
polynomial and there can be at most $t$ corrupt parties $P_{j}\in\mathcal{C}$
who may provide incorrect values of $g_{ji}$, party $P_{i}$ can error-correct
these values and obtain ${F}^{\star}(x,\alpha_{i})$.

The above method is inefficient, as finding a maximum-sized clique is an NP-
complete problem. Instead, the parties check for the presence of a
$\mathsf{star}$. If $\mathsf{D}$ is honest then the set of honest parties
constitute a potential clique of size $n-t$ in $G$ and so a $\mathsf{star}$ is
always obtained. If a $\mathsf{star}$ $(\mathcal{C},\mathcal{D})$ is obtained,
then there are at least $|\mathcal{C}|-t=t+1$ honest parties in $\mathcal{C}$
holding degree-$t$ row-polynomials and at least $|\mathcal{D}|-t=2t+1$ honest
parties in $\mathcal{D}$ holding degree-$t$ column-polynomials, which are
pair-wise consistent and hence lie on a single degree-$(t,t)$ bivariate
polynomial ${F}^{\star}(x,y)$. Any $P_{i}\not\in\mathcal{C}$ obtains its
corresponding row-polynomial ${F}^{\star}(x,\alpha_{i})$ by applying the
error-correction procedure as discussed above on the $g_{ji}$ values received
from $P_{j}\in\mathcal{D}$. Protocol
$\mathsf{2GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ is presented in Fig 11; the
reconstruction protocol $\mathsf{2GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Rec}}$ is
the same as $\mathsf{7BGW\mbox{-}VSS}\mbox{-}\mathsf{Rec}$.  $\bullet$ Round
I: $\mathsf{D}$ picks $F(x,y)$ and distributes $f_{i}(x),g_{i}(y)$ lying on
$F(x,y)$ to each $P_{i}$. In parallel, each $P_{i}$ sends a random mask
$r_{ij}$ to each $P_{j}$. $\bullet$ Round II: Each $P_{i}$ broadcasts
$a_{ij}=f_{i}(\alpha_{j})+r_{ij}$ and
$b_{ij}=g_{i}(\alpha_{j})+r^{\prime}_{ji}$, where $r^{\prime}_{ji}$ is the
pad, received from $P_{j}$. $\bullet$ Local computation at the end of round II
— each party $P_{i}$ does the following:  – Construct an undirected graph $G$
over $\mathcal{P}$, where the edge $(P_{l},P_{m})$ is present if
$a_{lm}=b_{ml}$ and $a_{ml}=b_{lm}$ holds. Run the $\mathsf{star}$-finding
algorithm over $G$. – If no $\mathsf{star}$ is obtained, then discard
$\mathsf{D}$. Else let $(\mathcal{C},\mathcal{D})$ be the $\mathsf{star}$
obtained in $G$.  – If $P_{i}\in\mathcal{C}$, then output the share
$f_{i}(0)$. – Else recompute the row-polynomial $f_{i}(x)$ as follows and
output the share $f_{i}(0)$.  – $\forall P_{j}\in\mathcal{D}$, compute
$g_{ji}=b_{ji}-r_{ij}$. Execute $\mathsf{RS}\mbox{-}\mathsf{Dec}(t,t,S_{i})$
to get $f_{i}(x)$, where $S_{i}\stackrel{{\scriptstyle
def}}{{=}}\\{g_{ji}\\}_{P_{j}\in\mathcal{D}}$.

Figure 11: The $2$-round $\mathsf{2GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$
protocol with $n>4t$ due to Genarro, Ishai, Kushilevitz and Rabin [33].

###  4.3 VSS Scheme with a Single Round

Genarro et al. [33] presented a VSS scheme (Fig 12) with $1$-round sharing-
phase, where $n=5$ and $t=1$. For simplicity, let $P_{1}$ be the dealer.
During the sharing phase, $P_{1}$ distributes Shamir-shares of its secret.
Since no additional rounds are available, the parties cannot verify whether
$\mathsf{D}$ has distributed consistent shares. In the reconstruction phase,
the dealer is not allowed to participate. The remaining parties exchange their
respective shares and try to error-correct one potential incorrect share. If
the error-correction is successful then the parties output the constant term
of the reconstructed degree-$1$ polynomial, else they output $\bot$. Since
there can be one corrupt party, there are two possible cases. If $P_{1}$ is
honest, then privacy is ensured and the shares of $P_{2},P_{3},P_{4}$ and
$P_{5}$ lie on a degree-$1$ polynomial. Hence during the reconstruction phase,
even if a potentially corrupt party provides incorrect share, it can be error-
corrected, thus guaranteeing the correctness property.

The case when $P_{1}$ is corrupt can be divided into three sub-cases. If
$P_{1}$ has distributed valid Shamir-shares (all lying on degree-$1$
polynomial), then the underlying Shamir-shared value will be reconstructed
correctly. The second sub-case is when $P_{1}$ has distributed valid Shamir-
shares to exactly three parties, say $P_{2},P_{3}$ and $P_{4}$, and let their
shares lie on a degree-$1$ polynomial ${q}^{\star}(\cdot)$. Hence during the
reconstruction phase, all honest parties reconstruct
$s^{\star}={q}^{\star}(0)$ by error-correcting the share provided by $P_{5}$.
The remaining sub-case is when the shares of no three parties among
$\\{P_{2},P_{3},P_{4},P_{5}\\}$ lie on a degree-$1$ polynomial. In this case
we define $s^{\star}\stackrel{{\scriptstyle def}}{{=}}\bot$, where
$\bot\not\in\mathbb{F}$, indicating that the sharing dealt by $P_{1}$ is
“invalid”. During the reconstruction phase, the error-correction will fail
(since the shares of no three parties lie on a degree-$1$ polynomial) and
hence the honest parties output $\bot$. Thus in all the $3$ sub-cases, strong
commitment property is achieved.  Sharing Phase: Protocol
$\mathsf{1GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ The dealer $P_{1}$ on having
input $s\in\mathbb{F}$, picks a random degree-$1$ polynomial $q(\cdot)$ over
$\mathbb{F}$ such that $q(0)=s$. For $i=2,\ldots,5$, it sends the share
$s_{i}=q(\alpha_{i})$ to $P_{i}$.
Reconstruction Phase: Protocol
$\mathsf{1GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Rec}}$ Each party
$P_{i}\in\\{P_{2},P_{3},P_{4},P_{5}\\}$ does the following:  $\bullet$ Send
$s_{i}$ to every $P_{j}\in\mathcal{P}\setminus\\{P_{1}\\}$. On receiving
$s_{j}$ from $P_{j}$, include $s_{j}$ in a list $W_{i}$. Execute
$\mathsf{RS}\mbox{-}\mathsf{Dec}(1,1,W_{i})$.  – If
$\mathsf{RS}\mbox{-}\mathsf{Dec}$ outputs a degree-$1$ polynomial $q(\cdot)$,
then output $q(0)$. Else output $\bot$.

Figure 12: The one round perfectly-secure VSS scheme of Genarro, Ishai,
Kushilevitz and Rabin [33].

Part III : Asynchronous Communication Setting

##  5 Preliminaries and Definitions

In the synchronous communication setting, each party knows in advance how long
it has to wait for an expected message, and if the message does not arrive
within that time-bound, then the sender party is corrupt. Unfortunately, it is
impossible to ensure such strict time-outs in real-world networks like the
Internet. Motivated by this, [11, 16] introduced the asynchronous
communication model with eventual message delivery. Apart from a better
modelling of real-world networks, asynchronous protocols have the advantage of
running at the actual speed of the underlying network. More specifically, for
a synchronous protocol, the participants have to pessimistically set the
global delay $\Delta$ to a large value to ensure that the messages sent by
every party at the beginning of a round reach their destination within time
$\Delta$. But if the actual delay $\delta$ is such that $\delta<<\Delta$, then
the protocol fails to take advantage of the faster network and its running
time will be proportional to $\Delta$.

In the asynchronous model, the messages can be arbitrarily, but finitely
delayed. The only guarantee is that any sent message is eventually delivered,
but probably in a different order. The sequence of message delivery is
controlled by a scheduler and to model the worst case scenario, we assume that
the scheduler is under the control of $\mathsf{Adv}$. Due to the lack of any
upper bound on the message delays, no party can wait to receive communication
from all its neighbours to avoid an endless wait (as a corrupt neighbour may
not send any message). As a result, a party can afford to wait for messages
from at most $n-t$ parties (including itself), thus ignoring communication
from $t$ potentially honest neighbours. Consequently, all synchronous VSS
protocols become insecure when executed in an asynchronous environment, as
they depend upon the fact that the messages of all the honest parties are
considered. Due to the absence of any global clock, the execution of any
asynchronous protocol is event-based, rather than round-based.

Informally, an AVSS scheme consists of an asynchronous sharing and an
asynchronous reconstruction phase, providing privacy, correctness and strong
commitment guarantees. However, we need these properties to hold eventually.
Additionally, we need termination guarantees. Namely, if $\mathsf{D}$ is
honest, then we require that these phases eventually terminate. On the other
hand, if $\mathsf{D}$ is corrupt, then the termination demands are “weaker”.
Namely, we require the honest parties to terminate the sharing and
reconstruction phase only if some honest party has terminated the sharing
phase. This models the fact that a potentially corrupt $\mathsf{D}$ may not
invoke the sharing phase in the first place (this is unlike synchronous VSS,
where protocols always terminate after a “finite” number of communication
rounds).

######  Definition 5.1 (Perfectly-Secure AVSS [16]).

Let $(\mathsf{Sh},\mathsf{Rec})$ be a pair of asynchronous protocols for the
$n$ parties, where a designated dealer $\mathsf{D}\in\mathcal{P}$ has a
private input $s$ for $\mathsf{Sh}$ and where each (honest) party who
completes $\mathsf{Sh}$, subsequently invokes $\mathsf{Rec}$, with its local
output of $\mathsf{Sh}$. Then $(\mathsf{Sh},\mathsf{Rec})$ constitute a
perfectly-secure AVSS scheme, if all the following holds for every possible
$\mathsf{Adv}$.

  * $\bullet$

Termination:

    * –

If $\mathsf{D}$ is honest, then every honest party will eventually complete
$\mathsf{Sh}$.

    * –

If some honest party has completed $\mathsf{Sh}$, then all honest parties will
eventually complete $\mathsf{Sh}$.

    * –

If some honest party has completed $\mathsf{Sh}$, then it will eventually
complete $\mathsf{Rec}$.

  * $\bullet$

Privacy and Correctness: Same as for synchronous VSS.

  * $\bullet$

Strong Commitment: If $\mathsf{D}$ is corrupt and some honest party completes
$\mathsf{Sh}$, then the joint view of the honest parties at the end of
$\mathsf{Sh}$ defines a value $s^{\star}$ (possibly different from $s$), such
that all honest parties eventually output $s^{\star}$ at the end of
$\mathsf{Rec}$.

We can have Type-I and Type-II AVSS schemes. All the existing perfectly-secure
AVSS schemes are of Type-II, where the secret is always shared as per the
Shamir’s secret-sharing scheme.

###  5.1 Asynchronous Tools

##### Asynchronous Reliable-Broadcast (ACast)

An ACast protocol allows a designated sender $\mathsf{S}\in\mathcal{P}$ to
identically send a message $m$ to all the parties. If $\mathsf{S}$ is honest,
then all honest parties eventually terminate with output $m$. While, if
$\mathsf{S}$ is corrupt and some honest party terminates with output
$m^{\star}$, then eventually every other honest party should terminate with
output $m^{\star}$. Hence the termination guarantees are “weaker” than
synchronous reliable-broadcast (RB), where the protocol always terminates,
irrespective of $\mathsf{S}$. Bracha [15] presented a very elegant
instantiation of ACast for any $n>3t$. We use the term $P_{i}$ broadcasts $m$
to mean that $P_{i}$ acts as $\mathsf{S}$ and invokes an instance of ACast
protocol to broadcast $m$. Similarly, the term $P_{j}$ receives $m$ from the
broadcast of $P_{i}$ means that $P_{j}$ completes the instance of ACast
protocol where $P_{i}$ is $\mathsf{S}$, with $m$ as output.

##### Online Error-Correction (OEC)

Let $s$ be $d$-shared among $\mathcal{P}^{\prime}\subseteq\mathcal{P}$ such
that $d<(|\mathcal{P}^{\prime}|-2t)$ holds. That is, there exists some
degree-$d$ polynomial $q(\cdot)$ with $q(0)=s$ and each
$P_{i}\in\mathcal{P}^{\prime}$ has a share $q(\alpha_{i})$. The goal is to
make some designated party, say $P_{R}$, reconstruct $s$ (actually OEC allows
$P_{R}$ to reconstruct $q(\cdot)$). In the synchronous setting, this is
achieved by letting every party in $\mathcal{P}^{\prime}$ to send its share to
$P_{R}$, who can apply the algorithm $\mathsf{RS}\mbox{-}\mathsf{Dec}$ and
error-correct up to $t$ potentially incorrect shares. Given that
$d<(|\mathcal{P}^{\prime}|-2t)$, the reconstruction will be robust. In the
asynchronous setting, achieving the same goal requires a bit of trick. The
intuition behind OEC is that $P_{R}$ keeps waiting till it receives $d+t+1$
shares, all of which lie on a unique degree-$d$ polynomial, which eventually
happens for $P_{R}$ (even if the corrupt parties in $\mathcal{P}^{\prime}$ do
not send their shares to $P_{R}$) as there are at least
$|\mathcal{P}^{\prime}|-t\geq d+t+1$ honest parties in $\mathcal{P}^{\prime}$.
This step requires $P_{R}$ to repeatedly apply
$\mathsf{RS}\mbox{-}\mathsf{Dec}$ and try recover $q(\cdot)$, upon
asynchronously receiving every new share from the parties in
$\mathcal{P}^{\prime}$. Once $P_{R}$ receives $d+1+1$ shares lying on a
degree-$d$ polynomial, say $q^{\prime}(\cdot)$, then
$q^{\prime}(\cdot)=q(\cdot)$. This is because among the $d+t+1$ shares, at
least $d+1$ are from the honest parties, which uniquely determine $q(\cdot)$.
We denote the OEC procedure by $\mathsf{OEC}(\mathcal{P}^{\prime},d)$.

##  6 Perfectly-Secure AVSS Schemes

We discuss the various perfectly-secure AVSS schemes [11, 50, 21]. While the
sharing phase requires $n>4t$, with the exception of [50] the reconstruction
phase requires $n>3t$. The necessity of the condition $n>4t$ follows from [13,
1], where it is shown that in any AVSS scheme designed with $n\leq 4t$, there
is a non-zero probability in the termination property. We summarize the AVSS
schemes in Table 2. While the degree of sharing $d$ is $t$ for [11, 21], the
degree $d$ could be more than $t$ for [50].

| Sharing Phase | Reconstruction Phase
---|---|---
Scheme | $n$ | $d$ | $L$ | $|\mathbb{F}|$ | Communication Complexity (CC) | $n$ | CC
$\mathsf{BCG\mbox{-}AVSS}$ [11] | $n>4t$ | $t$ | $1$ | $|\mathbb{F}|>n$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log n))$ | $n>3t$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|})$
$\mathsf{PCR\mbox{-}AVSS}$ [50] | $n>4t$ | $t<d<n-2t$ | $1$ | $|\mathbb{F}|>n$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log n))$ | $n>4t$ | $\mathcal{O}(n^{2}\log{|\mathbb{F}|})$
$\mathsf{CHP\mbox{-}AVSS}$ [21] | $n>4t$ | $t$ | $\geq n-3t$ | $|\mathbb{F}|>2n-3t$ | $\mathcal{O}(L\cdot n^{2}\log{|\mathbb{F}|}+\mathcal{BC}(n^{2}\log n))$ | $n>3t$ | $\mathcal{O}(L\cdot n^{2}\log{|\mathbb{F}|})$

Table 2: Summary of the perfectly-secure AVSS schemes. Here $L$ denotes the
number of values shared through a single AVSS instance and $\mathcal{BC}$
denotes the communication happening through ACast.

###  6.1 $\mathsf{BCG\mbox{-}AVSS}$ Scheme

The $\mathsf{BCG\mbox{-}AVSS}$ scheme is presented in Fig 13. The sharing
phase protocol $\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ is a slightly
modified and simplified version of the original protocol [11], based on the
simplifications suggested in [7, 50]. Protocol
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$ is similar to
$\mathsf{2GIKR\mbox{-}VSS}\mbox{-}{\mathsf{Sh}}$ (see Fig 11), executed in the
asynchronous setting. The protocol has four stages, each of which is executed
asynchronously.

During the first stage, $\mathsf{D}$ distributes the row and column-
polynomials to the respective parties. During the second stage, the parties
perform perform pair-wise consistency checks and publicly announce the
results, based on which parties build a consistency-graph. Since the results
of the consistency checks are broadcasted asynchronously, the consistency-
graph might be different for different parties (however, the edges which are
present in the graph of one honest party will be eventually included in the
graph of every other honest party). During the third stage, $\mathsf{D}$
checks for a $\mathsf{star}$ $(\mathcal{C},\mathcal{D})$ in its consistency-
graph, which it then broadcasts as a “proof” that the row-polynomials of the
(honest) parties in $\mathcal{C}$ and the column-polynomials of the (honest)
parties in $\mathcal{D}$ lie a single degree-$(t,t)$ bivariate polynomial,
which is considered as $\mathsf{D}$’s “committed” bivariate polynomial. A
party upon receiving $(\mathcal{C},\mathcal{D})$ from $\mathsf{D}$ accepts it,
when $(\mathcal{C},\mathcal{D})$ constitutes a $\mathsf{star}$ in its own
consistency-graph. Fo an honest $\mathsf{D}$, the set of honest parties
eventually constitute a clique and hence $\mathsf{D}$ eventually finds a
$\mathsf{star}$, which will be eventually accepted by every honest party.

Once a $\mathsf{star}$ is accepted by $P_{i}$ then in the last stage, its goal
is to compute its share, for which $P_{i}$ should hold its degree-$t$ row-
polynomial, lying on $\mathsf{D}$’s committed bivariate polynomial. If
$P_{i}\in\mathcal{C}$, then it already has this polynomial. Else, $P_{i}$
waits for the common values on the required row-polynomial from the parties in
$\mathcal{D}$ and error-corrects the incorrectly received values using OEC.
Since $P_{i}$’s desired row-polynomial has degree-$t$ and since each $P_{j}$
in $\mathcal{D}$ holds a share of this polynomial in the form of a common
value on its column-polynomial, OEC eventually outputs the desired row-
polynomial for $P_{i}$, as $|\mathcal{D}|\geq 3t+1$ and $\mathcal{D}$ contains
at most $t$ corrupt parties777For this step, it is necessary that $n>4t$. Else
$|\mathcal{D}|\leq 3t$ and OEC will fail to let $P_{i}$ obtain its desired
row-polynomial..

During reconstruction phase, every party sends its share to every other party.
The parties then reconstruct the secret by using OEC on the received shares
(this step will work even if $n>3t$).

Sharing Phase: Protocol $\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$
$\bullet$ Stage I : Distributing Polynomials — the dealer $\mathsf{D}$ does
the following – On having the input $s\in\mathbb{F}$, pick a random degree-$t$
Shamir-sharing polynomial $q(\cdot)$, such that $q(0)=s$ holds. Then pick a
random degree-$(t,t)$ bivariate polynomial $F(x,y)$, such that
$F(0,y)=q(\cdot)$ holds. – For $i=1,\ldots,n$, send the polynomials
$f_{i}(x)=F(x,\alpha_{i})$ and $g_{i}(y)=F(\alpha_{i},y)$. to $P_{i}$.
$\bullet$ Stage II : Pair-wise consistency checks and building consistency-
graph — each party $P_{i}$ – Upon receiving $f_{i}(x),g_{i}(y)$ from
$\mathsf{D}$, send $f_{ij}=f_{i}(\alpha_{j})$ and $g_{ij}=g_{i}(\alpha_{j})$
to $P_{j}$, for $j=1,\ldots,n$. – Upon receiving $f_{ji},g_{ji}$ from $P_{j}$,
broadcast $(\texttt{OK},i,j)$ if $f_{ji}=g_{i}(\alpha_{j})$ and
$g_{ji}=f_{i}(\alpha_{j})$ hold. – Construct a graph $G_{i}$ over
$\mathcal{P}$. Add the edge $(P_{j},P_{k})$ in $G_{i}$, if $(\texttt{OK},j,k)$
and $(\texttt{OK},k,j)$ are received from the broadcast of $P_{j}$ and $P_{k}$
respectively. Keep updating $G_{i}$, upon receiving new
$(\texttt{OK},\star,\star)$ messages. $\bullet$ Stage III : Finding
$\mathsf{star}$ in the consistency-graph — the dealer $\mathsf{D}$ does the
following – Let $G_{D}$ be the consistency-graph built by $\mathsf{D}$. After
every update in $G_{D}$, run the star-finding algorithm to check for the
presence of a $\mathsf{star}$ in $G_{D}$. If a $\mathsf{star}$
$(\mathcal{C},\mathcal{D})$ is found in $G_{D}$, then broadcast
$(\mathcal{C},\mathcal{D})$. $\bullet$ Stage IV : share computation — each
party $P_{i}$ does the following – If $(\mathcal{C},\mathcal{D})$ is received
from the broadcast of $\mathsf{D}$, then accept it if
$(\mathcal{C},\mathcal{D})$ is a $\mathsf{star}$ in the graph $G_{i}$. – If
$(\mathcal{C},\mathcal{D})$ is accepted, then compute the share $s_{i}$ as
follows and terminate.  – If $P_{i}\in\mathcal{C}$, then set $s_{i}=f_{i}(0)$,
where $f_{i}(x)$ is the degree-$t$ row-polynomial received from $\mathsf{D}$.
– Else initialize $W_{i}$ to $\emptyset$. Upon receiving $g_{ji}$ from
$P_{j}\in\mathcal{D}$, include $g_{ji}$ to $W_{i}$. Keep updating $W_{i}$ and
keep executing $\mathsf{OEC}(W_{i},t)$ till a degree-$t$ polynomial $f_{i}(x)$
is obtained. Then set $s_{i}=f_{i}(0)$.
Reconstruction Phase: Protocol
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}}$ Each party
$P_{i}\in\mathcal{P}$ does the following.  – Send the share $s_{i}$ to every
party $P_{j}\in\mathcal{P}$. – Initialize a set $R_{i}$ to $\emptyset$. Upon
receiving $s_{j}$ from $P_{j}$, include $s_{j}$ to $R_{i}$. Keep updating
$R_{i}$ and executing $\mathsf{OEC}(R_{i},t)$ till a degree-$t$ polynomial
$q(\cdot)$ is obtained. Then output $s=q(0)$ and terminate.

Figure 13: The perfectly-secure AVSS scheme of Ben-Or, Canetti and Goldreich
[11].

For the sake of completeness, we prove the properties of the scheme
$\mathsf{BCG\mbox{-}AVSS}$, as stated in Theorem 6.1. The proof for the
follow-up AVSS schemes also use similar arguments.

######  Theorem 6.1.

$(\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}},\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}})$
constitute a Type-II perfectly-secure AVSS scheme with respect to Shamir’s
$t\mbox{-out-of-}n$ secret-sharing scheme.

###### Proof.

Let us first consider an honest $\mathsf{D}$. The privacy simply follows from
the fact that during $\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$, the
adversary learns at most $t$ rows and column-polynomials, lying on $F(x,y)$.
If $\mathsf{D}$ is honest, then every pair of honest parties $P_{i},P_{j}$
eventually receive their respective polynomials and exchange the common points
on their polynomials. Since the pair-wise consistency test will pass, $P_{i}$
and $P_{j}$ eventually broadcasts $(\texttt{OK},i,j)$ and $(\texttt{OK},j,i)$
messages respectively and from the properties of ACast, these messages are
eventually delivered to every honest party. Since there are at least $n-t$
honest parties, the honest parties will eventually constitute a clique in
every honest party’s consistency graph. Consequently, $\mathsf{D}$ eventually
finds a $\mathsf{star}$ $(\mathcal{C},\mathcal{D})$ in its consistency graph
and broadcasts it, which is eventually delivered to every honest party.
Moreover, $(\mathcal{C},\mathcal{D})$ is eventually accepted by every honest
party, as $(\mathcal{C},\mathcal{D})$ eventually forms a $\mathsf{star}$ in
every honest party’s consistency graph. Now consider an arbitrary honest
$P_{i}$. If $P_{i}\in\mathcal{C}$, then it already has the polynomial
$f_{i}(x)$ and hence it outputs $f_{i}(0)$ as its share and terminates
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. On the other hand, even if
$P_{i}\not\in\mathcal{C}$, it eventually receives the common point on its row
polynomial from the honest parties in $\mathcal{D}$ as part of the pair-wise
consistency checks and hence by applying OEC, it eventually computes
$f_{i}(0)$ as its share and terminates
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Sh}}$. During
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}}$, the share of every honest
party is eventually delivered to every honest party. Consequently, by applying
OEC, every honest party eventually reconstructs $s$. This proves the
correctness property.

Next consider a corrupt $\mathsf{D}$ and let $P_{h}$ be the first honest party
to terminate $\mathsf{Sh}$. This implies that $P_{h}$ has received
$(\mathcal{C},\mathcal{D})$ from the broadcast of $\mathsf{D}$, which
constitutes a $\mathsf{star}$ in $P_{h}$’s consistency graph. From the
properties of ACast, every honest party will eventually receive and accept
$(\mathcal{C},\mathcal{D})$. This implies that the row-polynomials of the
honest parties in $\mathcal{C}$ and the column-polynomials of the honest
parties in $\mathcal{D}$ are pair-wise consistent and lie on a single
degree-$(t,t)$ bivariate polynomial, say $F^{\star}(x,y)$. Let
$q^{\star}(\cdot)=F^{\star}(0,y)$ and $s^{\star}=q^{\star}(0)$. Consider an
arbitrary honest $P_{i}$. If $P_{i}\in\mathcal{C}$, then it already has the
row-polynomial $F^{\star}(x,\alpha_{i})$ and hence it outputs
$F^{\star}(0,\alpha_{i})=q^{\star}(\alpha_{i})$ as its share of $s^{\star}$.
On the other hand, even if $P_{i}\not\in\mathcal{C}$, it eventually receives
the common point on its row polynomial from the honest parties in
$\mathcal{D}$ as part of the pair-wise consistency checks and hence by
applying OEC, it eventually computes $F^{\star}(0,\alpha_{i})$ as its share.
Moreover, it is easy to see that during
$\mathsf{BCG\mbox{-}AVSS}\mbox{-}{\mathsf{Rec}}$, every honest party
eventually outputs $s^{\star}$. This proves the strong commitment property. ∎

###  6.2 $\mathsf{PCR\mbox{-}AVSS}$ Scheme

Patra, Choudhury and Rangan [50] observed that the $\mathsf{BCG\mbox{-}AVSS}$
scheme can be modified in a non-trivial way to generate a $d$-sharing of
$\mathsf{D}$’s input in a verifiable fashion, for any given $d$ in the range
$t\leq d<n-2t$. The resultant scheme is presented in Fig 14. The main
motivation for an AVSS with the degree of sharing greater than $t$ is to get
efficient MPC protocols (see [28, 7, 8, 50]).