Andrej Bogdanov Chinese University of Hong Kong CRYPTOGRAPHY WHAT IS IT GOOD FOR? CMSC 57196 Feb 2012
CRYPTOGRAPHY WHAT IS IT GOOD FOR? Andrej Bogdanov Chinese University of Hong Kong CMSC 5719 | 6 Feb 2012
A model for encryption saopgpwnhx Alice nizpfkel3c Bob OK! ®P7 Eve Alice and Bob want to exchange messages but remain private to eavesdroppers
A model for encryption Alice Bob Alice and Bob want to exchange messages but remain private to eavesdroppers saopgpwnhx nizpfkel3c OK! ??! Eve
Bad news saopgpwnhx Alice nizpfkel3c Bob OK Eve impossible! Eve can simulate the states of Alice Bob and learn everything they know
Bad news Alice Bob impossible! saopgpwnhx nizpfkel3c OK! ??! Eve Eve can simulate the states of Alice & Bob and learn everything they know
The one-time pad Alice·● Bob want to say 10111001 10111001 he110=01101001 个 ⊕ 10111001 11010000 Alice and Bob share a secret key Bob can recover the message, but to Eve it looks totally random!
The one-time pad Alice 10111001 Bob want to say 10111001 hello = 01101001 ⊕ 10111001 11010000 Alice and Bob share a secret key Bob can recover the message, but to Eve it looks totally random!
Secret-key cryptography saopgpwnhx Alice nizpfkel3c OK Bob 10111001 10111001 Easy if they share a secret key ..but the key must be as long as all the messages they will ever exchange!
Secret-key cryptography Alice Bob saopgpwnhx nizpfkel3c OK! Easy if they share a secret key 10111001 10111001 … but the key must be as long as all the messages they will ever exchange!
Enter computation easy hard 953081 ×603749 hard? 575421700669
Enter computation easy 953081 × 603749 575421700669 easy hard? hard
The cryptographic revolution Assuming there exist digital tasks that are hard to reverse-engineer*we can do saopgpwnhx Alice nizpfkel3c Bob OK Eve public key encryption mental poker secure multiparty computation [Diffie-Hellman,Rivest-Shamir-Adleman] [Yao,Blum,Goldreich-Micali-Wigderson]
• Assuming there exist digital tasks that are hard to reverse-engineer* we can do The cryptographic revolution Alice Bob saopgpwnhx nizpfkel3c OK! ??! Eve public key encryption mental poker [Diffie-Hellman, Rivest-Shamir-Adleman] [Yao, Blum, Goldreich-Micali-Wigderson] secure multiparty computation