All but one Vector Commitment

All but one vector commitment is used to create a VOLE Correlation. All but one element of the binary tree can be conveyed to the other party.

The tree is constructed starting from a random seed $r$ of the root node, and the value $k$ of each leaf node is expanded by the PRG and hash function $H_0$ to two values, a seed $sd$ and a commitment $com$. Then the final seed $s{d}_0,...,s{d}_{N-1}$ is computed as $h_{com}=H_1(co{m}_0,...,co{m}_{N-1})$.　In other words, N-1 seeds are committed to $h_{com}$.

https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/FAEST-spec-web.pdf

The overall algorithm is as follows

1. Prover generates $r$ and computes $h_{com}$ using PRG and H0,H1.
2. Verifier sends challenge j (index of seed) to Prover
3. Prover sends $h_{com}$, $co{m}_j$, and siblings to Verifier
4. Verifier computes each $co{m}_i(i\ne j)$ from the received siblings
5. input $co{m}_j$ received in step 3 and each commitment calculated in step 4 into H1
6. Verifier check that the output value of H1 matches the $h_{c}om$ received in step 3

Example of j=3

1. Prover generates r and calculates h_com using PRG and H0,H1. This is a N-seeds commit
2. Verifier sends challenge(= 3) to Prover
3. Prover sends $h_{com}$,$co{m}_3$, and siblings($k_1^1,k_0^2,k_2^3$) to Verifier
4. Verifier computes each Com_i(i=j) from the received siblings $k_1^1$: $co{m}_4,co{m}_5,co{m}_6,co{m}_7$ $k_0^2$: $co{m}_0,co{m}_1$ $k_2^3$: $co{m}_2$
5. Enter the $co{m}_3$ received in step 3 and each of the commitments calculated in step 4 together in H1. output = H1(com1~com7)
6. Verifier checks that the output value of H1 matches the $h_{com}$ received in step 3

This vector commitment is repeated multiple times to prepare the number of VOLE correlations needed to evaluate the circuit.

the next step is to convert each vector commitment into a length-l, VOLE correlation.