Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming Subject: Re: bike locks and encryption Date: Wed, 8 Oct 2014 14:10:08 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 64 Message-ID: <20141008060405.204@kylheku.com> References: <144e68c8-e88b-47a4-af78-8129ad2557c7@googlegroups.com> <20141007135925.603@kylheku.com> NNTP-Posting-Host: X+c6YNb3AaWMPA3YfA4opg.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:4824 On 2014-10-08, RichD wrote: > On October 7, Kaz Kylheku wrote: >>> bicycle locks as examples of one way functions, so useful in >>> encryption. >> >> All the bicycle locks with which I am familiar are not one-way functions in any >> sense. > > Think harder. That's clearly your preferred domain, so it makes sense you would encourage others, but here you are required to think smarter, as well as to be better informed. >> Mechanical locks evaluate this function mechanically, powered by the user. For >> instance, you rotate some dials to bring them to some configuration, and then >> have the lock evaluate the matches? predicate by trying to pull the lock open. >> The lock either says "True" by separating or "No" by refusing to separate. > > well yeah > And you have to try every one. > > But you missed the point completely. > Think about trying to close (mate) an opened lock, without the > combination. What's the complexity? There's the one way function aspect. Closing the lock is just another form of unlocking the lock: changing the state of the lock, based on knowing the combination. The machine has a secret. If you know the secret, you can change the machine's state from open to closed or vice versa. The machine provides an elementary operation: you can load it with an input value by turning the dials, and it will report whether or not that value matches the correct combination. The machine does not compute any other function. You, the operator, can use this elementary operation to solve a search problem, thereby implementing a function. The search function can be made much faster when the lock is open, than when it is closed. The search function for the open state is bounded only by O(D), where D is the number of dials/digits. When the lock is closed, the search problem is O(N = 10**D), where N is the number of combinations. In the open situation, the search can be faster because the machine leaks information which provides the operator with an additional operation. The operator can not only load a trial value and test the lock, as before, but can also peek into the lock to determine whether the outermost dial is in the correct position to allow passage. If that is the case, it is possible to peek deeper, to see whether the second dial is in the correct position and so on. These two versions of the search problem are not the opposite directions of a one-way function. They are just variants of the same problem with different constraints on what information is available from the "black box". A one-way function is a calculation from M bits to N bits, where M > N. The inverse of a one-way function isn't a function, because more than one M-bit value corresponds to a given N-bit value. That's what "one way" means. For example, calculating a remainder is a one-way function. Both 31 mod 16, and 255 mod 16 produce 15; 15 cannot be uniquely reversed to 31 or 255. The solution set to "what positive integer, mod 16, produces 15" is an infinite set consisting of { 15, 31, 47, 63, ... }.