Alice and Bob want to play a card game over the internet. They don't want to use a third party because Eve may be able to compromise the third party and read or rearrange the deck as they play.
Because neither Alice nor Bob will be able to resist temptation, they need a way for both of their computers to agree on a deck order without knowing what that deck order is. While they play, they need a way to "draw" a card and update both computers to a new deck while only showing the player who "drew" the card what the card is.
Is there a way for this to happen, or is it impossible?
Why are Alice and Eve pretending they understand card games?
Is it the attention, or did they watch BBT and think being nerdy is cool now?
>>46139525
jfdslkfjsd;ldjskjf
>>46139557
Oh! Guys, I caused a tumblrina to have a fake panic attack! What do I win?
>>46139525
Congrats. Next time someone complains about SJWs and feminism being worse than redpill cockeaters like you, I'm showing them this post.
>>46139595
>Cockeaters
Whoa, now, don't go calling people a faggot like that, that's a SIN. You realize that sends you straight to hell, right? Oh wait, you're already going there. Silly me!
>>46139525
If you prefer you can call them Adam and Steve while attempting to answer the problem.
>>46139595
Thats sexist you white male ape.
>>46139794
But it's Adam and Eve, not Adam and Steve, you disgusting abomination.
>>46139468
Comedy aside... I don't see how this is a question.
There's nothing about software that requires it show its work to its user. So, say Alice is listen host and client, and Bob is a dedicated client, Alice generates deck, sends it to Bob's computer, neither computer showing the deck to either user. Each client's computer only shows their own card and tells the host system the card was drawn.
As this is the core principle through which 90% of online games operate, I fail to see where the problem lies.
Unless Bob accuses Alice of hacking, but let's face it, women can't actually hack.
>>46141238
Either one could be running some sort of debugger program and reading the memory where the cards lie, or even just using Wireshark to read the cards as they come in. Is there a way to prevent that, so that even if both players were good enough at computers to do this, neither one would be able to cheat?
>>46141507
A third computer that only sends each person their card and no other information?
>>46141691
That would be a third party, and that would be against the rules.
>>46139468
I don't think it's impossible, but It's certainly a high-level encryption question.
I've done something similar by creating an algorithm for calculating the product of three numbers, distributed across 3 computers, such that no computer knows the real inputs, but still produces the correct input.
>>46139468
Alice's computer has a list of all cards in the deck, in a random order, each encrypted with a hash value only Bob's computer has. Bob's computer has a list of the order in which cards will be drawn, with a hash value for each. When Alice draws a card, she asks Bob for the next draw. Bob then sends that line and the hash value. When Bob draws a card, he tells her the line, and she sends over that line from her program.
>>46139468
Oh yeah, I use a program for that all the time. I think it's atwww.GetNewFriendsThatDon'tActLikeChildren.au/tism
>>46139468
Using a moderately low level language, create a program that constructs a deck and has functionality allowing for a hand of cards, a discard from hand function, and a discard from deck function. All discards are blind, and the game keeps a counter of the number of discarded cards.
The program asks for a seed at startup and both players use the same seed, chosen randomly at the beginning of the game, to sync up their decks.
Past that it's honor system and coordinating who is dealt the first card. Ex. Alice is dealt first, so she draws a card, discards from deck, etc. and Bob discards from deck, draws, etc.
Assuming 5-card draw, or similar, when a player wants more cards, they declare it to their opponent so they can discard from the deck.
At the end, both players screenshot and send their final hand. Or start up a camera and video their screen to the other player.
Also there's no situation in which you will be satisfied with a solution, you will always poke holes in it.
>>46141507
There's memory encryption and hashing and the like, but nothing is entirely unhackable (regardless of what claims the FBI may make about iPhones). Particularly true if either of them has the source code for the program in question.
For anyone but the most determined and elite kings of hackers, however, such measures usually suffice.
>>46141691
I suppose Eve comes into play at that point. While it's true, one or the other of them can have a closed system, the data from that system still has to be transmitted, and the owner could interfere with that process.
>>46141997
>there's no situation in which there are no holes
Or better yet
>I cannot come up with a situation in which there are no holes
>>46141997
That won't work. Both players can see the next card by just generating the next number with the seed.
>>46141930
I guess this would work, though It's not particularly fanciful. At the start of the game, Bob generates keys, and encrypts the cards, sends them off to Alice, who then shuffles them, and Bob creates and shuffles his own the draw list.
>>46142055
This isn't a puzzle anyone can solve, this requires a certain level of knowledge in a particular subject.
At that point it's not a logic puzzle, it's a question that comes up in someone's job -or on an exam, since I'm sure that this is solved already and I can look it up.
>>46142147
>It's not particularly fanciful
It's programming, what do you want?
>>46141956
>what is a thought experiment
So if these two people are hardcore enough hackers to do shit like sniff packets to get the deck information, how about they get a physical fucking deck and play via some sort of video chat.
Still a pain in the ass to set up how to keep the host from getting the other person's card info, but since these two are apparent tech wizards, it may well be the only way.
>>46139829
At least I'm not a N.a.p.a. Faggot Like you
>>46142194
Well it can happen, and it's been done.
But it isn't absolutely unhackable - various methods have been used, and they've all been found vulnerable to various degrees at one or more stages.
It's more of a cryptography question - though adding the fact that a computer is doing the shuffling overcomplicates matters.
However, leaving all that aside, assuming the game involves *discarding* cards, each can still, with increasing accuracy, predict the next card, based on the cards already played, and that is impossible to get around - at least, not without inflicting brain damage on the players, or having the computer cheat...
Before play: each player randomly generates 52 keys, one for each card, and hashes each one while keeping them in order. Each player encrypts each card with its key. Both players now have a deck of encrypted cards from Ace of Spades to King of Hearts.
To shuffle: each player randomly selects a large number, then shuffles their deck (and the hashes of the keys) that number of times, using the same shuffling function as the other player. For example, Alice performs shuffle(deck) 492447 times, and Bob performs shuffle(deck) 92742 times. Each player now has a shuffled deck, but they're not in sync. They now send each other their decks (but keep a backup copy of their decks with their keys). Alice shuffles her copy of Bob's deck (which has been shuffled 92742 times) the same number of times she shuffled her own deck (492447 times, for a total of 585189 times), and Bob does the same to his copy of Alice's deck. Both decks are now in the same order, but neither player can tell what that other is.
To deal: When Alice draws a card, she moves the top card from her copy of Bob's deck to her hand and asks Bob to send the top card of her deck back to her. Bob sends the top card of his copy of Alice's deck over and puts a copy in Alice's hand on his machine (along with the key). Bob doesn't know what Alice's new card is, but Alice can decrypt and read what card she just drew. When Bob draws, the roles are reversed. Both players keep track of who drew which card in order.
To play: When Alice wants to play a card, she sends over her encrypted card and the key to decrypt the card. Bob can verify that Alice has the card she claims to be playing (it's in his own copy of her hand), and that the key corresponds to the card she sent (its hash would match the one attached to the card). Bob then decrypts the card and is up to date with what Alice played.
Does this work/even make sense?
>>46142418
They may also be such geniuses that they can simply count cards - what ya gonna do then, eh?
>>46142475
Not let them in my casino, but that doesn't really have anything to do with them wanting to play a card game.
There's a difference between tracking the probabilities of upcoming cards and peeking at the deck.
>>46142452
>each can still, with increasing accuracy, predict the next card, based on the cards already played
You mean card counting? Since that's a real problem with playing actual cards, it wouldn't be an issue in a perfect solution here (assuming it is in fact impossible to get around)
>All the players so much of a bunch cheating asshats with no will power
Why go through so much trouble in the first place?
>>46142514
Well that's kind of a point, regardless of fancy encryption technology over the internet, or a simple face to face old fashion deck of cards, they can still cheat, as the system itself is too simple.
Similar to how, regardless of how much an insane genious your opponent might be, you can always beat them at Tic-Tac-Toe, if you go first.
I suspect the question, however, is IT oriented, and is supposed to lead you to the classic hash-deck solution that is the tech behind various "secure" internet transactions already, and simply ignore the fact that it's possible to hack such systems. ...and just assume Alice and Bob are normal schmucks, rather than super hackers with unlimited time and determination at their disposal.
>>46141930
Wait, no, this solution is incorrect. It assumes that Bob somehow knows information about the order, and can send the correct line/hash combination for knowledge he shouldn't have.
>>46142462
One of the players could just shuffle their own deck 585189 times and know the exact order.
Remember that in these kinds of problems, information cannot be removed from a computer, only added.
>>46142658
It's a fucking logic puzzle. It's like asking why Tom-the-10-year-old wants to buy 32 apples and 14 bananas.
>>46142664
Any competent player two can always tie a game of tic tac toe. There are no plays player one can make which guarantee a win.
>>46142739
>It's a logic puzzle
No, it's a programming puzzle, and a tediously useless one at that. Take it to /g/ or /sci/.
>>46142664
>just assume Alice and Bob are normal schmucks, rather than super hackers with unlimited time and determination at their disposal.
Then you don't need any encryption or hashing at all. You just need the software not to show the user the damned deck or the other player's card. Wa'lah, problem solved with a Visual Basic GUI.
https://www.youtube.com/watch?v=hkDD03yeLnU
>>46142739
>shuffle their own deck 585189 times
How would they get that number though? They know how many times they themselves shuffled, but not the other player. They could have shuffled 92742 times, they could have shuffled 72841 times, they could have shuffled 50 times, they could have left the order alone.
>>46142846
>Wa'lah
>>46139468
Yes, it's possible.
Webcam showing cards
Bob shuffles deck, deals cards face down in front of Webcam.
Alice does the same.
Alice is shuffling deck provided by Bob, she has to shuffle on Webcam and vice versa
Bob and Alice marked their own cards - so only Alice knows list of her cards, and only Bob knows his symbols
So basically cards have a key value
Players have a list correlating key value to virtual card.
Both players can't cheat because they have no idea which combination of symbols produces which hand on other player list.
No way to cheat on the fly.
Change list after every game.
Basically one time pad encryption
Downside? They both have separate decks, so only such games might be played.
>>46142901
The algorithm says that they each shuffle a total of n+m times; n before they trade, m after. They each need to know both n and m, else they cannot sync.
>>46142846
Boring solution.
>>46142846
It's "voilà" you barbarian.
>>46142931
>>46143015
Obviously you've never been to Paris, the City of Lights.
>>46143014
>Boring solution
Ergo, the best.
>>46142846
>Wa'lah
what does this even mean
>>46143014
Alice shuffles her deck n times and sends it to Bob. She then receives Bob's deck and shuffles it n times.
Bob shuffles his deck m times and sends it to Alice. He then receives Alice's deck and shuffles it m times.
Alice only knows what n is, and Bob only knows what m is, but they both end up with decks shuffled n+m times.
>>46143095
I'm a goddamned idiot, sorry.
>>46143088
I dunno, but it seems sinister.
>>46143114
Happens.
>>46143014
>>46143095
Corrected version
Alice shuffles N times, Bob shuffles M times.
They trade decks, and Alice shuffles N times, Bob shuffles M times.
Both decks have been shuffled N+M times.
>>46139468
Trusted server keeps track of the decks. Fuck, why is this so hard?
>>46143151
I tried to structure the post to make it as unambiguous as I could that Alice only needs to know N and Bob only needs to know M
>>46143177
>They don't want to use a third party
>>46139468
Fuck off to /g/.
>>46139468
You know, if Eve gets between Alice and Bob, this normally IS a compromising situation. But if the two both consent to being compromised by Eve at the same time, it can be a way more exciting and pleasurable experience than some stupid card game.
>>46139557
...I think this may be ciphertext.
I'm on the case!
>>46143014
What is a shuffle?
Is the shuffle operation transitive?
How do they update the information about which card is removed from the deck without giving away which card has just been drawn?
>>46139468
There is no way to be absolutely sure that cheating is impossible, but this will make cheating both extremely difficult and extremely unlikely.
Alice and Bob each generate a public/private key pair and exchange public keys (this is a seperate problem which has been solved in numerous ways).
1. When Alice wants to draws a card, she uses her private key to sign a timestamp, which is passed to Bob.
2. Bob adds their own timestamp, plus a random number token and signings all four fields together. Call this the 'Draw Token' - Two timestamps, a random token, and two private-key signitures which can be verified with the appropriate public keys. The 'Draw Token' should be a completely unpredictable number/string for both parties.
3. Alice generates a (large, 64+ bit) random number, encrypts that number together with the Draw Token using her private key, then signs the resulting string. This signiture string is passed to Bob.
4. Bob also generates a (large, 64+ bit) random number, encrypts that number together with the Draw Token using her private key, then signs the resulting string. This signiture string is passed to Alice.
5. Once both Alice and Bob have something to verify the other person's random number against, they exchange encrypted random numbers. The two random numbers are added together, then a modulo for the remaining cards in the deck creates a purely-random number.
The cards don't even need to be shuffled (a sorted deck results in equally random card draws), and after the final exchange both parties should have all they need to figure out which card is drawn without further data exchange.
>>46139468
From https://en.wikipedia.org/wiki/Mental_poker#Shuffling_cards_using_commutative_encryption
The algorithm (using a commutative encryption scheme)
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.
Alice picks an encryption key A and uses this to encrypt each card of the deck.
Alice shuffles the cards.
Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
Bob shuffles the deck.
Bob passes the double encrypted and shuffled deck back to Alice.
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.
Alice picks one encryption key for each card (A1, A2, etc.) and encrypts them individually.
Alice passes the deck to Bob.
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.
Bob picks one encryption key for each card (B1, B2, etc.) and encrypts them individually.
Bob passes the deck back to Alice.
Alice publishes the deck for everyone playing (in this case only Alice and Bob, see wikipedia on expansion though).
The deck is now shuffled.
(continued in next post)
>>46145441
During the game, Alice and Bob will pick cards from the deck, identified in which order they are placed in the shuffled deck. When either player wants to see their cards, they will request the corresponding keys from the other player. That player, upon checking that the requesting player is indeed entitled to look at the cards, passes the individual keys for those cards to the other player. The check is to ensure that the player does not try to request keys for cards that do not belong to that player.
Example: Alice has picked cards 1 to 5 in the shuffled deck. Bob has picked cards 6 to 10. Bob requests to look at his allotted cards. Alice agrees that Bob is entitled to look at cards 6 to 10 and gives him her individual card keys A6 to A10. Bob decrypts his cards by using both Alice's keys and his own for these cards, B6 to B10. Bob can now see the cards. Alice cannot know which cards Bob has because she does not have access to Bob's keys B6 to B10 which are required to decrypt the cards.
The encryption scheme used must be secure against known-plaintext attacks: Bob must not be able to determine Alice's original key A (or enough of it to allow him to decrypt any cards he does not hold) based on his knowledge of the unencrypted values of the cards he has drawn. This rules out some obvious commutative encryption schemes, such as simply XORing each card with the key. (Using a separate key for each card even in the initial exchange, which would otherwise make this scheme secure, doesn't work since the cards are shuffled before they're returned.)
Depending on the deck agreed upon, this algorithm may be weak. When encrypting data, certain properties of this data may be preserved from the plaintext to the ciphertext. This may be used to "tag" certain cards. Therefore, the parties must agree on a deck where no cards have properties that are preserved during encryption.
>>46139468
Just use cockatrice or something and stop being spergs. Can't you trust your friends at all? Fuck.
Do your own homework ffs
>>46139468
Play in person, you spergs.
Failing that, have a webcam trained on the deck at all times.
There's a difference between making a program that solves a problem and creating pointless problems out of thin air to solve.
>>46139468
>Computers
>not solving it for a general purpose situation using letters or notes.
I tell Alice and Bob to install Tabletop Simulator on Steam.
>>46146842
Which introduces a third party that may or may not be trusted/corruptible, and thus doesn't follow the requirements.
That being said, it is the more practical option, and what a sane person would probably do.
>>46146436
>play in person
What if they're on the other side of the world?
>webcam trained on the deck
Which the host definitely can't see, right?
>>46139854
Adam and Will.Free Will.
