[Cryptography] XOR linked list & crypto

[Jerry Leichter]

> A famous XOR hack (Knuth??) enables traversing a list in either direction:
> 
> https://en.wikipedia.org/wiki/Xor_linked_list
> 
> Of course, you need *two* successive pointers in order to access the list.
> 
> "Features" "Given only one list item, one cannot immediately obtain the addresses of the other elements of the list"
> 
> "Drawbacks" "The pointers will be unreadable if one isn't traversing the list"
> 
> Yes, this inability is used as both a "feature" and as a "drawback".
> 
> Q: Have these features/drawbacks been used in any encryption scheme?
I remember some paper in which links were encoded as keys, provide a way to represent arbitrary graphs in a secure fashion.  Can't remember any of the details, though - sorry.

Speaking of the XOR trick:  I don't know who invented it or when, but I first heard about it in 1970 or thereabouts.  *Why* it worked bothered me for many years, until I finally came up with a way to think about it.  Imagine a linked list as a physical chain.  You hold onto one link and the chain falls off your hand in either direction.  You can easily move left or right along the chain.

The analogue for a linked list is that you can construct a two-way linked list from a one-way linked list by reversing the links as you traverse the list.  Unlike the XOR trick, this works just fine in a strongly-typed language where the only things you can do with pointers is assign them, follow them, or compare them for equality.  Of course, it means you need write access to the list even to read it, and the list can't be read by two separate threads at once.

Link reversal has actually been used in this fashion not for list traversal as such, but for garbage collection:  Walk the "points to" relation from the roots, reversing links as you go.  Then whenever you relocate a node,  you have a pointer to a list of everyone who points to that node, so you can flip the pointers back, but to the new location.
                                                        -- Jerry