I am reading a paper by Shacham and Waters on Compact Proofs of Retrievability. In this paper on page number 3 under section 1.1 in the very first line the author states that an encoded file is broken into n number of blocks $m_1,m_2...m_n \in Z_p$ for some large prime p.

I am not able to understand that in terms of programmimg what does it exactly mean to have a chunk of file data in a group/field. On the same page they mention an equation:

$σ_i = f_k(i) + αm_i \in Z_p$

What is the value of this $m_i$ in this equation. Is it the number of bytes/bits in each block? What value of $m_i$ would I take if I have to calculate this $σ_i$ in the equation ? The calculated value of sigma lies in the group of prime order $Z_p$.

I am not sure if I have posted the question in the right forum but I could not get any comments in stack overflow hence I have posted it to a forum I find closely related to. Any help will be valuable.

Thanks and Regards


1 Answer 1


You have to split your file in such way that each block will be smaller then prime $p$ you're using. After that you have $n$ such blocks.

You calculate $\sigma_i$ for every block so $i \in \{1,2,...,n\}$ and $m_i$ means block number $i$


Assume you're working in field $Z_p$ with $p=2^{255}-19$ (used in Curve25519 for example) and your file is 254 bytes or $254 \times 8$ bits long. In practice you can split it to blocks of (at most) 254 bits as $2^{254} \ll 2^{255}-19$. You can split your file to 8 parts, each 254bits long. So you have $n$=8, and each $m_1,m2,m3,m4,m5,m6,m7,m8$ are respective blocks from file.


Assume you're working in field $Z_p$ with $p=2^8+1$ and your file is 5 bytes long. You can split it to blocks of 8 bits as $2^8 \lt 2^8+1$. So you have 5 such parts and $n=5$ and $m1,m2,m3,m4,m5$ are respective bytes from file.

Please note that second example is in no way secure as target field is way too small.

  • $\begingroup$ what is the significance of -19 here ? I am actually working in a field Fe where e = 257. $\endgroup$
    – skii
    Jan 12, 2018 at 9:43
  • $\begingroup$ $2^{255}-19$ is just example prime I've chosen, something with actual cryptographic use, in your case $p=257=2^8+1$ so you can split your file in 8bit/1byte blocks BUT this is nowhere near secure field as it is really really small $\endgroup$ Jan 12, 2018 at 11:28
  • $\begingroup$ Ok I have a doubt in the answer you say that p = (2^255) - 19. But in the comment for field you are pointing that p = 257? I am confused here. so in the last case was p =255? or p = (2^255) - 19 $\endgroup$
    – skii
    Jan 12, 2018 at 11:35
  • $\begingroup$ I've updated my answer, please check if it's clearer now $\endgroup$ Jan 12, 2018 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.