Chapter 1IntroductionHistorically, cryptography arose as a means to enable parties to maintain privacy of the inform ationthey send to each other, even in the presence of an adversary with access to the communicationchannel. While providing privacy remains a central goal, the field h as expandeded to encompassmany others, including not just other goals of communication security, such as guaranteeing in-tegrity and authenticity of communications, but many more sophisticated and fascinating goals.Once largely the domain of the military, cryptography is now in widespread use, and you arelikely to have used it even if you don’t know it. When you shop on the Internet, for example to buya book at www.amazon.com, cryptography is used to ensure privacy of your credit card number asit travels from you to the shop’s server. Or, in electronic banking, cryptography is used to ensurethat your checks cannot be forged.Cryptography has been u sed almost since writing was invented. For the larger part of itshistory, cryptography remained an art, a game of ad hoc designs and attacks. Although the fieldretains some of this flavor, the last twenty-five years have brought in something new. The art ofcryptography has now been supplemented with a legitimate science. In this course we shall focuson that science, which is modern cryptography.Modern cryptography is a remarkable discipline. It is a cornerstone of computer and communi-cations security, with end products that are immin ently practical. Yet its study touches on branchesof mathematics th at may have been considered esoteric, and it brings together fields like numbertheory, computational-complexity theory, and probabiltity theory. This course is your invitationto this fascinating field.1.1 Goals and settingsModern cryptography addresses a wide range of problems. But the most basic pr oblem remainsthe classical one of ensuring security of communication across an insecure medium. To describe it,let’s intro duce the first two members of our cast of characters: our sender, S, and our receiver, R.(Sometimes people call these characters Alice, A, and Bob, B. Alice and Bob figure in m any workson cryptography. But we’re going to want the letter A for someone else, anyway.) The sender andreceiver want to communicate with each other.The ideal channel. Imagine our two parties are provided with a dedicated, untappable, im-penetrable pipe or tube into which the sender can whisper a m essage and the receiver will hear2 INTRODUCTIONSRAxxxxxxFigure 1.1: Several cryptographic goals aim to imitate some aspect of an ideal channel connectinga sender S to a receiver R.it. Nobody else can look inside the pipe or change what’s there. This pipe provides the perfectmedium, available only to the sender and receiver, as though they were alone in the world. It is an“ideal” communication channel from the security point of view. See Fig. 1.1.Unfortunately, in real life, there are no ideal channels connecting the pairs of parties that mightlike to communicate with each other. Usually such parties are communicating over some publicnetwork like the Internet.The most basic goal of cryptography is to provide such parties with a means to imbue theircommunications with security properties akin to those provided by the ideal channel.At this point we should introduce the third member of our cast. This is our adversary, de-noted A. An adversary models the source of all possible threats. We imagine the adversary ashaving access to the network and wanting to compromise the s ecur ity of the parties communica-tions in some way.Not all aspects of an ideal channel can be emulated. Instead, cryptographers d istill a few centralsecurity goals and try to achieve them. The first such goal is privacy. Providing privacy meanshiding the content of a transmission from the adversary. The second goal is authenticity or integ rity.We want the receiver, upon receiving a communication pertaining to be from the sender, to have away of assuring itself that it really did originate with the sender, an d was not sent by the adversary,or modified en route from the sender to the receiver.Protocols. In order to achieve security goals such as p rivacy or authenticity, cryptographysupplies the sender and receiver with a protocol. A protocol is just a collection of programs (equiva-lently, algorithms, software), one for each party involved. In our case, there would be some programfor the sender to run, and another for the receiver to run. The s en der’s program tells her how topackage, or encapsu late, her data for transmission. The receiver’s p rogram tells him how to decap-sulate the received package to recover the data together possibly with associated information tellingher whether or not to regard it as authentic. Both programs are a function of some cryptographickeys as we discuss next.Trust models. It is not hard to convince yourself that in order to communicate s ecur ely, theremust be something that a p arty knows, or can do, th at the adversary does not know, or cann otdo. There has to be some “asymmetry” between the situation in which the parties finds themselvesand situation in which the adversary finds itself.The trust model specifies w ho, initially, has what keys. There are two central trust m odels: thesymmetric (or shared-key) trust model an d the asymmetric (or public-key) trust model. We lookat them, and the cryptographic problems th ey give rise to, in turn.Bellare and Rogaway 3We will sometimes use words from the theo ry of “formal languages.” Here is thevocabulary you should know.An alphabet is a finite nonempty set. We usually use the Greek letter Σ to denotean alphabet. The elements in an alphabet are called characters. So, for example,Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is an alphabet having ten characters, and Σ = {0, 1}is an alphabet, called the binary alphabet, which has two characters. A stringis finite se quence of characters. The number of characters in a string is calledits length, and the length of a string X is denoted |X|. So X = 1011 is a stringof length four over the binary alphabet, and Y = cryptography is a string oflength 12 over the alphabet of English letters. The string of length zero is calledthe empty string and is denoted ε. If X and Y are strings then the concatenatio nof X and Y , denoted XkY , is the characters of X followed by the characters of Y .So, for example, 1011 k 0 = 10110. We c an encode almost anything into a string.We