Join Log in
Score:2
svm avatar Crypto

Verifying a prediction of the future

us flag
svm

I'm trying to find an algorithm to prove that someone knows some short secret message (for example some prediction of the future) before finally revealing it.

For example:

Alice knows what temperature will be outside tomorrow, she wants to prove to Bob that she had it without revealing the number until tomorrow. Bob on the other hand needs Alice to not be able to fake her prediction after the fact.

I have come up with a draft scheme that goes like this:

  1. Alice generates long random strings $r_s, r_p$.

  2. Alice sends $hash(r_s . r_p . T)$, and the $r_p$ to Bob.

    Here $T$ is the predicted temperature (a two-digit number).

  3. The next day Alice sends the $r_s$, and $T$ to Bob, so he can now verify, that Alice knew the $T$ at step 2, proving Alice had predicted the future.

Is it ok?, or could you point me to a better solution? If it is ok, what special properties should the $hash$ function has if any, except being cryptographically secure?

256
0 + 0
Score:3
knaccc avatar Crypto
es flag
knaccc

Your scheme works, but there is no need to have $r_p$.

If you remove $r_p$, then it's important to agree in advance what the bit length of your blinding factor $r_s$ will be, so that the commitment is not malleable by deciding to remove or add bits to the start of $T$ while adding or removing bits to what you later claim to be the value of your blinding factor $r_s$.

Alice then sends $hash(r_s \mathbin\| T)$ (where $\mathbin\|$ means concatenation), and later reveals $r_s$ and $T$. Just use any cryptographically secure hash that has a security level of at least 128 bits, such as SHA256. Use at least 128 bits for $r_s$ and make sure it's uniformly random, in order to prevent Bob from brute-forcing values of $r_s$ to discover your prediction in advance.

You may be additionally concerned about Bob being able to make derivatives of Alice's commitment, which is possible if the hash is vulnerable to length-extension attacks.

The scenario is: Alice commits to a prediction and announces the commitment, then Bob immediately announces a length-extension-attack-based commitment where something is appended to Alice's prediction. Bob can't open his commitment until Alice opens hers by revealing the blinding factor. The appearance of a duplicate blinding factor will be suspicious, but only if someone is paying attention.

You can avoid both this threat and avoid the need to agree the blinding factor bit length in advance by using one of the following methods:

  1. Calculate the commitment as hash(hash(blinding factor) $\mathbin\|$ hash(prediction)).

  2. As @kelalaka points out, use HMAC, with the blinding factor as the key. Therefore commitment = HMAC-SHA256(blinding factor, prediction).

0 + 0
svm avatar
us flag
svm
Yeah I've double checked and now I see that r_p was indeed unnecessary. I'l go with that scheme. Thank, you!
0
Reply
Score:1
kelalaka avatar Crypto
in flag
kelalaka

  • On should note that a simple concatenation with only $r_s$ will not work;

    The committer can fool the verifier. This is due to the simple concatenation. For example $H(\texttt{100110||11})$ is the commitment with the temperature prediction is $3^\circ$ ( $\texttt{11}$ in binary). If the temperature turns out $11^\circ$ then the committer can claim that that the secret $r_s = \texttt{1001}$ and the prediction was $\texttt{1011}$. This is works since their new claim can be also interperet as valid; $H(\texttt{1001||1011})$

    To mitigate this; either use

    • a public prefined delimiter like $\texttt{"<delimeter>}"$

      $$H(\texttt{100110<delimeter>11})$$

      or

    • release the size of the $r_s$ as part of the commitment.

    Yes, use at least 128-bit so that even the Bitcoin miner needs around $2^{34}$-year to find a possible commitment value as long as the used hash function provides at least 128-bit pre-image resistance. Use SHA-256 since we still believe that SHA-256 has around 256-bit preimage security.

    Alternatively, it is better to use $\operatorname{HMAC-SHA256}$ with $r_s$ as the key or better use $\operatorname{KMAC}$ of the $\operatorname{SHA-3}$ that is easier construction than $\operatorname{HMAC}$, though HMAC still is a beast.

The scheme in the question can work without the delimiters or size revealing

This is due to the publication of the $r_p$ that stands as delimiters. Still, it is better to use $\operatorname{HMAC,KMAC}$.

If one still wants to use a cryptographic hash function and there is a fear of length extension attacks on hash functions use SHA-3, BLAKE2, or SHA-512/256. Actually, there is no fear since the length extension attack will change the hash result.

Instead of using a different hash function for different platforms use domain separation;

$$H(\texttt{fixedDomainSeperationTextForPlatfromA}||r_s||r_p||T)$$

0 + 0
Maarten Bodewes avatar
in flag
Maarten Bodewes
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/133039/discussion-on-answer-by-kelalaka-verifying-a-prediction-of-the-future).
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.