Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4824

Re: bike locks and encryption

Show all headers | View raw

On 2014-10-08, RichD <r_delaney2001@yahoo.com> 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, ... }.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-06 23:28 -0700
  Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-07 11:39 +0100
    Re: bike locks and encryption Richard Heathfield <invalid@see.sig.invalid> - 2014-10-07 11:53 +0100
      Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-07 16:24 +0100
        Re: bike locks and encryption Richard Heathfield <invalid@see.sig.invalid> - 2014-10-07 21:26 +0100
          Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-08 01:34 +0100
          Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:16 -0700
      Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:27 -0700
  Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 13:57 -0700
    Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-07 21:21 +0000
      Re: bike locks and encryption "BartC" <bc@freeuk.com> - 2014-10-07 22:33 +0100
        Re: bike locks and encryption Jongware <jongware@no-spam.plz> - 2014-10-08 15:51 +0200
  Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-07 21:10 +0000
    Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:34 -0700
      Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-08 14:10 +0000
        Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-10 18:33 -0700

csiph-web