Algorithm to validate 1 of N inputs is part of output hash

TommyF

10/28/22, 6:39 PM

Is there an algorithm that allows proofing that an input x1 was used as 1 out of N inputs to create an output hash y, without knowing the other inputs?

I.e. if there are 5 users providing an input hash for example, can we create an output hash that allows each individual user to verify his input was part of the inputs without him needing to know all other inputs?

(it's ok to learn all inputs during the validation process, inputs are not secret just not feasibly available)

Some more info on the concrete usecase:

I need to represent the state of a system in a concise way (hash?).
The state changes/evolves constantly based on new user inputs.
There needs to be a way to check if a specific user input is already reflected in the current state.

The blunt approach would be to represent the system state as the list of inputs but this doesn't work due to some limitations.
Therefore I was hoping there might be a cryptographic function that would allow the state to be represented in a concise way. I've been looking into merkle trees, multi signature schemes etc. but so far haven't found something that really fits the bill.

0 + 6

hash

mac

hash-signature

bmm6o

10/28/22, 8:19 PM

It sounds like you could solve your problem with a Merkle Tree https://en.wikipedia.org/wiki/Merkle_tree

TommyF

10/29/22, 4:52 AM

@bmm6o unfortunately not, that also requires knowledge of other inputs or their aggregate hash, but thank you for the suggestion!

bmm6o

10/29/22, 4:06 PM

Right, the tree would need to be available to anyone who wanted to verify the computation.

SEJPM

10/30/22, 11:08 AM

So, what you want to prove is that for a given value $y$ there exists some $x_i$ from a set of size $N$ of values $S=\{x_1,x_2,\ldots,x_N\}$ such that $y=H(x_i)$ and that you know said $x_i$ (potentially without revealing it?)? Is interaction allowed in such a proof or is it required to be a statement comparable to a hash value?

TommyF

11/1/22, 7:22 AM

@SEJPM I added more information on my concrete usecase to make it more clear. Thanks for trying to help!

Ben Voigt

11/1/22, 6:19 PM

@TommyF: Have you tested this idea by the Pigeonhole Principle? That is, if each of *N* inputs has length of *k* bits and the hash output has length `x` bits, then if `x > N*k` the same output can be produced by many different inputs (2**(x - N*k)) and therefore even if you have a complete input and reproduce the hash calculation arriving at the same output, you can never know if you have the original input or merely a collision.

Elon Musk

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

EN: Algorithm to validate 1 of N inputs is part of output hash

TH: อัลกอริทึมเพื่อตรวจสอบอินพุต 1 จาก N เป็นส่วนหนึ่งของแฮชเอาต์พุต

RO: Algoritmul pentru validarea a 1 din N intrări face parte din hash de ieșire

RU: Алгоритм проверки 1 из N входов является частью выходного хэша

VI: Thuật toán để xác thực 1 trong số N đầu vào là một phần của hàm băm đầu ra

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.