Dealing Cards with Cryptography (with Ron Rivest) - Numberphile
video description
Date: 2022-04-08
Related videos
Comments and reviews: 9
amihart
One thing he didn't mention was that when you do your squaring or multiplications, given how the modulo operator works, you can actually take the modulus every step of the way.
Q-11 mod p = Q(Q-5 mod P)-2 mod p
Q-5 mod p = Q(Q-2 mod P)-2 mod p
Q-2 mod p = QQ mod p
The reason this is important because it shows you that every step of the way, your result never actually exceeds -p-. This kind of efficient exponentiation only really works for modulo because your answer is always contained. If you tried to do something like this on a regular exponentiation problem with 100s of digits without modulo your answer would blow up to a size so big you couldn't store it anyways.
reply
One thing he didn't mention was that when you do your squaring or multiplications, given how the modulo operator works, you can actually take the modulus every step of the way.
Q-11 mod p = Q(Q-5 mod P)-2 mod p
Q-5 mod p = Q(Q-2 mod P)-2 mod p
Q-2 mod p = QQ mod p
The reason this is important because it shows you that every step of the way, your result never actually exceeds -p-. This kind of efficient exponentiation only really works for modulo because your answer is always contained. If you tried to do something like this on a regular exponentiation problem with 100s of digits without modulo your answer would blow up to a size so big you couldn't store it anyways.
reply
Haradan
Who puts the cards in the envelopes in the first place, and how do you stop them keeping track of which envelope is which? If you do some cryptography to put the cards in envelopes, won't the envelopes still have to all look different from one another, even after they're all locked?
1. I put all the cards in envelopes and lock them.
2. You lock all the envelopes with your lock.
3. You send me your hand with the locks on, and I take my lock off each one and send them back to you. I can't compare them with how they were when I last had them because they still have your lock on.
I think I just answered my own question. Nice!
reply
Who puts the cards in the envelopes in the first place, and how do you stop them keeping track of which envelope is which? If you do some cryptography to put the cards in envelopes, won't the envelopes still have to all look different from one another, even after they're all locked?
1. I put all the cards in envelopes and lock them.
2. You lock all the envelopes with your lock.
3. You send me your hand with the locks on, and I take my lock off each one and send them back to you. I can't compare them with how they were when I last had them because they still have your lock on.
I think I just answered my own question. Nice!
reply
Nick
I think there are two big omissions in this video. Can someone confirm or correct these?
1) In the locked envelope example, each player knows they got genuinely random cards but each card is still only known by one of the players. The example problem requires all players to end up knowing both hands, but this method doesn't accomplish that.
2) They're actually working with (Q-K) mod P)-J) mod P but skip right to (Q-K)-J) mod P. I take it that they're equivalent, but they don't say anything about it and instead focus on the much more basic idea that exponentiation is commutative. However, properties are critical to the example.
reply
I think there are two big omissions in this video. Can someone confirm or correct these?
1) In the locked envelope example, each player knows they got genuinely random cards but each card is still only known by one of the players. The example problem requires all players to end up knowing both hands, but this method doesn't accomplish that.
2) They're actually working with (Q-K) mod P)-J) mod P but skip right to (Q-K)-J) mod P. I take it that they're equivalent, but they don't say anything about it and instead focus on the much more basic idea that exponentiation is commutative. However, properties are critical to the example.
reply
CaesarsSalad
What guarantee does the second person have that the dealer encrypted 52 unique cards? And what guarantee does either person have that the other person used the cards the got from the envelope? In this game, if I were the dealer, I would give myself an unbeatable hand and hope that you don't pick any duplicates (in which case you would know that I was cheating. This gives me a higher than 50% chance to win one round.
I also think that Brady and Ron took unnecessary steps. Brady could just have send back 10 cards, 5 of them unchanged and 5 of them with his locks added.
reply
What guarantee does the second person have that the dealer encrypted 52 unique cards? And what guarantee does either person have that the other person used the cards the got from the envelope? In this game, if I were the dealer, I would give myself an unbeatable hand and hope that you don't pick any duplicates (in which case you would know that I was cheating. This gives me a higher than 50% chance to win one round.
I also think that Brady and Ron took unnecessary steps. Brady could just have send back 10 cards, 5 of them unchanged and 5 of them with his locks added.
reply
Ath
The original dealer into envelopes might have marked the envelopes. You can't even work around this by having Brady mail the initial empty, unlocked, envelopes, as Ron could mark them as he inserts the cards before initial locking.
Also you could optimise out the last 3 steps by -not- applying Brady locks to 5 of the cards when he initially receives the single-locked envelopes. He simply sends those single-locked cards back as Ron's hand at the same time he sends the rest double-locked for Ron to pick his hand.
reply
The original dealer into envelopes might have marked the envelopes. You can't even work around this by having Brady mail the initial empty, unlocked, envelopes, as Ron could mark them as he inserts the cards before initial locking.
Also you could optimise out the last 3 steps by -not- applying Brady locks to 5 of the cards when he initially receives the single-locked envelopes. He simply sends those single-locked cards back as Ron's hand at the same time he sends the rest double-locked for Ron to pick his hand.
reply
Flat
To my mind, one of the most beautiful things about RSA cryptography and its offshoots is that even when an exponent is thousands of bits long, it represents an actual precise count of something (the number of times the additive identity would have to be multiplied by a particular number to yield the result. While exponentiation isn't actually done via simple sequential multiplication, it is defined in such terms, and so it's neat to have such huge numbers actually have a concrete meaning.
reply
To my mind, one of the most beautiful things about RSA cryptography and its offshoots is that even when an exponent is thousands of bits long, it represents an actual precise count of something (the number of times the additive identity would have to be multiplied by a particular number to yield the result. While exponentiation isn't actually done via simple sequential multiplication, it is defined in such terms, and so it's neat to have such huge numbers actually have a concrete meaning.
reply
Arthur
Can Ron Rivest explain how you do those auctions? I see a basic way to do it, but how do you prevent a bidder from providing a specially encrypted bid which decrypts to two different bids depending on the key provided during unmasking. Since the bidder can control both keys and the cypher text it seems like this would be possible despite the complexity of finding keys for arbitrary cypher text.
reply
Can Ron Rivest explain how you do those auctions? I see a basic way to do it, but how do you prevent a bidder from providing a specially encrypted bid which decrypts to two different bids depending on the key provided during unmasking. Since the bidder can control both keys and the cypher text it seems like this would be possible despite the complexity of finding keys for arbitrary cypher text.
reply
Sean
I'd love a follow-up, who generates K and J? It can't be one party or it has the other party's Key. If it's a third party how do both parties know that the third party is authentic and not your opponent pretending to be a third party and giving you keys it would know? I know there's an answer to this because my passwords usually aren't hacked, but I'd love to see the whole process
reply
I'd love a follow-up, who generates K and J? It can't be one party or it has the other party's Key. If it's a third party how do both parties know that the third party is authentic and not your opponent pretending to be a third party and giving you keys it would know? I know there's an answer to this because my passwords usually aren't hacked, but I'd love to see the whole process
reply
Gwahli
A very interesting example that shows how important protocols are for computer security. Even though it's Ron Rivest and he uses RSA encryption as an example, this would work just as well with symmetric cryptography like AES for example.
Now as an exercise for the viewer: Extend this protocol to play texas-hold-em with 6 players at the table or maybe a round of bridge.
reply
A very interesting example that shows how important protocols are for computer security. Even though it's Ron Rivest and he uses RSA encryption as an example, this would work just as well with symmetric cryptography like AES for example.
Now as an exercise for the viewer: Extend this protocol to play texas-hold-em with 6 players at the table or maybe a round of bridge.
reply
Add a review, comment
Other channel videos
