Compact Proofs of Retrievability publicly verifiable with RSA

empty_stack

12/6/23, 9:43 AM

I'm currently trying to implement compact proofs of retrievability that are publicly verifiable by RSA as described in this paper Compact Proofs of Retrievability in GO. I'm currently struggling on page 26 with the following equation:

$$ σ_i \leftarrow \left(H(\text{name}\mathbin\|i) \cdot \Pi_{j=1}^s u_j^{m_{ij}}\right)^d \bmod N $$

Especially the exponentiation part is a problem, as $u_j$ and $m_{ij}$ are way to big to calculate. I have the following numbers, the prime modulus is N = 2048 bits, $m_{ij}$ is a sector of 2047 bits, $u_j$ is a random number of between $(0,N]$. So I think the restriction that those elements must be part of $\mathbb{Z_N}$ holds. Maybe someone can correct me there? Is there some clever calculation I can do instead of just naively exponentiating $u_j$ with $m_{ij}$? I think all the operations are done in the multiplicative group $\mathbb{Z_N^*}$, but unfortunately I lack the knowledge to put it to clever use.

Any help is appreciated. Thanks and Regards.

0 + 6

group-theory

modular-arithmetic

Daniel S

12/6/23, 10:31 AM

Use the [modular exponentiation function](https://pkg.go.dev/math/big#Int.Exp) Exp(u,m,N)

empty_stack

12/6/23, 10:41 AM

That's what i did. It looks like the following: `new(big.Int).Exp(u[j], m[i][j], nil)` where both values u_j and m_ij have the properties i described above. I set N to nil, as i just want to exponentiate in the inner term of the function where u_j^m_ij.

Daniel S

12/6/23, 1:03 PM

Set $N$ to $N$, the mod operation should be applied to all of the individual operations.

empty_stack

12/6/23, 1:54 PM

@DanielS Thanks for your comment again. Okay, just to get you right. It would look like this: $$ σ_i \leftarrow \left(H(\text{name}\mathbin\|i) \cdot \Pi_{j=1}^s u_j^{m_{ij}} \bmod N\right)^d \bmod N $$ where the mod operation is now also applied for every single operation. Is this correct? Really appreciate your help.

Daniel S

12/6/23, 4:07 PM

Yes, that is correct apply mod with every exponentiation and multiplication. The answer will be the same, but the computation will be much more efficient.

empty_stack

12/7/23, 7:50 AM

@DanielS Thank you very much! Pretty obvious after I checked up on modular arithmetic again.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Compact Proofs of Retrievability publicly verifiable with RSA

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.