33
submitted 2 months ago by swordgeek@lemmy.ca to c/askscience@lemmy.world

OK, I had a hard time coming up with a single sentence title, so please bear with me.

Let's assume I have a computer with a perfect random number generator. I want to draw from a (electronic) deck of cards that have been shuffled. I can see two distinct algorithms to accomplish this:

  1. Fill a list with the 52 cards in random order, and then pull cards from the list in sequence. That is, defining the (random) sequence of cards before getting them. This is analogous to flipping over cards from a the top of a well-shuffled deck.

  2. Generate a random card from the set that hasn't been selected yet. In other words, you don't keep track of what card is going to come up next, you do a random select each time.

Programattically I can see advantages to both systems, but I'm wondering if there's any mathematical or statistical difference between them.

you are viewing a single comment's thread
view the rest of the comments
[-] tal@lemmy.today 4 points 2 months ago* (last edited 2 months ago)

I mean, you can get the same sequence of cards, as long as your mechanism used to select a card in #1 is the same as in #2. It's just like doing #2 52 times in advance and then recording the results.

There are certain reasons that you might want to do #1 that don't relate to the sequence of cards coming up. There are certain problems involving multiple untrusted parties where it can be advantageous to be able to prove that you have not fiddled with the card order after the initial "deal"; one way to do this is to generate and then transmit an encrypted list of cards, then later send the decryption keys.

https://en.wikipedia.org/wiki/Mental_poker

Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's flipping a coin over a distance, Yao's Millionaires' Problem, and Rabin's oblivious transfer.

The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?" (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.)

An algorithm for shuffling cards using commutative encryption would be as follows:

  1. Alice and Bob agree on a certain "deck" of cards. In practice, this means they agree on a set of numbers or other data such that each element of the set represents a card.
  2. Alice picks an encryption key A and uses this to encrypt each card of the deck.
  3. Alice shuffles the cards.
  4. Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
  5. Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
  6. Bob shuffles the deck.
  7. Bob passes the double encrypted and shuffled deck back to Alice.
  8. Alice decrypts each card using her key A. This still leaves Bob's encryption in place though so she cannot know which card is which.
  9. Alice picks one encryption key for each card (A1, A2, etc.) and encrypts them individually.
  10. Alice passes the deck to Bob.
  11. Bob decrypts each card using his key B. This still leaves Alice's individual encryption in place though so he cannot know which card is which.
  12. Bob picks one encryption key for each card (B1, B2, etc.) and encrypts them individually.
  13. Bob passes the deck back to Alice.
  14. Alice publishes the deck for everyone playing (in this case only Alice and Bob, see below on expansion though).

The deck is now shuffled.

this post was submitted on 23 Sep 2024
33 points (94.6% liked)

Ask Science

8672 readers
3 users here now

Ask a science question, get a science answer.


Community Rules


Rule 1: Be respectful and inclusive.Treat others with respect, and maintain a positive atmosphere.


Rule 2: No harassment, hate speech, bigotry, or trolling.Avoid any form of harassment, hate speech, bigotry, or offensive behavior.


Rule 3: Engage in constructive discussions.Contribute to meaningful and constructive discussions that enhance scientific understanding.


Rule 4: No AI-generated answers.Strictly prohibit the use of AI-generated answers. Providing answers generated by AI systems is not allowed and may result in a ban.


Rule 5: Follow guidelines and moderators' instructions.Adhere to community guidelines and comply with instructions given by moderators.


Rule 6: Use appropriate language and tone.Communicate using suitable language and maintain a professional and respectful tone.


Rule 7: Report violations.Report any violations of the community rules to the moderators for appropriate action.


Rule 8: Foster a continuous learning environment.Encourage a continuous learning environment where members can share knowledge and engage in scientific discussions.


Rule 9: Source required for answers.Provide credible sources for answers. Failure to include a source may result in the removal of the answer to ensure information reliability.


By adhering to these rules, we create a welcoming and informative environment where science-related questions receive accurate and credible answers. Thank you for your cooperation in making the Ask Science community a valuable resource for scientific knowledge.

We retain the discretion to modify the rules as we deem necessary.


founded 1 year ago
MODERATORS