mikkorantalainen · December 25, 2024 16:54
diff --git a/secret-santa-algorithm-zero-trust.txt b/secret-santa-algorithm-zero-trust.txt
 Author: Mikko Rantalainen
 License: CC-0

 Here's an idea that should only require two rounds and all published data to anybody can be immediately public to whole group and published in any order and you only need a good enough hash to store passwords safely and a good enough one-way hash that changes a lot when input changes even by one bit. I'm using bcrypt and SHA-512 as an example but feel free to use any other algorithm:

 1. Everybody creates a new ASCII string that identifies them to the group. For example, email address would be okay.
 2. Everybody creates their own secret data as ASCII text string (e.g. UUID v4)
 3. Everybody concatenates the strings from step 1 and step 2 with a colon, which would result in their secret string of format "email:UUID"
 4. Everybody publishes bcrypt hash for the string generated in step 3. Everyone can freely select the salt and cost factors to match his or her expectations to make sure the private key cannot be decrypted during the secret santa selection process. Random max length salt and cost factor 13 should be good enough nowadays.
 5. Everybody publishes the string used to compute bcrypt hash.
 6. Verify that all the published strings match their respective bcrypt hashes.
 7. All the published strings are saved as a text file, each line separated by U+000D (UNIX line feed) and the last line also has the final U+000D.
 8. The generated file is sorted in ASCII order.
 9. SHA-512 hash is computed for the sorted file. This hash represented as ASCII hex string is represented as X below.
 10. The file is sorted again using SHA-512({X concatenated with the published line contents}) as the data to use as sort key for the line. Logically you sort the file using pseudo-random line id that depends on both the contents of all the original secret for that line and the contents of the line.
 11. Everybody buys a present for the next person on the list. The last person on the list buys a present for the first one on the list.

 As long as bcrypt or SHA-512 isn't broken, this will result in ordering where the ordering is affected by all secret data from all members of the group. And since everybody published their hashes before publishing the secrets the person publishing their data last cannot affect the ordering at will.

 And obviously you would write a small program to do all this so everybody can run the verification by themselves. In practice, you need two rounds:

 1. Everybody publishes bcrypt hashes.
 2. Everybody publishes their secrets.

 And both can be computed by the group member at once but must be published on two rounds. As long as you can keep your own secret unknown to the group until step 5, nobody else can force the final order for the list.

 And you could use even SHA-1 for the first round if the secret is long enough to make finding the preimage too hard in practice but bcrypt is better here because it's designed for specific use case to guard the secret when the hash is public.
	Author: Mikko Rantalainen
	License: CC-0

	Here's an idea that should only require two rounds and all published data to anybody can be immediately public to whole group and published in any order and you only need a good enough hash to store passwords safely and a good enough one-way hash that changes a lot when input changes even by one bit. I'm using bcrypt and SHA-512 as an example but feel free to use any other algorithm:

	1. Everybody creates a new ASCII string that identifies them to the group. For example, email address would be okay.
	2. Everybody creates their own secret data as ASCII text string (e.g. UUID v4)
	3. Everybody concatenates the strings from step 1 and step 2 with a colon, which would result in their secret string of format "email:UUID"
	4. Everybody publishes bcrypt hash for the string generated in step 3. Everyone can freely select the salt and cost factors to match his or her expectations to make sure the private key cannot be decrypted during the secret santa selection process. Random max length salt and cost factor 13 should be good enough nowadays.
	5. Everybody publishes the string used to compute bcrypt hash.
	6. Verify that all the published strings match their respective bcrypt hashes.
	7. All the published strings are saved as a text file, each line separated by U+000D (UNIX line feed) and the last line also has the final U+000D.
	8. The generated file is sorted in ASCII order.
	9. SHA-512 hash is computed for the sorted file. This hash represented as ASCII hex string is represented as X below.
	10. The file is sorted again using SHA-512({X concatenated with the published line contents}) as the data to use as sort key for the line. Logically you sort the file using pseudo-random line id that depends on both the contents of all the original secret for that line and the contents of the line.
	11. Everybody buys a present for the next person on the list. The last person on the list buys a present for the first one on the list.

	As long as bcrypt or SHA-512 isn't broken, this will result in ordering where the ordering is affected by all secret data from all members of the group. And since everybody published their hashes before publishing the secrets the person publishing their data last cannot affect the ordering at will.

	And obviously you would write a small program to do all this so everybody can run the verification by themselves. In practice, you need two rounds:

	1. Everybody publishes bcrypt hashes.
	2. Everybody publishes their secrets.

	And both can be computed by the group member at once but must be published on two rounds. As long as you can keep your own secret unknown to the group until step 5, nobody else can force the final order for the list.

	And you could use even SHA-1 for the first round if the secret is long enough to make finding the preimage too hard in practice but bcrypt is better here because it's designed for specific use case to guard the secret when the hash is public.