2
$\begingroup$

Suppose Alice wants to prove to Bob that t1 is less than t2. t1 and t2 represent timestamps. Alice does not want to reveal t1 and t2. However, she needs to receive Bob’s confirmation that t1 < t2. In order to prevent Bob from performing a brute-force attack to find t1 and t2, Alice wants to use some salt with the timestamps.

Any idea how to use cryptographic algorithms in order to solve this problem?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This seems to be a combination of a commitment and a zero knowledge proof. Your hashes solve the commitment part, but make the ZKP part impossible. There is a similar problem called Yao's Millionaires' Problem but there alice knowns one value and bob the other. You should search for "Zero knowledge proof" or perhaps "secure multi party computation". $\endgroup$ – CodesInChaos Jun 4 '14 at 10:42
  • $\begingroup$ Yes, ZKP makes it impossible but they are expensive in terms of operations. Having a simple and fast function, such as Order Preserving Hash can make it easier. It depends on to what extent we want to achieve privacy. $\endgroup$ – Mohammad Khodaei Jun 4 '14 at 15:31
1
$\begingroup$

From the last part of your question, I understand that you need order preserving hash function or encryption. Look into this thread How does order-preserving encryption work?

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This may be usable as fallback solution, but generally order preserving encryption leaks a bit much. If there is an efficient ZKP, it will be much stronger than OPE. $\endgroup$ – CodesInChaos Jun 4 '14 at 11:07
  • $\begingroup$ You are right, OPE is vulnerable to cryptanalysis however it can be useful when the time window for secrecy is preferentially smaller. In other words, if plaintext becomes useless after a short time (within which cryptanalysis will be impossible) then OPE can be used as a solution. $\endgroup$ – Syed Jun 4 '14 at 12:39
1
$\begingroup$

Use secure two-party computation, to prove that t1 < t2 holds. There's been a lot of recent work on schemes for secure two-party computation (e.g., using Yao-style garbled circuits), and they should easily be able to handle this.

You will need some way to prevent the parties from simply lying about their inputs. For instance, if you assume that Alice has previously published a commitment to t1 and Bob has published a commitment to t2, you can use secure two-party computation to simultaneously check whether their inputs are consistent with the commitment and their order.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.