1
$\begingroup$

As well known, different assumptions of difficulty of some problems are used in provable security. E.g., if some crypto-scheme is breakable only in case the attacker finds preimages for hash function, we say that the scheme is as secure as preimage resistance of hash-function. Imaging, that some hash function is not preimage resistant in general (e.g. it has not enough length, say only 64 bit). Nevertheless, it's obviously difficult to find preimages in short time (say 10 minutes). And imaging that we're able to construct a reduction that implies that successful attacker is able to find preimages in some short time, e.g. during some short session of protocol (e.g. some online key exchange which is abandoned in 10 minutes in case counter-party doesn't respond ). In this case, the scheme should be recognized as secure based on 2 assumptions:

  1. party controls time of sessions and discontinues a session after 10 minutes of waiting
  2. hash function is preimage resistant within time 10 minutes.

My question is whether you know some research/papers which use such approach in provable security, i.e. they use such assumptions of form "preimage resistance in small time T", instead of conventional "preimage resistance in acceptable(polinomial) time"? Concrete problem (preimage resistance or something else) doesn't matter obviously, I'm interesting only in time-restriction. And does this approach could be reasonable at all?

$\endgroup$
1
$\begingroup$

One area that tries to address such questions is fine-grained cryptography [DVV]. Here the working assumption is that the protocols should be secure "against adversaries with an a-priori bounded polynomial amount of resources but the honest algorithm requires less resources than the adversaries they are designed to fool". A classical example of such a protocol is the Merkle puzzle, which is a key-exchange/public-key scheme that requires $O(n)$ time/queries for the parties carrying out the protocol but it takes an adversary $\Theta(n^2)$ time/queries.

More recently, there have been attempts at building public-key cryptography where the gap is arbitrary (e.g., $O(n^c)$ vs $O(n^{c+1})$ for any constant $c$) and these rely on computation problems such as the orthogonal vector problem [B+] where there is a gap between computation and verification (and this gap is inherent conditioned on SETH). This has also resulted in an interesting notion of proofs of work called useful proof of work [B+] where the goal is to utilize otherwise wasteful work (as for example in Bitcoin).

You can find a nice overview of the area by Alon Rosen here.

[B+] Ball et al, Proof of useful work, Crypto'18

[DVV]: Degvekar, Vaikuntanathan and Vasudevan, Fine-grained Cryptography, Crypto'16.

| 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.