1

It is interesting to read about the random number generation problems in the last USA conscription. If, for the same purpose, we need a random permutation of the 366 birthdays, what should the president do in the future?

It would be nice if the average Joe did not need to trust any people, but that can get expensive, and at the end of the day, there always seems to be some trust involved. There are many other important factors, but listing them all is difficult and actually clouds the problem, so I'd simply like to know what you would ultimately want done in your country.

Some potential options:

  1. Televise (with live witnesses) same drum selection method used in 1970
    • Using #3 below for the loading order to generalize the 1970 method
  2. Televise (with live witnesses) repeated machine-rolling of dice
    • E.g., rolling four distinguishable dice gives 1296 outcomes (366*3+198, so most outcomes specify the first birthday for the sequence while 198 outcomes cause a redo, and so forth; this is my personal trusted favorite despite being ugly and being hard for Joe to understand)
  3. Summing random numbers from separate trustworthy people/companies
  4. Cryptographic generation where anyone can contribute a seed
    • Details are important (I worry about DDoS attacks and, depending on Joe, cryptographic methods can be hard to trust, and can even be mistaken)
  5. Your idea (I'd rather hear new proposals than problems with my options)

The correct answer I choose here will simply be the method I feel is best for the country. #1 above might win in the end. I don't need to reinvent the wheel.

  • Notice that the issue here is not a lack of randomness (people are born randomly, so the implication that it's necessary to randomly choose dates to ensure "fairness" is ludicrous on the face of it). Rather, the issue was perceived lack of fairness, in an ordeal that everyone had very low regard for. You can improve the RNG, but that won't keep people from finding other reasons to hate a Draft. – gowenfawr Oct 27 '16 at 1:21
  • @gowenfawr The randomness prevents anyone specific from being chosen out for conscription. – Macil Oct 27 '16 at 1:32
  • @AgentME if that were the case, then simply calling "January 1! January 2! January 3!" would be sufficient - no one specific, you see, is being chosen out for conscription; just the people who happened to be born on those days. There is no relation between those three sets of people. – gowenfawr Oct 27 '16 at 1:42
  • @gowenfawr: people are not born randomly: livescience.com/32728-baby-month-is-almost-here-.html – dandavis Oct 27 '16 at 3:22
  • 2
    @gowenfawr If I were corrupt, I hated someone born on January 2, and I had friends born late in December, then I might argue strongly for your scheme of starting on Jan 1. It doesn't matter that people had their birthdays assigned somewhat randomly in the first place. It matters that people's birthdays may be known and the person picking the scheme could know or be influenced by people affected. – Macil Oct 27 '16 at 19:54
1

The method I would suggest is to use these methods to generate a key that is used to generate a sequence. Then have some extremely complex algorithm that takes days to execute to generate the birthday from the sequence. This ensures that the value can't be monkeyed with by whoever makes the last contribution to it.

For example, a dozen well-known people could be asked to pick a number from 1 to 1 million at the same time. The numbers would be concatenated in base 10 and the result made public immediately. Then that number would be hashed with a memory-hard hashing algorithm billions of times (the number pre-determined to be doable in a week or so but not practical to do in less than a day by any adversary). The hash would then be mapped to the birthday.

If you want to ensure that anyone can confirm that the right birthday was given and the week-long process wasn't monkeyed with, a small change fixes this. Instead of hashing billions of times, hash once. The resulting hash is then used as a private key that is brute forced to find the corresponding public key in a cryptosystem just easy enough for this to be possible. The birthday is derived from the public key. Anyone can confirm that the correct public key was revealed when the brute forcing is done.

  • This gives good details and falls within my #4. But, I don't really like the last paragraph because brute-forcing speed scales with the number of computers, so if my adversary "makes the last contribution", I worry that he might have already checked a few potential outcomes on his millions of computers (compared to the system's one computer to keep costs down). Repeated hashing is better because it does not have this speed scaling. – bobuhito Oct 27 '16 at 1:55
  • I bet it's possible to come up with an algorithm that has (at least some of) both properties, but I don't know of one. – David Schwartz Oct 27 '16 at 2:27
  • Also, I think the state of this computation (and the size of the individual numbers submitted by each of the 10 people) would need to be numbers from 1 to roughly 10^100 to give full control of the possible permutations. That's still fine, but IMHO the original #1 looks better. – bobuhito Oct 28 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.