undefined | Better HN

0 pointsjlokier5y ago0 comments

> Or maybe it's impossible to implement that hash function reversibly without preserving a copy of the input in the output.

Cryptographic hash functions rely on locally non-reversible non-linear operations.[1]

So you don't need to copy the original input, but you will need to copy bits here and there throughout the hash function, which allow the input to be reconstructed.

But that's not surprising, even a humble AND gate is non-reversible. So even a humble AND gate program will need to copy its inputs to the output if it's to be reversible.

[1] (As well, cryptographic hash functions are generally not reversible anyway. As in, different inputs hash to the same output value, so there's no unambiguous reversal.)

0 comments

thisrod5y ago

> So even a humble AND gate program will need to copy its inputs to the output if it's to be reversible.

It's been 20 years since I had to think closely about reversible computing, and I've forgotten lots of the details. When I said "implement a hash function", I actually meant "implement exclusive-or with the result of the hash function" or something similar.

> As well, cryptographic hash functions are generally not [invertible] anyway.

Good point. But aren't there one-to-one equivalents, called one-way functions, trapdoor functions or something like that? My cryptography is even rustier.

jlokierOP5y ago

> It's been 20 years since I had to think closely about reversible computing, and I've forgotten lots of the details. When I said "implement a hash function", I actually meant "implement exclusive-or with the result of the hash function" or something similar.

Well that gets a bit more interesting. If the hash is of a key K, and the hash output is exclusive-or'd with input M, then of course it's reversible with respect to M but not K.

You can think of the above as an easily reversible program with M as its only input. (If K is treated as a constant, then it's just part of the program.).

In that case, yes you can make an efficiently reversible version in Nilang.jl, and it will have all the differentiability properties etc.

But it will only have those properties under the assumption of holding K constant. The new program won't resemble the stated problem of inverting a cryptographic hash :-)

In general there will be some parts of a program which are reversible without needing to record any state, and other parts where you have to retain some state (or generally a function of the state, which might be less overhead) in order to make the whole thing reversible.

Quantum computers face this problem too. Every quantum program is fully reversible, but you can't copy qubits, so you can't translate a classical non-reversible program to quantum by retaining copies of state as described above. You have to do stranger things to translate the program.

The fact you can actually do that shows that recording internal states isn't the only way to make a program reversible. But the fact it takes exponential time to simulate the resulting program on a classical computer shows that the alternative doesn't let you invert a cryptographic hash that easily either :-)

> But aren't there one-to-one equivalents, called one-way functions, ...

In general one-way functions map multiple inputs to the same output, so they aren't reversible.

You're thinking of a rarer kind called one-way permutations.

There aren't many of these around, and they aren't what is generally intended when talking about a cryptographic hash. It would be convenient if hashes were permutations, but they generally aren't.

thisrod5y ago

Thanks

j / k navigate · click thread line to collapse