Score:2

Hash verification by key

cn flag

I want to implement the following algorithm, but don't know what tools to use.

D - data

  1. I generate some universal value for D - Y
  2. I generate some random key - K, get a hash of D by this key - H
  3. I want to be able to have a function - F: F(Y, K, H) = true if H is correct and false otherwise.

The main goal: to prove the validity of hash of data by some key using only some piece of original data.

Usage: Say we have computers: A, B, C. A sends some data to B, then the data is deleted from A. Now, I want to be able to check (from nodes A, C) that B contains the data every 10 minutes, but I can't trust it, so I need some tool to be sure, that B isn't fooling me.

Answer: PDP (Proof of Data Posession)

kelalaka avatar
in flag
Are you asking HMAC or more?
ischenko avatar
cn flag
@kelalaka I want to be able to prove that data exists on another device, so I want to send it requests with different keys, and receive hashes, then check the hashes by some piece of data (of fixed size) extracted from the original data
ischenko avatar
cn flag
@kelalaka added a usage section
ischenko avatar
cn flag
@kelakala I send requests with random keys, so B has to keep the data to calculate the hash for the given key (am I wrong?)
ischenko avatar
cn flag
yeah, that's the biggest problem, i must be able to verify the pair (key, hash) by some small piece of original data (but it must be impossible to get the hash (by a given key) from this snippet)
kelalaka avatar
in flag
Use HMAC, send the key get the HMAC value to verify that, though you will have limited queries with the number of pairs you had stored. There may be a clever solution that I don't see now.
ischenko avatar
cn flag
@kelakala, moreover, I can't precalculate hashes, because the A node is neither trusted, so I must come up with some small data representation, that could work as a hash verifier.
kelalaka avatar
in flag
Could you completely re-write your question including all details...
ischenko avatar
cn flag
oh, sorry for confusion
kelalaka avatar
in flag
Please [don't cross-post](https://stackoverflow.com/q/70852888/1820553), only maintain one copy. [See this meta](https://meta.stackexchange.com/q/64068/403350)
knaccc avatar
es flag
What exactly do you mean by "the A node is neither trusted"? Do you mean A can lie about what data it claims to have stored with B?
ischenko avatar
cn flag
@knaccc yes. The correct answer for was to use some PDP algorithm (Proof of data posession)
knaccc avatar
es flag
It'd be interesting if you could explain exactly what PDP method satisfies the criteria in your question. As far as I can see, the simplest method of a random challenge $c$ and a response calculated as $H(c\mathbin\|data)$ would not satisfy your criteria.
ischenko avatar
cn flag
@knaccc I'm sorry I'm not really into cryptography, so I can make mistakes. I found out that there's a very powerful thing - homomorphic hashes and it seems like they can help me to build (or find an existing) algorithm, that would solve my problem.
mangohost

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.