香港中文大学：《CMSC5719 Seminar》课程教学资源（讲义）Lecture 04 CRYPTOGRAPHY

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

里含 宜 IN TEN 星 MINUTES 净 星 含 净 里 净 里 里 里 7 平 牌 净 里含 里里造里生里注里注7

phhw ph dw wjh uxelfrq l know what he is up to！

phhw ph dw wjh uxelfrq I know what he is up to!

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

The foundations of cryptography 953081 ×603749 Is it really that hard? 575421700669 We can't say for sure, but many have tried and failed

The foundations of cryptography 953081 × 603749 575421700669 Is it really that hard? We can’t say for sure, but many have tried and failed