Score:2

Crypto

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

jiedo

10/12/22, 10:25 AM

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?

1 + 7

hash

sha-256

kelalaka

10/12/22, 10:52 AM

Welcome to Cryptography.SE. What is the origin of this question? What are the sizes of $A$ and $B$.

jiedo

10/12/22, 11:53 AM

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

10/12/22, 11:58 AM

Well, that is input the SHA256 so if you can't find a collision then you need to tell all.

jiedo

10/12/22, 12:13 PM

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

10/12/22, 12:21 PM

If B is short then Bob can brute force it

jiedo

10/12/22, 12:25 PM

I mean prove B is **suffix** if B is short. with out A. Bob can not brute force.

kodlu

10/13/22, 1:29 PM

what does A+B mean ? concatenation?

Score:3

Crypto

Richard Thiessen

10/14/22, 3:44 AM

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.

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.

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.

0 + 0

Elon Musk

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

EN: 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

TH: ใน sha256 เป็นไปได้ไหมที่จะใช้ข้อมูลน้อยกว่า preimage แบบเต็มเพื่อพิสูจน์ว่าคำนำหน้าของ preimage เป็นสตริงที่แน่นอน

RO: În sha256, este posibil să folosiți mai puține informații decât preimaginea completă pentru a demonstra că prefixul preimaginei este un anumit șir?

RU: В sha256 можно ли использовать меньше информации, чем полный прообраз, чтобы доказать, что префикс прообраза является определенной строкой

VI: Trong sha256, có thể sử dụng ít thông tin hơn tiền tố đầy đủ để chứng minh rằng tiền tố của tiền tố là một chuỗi nhất định không

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.