On another post [Christmas Secret Maker], we’re organising a Secret Maker.
As part of that, we need to select which person makes for which other, and Beth (@beth) asked me to organise the random part.
Be warned it is ridiculously overengineered for what’s required for the Secret Maker, but it was a little piece of cryptographic fun so I thought I’d write it up as a “project”.
The problem: we will have an unknown number N of members joining up. We want to “shuffle” them into an order so that person 1 makes something for person 2, who makes something for person 3, and so on up to person N who makes something for person 1.
The shuffle must be:
- Random
- Secret
- Resilient to gaming or tampering
The solution
I made some random shuffles for any number of people (up to 200). Each contains a number of different shuffles R.
For example, here are two shuffles for three makers:
Shuffle 1: 3 , 1, 2.
Shuffle 2: 2, 1 , 3.
We need to use a mathematical function called a hash (skip this para if you know what they are). A hash is a function which turns a file of any kind and any size into a random-looking number. It’s extremely easy to calculate the hash of any given file, and extremely difficult to make a file with any particular hash. There are dozens of different kinds of hash function. “Extremely difficult” means no one knows how to do it in general, and this is used in basically all the encryption and banking of the world. Exactly how hard “extremely” is depends on the mathematics of the day and how powerful computers are at any given moment. Yesterday’s impossible might be today’s possible and tomorrow’s easy. We are using the hashes called ‘SHA256’.
Step 1: We generate M sets of shuffles of N makers and store them
Step 1a: We publish the “precommitment hashes” of those shuffles at date T0 (ignore this for a moment)
Step 2: We collect the list of makers up to date T1.
Step 3: At date T1 we know how many makers are in the game (N).
Step 3: Agent 1 chooses are random number R from 1 to M and another Q from 1 to N
Step 5: We find the hashes of the home pages of each maker
Step 6: We order all the makers according to the hashes and rotate so maker Q is now maker 1
Step 7: We use shuffle R for N makers
Step 8: Agent 2 can see the shuffles and sends each maker a message "Dear Maker X: You have been selected at random to secretly make a thing for Maker Y"
Step 9: At date T2 we go round and each maker gives their gift to their recipient.
Step 10: Agent 2 publishes the list of shuffles, which will match the precommitment hash at 1a.
Agent 1 is Beth; Agent 2 is me. Just for illustration, her profile hash (at the moment) is d87e, mine is f70c, Dermot’s is fd5f, and so we’d be in that order: Beth=1, me=2, Dermot=3. Suppose Agent 1 picks Q as 2 and R as 1. As Q is 2, we rotate so now Me=1, Dermot=2, Beth=3. As R is 1 we use “shuffle number 1” (3, 1, 2) so Beth makes for me who makes for Dermot who makes for Beth.
(In reality these hashes are 64 characters long, but I truncated them just for illustration.)
Secrecy is provided against everybody except Agent 2 at step 8, or if agents collude or if makers publish.
Antitampering is provided fully because: 1) Agent 1 can control the ordering by choosing R and Q, 2) Agent 2 can control the ordering by choosing the shuffles in the first place (but tampering will be evident after the step 10), 3) Any maker can reorder the list by changing their discourse profile in any way (a post, a login, a comment). Because any maker or agent can completely reorder the list no one can cheat.
The “precommitment hashes” are hashes published before an event. In this case, I’ll publish the hashes of the shuffle files today (7 Nov) … after everything is done in December I’ll publish the actual file of shuffles for N makers. You know I didn’t change the file in between because it will have the hash I posted today, and no one knows how to make a file with a given hash.
Just to repeat, this is just a spot of fun as how to solve a cryptographic problem as I’m sure it’s hardly necessary for our Secret Maker.
Kind regards to all,
Jonathan.
M is chosen as 6, so there are 6 shuffles in each file, named for how many makers, ie the first one is for ten makers. These pre-commitment hashes (up 30 makers, will publish more if list grows lots):
359744cdbcf9c5d673afe554cb42a733dcc6f6bad5539c60cf94e0ef7bf04b9c shuffle-010
010763dfa48c49f7cd759ddf56ce1161e3c4cff483a15ceb2c32d66725c30620 shuffle-011
08ae83aa12a8a8f73495795037a71e800a926fc4c272f4a2f51f878f47068900 shuffle-012
f5f22d657c752e629391f57fc932ed57b56a2ef7c8dbfec1acf485fe031d6138 shuffle-013
dc46c27aa3b09dd5b740d4daf0df5a0b939acdcbbfeed97d36c50ab1a222fde5 shuffle-014
315a53f39403caec84ae35b636d1481402558ee63f7e6ac557c65cc902b1504b shuffle-015
5fbbf354365c44445d312a6c3a777e8613391c361086234cc8aa1f94e93f6255 shuffle-016
a7471a01aedc469f503465cf48707e02c270874077182f61039e9bd5083132d7 shuffle-017
b5f6c1d0a5e863b98bc374bb51cf090b7ff98f214ca6448f006f9d5798e83fbd shuffle-018
539bbbdd42dc02c437bc41f9b0739aed88ad4ff12d315496f73eee0001cd9f29 shuffle-019
6317267a6f917e32758f4428f0f6eece949feffdfeefcc463d17018df5fb513c shuffle-020
42d068e3ee4139935d90061c382b767b427d156b0193735f48e8bb45394a3179 shuffle-021
bb7e239aa537b294b3b2b88abaef28bffe58cbb603928d8f29e0f5e9b8d5b7ff shuffle-022
654d4fc56c1082e6a5073a42c15fc97b9c12296c08ce35ef5cb160e20d32cafb shuffle-023
1400afbceb268fd480c818170dd5f6b6dab19568b6b0132921123ad3baeec252 shuffle-024
a52629ca8ce97f75da9f38db6c265f63ae1c8f4111731179c853072a96c57e7a shuffle-025
5177322281f7d220e9bc29f7bf8ec6db1e177d8faaba8e9d19c0d7fd98e87d7b shuffle-026
228fc6249ede1a1e55ba8d09de53a8e41bed4acf7eaab9f86c5003146c426914 shuffle-027
cbf29d3682aaf8489dc9e61ae8115fb3d84c8f3c1f230717758d5d20fd1231db shuffle-028
59eb6c09413a869fb81c9c61817c94f9e80804d24a914e33d22a69467a7fb14f shuffle-029
2ecb4855cb7e3376c9bc33ffeab7a830ff197fa34e568a4a6e4ee6f53e65e92a shuffle-030