Cryptography and Computer Security – Anna Lysyanskaya, Brown University
iSpeech
Cryptography and Computer Security
Anna Lysyanskaya, Brown University
Cryptography is the mathematical study of how to protect communication and computation against adversarial behavior. Unlike many other branches of computer science, cryptography must be abstract and mathematical, rather than empirical, in nature. It is impossible to empirically demonstrate absence of attacks: just because a particular attack fails, it does not mean that another attack cannot succeed. Instead, cryptographers give mathematical definitions of security for a particular task (say, encryption), and a cryptographic system must be proven secure under this definition.
Such a proof of security often boils down to demonstrating that a particular computational task is impossibly hard, and so no adversary will be able to carry it out. Unfortunately, given the current state-of-the-art in theoretical computer science, we are unable to prove such statements: a proof of security of a public-key cryptosystem would immediately resolve the most important open problem in computer science, that is, the P vs. NP problem. Therefore, cryptographers settle for proofs of security that assume that certain computational tasks (for example, finding the prime factorization of large integers) cannot be completed in a reasonable amount of time. Usually, a proof of security would demonstrate how an adversary who breaks the security of the cryptographic system at hand could be exploited to solve an impossible computational problem.
Armed with this methodology, cryptographers have been able to give algorithms for seemingly impossible scenarios. Notable examples include:
• Public-key encryption, where Alice can send an encrypted message to Bob, even though she has never met him before, she only has access to his public information
• Zero-knowledge proofs that allow Alice to prove to Bob that she knows a solution to a computationally hard problem (for example, a Sudoku puzzle) without revealing this solution
• Secure multi-party computation that allows several participants (for example, voters in an election) to jointly compute any function of their private inputs (for example, they can compute the outcome of the election) without revealing these private inputs (so they don’t reveal anyone’s private vote).
So why is it that, even though we have these great cryptographic algorithms for very sophisticated tasks, our computers and networks are so vulnerable to attacks? Unfortunately, it is not enough to have good algorithms; care must be taken when implementing them. Additionally, a lot of the computer security problems plaguing us today stem from the use of operating and network systems not designed, implemented and debugged with the worst-case scenario in mind.
Further reading:
• Lecture notes and handouts from Ron Rivest’s course “6.875: Computer and Network Security” at MIT: http://courses.csail.mit.edu/6.857/2008/lecture.html
• Oded Goldreich. Foundations of Cryptography. Cambridge University Press.
source
Gloss