I'm surprised your page on the Infinity Machine doesn't mention Godel's theorem, even if only to say "this machine always halts within two seconds even given an Godel-unsolvable question".
I can't work out whether machine at the moment supports real numbers or just infinite floating point, and whether it's memory capacity is Aleph-0 or Aleph-1. If it has integer addressing I guess it must be Aleph-0.
I think a hash function may be impossible if you want to hash infinite messages to a finite hash, because there are infinitely many messages that hash to the same thing and they can all be found in a single run. Hashing infinite messages to infinite-length hashes is possible but I can't see it being useful.
I think signature algorithms are also impossible, because I can always generate all possible signatures and check to see if that is a valid signature for the message I want to sign.
I think the way to useful crypto may be to find problems which have Aleph-1 possible solutions, which the infinity machine can only generate and try Aleph-0 attempts at.
Everything in the Infinity Machine is at most countably infinite (aleph-0). Memory is countable since memory locations are directly bijectable on to the natural numbers; processing power is countable too, since every instruction occupies a non-zero time interval, and we can therefore show that at most countably many instructions are ever executed by observing that each such interval contains at least one rational.
There's no difference between real numbers and "infinite floating point" (modulo the occasional number with redundant encodings, such as 0.9 recurring being equal to 1). The reals are the same size as 2^aleph-0. (Be careful saying "aleph-1"; that's not a terribly useful concept owing to the undecidability of the Continuum Hypothesis. For the infinity of the reals we generally say C.)
A signature algorithm generating an infinitely long signature is not impossible (or at least can't be shown to be impossible by this type of argument), since there are uncountably many such signatures and hence even the Machine can't generate and test them all. Likewise a public/private key scheme and a Diffie-Hellman-like key exchange: anything which involves generating an infinitely long bit string using a secret key is secure in principle, because another Machine can't possibly generate all the possibilities to reverse the algorithm.
I agree that a finitely long hash wouldn't be secure for most purposes, but even an infinitely long one would have uses. For example, consider the cryptographic scissors-paper-stone protocol: I tell you the hash of my move, you tell me your move, I reveal my move and you check the hash. The virtue of a hash is not just that it reduces the size of the data; its trapdoor-ness is also useful.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
I can't work out whether machine at the moment supports real numbers or just infinite floating point, and whether it's memory capacity is Aleph-0 or Aleph-1. If it has integer addressing I guess it must be Aleph-0.
I think a hash function may be impossible if you want to hash infinite messages to a finite hash, because there are infinitely many messages that hash to the same thing and they can all be found in a single run. Hashing infinite messages to infinite-length hashes is possible but I can't see it being useful.
I think signature algorithms are also impossible, because I can always generate all possible signatures and check to see if that is a valid signature for the message I want to sign.
I think the way to useful crypto may be to find problems which have Aleph-1 possible solutions, which the infinity machine can only generate and try Aleph-0 attempts at.
There's no difference between real numbers and "infinite floating point" (modulo the occasional number with redundant encodings, such as 0.9 recurring being equal to 1). The reals are the same size as 2^aleph-0. (Be careful saying "aleph-1"; that's not a terribly useful concept owing to the undecidability of the Continuum Hypothesis. For the infinity of the reals we generally say C.)
A signature algorithm generating an infinitely long signature is not impossible (or at least can't be shown to be impossible by this type of argument), since there are uncountably many such signatures and hence even the Machine can't generate and test them all. Likewise a public/private key scheme and a Diffie-Hellman-like key exchange: anything which involves generating an infinitely long bit string using a secret key is secure in principle, because another Machine can't possibly generate all the possibilities to reverse the algorithm.
I agree that a finitely long hash wouldn't be secure for most purposes, but even an infinitely long one would have uses. For example, consider the cryptographic scissors-paper-stone protocol: I tell you the hash of my move, you tell me your move, I reveal my move and you check the hash. The virtue of a hash is not just that it reduces the size of the data; its trapdoor-ness is also useful.