I guess I would have failed to create complexity theory with my solution --- but everyone involved would have understood it, no long calculations required: give the guard a lock and the spy a key. It's still a sort of one-way function (easier to make a lock from a key then a key for a lock), but it doesn't require squaring 100 digit numbers in the dead of night before deciding whether to shoot a man.
Practical, literal-minded solutions are not the kind of thing that typically inspires theoretical insight into mathematics, though. That's like saying Euler could have just swum across some of the rivers in Koenigsberg.
For what its worth, my solution was to give the guard a set of sealed envelopes. Each envelope having a password written on the outside and a password written on a piece of paper inside. The spy would give the guard the word that is written on one of the envelopes, the guard would then open the envelope and ask the spy for the password contained inside.
Doesn't anyone else find the solution a bit problematic: sure great concept but unless the guards have a black box tool which is secured and can churn out Y from X, they will have to know the function to prove that Y was congruent with an X...and if they know the function, so too would the enemy. On the other hand if they have a secure tool that does this fine, but this seems to simplify the problem considerably b/c the key is that the guard doesn't need to know anything at all: the tool does all the work.
Let f(x) = y. The guards have f and y. A spy gives a guard an x, and the guard computes f(x) and checks it against his list of ys. If it's on the list, the spy can pass. The enemy has f and y too, but it doesn't help them! f(x) is trivial to compute but the inverse is hard, so the enemy knows exactly the answer they want the guard to get and no idea how to make him get it!
One-way functions are very cool and form the basis of public-key cryptography, although it's quite a bit more complicated than this example.
In the given example, the careless guards are analogous to a safe, non-malicious recipient connected to an unencrypted channel. In your example, a drunken guard is an unsafe (hackable) client.
Define "truly one-way"! We don't have any functions that are truly one-way, just very hard to go in the other direction. This is probably easier to reverse than prime factorisation for example, but it's still asymmetric in its difficulty.
The solution doesn't seem to work on its face. If the spy simply gives the guard Y, the scheme is the same as having a bunch of fixed passwords. If the spy gives the guard X, X becomes public to the enemy. Some machine that lets the spy input X (with the input hidden to the guard) and displays Y to the guard would work, assuming the guard doesn't snoop around to discover X.
Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.
A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function.
You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n.
When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it.
The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers.
Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.
No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break.
A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.
I don't see how that solves anything. If the guard knows the answer, then you assume the enemy knows the answer. So all "throwing it away" does, is allow the enemy to cross the border once and the spy stranded!
Well, the guard knows Y, and the enemy knows Y... but the guard's authentication procedure involves taking an X (not Y) supplied by the friendly spy, executing the calculation, and asserting the result is equal to Y. Since the enemy does not know X, and X cannot be trivially derived from Y (one-way function), the scheme is secure.
The idea is that X is the credential, and Y is a sort of digital signature of X.
So the spy knows X, and the border guard has a record of Y. When the spy wants to cross the border, he tells the guard X, and the guard can check that the credential is legitimate by seeing whether it matches the signature Y.
The machine is necessary. Although the spy is able to produce a Y number with the machine and the guard knows Y, if the guard doesn't know X he also doesn't know how to generate a Y number with the machine.
Yeah, you have to make a leap that's not explained in the puzzle. An intermediate machine or some other method has to be used to keep the secret a secret, yet the answer can be "public".
Just read your comment after posting the exact same thing above... it seems the key we both figured out is that you have a secure tool that does the work for the guard. But if this is the case then the problem isn't a problem at all: b/c with a secure tool you don't need to worry about a guard who blabbs... but that certainly didn't seem to be in the universe of hte problem that was posed
Right; you'd actually need some sort of public-key cryptography: the guard gives the spy a challenging problem which only the spy can solve correctly, but for which anyone (including the guard) can check the answer.
If you don't assume a fixed 100 digit input, but any number of digits (especially a float) then there are theoretically an infinite number of numbers that have those 100 digits in their middle.
If I have a secret number, I can calculate the square and find the middle 100 digits. If you have the 100 middle digits, it will not be easy for you to find the secret number.
