4 ms·

Does anyone have some examples of use cases for timestamped random entropy values?

by xd1936 2y ago

CaliforniaKarl 2y ago
https://csrc.nist.gov/CSRC/media/Presentations/usages-of-public-randomness/images-media/20191106-NIST-ITL-Science-Day-poster-Beacon--ts-20191118.pdf https://csrc.nist.gov/CSRC/media/Presentations/usages-of-pub... has some.
rainsford 2y ago
The NIST site has a few, but basically it's useful any time you need to randomly select things and prove your selection is really random. The idea is you commit to using a specific future beacon value in a particular way to do your random selection, so you can't game either your random value or the process to get the selection results you want. One example the paper gives is auditing an election by looking at a random sample of polling sites. Before the election, the government commits to using a specified algorithm to select polling sites to audit, with the random input coming from the first beacon value on the day after the election. This verifies prior to the election that the auditing will be random without revealing what polling sites will be audited (in fact there is no way for anyone to know that prior to the beacon value being published). The government can also use multiple independent beacons. Assuming not all the parties are colluding, this does a pretty good job demonstrating the auditing is random.
- whatshisface 2y ago
  There is a decentralized version of this, too: 1. Each party shares an encrypted string whose plaintext starts with, "I'm being honest about my key." 2. The parties share their keys and decrypt everyone else's strings. 3. The strings are concatenated and hashed to produce a number that no party can bias. This is a formalization of rock-paper-scissors, a protocol for generating fair random numbers that we may have used as kids.
  - 0cf8612b2e1e 2y ago
    I know nothing of encryption- is there significance to each party starting their string with an identical prefix?
    - whatshisface 2y ago
      That part is to stop them from choosing the decryption key after sharing the encrypted strings with the intended result of guiding the outcome of the hash. If the content of the strings was wholly random a participant would be able to claim that the gibberish resulting from using a key chosen later was what they had meant to encrypt in step one.
      - 0cf8612b2e1e 2y ago
        Ah, that makes sense. Thanks.
  - rainsford 2y ago
    That's true, although like with rock paper scissors, ensuring simultaneous sharing of the keys is hard. So whoever reveals their key "last" knows the outcome before the other participants, which can be bad depending on the application. Adding a random beacon value from a 3rd party to the game (say as an input to the hash in step 3) means all participants can learn the outcome at the same time and that the reveal time is known in advance. Of course now it's the 3rd party that knows in advance, but for many applications you can trust them to be disinterested in the result and you can use multiple independent 3rd parties for better security. An interesting property here is that with the old NIST beacon version, the beacon operator could actually change the result assuming the other parties in your construct reveal their keys before the beacon value is published (because NIST or whoever could just pick a beacon value that gives a particular result). However the new version includes a hash commitment in the current beacon for the next beacon, so participants could wait for that to be published, then share their keys now that the beacon operator can't change the next beacon value.

Does anyone have some examples of use cases for timestamped random entropy values?

by xd1936 2y ago

Does anyone have some examples of use cases for timestamped random entropy values?

https://csrc.nist.gov/CSRC/media/Presentations/usages-of-public-randomness/images-media/20191106-NIST-ITL-Science-Day-poster-Beacon--ts-20191118.pdf https://csrc.nist.gov/CSRC/media/Presentations/usages-of-pub... has some.

rainsford 2y ago

The NIST site has a few, but basically it's useful any time you need to randomly select things and prove your selection is really random. The idea is you commit to using a specific future beacon value in a particular way to do your random selection, so you can't game either your random value or the process to get the selection results you want. One example the paper gives is auditing an election by looking at a random sample of polling sites. Before the election, the government commits to using a specified algorithm to select polling sites to audit, with the random input coming from the first beacon value on the day after the election. This verifies prior to the election that the auditing will be random without revealing what polling sites will be audited (in fact there is no way for anyone to know that prior to the beacon value being published). The government can also use multiple independent beacons. Assuming not all the parties are colluding, this does a pretty good job demonstrating the auditing is random.

whatshisface 2y ago
There is a decentralized version of this, too: 1. Each party shares an encrypted string whose plaintext starts with, "I'm being honest about my key." 2. The parties share their keys and decrypt everyone else's strings. 3. The strings are concatenated and hashed to produce a number that no party can bias. This is a formalization of rock-paper-scissors, a protocol for generating fair random numbers that we may have used as kids.
- 0cf8612b2e1e 2y ago
  I know nothing of encryption- is there significance to each party starting their string with an identical prefix?
  - whatshisface 2y ago
    That part is to stop them from choosing the decryption key after sharing the encrypted strings with the intended result of guiding the outcome of the hash. If the content of the strings was wholly random a participant would be able to claim that the gibberish resulting from using a key chosen later was what they had meant to encrypt in step one.
    - 0cf8612b2e1e 2y ago
      Ah, that makes sense. Thanks.
- rainsford 2y ago
  That's true, although like with rock paper scissors, ensuring simultaneous sharing of the keys is hard. So whoever reveals their key "last" knows the outcome before the other participants, which can be bad depending on the application. Adding a random beacon value from a 3rd party to the game (say as an input to the hash in step 3) means all participants can learn the outcome at the same time and that the reveal time is known in advance. Of course now it's the 3rd party that knows in advance, but for many applications you can trust them to be disinterested in the result and you can use multiple independent 3rd parties for better security. An interesting property here is that with the old NIST beacon version, the beacon operator could actually change the result assuming the other parties in your construct reveal their keys before the beacon value is published (because NIST or whoever could just pick a beacon value that gives a particular result). However the new version includes a hash commitment in the current beacon for the next beacon, so participants could wait for that to be published, then share their keys now that the beacon operator can't change the next beacon value.