1
$\begingroup$

Suppose I first define some function f(x) where x is some unsigned 256-bit integer, and the function's output is a set of distinct strings of any length so that output set would be 2^256 unique strings, i.e. a bijection for the specified domain of x.

Example f(x) = 0xAA || x || 0xBB (|| indicates byte concatenation), but it could also be more complex like f(x) = 0xAA || g(x) || 0xBB.

Then, if I plugged that function into some Hash_256 function, like so: Hash_256(f(x)), could a quantum computer reveal a matching f(x) for some known output of the composite function, and that in 2^128 attempts? By treating the composite function as the "black box" function and do a quantum search on x, would that work?

Context: Bitcoin addresses, trying to answer my own question here. It is really a message template search against 160-bit hash that I'm after.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Yes, but note that these operations must be performed serially as Grover's algorithm is highly non-parallelisable. Even if we build quantum computers which can evaluate the function in one cycle and clock rates comparable to modern computers (both very extreme advances) this will take over $2^{80}$-years. If you wish to take 1/10th the time then you would have to buy 100 times more of this high-end quantum computer.

$\endgroup$
6
  • $\begingroup$ Oh that's interesting, so a "quantum computer" then really means a single-threaded QCPU? So 2^128 cycles would be slow in single thread, and doing 2 x 2^127 by building 2 QCPUs would linearly increase the expenses right? And they'd be clocked to rates on the scale of GHz, too? Ok, how about 2^80, is that feasible in single-thread? I calculated about 10 million years... or 10 million QCPUs working for a year, yes? Because there are addresses secured using a 160-bit hash, so that's in the danger zone (2^80) then, right? $\endgroup$ Nov 3, 2022 at 18:44
  • $\begingroup$ re. "highly non-parallelisable" can't we define a bunch of these inner f(x)es so that they compress a 2^256 input space to like 2^248 output space and use that as input to the hash function, and design a family of 8 of these inner functions so that their outputs doesn't overlap meaning we still search the whole space of the hash function domain, could we then be cracking in parallel? $\endgroup$ Nov 3, 2022 at 18:46
  • 1
    $\begingroup$ Highly non-parallelisable means that using $4^k$ CPUs will take time $2^{128-k}$ for the 256-bit problem and $2^{80-k}$ for the 180-bit problem i.e. dividing the search space means that resources scale inverse quadratically with time. Thus a single threaded QCPU running for 10 million years could be replaced 100 trillion QCPUs working for a year. $\endgroup$
    – Daniel S
    Nov 4, 2022 at 7:07
  • $\begingroup$ Note also that QCPUs currently operate at the kHz rate. $\endgroup$
    – Daniel S
    Nov 4, 2022 at 7:07
  • 1
    $\begingroup$ You might like to start with Scott Fluhrer's paper Reassessing Grover's algorithm. $\endgroup$
    – Daniel S
    Nov 4, 2022 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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