# Bivariate proximity test-based Asynchronous
Verifiable Secret Sharing

Daniel Augot<sup>2,1</sup>, Olivier Blazy<sup>1,2</sup>, Hugo Delavenne<sup>1,2</sup>, and Lola-Baie Mallordy<sup>1,2</sup>

<sup>1</sup> LIX, École Polytechnique, Institut Polytechnique de Paris

<sup>2</sup> Inria

**Abstract.** We present an Asynchronous Verifiable Secret Sharing (AVSS) protocol leveraging Interactive Oracle Proofs of Proximity (IOPPs). By integrating an IOPP to the product of Reed-Solomon codes i.e., to bi-variate polynomials, we achieve strong agreement properties while maintaining efficiency: our scheme achieves a total communication complexity of $O(n^2)$ for the dealer and $O(n \log^2(n))$ per party, and a computational complexity of only $O(n \log(n))$ per party. It provides *optimal resilience* i.e., is secure against up to $t < n/3$ corrupted parties. Furthermore, our construction is resistant against post-quantum adversaries, as its security relies solely on the security of the underlying hash functions.

**Keywords:** Hash-based, Verifiable Secret Sharing, Asynchronous, Coding Theory, Multivariate IOPP, Polynomial Commitment Scheme

# 1 Introduction

## 1.1 Secret Sharing

Secret sharing is a fundamental cryptographic primitive that enables a dealer to distribute shares of a secret among a set of participants in such a way that only authorized subsets can reconstruct it, while unauthorized subsets gain no information from their shares. Introduced by Shamir and Blakley in 1979 [Sha79, Bla79], secret sharing schemes have become a cornerstone of secure multiparty computation (MPC), threshold cryptography, and distributed trust protocols.

However, classical secret sharing assumes an honest dealer who correctly distributes the shares. In real-world applications, this assumption is often unrealistic. An adversarial dealer might distribute incorrect or inconsistent shares, leading to undetectable failures in later reconstruction. This limitation motivated the introduction of Verifiable Secret Sharing (VSS) by Chor et al in 1985 [CGMA85], which enhances secret sharing with a verification mechanism that ensures participants can detect and reject invalid shares before the reconstruction phase.

VSS is particularly crucial in adversarial settings, such as Byzantine fault-tolerant systems, secure distributed key generation, and blockchain protocols. A robust VSS scheme must satisfy two key properties: correctness, ensuring that honest participants can reconstruct the original secret, and verifiability,
guaranteeing that any misbehavior by the dealer or dishonest participants can be
detected and mitigated. Achieving these guarantees without hindering efficiency,
especially in the presence of a computationally unbounded adversary, remains
an active area of research.

It is also imperative to address the emerging challenges posed by advance-
ments in quantum computing. Quantum computers have the potential to break
many of the cryptographic schemes currently in use, rendering classical VSS
protocols vulnerable. In response to this threat, research has been directed to-
wards developing VSS schemes based on quantum-resistant assumptions. This
has been via post-quantum hypotheses like isogeny-based cryptography [EB22],
hybrid assumptions based on both discrete logarithm and lattice assumptions
like [GHL22]; or purely-based on symmetric key cryptography as in [CCG24]. In
this paper, we rather explore solutions which only rely on lightweight primitives
such as hash functions.

Asynchronous Verifiable Secret Sharing (AVSS) [BCG93] extends traditional
VSS to make it more suitable for the real-world setting where communication
is asynchronous, meaning there is not a global clock or guaranteed message de-
ivery within a fixed time. This model is particularly relevant in distributed
systems such as blockchain networks, secure multiparty computation (MPC),
and Byzantine fault-tolerant consensus protocols, where network delays and ad-
versarial interference can disrupt protocol execution. An AVSS protocol must
guarantee the additional properties that all honest parties obtain their shares
even if they do not receive the message from the dealer in time, and that they are
able to know when all honest parties have obtained their shares and are ready
for a successful secret reconstruction.

Some AVSS protocols rely on polynomial commitment schemes to ensure that
honest participants can verify their share consistency and correctly reconstruct
the secret. In the sharing phase, the dealer commits to the polynomial that it will
use in the sharing, using univariate [AVZ21] or bivariate [BDK13] polynomial
commitment schemes. The parties can then assert whether their share is a correct
evaluation of the committed polynomial. In this paper, we prove these kinds of
statements by using *Proofs of Proximity* to a code.

1.2 Interactive Oracle Proof of Proximity

An *Interactive Oracle Proof of Proximity* (IOPP) [BCS16] is a protocol between
a Prover and a Verifier in which the Prover aims to convince the Verifier that a
given word $f \in \mathbb{F}^n$ is $\delta$-close to a given code $C \subseteq \mathbb{F}^n$.

The Prover is given the word $f$ as input while the Verifier is only given oracle
access to $f$. That is, the Verifier can query any coordinate of $f$ without having
to read it entirely. During the protocol, the Prover can provide access to new
oracles to the Verifier. Several complexity measures are considered for IOPPs:

- the computational complexity of the Prover,

- the computational complexity of the Verifier,

- the round complexity (the number of rounds of interaction),
- the query complexity (the number of queries done by the Verifier), and

- the proof length (the sum of the length of the oracles).

An IOPP must satisfy two properties.

- Completeness: there exists an honest Prover such that if $f \in C$ then the
  Verifier accepts with probability 1,

- Soundness: for any Prover, if the distance between $f$ and $C$ is large enough, the Verifier accepts with probability bounded by a soundness parameter,

where the probabilities are taken over the Verifier's internal randomness.

We require the protocols to be public-coin in order to apply the Fiat-Shamir heuristic to turn them into non-interactive proofs [FS87,BCS16]. The oracles are implemented as Merkle trees. The Prover provides an oracle by sending the root of a Merkle tree to the Verifier. When the Verifier queries to open a coordinate, the Prover only has to open the corresponding branch of the Merkle tree.

We use in particular the Fast Reed-Solomon IOPP (FRI) [BBHR18] that tests proximity to Reed-Solomon codes, and its bivariate equivalent [ABN23], that tests proximity to tensor products of Reed-Solomon codes.

1.3 Contributions

We leverage existing IOPP protocols to obtain a new efficient IOPP-based AVSS
scheme. Let $n$ be the total number of parties $P_1, \dots, P_n$, and $t$ be the maximum
number of corrupted parties. Our protocol is secure when $n \ge 3t + 1$, which is
the optimal resilience for asynchronous schemes.

Following the standard bivariate AVSS construction, our dealer commits to a (t,t)-degree polynomial $\varphi(X,Y)$ such that $\varphi(0,0) = s$ the secret to be shared. It computes a bivariate IOPP [ABN23] on $\varphi(X,Y)$ and proves that its degree in both variables is not greater than $t$. Since this proximity proof is not zero-knowledge, the dealer samples another masking polynomial $r$ of degree at most $t$ in both variables, and proves the statement on a random linear combination $\psi := \varphi + ar$, where $\alpha$ is derived with a hash function from both $\varphi$ and $r$. The rest of the dealer operations are reduced to several univariate Merkle trees computations: its overall complexity comes from the evaluation of the bivariate polynomial $\psi$ in $n^2$ points, which is in $O(n^2 \log(n))$, assuming the underlying field is FFT-friendly.

Each party $P_i$'s share is a partial evaluation $\varphi(X, i)$ in one variable, which is verified with Merkle tree openings. This makes our protocol very efficient on each party $P_i$'s side, since a Merkle tree opening has logarithmic complexity. In the reconstruction phase, each party computes a proof of univariate polynomial evaluation on its share using the dealer's polynomial commitment, and sends it to the other parties. We reduce this proof to a univariate IOPP [BGKS20], which has a quasi linear complexity for the prover.

Using these techniques, our IOPP-based AVSS scheme enjoys the following
properties:
- **Efficiency:** our AVSS scheme has a state of the art dealer computational complexity of $O(n^2 \log(n))$, the same as Bingo [AJM$^+$23] and FRISS [ZLG$^+$24], and a better computational complexity per party of only $O(n \log(n))$. The only other scheme [YLF$^+$21] with such a complexity on a party's side relies on the q-SDH assumption, which is not post-quantum.

- **Strong Agreement:** We use a bivariate IOPP to ensure that, if the reconstruction phase succeeds, all of the honest parties reconstruct the same secret $\varphi(0, 0)$ where $\varphi$ is a polynomial of degree at most $t$ in both variables, without an honest dealer assumption. This is a stronger property than the agreement property that is proven in recent similar FRI-based AVSS protocols [ZLG$^+$24].

- **Lightweight:** We only use lightweight cryptographic primitives such as hash functions, which makes our protocol resistant against quantum adversaries. We prove our security in the *Random Oracle Model* (ROM). Additionally, we obtain better computational complexity than those requiring e.g. exponentiations or pairings.

## 1.4 Related Work

Asynchronous VSS schemes allow parties to both recover their share even if they do not receive the message from the dealer in time, and know when all honest parties obtain their shares and are ready for reconstruction. A common approach in asynchronous secret sharing is to send to each $P_i$ shares of every $P_j$'s share, and let them redistribute each shares of share to the corresponding party $P_j$. This way, a party does not only depend on the dealer to receive its share, but needs only $t+1$ messages out of the $n$ participants.

The eAVSS scheme [BDK13] was the first one with $O(n^2)$ global communication complexity, using Pedersen bivariate polynomial commitments which would not be secure against quantum adversaries. Their dealer complexity is in $O(n^3)$. More recent works also rely on Pedersen commitments [DXT$^+$23, LLS$^+$24]. The former [DXT$^+$23] uses only univariate polynomials, but their dealer needs to stay online until the sharing phase is over. The work of [AVZ21] also uses only univariate polynomials, but this yields a dealer complexity of $O(n^3)$.

The hbACSS scheme [YLF$^+$21] uses a *encrypt-then-disperse* strategy to obtain quasi linear communication complexity on the parties side. However, as Bingo [AJM$^+$23], they rely on pairings which does not provide security against a quantum adversary. The works of [SS24, CLL$^+$24] also use this approach, relying only on *lightweight* cryptography, however their communication complexity in the worst case is in $O(n^3)$. The recent work of [CP23] also yields a communication complexity of $O(n^3)$, and provides information-theoretic security.

Most recently, FRISS [ZLG$^+$24] also relies on code-based polynomial commitments. Their work has the same dealer complexity as ours, but they have a computational complexity of $O(n \log^2(n))$ per party, while we obtain a lower one. Unlike our present contribution, they do not prove the *Commitment* property introduced in [PCR09] i.e., that if the reconstruction phase succeeds, all honest parties reconstruct the same secret. The work of [BCI$^+$23] on IOPP for
Reed-Solomon codes also proposed an application to verifiable secret sharing. However, they do not work in the asynchronous setting: they do not achieve the property that if an honest user completes the sharing phase, then all honest users will achieve the sharing phase.

Other asynchronous schemes also were designed in the particular setting of proactive secret sharing [GDKK22, LRU22]. We summarize these comparisons in Table 1.

<table><caption>Table 1: A comparison of the computation (for the dealer and each party) complexities, communication overhead and security assumptions of existing AVSS protocol, for a number of $n$ parties. In our protocol, the dealer has a total communication complexity of $O(n^2)$ while each party only has one of $O(n \log^2(n))$.</caption><thead><tr><th></th><th>Dealer</th><th>Party</th><th>Comm.</th><th>Assumption</th></tr></thead><tbody><tr><td>eAVSS [BDK13]</td><td>O(n<sup>3</sup>)</td><td>O(n)</td><td>O(n<sup>2</sup>)</td><td>q-SDH</td></tr><tr><td>hbACSS [YLF+21]</td><td>O(n<sup>2</sup>)</td><td>O(n log(n))</td><td>O(n<sup>2</sup> log(n))</td><td>q-SDH</td></tr><tr><td>HAVEN-1 [AVZ21]</td><td>O(n<sup>3</sup>)</td><td>O(n)</td><td>O(n<sup>2</sup>)</td><td>q-SDH</td></tr><tr><td>Bingo [AJM+23]</td><td>O(n<sup>2</sup> log(n))</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>q-SDH</td></tr><tr><td>HAVEN-2 [AVZ21]</td><td>O(n<sup>3</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup> log(n))</td><td>DLog</td></tr><tr><td>FRISS [ZLG+24]</td><td>O(n<sup>2</sup> log(n))</td><td>O(n log<sup>2</sup>(n))</td><td>O(n<sup>2</sup> log(n))</td><td>ROM</td></tr><tr><td>Our Protocol</td><td>O(n<sup>2</sup> log(n))</td><td>O(n log(n))</td><td>O(n<sup>2</sup>)</td><td>ROM</td></tr></tbody></table>

# 2 Preliminaries

## 2.1 Polynomial Commitment schemes

A Merkle tree is a vector commitment scheme with linear prover time and logarithmic verifier time. In this paper, we use it to commit evaluations of polynomials $p$ in one or two variables, at $n$ points for $n > \deg(p)$ for univariate polynomials, or $n^2$ points for bivariate polynomials of $p$ is of degree less than $n$ in both variables.

**Definition 1 (Merkle Tree [Mer87]).** It consists of three different algorithms:

- MT Comitt ( $(p(x))_{x \in \mathcal{I}}$ ) $\rightarrow$ c: outputs the Merkle root for the vector of evaluations $(p(x))_{x \in \mathcal{I}}$, assuming that $|\mathcal{I}| > \deg(p)$.

- MT Open $(y, x, c) \rightarrow \pi$: outputs the path $\pi$ to the value $y = p(x)$ for the Merkle root $c$.

- MT Verif $(c, y, x, \pi) \rightarrow b \in \{0, 1\}$: Checks whether the path to the Merkle root $c$ is correct for the value $y = p(x)$.

If one wants to produce evaluation proofs $p(x) = y$ at any point $x \in \mathbb{F}$, they must use polynomial commitment schemes.

**Definition 2 (Polynomial Commitment [KZG10]).** A polynomial commitment scheme consists of the three following algorithms:

- PC Commit $(p) \rightarrow c$: outputs a commitment $c$ to the polynomial $p$.
- PC.Open(y, x, p, c) → π: outputs a proof π that y is a correct evaluation of p at x.

- PC.Verif(c, y, x, π) → b ∈ {0, 1}: Checks whether the proof π is correct for the value y at x for commitment c.

In our work, we use polynomial commitment schemes whose commit algorithm is a Merkle tree commitment, and then use it to produce more complex proofs.

## 2.2 Asynchronous Verifiable Secret Sharing

We denote by $[n]$ the set $\{1, \dots, n\}$.

A $(t, n)$-AVSS scheme consists of two different phases, the sharing phase and the reconstruction phase. In the first phase, the dealer executes the algorithm **Deal** to distribute shares of a secret $s$ to all $n$ parties $P_i$ for all $i \in [n]$. Then, the parties $P_i$ communicate with each other to obtain their share $s_i$, and complete the **GetShare** algorithm. In the reconstruction phase, the honest parties can execute **Recover** to reconstruct the secret $s$ provided that they know at least $t+1$ valid shares. The parties are connected by an asynchronous channel providing authenticity and privacy. We furthermore assume the dealer can broadcast messages to all parties by reliable broadcast.

We denote by **Hon** the set of honest parties, and by **Corr** the set of corrupted parties. We denote by $\mathbb{F}_{\le t}[X, Y]$ the set of polynomials of degree at most $t$ in both $X$ and $Y$.

**Definition 3 (Asynchronous Verifiable Secret Sharing [BCG93]).** Assume that no adversary can corrupt more than $t$ parties, and let $n > 3t$. A $(t, n)$-Asynchronous Verifiable Secret Sharing must verify the following properties:

- Correctness: If the dealer is honest, the reconstructed value is equal to the dealer's secret $s$.

- Liveness: If the dealer is honest, all the honest parties complete the **GetShare** algorithm.

- Agreement: If some $P_i \in \text{Hon}$ completes the **GetShare** algorithm, then all $P_j \in \text{Hon}$ will eventually complete the **GetShare** algorithm. Then if all $P_j \in \text{Hon}$ subsequently start the **Recover** protocol, they will all complete the **Recover** protocol.

- Strong Agreement (Commitment in [PCR09]): If the honest parties achieve the reconstruction phase, then they all reconstruct the same $\varphi(0, 0)$ with $\varphi \in \mathbb{F}_{\le t}[X, Y]$.

- Secrecy: If the dealer is honest, any PPT adversary $\mathcal{A}$ cannot distinguish between the sharing of two messages.

With the strong agreement property, we are ensured that there are only two scenarios possible: either none of the honest parties complete the sharing phase, or all the honest parties complete the sharing phase, and they all reconstruct the same $\varphi(0, 0)$ with $\varphi \in \mathbb{F}_{\le t}[X, Y]$.
## 2.3 IOPP-based low-degree commitment

We denote by $\Delta$ the relative Hamming distance.

**Definition 4 (Relative Hamming distance).** For $u, v \in \mathbb{F}^n$, denote $\Delta(u, v) := \frac{1}{n}\{|i \in [n] \mid u_i \neq v_i\}|$ the relative Hamming distance between $u$ and $v$. If $V \subseteq \mathbb{F}^n$, denote $\Delta(u, V) := \min_{v \in V}(\Delta(u, v))$.

We fix $n$ distinct values $x_1, \dots, x_n \in \mathbb{F}$. For $k < n \in \mathbb{N}$, denote by $\mathrm{RS}[n, k]$ the Reed-Solomon code $\{(f(x_1), \dots, f(x_n)) \mid f \in \mathbb{F}_{<k}[X]\}$, and denote by $\mathrm{RS}^2[n, k]$ the product $\mathrm{RS}[n, k] \otimes \mathrm{RS}[n, k]$.

Throughout the paper, whenever a word $f$ is at unique decoding distance from a Reed-Solomon code (resp. product of Reed-Solomon codes), we denote by $\tilde{f}$ the closest codeword. Recall that for the Reed-Solomon code $\mathrm{RS}[n, t+1]$, the unique decoding radius is $\frac{n-t-1}{2n}$, and for product of Reed-Solomon codes $\mathrm{RS}^2[n, t+1]$, the unique decoding radius is $\frac{(n-t)^2-1}{2n^2}$.

When $f = (f(x_i))_{i \in [n]}$ is a one-dimensional evaluation, we denote $\hat{f}(X)$ the lowest degree polynomial such that $\hat{f}(x_i) = f(x_i)$ for all $i \in [n]$. When $f = (f(x_i, x_j))_{i,j \in [n]}$ is a two-dimensional evaluation and $\Delta(f, \mathrm{RS}^2[n, t+1])$ is smaller than the unique decoding radius, we denote $\tilde{f}(X, Y) \in \mathbb{F}_{\le t}[X, Y]$ the polynomial such that $\tilde{f}(x_i, x_j) = \tilde{f}(x_i, x_j)$ for $i, j \in [n]$.

Fix $\delta_{\mathrm{Corr}} := \frac{(n-t)^2-1}{4n^2}$, $\delta_{\mathrm{BiFRI}} := \frac{(n-t)^2-1}{6n^2}$ and $\delta_{\mathrm{PC}} := \frac{n-t-1}{2n}$ the distance thresholds that we use throughout the paper.

# 3 Proximity tests

## 3.1 Proximity test to a linear combination

Since the FRI protocol, that we use for our proximity tests, leaks values of the word tested, we have to hide the values $\varphi$ by adding another random polynomial $r$. In order for the proximity test on the combination $\psi$ of $\varphi$ and $r$ to $\mathrm{RS}^2[n, t+1]$ to also prove proximity of $\varphi$ and $r$ to $\mathrm{RS}^2[n, t+1]$, we also require that this combination is a random linear combination $\psi := \varphi + \alpha r$, where $\alpha$ is given by the random oracle. As we show in Proposition 14, this masking technique does not leak any information on $\varphi$. The property that the proximity of $\psi$ also proves the proximity of $\varphi$ and $r$ with high probability on $\alpha$ is obtained by the correlated agreement from [BKS18], stated here in Lemma 1. Note that contrary to more regular uses of IOPP, we are here interested to prove proximity below the unique decoding radius and hence the soundness is lower than for instance [BKS18, Theorem 9].

**Lemma 1 (Correlated agreement for linear codes [BKS18, Lemma 8]).**

Let $C \subseteq \mathbb{F}^N$ be a linear code. Let $\delta < \frac{\Delta(C)}{2}$ and $\eta$ such that $\delta - \eta < \frac{\Delta(C)}{3}$. Let $u_1, u_2 \in \mathbb{F}^N$. If $\mathbb{P}_{\alpha \in \mathbb{F}}(\Delta(u_1 + \alpha u_2, C) < \delta - \eta) > \frac{1}{\eta|\mathbb{F}|}$ then $\Delta(u_1, C) \le \delta$ and $\Delta(u_2, C) \le \delta$.
Since $\delta_{\text{BiFRI}} < \frac{(n-t)^2-1}{3n^2}$ we can apply Lemma 1, with $C := \text{RS}^2[n, t+1]$, to obtain Corollary 1.

**Corollary 1 (Correlated agreement for product of Reed-Solomon codes).**

Let $\varphi, r : [n] \times [n] \to \mathbb{F}$. If

$$ \mathbb{P}_{\alpha \in \mathbb{F}} (\Delta(\varphi + \alpha r, \text{RS}^2[n, t+1]) < \delta_{\text{BiFRI}}) > \frac{1}{(\delta_{\text{Corr}} - \delta_{\text{BiFRI}})|\mathbb{F}|} = \frac{12n^2}{(n-t)^2|\mathbb{F}|} \quad (1) $$

then

$$ \begin{cases} \Delta(\varphi, \text{RS}^2[n, t+1]) \le \delta_{\text{Corr}} \\ \Delta(r, \text{RS}^2[n, t+1]) \le \delta_{\text{Corr}}. \end{cases} $$

## 3.2 Bivariate proximity testing to product of Reed-Solomon codes

We define the function ProximityProof that takes as argument a bivariate polynomial $\psi \in \mathbb{F}[X_1, X_2]$ and an integer $t$, and that outputs a SNARK proof $\pi$. This SNARK proof is obtained by applying the transformation to non-interactive random-oracle proof from [BCS16, Section 6] to the Interactive Oracle Proof defined in Definition 5.

**Definition 5 (Bivariate IOPP).**

**Prover input:** $\psi \in \mathbb{F}^{n \times n}$, $t \in \mathbb{N}$

**Verifier input:** oracle access to $\psi \in \mathbb{F}^{n \times n}$, $t \in \mathbb{N}$

**Claim:** $\Delta(\psi, \text{RS}^2[n, t+1]) < \delta_{\text{BiFRI}}$

- Prover and Verifier perform a bivariate FRI protocol defined in [ABN23, Section 7.3] to prove $\delta_{\text{BiFRI}}$-proximity of $\psi$ to $\text{RS}^2[n, t+1]$.

The protocol defined in Definition 5 has perfect completeness: if $\psi \in \text{RS}^2[n, t+1]$ then the Verifier accepts with probability 1.

**Proposition 1 (Bivariate FRI soundness [ABN23, Theorem 2]).** Let $\delta_{\text{BiFRI}}$ be defined as in Corollary 1. In the protocol defined in Definition 5, for any $0 < \eta < \delta_{\text{BiFRI}}$, if $\Delta(\psi, \text{RS}^2[n, t+1]) \ge \delta_{\text{BiFRI}}$, with $\mu_{\text{BiFRI}} \in \mathbb{N}$ a complexity parameter, the verifier accepts with probability at most

$$ \varepsilon_{\text{BiFRI}} := \frac{4 \log n}{\eta^2 |\mathbb{F}|} + (1 - \delta_{\text{BiFRI}} + 2\eta \log n)^{\mu_{\text{BiFRI}}}, $$

where the probability is taken over its internal randomness.

Our AVSS protocol also requires that the $\delta_{\text{BiFRI}}$-proximity of $\psi$ proves the $\delta_{\text{Corr}}$-proximity of $r$ to $\text{RS}^2[n, t+1]$. We state that soundness in Proposition 2.

**Proposition 2 (Correlated agreement and bivariate FRI soundness).**

Let $\varphi, r \in \mathbb{F}^{n \times n}$. Let $\alpha \in \mathbb{F}$ be given by a random oracle. Let $\psi := \varphi + \alpha r$. The probability that the Verifier accepts the proof defined in Definition 5 while

$$ \Delta(\varphi, \text{RS}^2[n, t+1]) > \delta_{\text{Corr}} \quad (2) $$
is at most

$$ \varepsilon_{\text{Corr}} := \varepsilon_{\text{BiFRI}} + \frac{12n^2}{(n-t)^2|\mathbb{F}|}, \qquad (3) $$

where the probability is taken over the Verifier's internal randomness and the random oracle for $\alpha$.

**Proof.** Let $A$ denote the event “the Verifier accepts the proof” and $B$ the event “$\Delta(\psi, \mathbb{RS}^2[n, t+1]) < \delta_{\text{BiFRI}}$”. Then by the law of total probability,

$$ \mathbb{P}(A) \le \mathbb{P}(B) + \mathbb{P}(A | \bar{B}). \qquad (4) $$

Since we assume eq. (2), by contrapositive of Corollary 1, we have that $\mathbb{P}(B) \le \frac{12n^2}{(n-t)^2|\mathbb{F}|}$. By Proposition 1, we have that $\mathbb{P}(A | \bar{B}) \le \varepsilon_{\text{BiFRI}}$. Combining these in eq. (4) gives eq. (3). $\square$

**Theorem 1 (Bivariate FRI complexity [ABN23, Theorem 2]).** The protocol defined in Definition 5, with the complexity parameter $\mu_{\text{BiFRI}}$ from Proposition 1, has the following complexity:

- Prover complexity: $< 8n^2$

- Verifier complexity: $< 24\mu_{\text{BiFRI}} \log n$

- Round complexity: $< \log n$

- Query complexity: $< 4\mu_{\text{BiFRI}} \log n + 1$

- Proof length: $< n^2/3$

Using [BCS16, Theorem 7.1], we can compute the length of the proof $\pi$ obtained after transforming this IOPP into a non-interactive proof of proximity.

**Proposition 3 (Length of the proof of proximity).** The non-interactive proof $\pi$ obtained from the IOPP defined in Definition 5 has length

$$ O(\mu_{\text{BiFRI}} \log^2 n). $$

## 3.3 Evaluation IOP

We define the functions PC.Open and PC.Verif from Definition 2 as a SNARK proof and the verification of that SNARK proof. The function PC.Open takes as argument a vector $f \in \mathbb{F}^n$, the root of a Merkle tree of the values $(f(x_i))_{i \in [n]}$ and a value $y \in \mathbb{F}$, and outputs a SNARK proof $\pi$. PC.Open is obtained by applying the transformation to a non-interactive random-oracle proof [BCS16, Section 6] on the Interactive Oracle Proof defined in Definition 6. The function PC.Verif takes as argument the root of a Merkle tree of values $(f(x_i))_{i \in [n]}$, a SNARK proof $\pi$ and a value $y \in \mathbb{F}$. PC.Verif is obtained by running the non-interactive verifier of the IOP defined in Definition 6.

In order to prove that $f(0) = y$, we prove instead that $f(X)-y$ can be divided by $X$ as a polynomial, since $f(0) = y$ if, and only if, there exists $g \in \mathbb{F}_{\le \deg f-1}[X]$ such that $f(X) - y = Xg(X)$.
**Proposition 4 (Reduction to proximity testing).** Let $\delta_{\text{PC}} \le \frac{n-t-1}{2n}$. Let $(f(x_i))_{i \in [n]} \in \mathbb{F}^n$ and $(g(x_i))_{i \in [n]} \in \mathbb{F}^n$. Let $y \in \mathbb{F}$. Assume that

$$ \Delta(f, \text{RS}[n, t+1]) < \delta_{\text{PC}} \qquad (5) $$

$$ \Delta(g, \text{RS}[n, t]) < \delta_{\text{PC}} \qquad (6) $$

$$ \mathbb{P}_{i \in [n]} (f(x_i) - y = x_i g(x_i)) > \frac{t}{n} + 2\delta_{\text{PC}}. \qquad (7) $$

Then

$$ \hat{\tilde{f}}(X) - y = X \hat{\tilde{g}}(X). \qquad (8) $$

*Proof.* The proof is done by contrapositive, by assuming eqs. (5) and (6) and that

$$ \hat{\tilde{f}}(X) - y \neq X \hat{\tilde{g}}(X) \qquad (9) $$

There exists $D_0, D_1 \subseteq [n]$ such that $|D_i| > (1 - \delta_{\text{PC}})n$ for $i = 0, 1$, and $(\tilde{\hat{f}}(x_j))_{j \in D_0} = (f(x_j))_{j \in D_0}$ and $(\tilde{\hat{g}}(x_j))_{j \in D_1} = (g(x_j))_{j \in D_1}$. Let $D := D_0 \cap D_1$. Then $|D| > (1 - 2\delta_{\text{PC}})n$. Note that

$$ \mathbb{P}_{j \in [n]} (f(x_j) - y = x_j g(x_j)) \le \mathbb{P}_{j \in [n]} (f(x_j) - y = x_j g(x_j) \text{ and } j \in D) + \mathbb{P}_{j \in [n]} (j \notin D). \qquad (10) $$

By eq. (9) and by the Schwartz-Zippel lemma [Sch80] we have

$$ \begin{aligned} \mathbb{P}_{j \in [n]} (f(x_j) - y = x_j g(x_j) \text{ and } j \in D) &= \mathbb{P}_{j \in [n]} (\tilde{\hat{f}}(x_j) - y = x_j \tilde{\hat{g}}(x_j) \text{ and } j \in D) \\ &\le \mathbb{P}_{j \in [n]} (\tilde{\hat{f}}(x_j) - y = x_j \tilde{\hat{g}}(x_j)) \\ &\le \frac{t}{n}. \end{aligned} \qquad (11) $$

Furthermore, since $|D| > (1 - 2\delta_{\text{PC}})n$, we have $\mathbb{P}(j \notin D) < 2\delta_{\text{PC}}$. Thus, by eqs. (10) and (11),

$$ \mathbb{P}_{j \in [n]} \left( \hat{\tilde{f}}(X) - y = X \hat{\tilde{g}}(X) \right) \le \frac{t}{n} + 2\delta_{\text{PC}}, $$

which concludes the proof.

□

We now define the IOP that proves this statement.

**Definition 6 (Proof of evaluation IOP).**

*Prover input:* $f \in \mathbb{F}^n, t \in \mathbb{N}, y \in \mathbb{F}$

*Verifier input:* oracle access to $f \in \mathbb{F}^n, t \in \mathbb{N}, y \in \mathbb{F}$

*Claim:* $\Delta(f, \text{RS}[n, t+1]) \le \delta_{\text{PC}}$ and $\hat{\tilde{f}}(0) = y$

– Prover provides an oracle access to $(g(x_i))_{i \in [n]}$ to Verifier
- Prover and Verifier perform a FRI protocol on $(f(x_i))_{i \in [n]}$ to prove $\delta_{PC}$-proximity to $RS[n, t+1]$.

- Prover and Verifier perform a FRI protocol on $(g(x_i))_{i \in [n]}$ to prove $\delta_{PC}$-proximity to $RS[n, t]$.

- Verifier chooses $\ell$ random values $i_1, ..., i_\ell \stackrel{\$}{\leftarrow} [n]$, and for $j = 1, ..., \ell$, Verifier queries $f(x_{i_j})$ and $g(x_{i_j})$, and checks that $f(x_{i_j}) - y = x_{i_j}g(x_{i_j})$.

In Proposition 5, we state the completeness of the protocol defined in Definition 6 in the case where $f \in RS[n, t+1]$.

**Proposition 5 (Proof of evaluation completeness).** If the claim of Definition 6 holds, then there exists a prover that makes the Verifier accept with probability 1.

*Proof.* Since $\deg \hat{f} < t+1$ and $\hat{f}(0) = y$, there exists a polynomial $\hat{g}$ of degree $\deg \hat{f}-1 < t$ such that $\hat{f}(X)-y = X\hat{g}(X)$. Hence the FRI protocol on $(\hat{g}(x_i))_{i \in [n]}$ to $RS[n, t]$ reaches perfect completeness, and for any $i \in [n]$, $f(x_i)-y = x_ig(x_i)$. Thus, the protocol has perfect completeness. $\square$

For the soundness, since our AVSS requires the unique decoding bound, we restate the FRI protocol soundness under the unique decoding bound, with $\delta_{PC} := \frac{n-t-1}{3n} < \frac{n-t-1}{2n}$.

**Theorem 2 (FRI soundness [BKS18, Lemma 8 and Theorem 16]).** If $\Delta(f, RS[n, t+1]) > \delta_{PC}$, with $\mu_{FRI}$ a complexity parameter, the verifier accepts with probability at most

$$ \varepsilon_{\text{FRI}} := \frac{\log n}{\eta|\mathbb{F}|} + (1 - \delta_{\text{PC}} + \eta \log n)^{\mu_{\text{FRI}}}. $$

**Proposition 6 (Proof of evaluation soundness).** The soundness of the IOP defined in Definition 6 is

$$ \varepsilon_{\text{PC}} := \max \left( \left( \frac{t}{n} + 2\delta_{\text{PC}} \right)^{\ell}, \varepsilon_{\text{FRI}} \right). \qquad (12) $$

*Proof.* Let $A$ denote the event “the Verifier accepts the proof” and $B$ the event “$\Delta(f, RS[n, t+1]) < \delta_{PC}$ and $\Delta(g, RS[n, t]) < \delta_{PC}$”. We have

$$ \mathbb{P}(A) \leq \max(\mathbb{P}(A | B), \mathbb{P}(A | \bar{B})). \qquad (13) $$

By Theorem 2, we have that

$$ \mathbb{P}(A | \bar{B}) \leq \varepsilon_{\text{FRI}}. \qquad (14) $$

If $B$ holds, then since the claim does not hold, we have that $\hat{f}(X)-y \neq X\hat{g}(X)$. Therefore, by contrapositive of Proposition 4, since eqs. (5) and (6) hold but
eq. (8) does not hold, we have that eq. (7) does not hold. Hence, using the notation of Definition 6, by independence,

$$ \mathbb{P}_{i_1, \dots, i_\ell \in [n]} \left( \bigcap_{i=1}^\ell f(x_{i_j}) - y = x_{i_j} g(x_{i_j}) \right) = \prod_{i=1}^\ell \mathbb{P}_{j_i \in [n]} (f(x_{i_j}) - y = x_{i_j} g(x_{i_j})) \\ \le \left( \frac{t}{n} + 2\delta_{\text{PC}} \right)^\ell. \qquad (15) $$

By combining eqs. (14) and (15) in eq. (13), we obtain eq. (12) as desired. □

As in Proposition 3, we use [BCS16, Theorem 7.1] to compute the length of the proof obtained after transforming this IOPP into a non-interactive random-oracle proof, in Proposition 8.

**Proposition 7 (FRI complexity [BBHR18, Theorem 2]).** The protocol defined in Definition 6, with the complexity parameter $\mu_{\text{FRI}}$ from Theorem 2, has the following complexity:

- Prover complexity: $< 6n$

- Verifier complexity: $< 21\mu_{\text{FRI}} \log n$

- Round complexity: $< \log n$

- Query complexity: $< 2\mu_{\text{FRI}} \log n$

- Proof length: $< n/3$

**Proposition 8 (Length of the proof of evaluation).** The non-interactive proof obtained from the IOPP defined in Definition 6 has length

$$ O(\mu_{\text{FRI}} \log^2 n + \ell). $$

## 3.4 Unicity of the secret

In order to prove that a malicious dealer cannot generate shares that would recover to different secrets, we prove that under the validity of the bivariate proximity proof, any $2t + 1$ honest parties would recover the same secret.

**Proposition 9 (Unique recovering).** Suppose that

$$ n = 3t + 1. \qquad (16) $$

Let $\varphi \in \mathbb{F}^{n \times n}$. Assume that

$$ \Delta(\varphi, \text{RS}^2[n, t+1]) \le \delta_{\text{Corr}}. \qquad (17) $$

For any $H \subseteq [n]$ of size $2t + 1$, one can construct in polynomial time from $(\varphi(x_i, x_j))_{(i,j) \in H \times [n]}$ a set $I = \{\ell_1, \dots, \ell_{t+1}\} \subseteq H$ of size $t + 1$ such that by denoting for $i, j \in [n]$, $f_i(x_j) := \varphi(x_i, x_j)$, we have

$$ \forall i \in I, \Delta((f_i(x_j))_{j \in [n]}, \text{RS}[n, t+1]) \le \frac{t}{n}, \qquad (18) $$
and furthermore, with $L_{\ell_1}^I(X), \dots, L_{\ell_{t+1}}^I(X)$ the degree $t$ polynomials such that for $i, j \in I$, $L_i(x_j) = 1$ if $i = j$ and $0$ otherwise, we have

$$ \hat{\tilde{\varphi}}(X, Y) = \sum_{i \in I} L_i(X) \hat{f}_i(Y). \qquad (19) $$

*Proof.* Let $H \subseteq [n]$ of size $2t+1$. By eq. (17), there exists $\tilde{\varphi} \in \mathbf{RS}^2[n, t+1]$ such that $\Delta(\tilde{\varphi}, \tilde{\hat{\varphi}}) \le \delta_{\text{Corr}}$. Let

$$ R := \{ (x_i, x_j) \in H \times [n] \mid \varphi(x_i, x_j) \neq \tilde{\varphi}(x_i, x_j) \}. $$

Then

$$ |R| \le \delta_{\text{Corr}} n^2. \qquad (20) $$

For $i \in H$, let $R_i := \{j \in [n] \mid (i, j) \in R\}$, and let $B := \{i \in H \mid |R_i| > t\}$. Then

$$ \bigsqcup_{i \in B} (\{i\} \times R_i) \subseteq R, $$

and therefore

$$ |R| \ge \sum_{i \in B} |R_i| \ge t|B|. \qquad (21) $$

Hence by eqs. (16), (20) and (21), and since $\delta_{\text{Corr}} \le \frac{1}{9}$,

$$ \begin{aligned} |B| &\le \frac{\delta_{\text{Corr}} n^2}{t} \\ &= \delta_{\text{Corr}} \frac{(3t+1)^2}{t} \\ &= 9\delta_{\text{Corr}}(t + 1/3 + 1/9t) \\ &< t + 1. \end{aligned} \qquad (22) $$

Since $|H| \ge 2t+1$, by eq. (22) we have $|H \setminus B| \ge t+1$.

By applying a decoding algorithm such as Berlekamp-Welch [WB86] to each element of $H$, it will succeed for $i \in H \setminus B$. Thus one can construct a set $I = \{\ell_1, \dots, \ell_{t+1}\} \subseteq H \setminus B$ of size $t+1$. For $i \in I$, since $\Delta(f_i, \mathbf{RS}[n, t+1]) \le \Delta(f_i, (\tilde{\varphi}(x_i, x_j))_{j \in [n]})$, we have that $f_i$ is at unique decoding radius from $\mathbf{RS}[n, t+1]$, and thus $\hat{f}_i$ is well-defined. Furthermore, we have $\hat{f}_i(Y) = \hat{\tilde{\varphi}}(x_i, Y)$.

By eq. (17), $\hat{\tilde{\varphi}}(X, Y) \in \mathbb{F}_{\le t}[X, Y]$ is well-defined. Since $L_{\ell_1}^I(X), \dots, L_{\ell_{t+1}}^I(X)$ is a basis of $\mathbb{F}_{\le t}[X]$, there exists polynomials $\hat{g}_{\ell_1}(Y), \dots, \hat{g}_{\ell_{t+1}}(Y) \in \mathbb{F}_{\le t}[Y]$ such that $\hat{\tilde{\varphi}}(X, Y) = \sum_{i \in I} L_i^I(X) \hat{g}_i(Y)$. For $i \in I$, we have $\hat{g}_i(Y) = \hat{\tilde{\varphi}}(x_i, Y) = \hat{f}_i(Y)$, and thus $\hat{\tilde{\varphi}}(X, Y) = \sum_{i \in I} L_i^I(X) \hat{f}_i(Y)$, which concludes the proof. $\square$
# 4 Asynchronous Verifiable Secret Sharing

## 4.1 Our AVSS protocol

Let $n$ be the number of parties $\{P_1, \dots, P_n\}$ and $t < n$ a given threshold. We assume that $n \ge 3t+1$, which is the optimal threshold for asynchronous schemes. Our construction is similar to eAVSS [BDK13], using code-based polynomial commitments instead of KZG [KZG10].

We detail the dealer algorithm in Figure 1 and the parties algorithms GetShare in Figure 2 and Recover in Figure 3. Let $H$ be a pseudorandom one-way hash function.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The dealer's algorithm Deal for our $(t, n)$-AVSS protocol, for a secret $s$.</figcaption></figure>

**Sharing phase – Dealer’s side.** The dealer samples a polynomial $\varphi \in \mathbb{F}_{\le t}[X, Y]$ such that $\varphi(0, 0) = s$. Since our ProximityProof is not zero-knowledge, the dealer samples another polynomial $r \leftarrow \mathbb{F}_{\le t}[X, Y]$ to perform the proof on the random linear relation $\psi = \varphi + \alpha r$ rather than on $\varphi$ itself. The dealer commits to both $r(x_i, Y)$ and $r(X, x_i)$ for $i \in [n]$, and also to $\varphi(X, Y)$ using Merkle trees. The coefficient $\alpha$ is chosen to be the hash of those trees, to prevent the dealer from manipulating this value. Then, the dealer computes the Merkle trees commitments $c_{\psi(X,x_i)}$, $c_{\psi(x_i,Y)}$ of each $\psi(X, x_i)$ and $\psi(x_i, Y)$ for $i \in [n]$, and derives the Merkle tree $c$ of $\psi$ from them by using each $c_{\psi(X,x_i)}$ as its subbranches. This is depicted
in Figure 4. The dealer broadcasts the proximity proof and all the commitments, and sends to each party $P_i$ their share $\{a_{i,j} = \varphi(x_i, x_j), b_{i,j} = r(x_i, x_j)\}_{j \in [n]}$.

<figure><img src="image_2.png" /><figcaption>Fig. 2: The GetShare algorithm for our $(t, n)$-AVSS protocol.</figcaption></figure>

**Sharing phase - Party's side.** Upon receiving its share, a party $P_i$ will first check its validity by verifying the proximity proof. If the proof is not valid, it will immediately abort the protocol. Otherwise, $P_i$ will compute the Merkle trees of its points $\{b_{i,j} = r(x_i, x_j)\}_{j \in [n]}$ and $\{w_{i,j} = a_{i,j} + \alpha b_{i,j} = \psi(x_i, x_j)\}_{j \in [n]}$. If the roots of the Merkle trees match the values $c_{r(x_i, Y)}$ and $c_{\psi(x_i, Y)}$ published by the dealer, and the commitment $c_\varphi$ opens with path $\pi_i$ to the points $\{a_{i,j}\}_{j \in [n]}$, the party $P_i$ is ensured that it received correct shares. In this case, it sets the dealer as honest with $hon_d \leftarrow 1$, and $P_i$ can relay these shares to the corresponding parties. It sends an Echo message to each $P_j$ containing the points $\{a_{i,j}, b_{i,j}\}$ along with the corresponding paths in the Merkle trees $c_{\psi(x_i, Y)}$ and $c_{r(x_i, Y)}$.

Finally, upon receiving an Echo message from another $P_j$, $P_i$ checks its validity using the received paths $\pi_{j,i}$ and $\pi'_{j,i}$ and the Merkle trees root $c_{r(x_j, Y)}$ and $c_{\psi(x_j, Y)}$ broadcast by the dealer. $P_i$ can send a Ready message under two conditions: either it already received more than $2t$ valid shares and the dealer is honest, or it already received $t+1$ Ready messages. When $P_i$ has received at least $2t+1$ Ready and at least $t+1$ Echo messages, it can obtain its share $(\varphi(X, x_i), r(X, x_i))$ by interpolating the points $\{a_{j,i}\}_j$ and $\{b_{j,i}\}_j$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: The Recover algorithm for our (t, n)-AVSS protocol.</figcaption></figure>

**Reconstruction phase.** Each $P_i$ sends to each $P_j$ an evaluation at 0 of their share polynomials $\varphi_i(X), r_i(X)$. If the dealer was honest in the sharing phase, $P_i$ sends a **Strong** label along with a proof of evaluation using the polynomial commitments $c_{r(X,x_i)}$ and $c_{\psi(X,x_i)}$, otherwise it sends a **Weak** label without any proof. To recover the secret, each party needs either $t+1$ strong shares to interpolate, or fewer strong shares completed with weak shares such that the secret can be recovered using Reed-Solomon decoding algorithms e.g., Berlekamp-Welch [WB86].

**Complexity.** In **Deal**, the dealer has to compute $n^2$ evaluations of the bivariate polynomials $\varphi(X, Y), r(X, Y)$, which as a complexity of $O(n^2 \log(n))$ with the Fast Fourier Transform. Using these evaluations, the dealer can compute the Merkle Trees of $r(X, x_i), r(x_i, Y)$ and $\varphi(X, Y)$ all in $O(n)$. Additionally, deriving the Merkle Tree of $\psi(X, x_i), \psi(x_i, Y)$, and then $\psi$ can also be done in linear time. The proximity proof has complexity $O(n^2)$ (c.f. Proposition 1). Hence, the total dealer complexity is in $O(n^2 \log(n))$. As for the communications, the dealer broadcast size is $(4n + 2)|H| + O(\log^2(n))$, with $|H|$ the size of the output of the hash function $H$. It sends $2n|\mathbb{F}| + \log(n)|H|$ bits to each party, with $|\mathbb{F}|$ the size of an element in $\mathbb{F}$.

In **GetShare**, each $P_i$ verifies the proximity check, with complexity $\log(n)$. They open the Merkle tree roots $c_{r(x_i, Y)}, c_{\psi(x_i, Y)}$ and $c_\varphi$ with their shares $\{b_{i,j}\}_{j \in [n]}, \{a_{i,j}\}_{j \in [n]}$ and the path $\pi_i$, which takes a linear complexity. They send the Merkle branches $\pi_{i,j}$ and $\pi'_{i,j}$ that they computed during the verifications in $c_{r(x_i, Y)}$ and $c_{\psi(x_i, Y)}$ to each party $P_j$. The Merkle tree verifications in step 14, which are repeated at most $n-1$ times, have a $O(\log(n))$ complexity. Thus each party's complexity in the dealing phase is bounded by $O(n \log(n))$. As for communications, each party sends a total of $2n|\mathbb{F}| + 2n \log(n)|H|$ bits.
In Recover, each party computes one proof of evaluation for its share, with complexity $O(n \log(n))$. It verifies less than $n$ other party's share, each of which has complexity $O(\log(n))$. Finally from Proposition 3 the proofs of evaluation have a size $O(\log^2(n))$, thus each party sends a total of $O(n \log^2(n))$ bits.

<figure><img src="image_4.png" /><figcaption>Fig. 4: The Merkle tree of $\psi(X, Y)$ computed by the dealer. The Merkle root $c$ is computed from the $n$ subbranches $c_{\psi(X,x_i)}$ for $i \in [n]$.</figcaption></figure>

## 4.2 Security analysis

We prove that our protocol achieves the correctness, liveness, agreement and secrecy properties. We consider the case where $n = 3t+1$ where $t$ is the maximum number of corrupted parties.

**Proposition 10 (Correctness).** If the dealer is honest, the reconstructed value is equal to the dealer's secret s under the assumption that the proof PC.Open is sound.

*Proof.* As the dealer is honest, the proximity proof is valid and all the commitments are consistent with the shares $\{a_{i,j} = \varphi(x_i, x_j), b_{i,j} = r(x_i, x_j)\}_{j \in [n]}$. Hence, all the $P_i \in \text{Hon}$ will send (Echo, $a_{i,j}$, $b_{i,j}$, $\pi_{i,j}$, $\pi'_{i,j}$) to each $P_j$. As the dealer is honest, each $P_i \in \text{Hon}$ party will receive at least $|\text{Hon}| \ge 2t+1$ valid shares with proofs consistent with the dealer's commitments, and will send a Ready message. Thus, all $P_i \in \text{Hon}$ are able to compute their share which is $(\varphi_i(X) = \varphi(X, x_i), r_i(X) = r(X, x_i))$.

In the reconstruction phase, the corrupted parties send at most $t$ out of $n$ wrong points for which they cannot forge false evaluation proofs consistent with the dealer's commitments under the soundness assumption of PC.Open. Hence, as the honest parties receive at least $2t+1$ valid points $\varphi(0, x_i)$, they are able to decode the same secret, which is $\varphi(0, 0)$. $\square$

**Proposition 11 (Liveness).** If the dealer is honest, all the honest parties complete the GetShare algorithm.
**Proof.** If the dealer is honest, then the proximity proof is valid and the commitments are consistent with the shares {$a_{i,j}, b_{i,j}$}$_{j \in [n]}$. Hence, all the $P_i \in \text{Hon}$ will send (Echo, $a_{i,j}, b_{i,j}$) to each $P_j$. Thus, each honest party will receive at least $|\text{Hon}| \ge 2t + 1$ correct shares, and will send a Ready message. Finally, each $P_i \in \text{Hon}$ will receive at least $2t + 1$ Ready messages and will be able to reconstruct $(\varphi(X, x_i), r(X, x_i))$, and complete the GetShare algorithm. □

**Proposition 12 (Agreement).** If some $P_i \in \text{Hon}$ completes the GetShare algorithm, then all $P_j \in \text{Hon}$ will eventually complete the GetShare algorithm. If all $P_j \in \text{Hon}$ subsequently start the Recover protocol, they will all complete the Recover protocol.

**Proof.** First, assume that $P_i \in \text{Hon}$ completes the GetShare algorithm. This means that $P_i$ received at least $2t + 1$ Ready messages, with at least $t + 1$ of them resulting from honest parties that sent valid $w_{i,j}$. If an honesty party that has not sent Ready receives $t + 1$ Ready messages, it will also send Ready. Thus, every honest party will eventually receive $2t + 1$ Ready messages.

If all $P_j \in \text{Hon}$ send Ready messages by step 19, that means that $t + 1$ Ready messages were sent by corrupted parties, which is impossible since $|\text{Corr}| \le t$. Hence, at least one honest party sent Ready by step 17, which means that at least $t + 1$ honest parties sent valid Echo messages. Hence, all honest parties will eventually complete GetShare.

Lastly, assume that all $P_j \in \text{Hon}$ start the Recover protocol. As we saw above, at least $t + 1$ honest parties sent valid Echo messages, hence at least $t + 1$ honest parties will send Strong recovery messages. Hence, eventually all honest parties will receive at least $t + 1$ valid Strong messages. Assume that the $t$ other honest parties only send valid Weak messages, each honest party will get

$$|S_{\text{Weak}}| + 2|S_{\text{Strong}}| \ge t + 2(t + 1) = 3t + 1,$$

thus all $P_i \in \text{Hon}$ will be able to recover its secret. □

**Proposition 13 (Strong Agreement).** If the honest parties achieve the reconstruction phase, then they all reconstruct the same $\tilde{\varphi}(0, 0)$ with $\tilde{\varphi} \in \mathbb{F}_{\le t}[X, Y]$ with probability

$$p_A \le t\varepsilon_{\text{FRI}} + \varepsilon_{\text{Corr}}$$

for $\varepsilon_{\text{PC}}$ the soundness of PC.Open and $\varepsilon_{\text{Corr}}$ the soundness of the correlated proximity proof from Proposition 6.

**Proof.** Assume that $\mathcal{A}$ breaks the strong agreement property of our scheme, we build a simulator $\mathcal{S}$ against the soundness of the proximity proof. Let $\varepsilon_{\text{PC}}$ be the soundness of the proof PC.Open as defined in Proposition 6.

First, the simulator receives a proximity proof $\pi$ and commitments from $\mathcal{A}$. Assuming that the proximity proof $\pi$ is correct, from Proposition 2 we know that $\varphi$ is also $\delta_{\text{Corr}}$-close to $\mathbb{RS}^2[n, t + 1]$.
Denote by $\mathcal{A}$ the event “some honest parties do not reconstruct $\hat{\tilde{\varphi}}(0, 0)$” and denote by $\mathcal{S}$ the event “there exists a malicious party that created a false proof $\pi_i$”. Then

$$p_A = \mathbb{P}(A) \le \mathbb{P}(S) + \mathbb{P}(A | \bar{S}). \qquad (23)$$

We assume now that in the reconstruction phase, $\mathcal{A}$ succeeds and sends corrupted shares such that the recovered secret is $s' \ne \hat{\tilde{\varphi}}(0, 0)$, while no malicious party could create a false proof $\pi_i$. Then by taking $H \subseteq [n]$ of size $2t + 1$ that contains the corrupted shares and by denoting $\tilde{\varphi}'(X, Y) := \sum_{i \in I} L_i^I(X) \hat{f}_i(Y)$ the polynomial reconstructed using Proposition 9, we have that $\tilde{\varphi}'(0, 0) \ne \hat{\tilde{\varphi}}(0, 0)$ and therefore $\tilde{\varphi}'(X, Y) \ne \hat{\tilde{\varphi}}(X, Y)$, which contradicts the fact that $\varphi$ is at unique decoding radius from $\mathrm{RS}^2[n, t+1]$. Therefore eq. (17) does not hold, the proof of proximity $\pi$ is false, and hence $\mathcal{A}$ managed to break the soundness of Proposition 2. Thus

$$\mathbb{P}(A | \bar{S}) \le \varepsilon_{\mathrm{Corr}}. \qquad (24)$$

By Proposition 6, we have

$$\mathbb{P}(S) \le t\varepsilon_{\mathrm{FRI}}. \qquad (25)$$

Combining eqs. (24) and (25) in eq. (23), it results that any adversary has a probability $p_A$ to break the strong agreement property bounded by $p_A \le t\varepsilon_{\mathrm{FRI}} + \varepsilon_{\mathrm{Corr}}$. $\square$

**Proposition 14 (Secrecy).** We model the hash function in the Merkle tree as a random oracle. Then, in the sharing phase, if the dealer is honest, any PPT adversary $\mathcal{A}$ can distinguish between the sharing of two messages with probability

$$p_A \le n_q / |\mathbb{F}|^{t+1},$$

where $n_q$ is the number of queries from $\mathcal{A}$ to the random oracle.

*Proof.* Let $\mathcal{C}$ be the challenger in the secrecy game. Let $(m_0, m_1)$ be the challenge that $\mathcal{C}$ receives from $\mathcal{A}$. The adversary wins if it can guess which message $m_b$ the challenger has shared, after the sharing phase is complete.

We modify the challenger in the following way. First, it samples $b \leftarrow \mathbb{F}\{0, 1\}$, $r \leftarrow \mathbb{F}_{\le t}[X, Y]$ and $(a_{i,j})_{j \in [n]} \leftarrow \mathrm{RS}[n, t+1]$ for each $i \in \mathrm{Corr}$. Then, $\mathcal{C}$ sets $\varphi$ to be the polynomial of degree $t$ such that $\varphi(x_i, x_j) = a_{i,j}$ for all $i \in \mathrm{Corr}, j \in [n]$ and $\varphi(0, 0) = m_b$. Using $\varphi$ and $r$, the simulator computes $c_{\varphi}, \{c_r(X, x_i), c_r(x_i, Y)\}_{i \in [n]}$ and $\{c_{\psi(x_i, Y)}\}_{i \in \mathrm{Corr}}$ honestly.

To prepare the Echo messages, $\mathcal{C}$ completes the set $(a_{j,i})_{j \in \mathrm{Corr}}$ with random values $(a_{j,i})_{j \in \mathrm{Hon}}$ for $i \in \mathrm{Corr}$ such that $(a_{j,i})_{j \in [n]} \in \mathrm{RS}[n, t+1]$. Due to the perfect secrecy of Shamir's secret sharing, these random points are indistinguishable from an honest sharing of $m_b$ since $\mathcal{A}$ only learns at most $t$ univariate polynomials $\varphi(X, x_i)$ and $\varphi(x_i, Y)$ for $i \in \mathrm{Corr}$, while $\varphi(X, Y)$ is of degree $t$ in both variables. From these points $(a_{i,j})_{i,j}$, the previously chosen $(b_{i,j})_{i,j}$ and
$\alpha = H(c_{r(x_1, Y)} || \dots || c_{r(x_n, Y)} || c_{\varphi})$, it derives the polynomial $\psi(X, Y)$. Then, $\mathcal{C}$ computes the rest of the Merkle trees $\{c_{\psi(x_i, Y)}\}_{i \in \text{Hon}}$, $\{c_{\psi(X, x_i)}\}_{i \in [n]}$, $c$ and the proximity proof $\pi$.

The challenger sends all the broadcast values $c, \pi, c_{\varphi}, \{c_r(X, x_i)\}_{i \in [n]}, c_{\psi(X, x_i)}, c_{\psi(x_i, Y)}\}_{i \in [n]}$ to the adversary. Then, it sends Echo message to the adversary with the shares $(a_{j,i}, b_{j,i})$ for $j \in \text{Hon}, i \in \text{Corr}$ and their corresponding Merkle paths.

If $\mathcal{A}$ can answer with a bit $b' = b$ with non-negligible probability, considering that all values except $c_{\varphi}$ were chosen independently of $m_b$, then $\mathcal{A}$ can distinguish between $c_{\varphi}$ and the output of a random function. However, $\mathcal{A}$ lacks at least $t+1$ points in $\mathbb{F}$ (i.e., at least one partial evaluation $\varphi(X, x_i)$ or $\varphi(x_i, Y)$) to entirely determine $\varphi(X, Y)$. Let $n_q$ be the number of queries of $\mathcal{A}$ to the random oracle, its probability to guess these points is $n_q/|\mathbb{F}|^{t+1}$. $\square$

## 4.3 Choice of complexity parameters

In order to fix the parameters of the IOPPs used as a function of the security parameter $\lambda$, we compute the overall soundness of our protocol in the random-oracle model.

If $\lambda \in \mathbb{N}$ is a security parameter, by Proposition 13, we can choose $\mathbb{F}, \mu_{\text{BiFRI}}, \ell$ and $\mu_{\text{FRI}}$ such that $t\varepsilon_{\text{PC}} + \varepsilon_{\text{Corr}} \le 2^{-\lambda}$. Hence we can choose these parameters such that $\varepsilon_{\text{PC}} \le \frac{1}{t}2^{-\lambda-1}$ and $\varepsilon_{\text{Corr}} \le 2^{-\lambda-1}$. By Proposition 2, we can choose $\mathbb{F}$ and $\mu_{\text{BiFRI}}$ such that

$$ \varepsilon_{\text{BiFRI}} + \frac{12n^2}{(n-t)^2|\mathbb{F}|} \le 2^{-\lambda-1}, $$

and by Proposition 6, we can choose $\mathbb{F}, \ell$ and $\mu_{\text{FRI}}$ such that

$$ \max \left( \left( \frac{t}{n} + 2\delta_{\text{PC}} \right)^{\ell}, \varepsilon_{\text{FRI}} \right) \le \frac{1}{t} 2^{-\lambda-1}. $$

Assume that $n = 3t + 1$. Let

$$ |\mathbb{F}| \ge \begin{cases} 5184 \log^3 n \cdot 2^{\lambda+3} & \approx \log^3 n \cdot 2^{\lambda+15.34} \\ 12t \log^2 n \cdot 2^{\lambda+2} & \approx t \log^2 n \cdot 2^{\lambda+5.58}. \end{cases} \quad (26) $$

- **Obtaining $\varepsilon_{\text{BiFRI}} \le 2^{-\lambda-2}$.** Since $t \ge 1$ we have $n \ge 4$ and therefore $2/27n + 8/27n^2 \le 1/27$. Hence $\delta_{\text{BiFRI}} = \frac{1}{2} \frac{(n-t)^2-1}{3n^2} = \frac{1}{2} \left( \frac{4}{27} - \frac{2}{27n} - \frac{8}{27n^2} \right) \ge \frac{1}{18}$. By Proposition 1 we have $\varepsilon_{\text{BiFRI}} = \frac{4\log n}{\eta^2|\mathbb{F}|} + (1 - \delta_{\text{BiFRI}} + 2\eta \log n)^{\mu_{\text{BiFRI}}}$. Let $\eta = 1/72 \log n$. By eq. (26), $|\mathbb{F}| \ge 5184 \log^3 n \cdot 2^{\lambda+3} \approx \log^3 n \cdot 2^{\lambda+15.34}$, therefore $\frac{4\log n}{\eta^2|\mathbb{F}|} \le 2^{-\lambda-3}$. We can choose $\mu_{\text{BiFRI}}$ such that $(17/18 + 2\eta \log n)^{\mu_{\text{BiFRI}}} \le 2^{-\lambda-3}$, i.e.

$$ \mu_{\text{BiFRI}} \ge \frac{\lambda + 3}{\log 36/35} \approx 24.6(\lambda + 3). \quad (27) $$

- **Obtaining $\frac{12n^2}{(n-t)^2|\mathbb{F}|} \le 2^{-\lambda-2}$.** By eq. (26), we have $|\mathbb{F}| \ge 27 \cdot 2^{\lambda+2}$. Therefore $\frac{12n^2}{(n-t)^2|\mathbb{F}|} = \frac{108}{4|\mathbb{F}|} \le \frac{27}{|\mathbb{F}|} \le 2^{-\lambda-2}$.
- Obtaining $(\frac{t}{n} + 2\delta_{\text{PC}})^{\ell} \le \frac{1}{t} 2^{-\lambda-1}$. Since $\delta_{\text{PC}} = \frac{n-t-1}{3n} < \frac{2n/3}{3n} = \frac{2}{9}$, we have $\frac{t}{n} + 2\delta_{\text{PC}} < \frac{1}{3} + \frac{4}{9} = \frac{7}{9}$. Therefore, we can choose $\ell$ such that $(\frac{7}{9})^{\ell} \le \frac{1}{t} 2^{-\lambda-1}$, i.e.

$$ \ell \ge \frac{\log t + 1}{\log 9/7} \approx 2.76(\lambda + \log t + 1). \qquad (28) $$

- Obtaining $\varepsilon_{\text{FRI}} \le \frac{1}{t} 2^{-\lambda-1}$. By Theorem 2 we have $\varepsilon_{\text{FRI}} = \frac{\log n}{\eta|\mathbb{F}|} + (1 - \delta_{\text{PC}} + \eta \log n)^{\mu_{\text{FRI}}}$. Let $\eta = 1/12 \log n$. By eq. (26), $|\mathbb{F}| \ge 12t \log^2 n \cdot 2^{\lambda+2}$ and therefore $\frac{\log n}{\eta|\mathbb{F}|} \le \frac{1}{t} 2^{-\lambda-2}$. Then we can choose $\mu_{\text{FRI}}$ such that $(11/12)^{\mu_{\text{FRI}}} \le \frac{1}{t} 2^{-\lambda-2}$, i.e.

$$ \mu_{\text{FRI}} \ge \frac{\log t + 2}{\log 12/11} \approx 8(\lambda + \log t + 2). \qquad (29) $$

For instance, the Goldilocks field $\mathbb{F}_p$ for $p = 2^{64} - 2^{32} + 1$ [Ham15] could be considered. It is FFT-friendly since it has $2^{32}$ distinct $2^{32}$-th roots of unity, hence allowing to use the FRI up to $t \le 2^{32}$. By plugging $t = 2^{32}$ in eq. (26), we get that taking a degree 3 extension of $\mathbb{F}_p$ suffices to achieve a security parameter $\lambda = 128$ even far beyond $n = 2^{64}$. Achieving 256 bits of security would require a degree 5 extension of $\mathbb{F}_p$ for a similar range of parameters $n$ and $t$.

# 5 Conclusion

The AVSS protocol we propose achieves both low complexity parameters and strong post-quantum security thanks to the proximity test to products of Reed-Solomon codes. Lower complexity parameters could be achieved by using a correlated agreement (Corollary 1) under the unique decoding radius that is more specific to products of Reed-Solomon codes, like the one for univariate Reed-Solomon codes from [BCI+23, Lemma 4.2].

# References

ABN23. Daniel Augot, Sarah Bordage, and Jade Nardi. Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes. *Designs, Codes and Cryptography*, 91(3):1111–1151, 2023.

AJM+23. Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, and Gilad Stern. Bingo: Adaptivity and asynchrony in verifiable secret sharing and distributed key generation. In *Helena Handschuh and Anna Lysanskaya, editors, CRYPTO 2023, Part I*, volume 14081 of LNCS, pages 39–70. Springer, Cham, August 2023.

AVZ21. Nicolas Alhaddad, Mayank Varia, and Haibin Zhang. High-threshold avss with optimal communication complexity. In *Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part II 25*, pages 479–498. Springer, 2021.
BBHR18. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

BCG93. Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In 25th ACM STOC, pages 52–61. ACM Press, May 1993.

BCI<sup>+</sup>23. Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity Gaps for Reed–Solomon Codes. J. ACM, 70(5), October 2023.

BCS16. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume 9986 of LNCS, pages 31–60. Springer, Berlin, Heidelberg, October / November 2016.

BDK13. Michael Backes, Amit Datta, and Aniket Kate. Asynchronous computational VSS with reduced communication complexity. In Ed Dawson, editor, CT-RSA 2013, volume 7779 of LNCS, pages 259–276. Springer, Berlin, Heidelberg, February / March 2013.

BGKS20. Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: sampling outside the box improves soundness. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 5:1–5:32. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

BKS18. Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-case to average case reductions for the distance to a code. Electron. Colloquium Comput. Complex., TR18-090, 2018.

Bla79. G. R. Blakley. Safeguarding cryptographic keys. Proceedings of AFIPS 1979 National Computer Conference, 48:313–317, 1979.

CCG24. Ignacio Cascudo, Daniele Cozzo, and Emanuele Giunta. Verifiable secret sharing from symmetric key cryptography with improved optimistic complexity. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part VII, volume 15490 of LNCS, pages 100–128. Springer, Singapore, December 2024.

CGMA85. Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In 26th FOCS, pages 383–395. IEEE Computer Society Press, October 1985.

CLL<sup>+</sup>24. Hao Cheng, Jiliang Li, Yizhong Liu, Yuan Lu, Weizhi Meng, and Zhenfeng Zhang. Resilience-optimal lightweight high-threshold asynchronous verifiable secret sharing. Cryptology ePrint Archive, Paper 2024/1761, 2024.

CP23. Ashish Choudhury and Arpita Patra. On the communication efficiency of statistically secure asynchronous MPC with optimal resilience. Journal of Cryptology, 36(2):13, 2023.

DXT<sup>+</sup>23. Sourav Das, Zhuolun Xiang, Alin Tomescu, Alexander Spiegelman, Benny Pinkas, and Ling Ren. Verifiable secret sharing simplified. Cryptology ePrint Archive, Paper 2023/1196, 2023.

EB22. Khadijeh Eslamia and Mojtaba Bahramiana. An isogeny-based quantum-resistant secret sharing scheme. Filomat, 36(10):3249–3258, 2022.
FS87. Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, *Advances in Cryptology — CRYPTO' 86*, pages 186–194, Berlin, Heidelberg, 1987. Springer Berlin Heidelberg.

GDKK22. Christoph U. Günther, Sourav Das, and Lefteris Kokoris-Kogias. Practical asynchronous proactive secret sharing and key refresh. *Cryptology ePrint Archive*, Paper 2022/1586, 2022.

GHL22. Craig Gentry, Shai Halevi, and Vadim Lyubashevsky. Practical non-interactive publicly verifiable secret sharing with thousands of parties. In Orr Dunkelman and Stefan Dziembowski, editors, *EUROCRYPT 2022, Part I*, volume 13275 of LNCS, pages 458–487. Springer, Cham, May / June 2022.

Ham15. Mike Hamburg. Ed448-goldilocks, a new elliptic curve. *Cryptology ePrint Archive*, 2015.

KZG10. Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, *ASIACRYPT 2010*, volume 6477 of LNCS, pages 177–194. Springer, Berlin, Heidelberg, December 2010.

LLS<sup>+24</sup>. Junming Li, Zhi Lu, Renfei Shen, Yuanqing Feng, and Songfeng Lu. Asynchronous verifiable secret sharing with elastic thresholds and distributed key generation. *Cryptology ePrint Archive*, Paper 2024/1463, 2024.

LRU22. Christophe Levrat, Matthieu Rambaud, and Antoine Urban. Breaking the $t < n/3$ consensus bound: Asynchronous dynamic proactive secret sharing under honest majority. *Cryptology ePrint Archive*, Paper 2022/619, 2022.

Mer87. Ralph C Merkle. A digital signature based on a conventional encryption function. In *Conference on the theory and application of cryptographic techniques*, pages 369–378. Springer, 1987.

PCR09. Arpita Patra, Ashish Choudhary, and C Pandu Rangan. Efficient statistical asynchronous verifiable secret sharing with optimal resilience. In *International Conference on Information Theoretic Security*, pages 74–92. Springer, 2009.

Sch80. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. *J. ACM*, 27(4):701–717, October 1980.

Sha79. Adi Shamir. How to share a secret. *Communications of the Association for Computing Machinery*, 22(11):612–613, November 1979.

SS24. Victor Shoup and Nigel P Smart. Lightweight asynchronous verifiable secret sharing with optimal resilience. *Journal of Cryptology*, 37(3):27, 2024.

WB86. Lloyd R Welch and Elwyn R Berlekamp. Error correction for algebraic block codes, December 30 1986. US Patent 4,633,470.

YLF<sup>+21</sup>. Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller. hbACSS: How to robustly share many secrets. *Cryptology ePrint Archive*, Paper 2021/159, 2021.

ZLG<sup>+24</sup>. Zongyang Zhang, Weihan Li, Yanpei Guo, Kexin Shi, Sherman S. M. Chow, Ximeng Liu, and Jin Dong. Fast RS-IOP multivariate polynomial commitments and verifiable secret sharing. In Davide Balzarotti and Wenyuan Xu, editors, *USENIX Security 2024*. USENIX Association, August 2024.