Overview from Jeremiah

Ozgun: I would like you to review the following background materials and try to arrive at a solid theoretical and mathematical understanding of the ability to use certain algebraic hash functions to provide fingerprints for polynomials. I have some intuition that we can leverage this ability within our new PoAS protocol, in conjunction with the KZG schemes we are already using. For example, we might be able to commit to some data using an algebraic hash function instead of a normal hash function, and then commit to those hashes using KZG. I don’t have a clear understanding of the math and how existing constructions work to be able to think about this properly yet — that’s where I need your help.

Please read the following three papers, including any other relevant background materials or secondary sources you deem usefully. I would like you to document your findings and try to unpack the theory and math behind how they work, similar to what you did for Dankrad’s article on KZG. My intuition is that these are all variations on a common theme. Ideally we would be able to publish this as a blog post again, but don’t focus on making it high-quality just yet. I would like you time box this to what you can accomplish within one week.

Background

I believe both all of these schemes are related to the simple commitment scheme presented in the introduction of the KZG paper.

<aside> <img src="/icons/mathematics_purple.svg" alt="/icons/mathematics_purple.svg" width="40px" /> Let $g$ and $h$ be two random generators of a group ${\mathbb G}$ of prime order $p$. The committer can commit to a random message $m\in \Z_p$ simply as $C_{\langle g \rangle}(m) = g^m$.

</aside>

Materials

• It might be helpful background information to read the updated citation by Damgard — Commitment Schemes and Zero-Knowledge Protocols with a focus on exercise 6
• Dan’s overview of commitment schemes (understanding how Pedersen commitments work) — this short video may also prove helpful, and I believe Pedersen commitments are of a similar flavor
• Read: Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance — focus on section 3 fingerprints
• Read Verifying Distributed Erasure Coded Data (VDECD) — focus on section 2 homomorphic fingerprinting

Follow Ups (FLUPs) @Ozgun Ozerk

1. Is the algebraic hash function I outline above the same as the one presented in these papers and elaborated on by you below? I initially thought it was, but your write-up seems to describe a different class of function. If not, then does the function described above also have the same homomorphic properties?
2. I think it would be helpful to provide an overview of the different types of homomorphic hash functions and commitment schemes and their different properties, perhaps in a table form. I think these things are obvious to cryptographers and are glossed over very quickly (i.e. in the beginning of the KZG paper), but its not clear to me. So far, that appears to be: simple algebraic hash (example above), Pedersen commitments, homomorphic hash (three flavors in your example below), and KZG commitments.
3. Do the functions described below have the same property as the scheme in Semi-AVID-PR and how I understand the VDECD scheme to work, namely that an erasure coding of a set of homomorphic hashes will result in the homomorphic hashes of the erasure coding for the source data (in a cross-commit scheme)?
4. Can you extend the section on evaluation fingerprinting? If not, can you reach out to Dariia for help?