Tuesday, May 22, 2018

[mkthxboj] Dance cipher

We sketch out some ideas for designing a block cipher inspired by moves used in contra dance.

Each person keeps track of one number in their memory, maybe as little as 1 bit of memory.  During the "swing" move, two people meet, tell each other their current number, then compute new numbers to remember based on their old numbers, some relatively simple function computable with mental arithmetic.  (This is a nice example of SIMD parallel computation done by humans.)  It might need to be a invertible function for decryption to be possible (unless part of a larger structure like a Feistel network).

Everything else is permutations of the dancers causing different people to meet, causing mixing.  Various contra dance and contra dance inspired moves available as permutations:

Standard progression: ONEs move one couple down the hall, TWOs up.

Horizontal movement: align the grid of dancers as horizontal sets across the hall and do any of these permutation moves. A simpler variation might only have the couples out at the top execute a horizontal permutation.

Whole set take hands in giant oval and turn the oval.  Traditionally the oval eventually turns back the same amount, but break tradition to allow mixing of distant dancers.  Practically, turning the oval by a constant and consistent amount might be tricky.

Pull by right pull by left around the whole set (grand right left).  Again, seeking mixing with distant dancers.  Not following this move by its inverse (as would be traditionally done) will break up couples: this is a mixer.

Different sets do different permutations.  Maybe one set does oval for 10 counts followed by 6 counts of something else that doesn't travel (e.g., swing), while another set does 8 and 8.  Because dancers move horizontally between sets, they will need to pay attention to where they are to know what to do.

Or, a similar effect as different sets doing different moves could accomplished by simply having sets of different lengths.  When combined with the possibility of horizontal sets, the grid of dancers needs to start out convex, e.g., house-shaped pentagon with the ground at the top of the hall.

The need for these permutations causing mixing with initially distant dancers was inspired by how the rho step of Keccak specifies different bit rotation amounts (triangular numbers) depending on the position of the word within the 5x5 matrix.

All the other contra dance moves (and sequences of moves) which are equivalent to the identity permutation can also be included for aesthetic purposes, e.g., flow.

The dance does not strictly repeat, maybe different global round constants called out on the fly and used in the swing computation.  Or, different rounds correspond to different dances, where people start the next dance exactly where they ended the previous dance.  You can't leave, though you can have a substitute to take your place.

No comments :