[Cryptography] XOR linked list & crypto

[Henry Baker]

At 09:06 AM 2/15/2016, Jerry Leichter wrote:
>> 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.

Thanks very much, Jerry; this idea sounds pretty interesting.  Can you recall anything else that might help me Google this paper?

> Link reversal has actually been used in this fashion not for list traversal as such, but for garbage collection...

Yes, I've heard rumors of such things...  ;-)