Score:2

In sha256, is it possible to use less information than the full preimage to prove that the prefix of the preimage is a certain string

de flag

Alice split a long string P into two segments A and B. A is relatively short and B is long.

H = sha256(A + B)

Bob does not know P, but knows H.

Is it possible for Alice to prove to Bob that A is the prefix of P, but only needs to provide additional information much shorter than B?

kelalaka avatar
in flag
Welcome to Cryptography.SE. What is the origin of this question? What are the sizes of $A$ and $B$.
jiedo avatar
de flag
Thanks, this is a question I think of when I am exploring the delivery of Bitcoin tx. I hope that without telling all the tx, I can prove to others which is the first utxo spent by this tx. so A is about 40 Bytes, B may more than 1000 KB.
kelalaka avatar
in flag
Well, that is input the SHA256 so if you can't find a collision then you need to tell all.
jiedo avatar
de flag
Got it. If A is long and B is short, it is possible to prove that B is the suffix of P with content shorter than A. But the reverse seems to be really impossible.
kelalaka avatar
in flag
If B is short then Bob can brute force it
jiedo avatar
de flag
I mean prove B is **suffix** if B is short. with out A. Bob can not brute force.
kodlu avatar
sa flag
what does A+B mean ? concatenation?
Score:3
mx flag

Because of the way SHA2 works, no.

SHA2 splits the message up into blocks, then uses a compression function to compress each block into the state. The final state is the hash value.

Merkle-Damgard Hashing

This means that the only way to "connect" the intermediate state after A has been processed with the final value is to hash all the blocks for the B part, requiring the entirety of B. It's impossible to use fewer bits.

Merkle trees

If you want to verify sub-strings quickly, the standard solution is to use a Merkle tree.

Merkle tree

Any node in the tree can be calculated using its children, so we can avoid sending all the content and just supply the nodes necessary to move up the tree to the root node.

If L1 and L2 were the A string and L3 and L4 were the B string, Alice could supply A along with Hash 1 and Bob does not need to know the L3 and L4 blocks to calculate the root hash. Alice can prune the tree to include only what's necessary.

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.