Round-efficient multiplication

This functionality (which we denote as normal multiplication ni=1xi\underset{i=1}{\overset{n}\prod}x_i and always use in case we need to multiply >2>2 factors) computes the product of nn elements. It works as follows:

  1. [riRFp], for i{0..n}[r_i \in_R \mathbb{F}_p], \text{ for }i \in \{0 .. n\}
  2. [si]=[ri/ri1] for i{1..n}[s_i] = [r_i / r_{i-1}] \text{ for }i \in \{1 .. n\} //this can be computed in the offline phase
  3. [yi]=[si][xi] for i{1..n}[y_i] = [s_i] [x_i] \text{ for }i \in \{1 .. n\}
  4. Open yiy_i, calculate Y=ni=1yiY = \underset{i=1}{\overset{n}\prod}y_i.
  5. Output Y[r0rn1]Y [r_0 r_n^{-1}]

This also allows to compute running product x1;x1x2;...;x1x2...xnx_1; x_1 x_2; ...; x_1 x_2 ... x_n in one go using the same method: in step 4 we compute all Yk=ki=1yiY_k = \underset{i=1}{\overset{k}\prod}y_i, and then calculate Yk[r0rk1]Y_k[r_0 r_k^{-1}]

results matching ""

    No results matching ""