3 ms·
Typically we calculate assuming the total energy needed at the Landauer limit at 3K. It's usually going to be multiples of the entire sun's energy output for bi
by SAI_Peregrinus 5y ago
Typically we calculate assuming the total energy needed at the Landauer limit at 3K. It's usually going to be multiples of the entire sun's energy output for billions of years, more if not using a quantum computer. Money isn't the relevant metric at the scales of modern cryptography.
- amluto 5y agoBut the Landauer limit, even at 300K, for a first preimage of even a completely secure hash is essentially zero. Define: f(s, n, h) = 1 if there exists an n-bit preimage of h that starts with s, else 0 Computing f by brute force costs one bit erasure to prepare room for the answer. (And takes 2^(n - len(s)) operations, but we’re imagining a civilization that can build Dyson spheres and has quantum, and hence at least somewhat reversible, computers. We’re talking about the Landauer limit in particular.) Now choose an appropriate n (slightly greater than the length of the hash) and compute f for s=[0] and s=[1]. After at most two tries, you’ll get a match, assuming a preimage exists. Call the first match s_1. Now repeat for s_1||0 and s_1||1. Call the first match s_2. Repeat this up to s_n. Now s_n is the lexicographically first n-bit preimage! This costs O(n) energy at the Landauer limit. All crypto is broken! Never mind that the actual computation involved exceeds 2^n.
- SAI_Peregrinus 5y agoWith reversible computing, yes. I strongly suspect that'll never be practically realized, or in the event that they are that the slowdown will be large enough that other fundamental limits on the speed (rather than the energy) of computing will instead dominate.