Could Grover's algorithm perform a search in N/2 for a match in a particular subset of a hash function preimage?

bca-0353f40e

11/3/23, 5:53 PM

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.

1 + 1

quantum-cryptography

kelalaka

11/4/23, 6:45 PM

[Can we speed up the Grover's Algorithm by running parallel processes?](https://quantumcomputing.stackexchange.com/q/4531/4866) in short, for $k$ machine one get $\sqrt{k}$ speed up.

Score:2

Crypto

Daniel S

11/3/23, 6:34 PM

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.

+ 6

bca-0353f40e

11/3/23, 6:44 PM

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?

bca-0353f40e

11/3/23, 6:46 PM

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?

Daniel S

11/4/23, 7:07 AM

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.

Daniel S

11/4/23, 7:07 AM

Note also that QCPUs currently operate at the kHz rate.

bca-0353f40e

11/4/23, 7:28 AM

Thanks, I didn't know that scaling rule although your 1/10th vs 100 in the answer reveals it. Are there some good reads on why that is so?

Daniel S

11/4/23, 8:01 AM

You might like to start with Scott Fluhrer's paper [Reassessing Grover's algorithm](https://eprint.iacr.org/2017/811.pdf).

Elon Musk

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

EN: Could Grover's algorithm perform a search in N/2 for a match in a particular subset of a hash function preimage?

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.