ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mv="http://macVmlSchemaUri" xmlns="http://www.w3.org/TR/REC-html40" xmlns:ns0="urn:schemas-microsoft-com:office:smarttags"> <head> <meta name=Title content="Introduction to Cryptography"> <meta name=Keywords content=""> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 14"> <meta name=Originator content="Microsoft Word 14"> <link rel=File-List href="index_files/filelist.xml"> <link rel=Edit-Time-Data href="index_files/editdata.mso"> <!--[if !mso]> <style> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} </style> <![endif]--> <title>Introduction to Cryptography</title> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:LastAuthor>Rafael Pass</o:LastAuthor> <o:Revision>10</o:Revision> <o:TotalTime>15</o:TotalTime> <o:Created>2013-09-02T18:35:00Z</o:Created> <o:LastSaved>2013-09-02T19:06:00Z</o:LastSaved> <o:Pages>2</o:Pages> <o:Words>1203</o:Words> <o:Characters>6862</o:Characters> <o:Lines>57</o:Lines> <o:Paragraphs>16</o:Paragraphs> <o:CharactersWithSpaces>8049</o:CharactersWithSpaces> <o:Version>14.0</o:Version> </o:DocumentProperties> <o:OfficeDocumentSettings> <o:AllowPNG/> </o:OfficeDocumentSettings> </xml><![endif]--> <link rel=themeData href="index_files/themedata.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:Zoom>141</w:Zoom> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:TrackMoves>false</w:TrackMoves> <w:TrackFormatting/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>X-NONE</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:SplitPgBreakAndParaMark/> </w:Compatibility> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false" DefSemiHidden="false" DefQFormat="false" LatentStyleCount="276"> <w:LsdException Locked="false" QFormat="true" Name="Normal"/> <w:LsdException Locked="false" QFormat="true" Name="heading 1"/> <w:LsdException Locked="false" QFormat="true" Name="heading 2"/> <w:LsdException Locked="false" QFormat="true" Name="heading 3"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 4"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 5"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 6"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 7"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 8"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="heading 9"/> <w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="caption"/> <w:LsdException Locked="false" QFormat="true" Name="Title"/> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" QFormat="true" Name="Subtitle"/> <w:LsdException Locked="false" Priority="99" Name="Hyperlink"/> <w:LsdException Locked="false" QFormat="true" Name="Strong"/> <w:LsdException Locked="false" QFormat="true" Name="Emphasis"/> <w:LsdException Locked="false" Priority="99" Name="No List"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 1"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 2"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 3"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 4"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 5"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 6"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 7"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 8"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" UnhideWhenUsed="true" Name="Note Level 9"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" Name="Placeholder Text"/> <w:LsdException Locked="false" Priority="1" QFormat="true" Name="No Spacing"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading"/> <w:LsdException Locked="false" Priority="61" Name="Light List"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3"/> <w:LsdException Locked="false" Priority="70" Name="Dark List"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 1"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 1"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 1"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 1"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 1"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 1"/> <w:LsdException Locked="false" Priority="99" SemiHidden="true" Name="Revision"/> <w:LsdException Locked="false" Priority="34" QFormat="true" Name="List Paragraph"/> <w:LsdException Locked="false" Priority="29" QFormat="true" Name="Quote"/> <w:LsdException Locked="false" Priority="30" QFormat="true" Name="Intense Quote"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 1"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 1"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 1"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 1"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 1"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 1"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 1"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 1"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 2"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 2"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 2"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 2"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 2"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 2"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 2"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 2"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 2"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 2"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 2"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 2"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 2"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 2"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 3"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 3"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 3"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 3"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 3"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 3"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 3"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 3"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 3"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 3"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 3"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 3"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 3"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 3"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 4"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 4"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 4"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 4"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 4"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 4"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 4"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 4"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 4"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 4"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 4"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 4"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 4"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 4"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 5"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 5"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 5"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 5"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 5"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 5"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 5"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 5"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 5"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 5"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 5"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 5"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 5"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 5"/> <w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 6"/> <w:LsdException Locked="false" Priority="61" Name="Light List Accent 6"/> <w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 6"/> <w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 6"/> <w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 6"/> <w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 6"/> <w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 6"/> <w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 6"/> <w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 6"/> <w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 6"/> <w:LsdException Locked="false" Priority="70" Name="Dark List Accent 6"/> <w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 6"/> <w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 6"/> <w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 6"/> <w:LsdException Locked="false" Priority="19" QFormat="true" Name="Subtle Emphasis"/> <w:LsdException Locked="false" Priority="21" QFormat="true" Name="Intense Emphasis"/> <w:LsdException Locked="false" Priority="31" QFormat="true" Name="Subtle Reference"/> <w:LsdException Locked="false" Priority="32" QFormat="true" Name="Intense Reference"/> <w:LsdException Locked="false" Priority="33" QFormat="true" Name="Book Title"/> <w:LsdException Locked="false" Priority="37" SemiHidden="true" UnhideWhenUsed="true" Name="Bibliography"/> <w:LsdException Locked="false" Priority="39" SemiHidden="true" UnhideWhenUsed="true" QFormat="true" Name="TOC Heading"/> </w:LatentStyles> </xml><![endif]--> <style> <!-- font-face {font-family:Tahoma;} font-face {font-family:Tahoma;} /* Font Definitions */ @font-face {font-family:Arial; panose-1:2 11 6 4 2 2 2 2 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-536859905 -1073711037 9 0 511 0;} @font-face {font-family:¼ÕÐ; mso-font-charset:79; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:1 151388160 16 0 524288 0;} @font-face {font-family:¼ÕÐ; mso-font-charset:79; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:1 151388160 16 0 524288 0;} @font-face {font-family:Tahoma; panose-1:2 11 6 4 3 5 4 4 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-520082689 -1073717157 41 0 66047 0;} @font-face {font-family:"Lucida Grande"; panose-1:2 11 6 0 4 5 2 2 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman";} h1 {mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 1 Char"; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; mso-outline-level:1; font-size:24.0pt; font-family:"Times New Roman"; mso-fareast-font-family:¼ÕÐ; font-weight:bold;} h2 {mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 2 Char"; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; mso-outline-level:2; font-size:18.0pt; font-family:"Times New Roman"; mso-fareast-font-family:¼ÕÐ; font-weight:bold;} h3 {mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 3 Char"; margin-top:12.0pt; margin-right:0in; margin-bottom:3.0pt; margin-left:0in; mso-pagination:widow-orphan; page-break-after:avoid; mso-outline-level:3; font-size:13.0pt; font-family:Arial; mso-fareast-font-family:¼ÕÐ; font-weight:bold;} a:link, span.MsoHyperlink {mso-style-priority:99; mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-unhide:no; color:blue; text-decoration:underline; text-underline:single;} p {mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman";} p.MsoAcetate, li.MsoAcetate, div.MsoAcetate {mso-style-unhide:no; mso-style-link:"Balloon Text Char"; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:8.0pt; font-family:Tahoma; mso-fareast-font-family:"Times New Roman";} span.Heading1Char {mso-style-name:"Heading 1 Char"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Heading 1"; mso-ansi-font-size:16.0pt; mso-bidi-font-size:16.0pt; font-family:Calibri; mso-ascii-font-family:Calibri; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"-ÿ3ÿ ´0·0Ã0¯0"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#345A8A; mso-themecolor:accent1; mso-themeshade:181; font-weight:bold;} span.Heading2Char {mso-style-name:"Heading 2 Char"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Heading 2"; mso-ansi-font-size:13.0pt; mso-bidi-font-size:13.0pt; font-family:Calibri; mso-ascii-font-family:Calibri; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"-ÿ3ÿ ´0·0Ã0¯0"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#4F81BD; mso-themecolor:accent1; font-weight:bold;} span.Heading3Char {mso-style-name:"Heading 3 Char"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Heading 3"; mso-ansi-font-size:12.0pt; mso-bidi-font-size:12.0pt; font-family:Calibri; mso-ascii-font-family:Calibri; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"-ÿ3ÿ ´0·0Ã0¯0"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#4F81BD; mso-themecolor:accent1; font-weight:bold;} span.BalloonTextChar {mso-style-name:"Balloon Text Char"; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Balloon Text"; mso-ansi-font-size:9.0pt; mso-bidi-font-size:9.0pt; font-family:"Lucida Grande"; mso-ascii-font-family:"Lucida Grande"; mso-hansi-font-family:"Lucida Grande";} span.SpellE {mso-style-name:""; mso-spl-e:yes;} span.GramE {mso-style-name:""; mso-gram-e:yes;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} /* List Definitions */ @list l0 {mso-list-id:492334927; mso-list-template-ids:-181741152;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l0:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1 {mso-list-id:740951017; mso-list-template-ids:1849841160;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l1:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2 {mso-list-id:893392967; mso-list-template-ids:291655466;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l2:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3 {mso-list-id:930546903; mso-list-template-ids:-1747545360;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l3:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4 {mso-list-id:931817807; mso-list-template-ids:-1387617556;} @list l4:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l4:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l4:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5 {mso-list-id:1093092298; mso-list-template-ids:-1262974694;} @list l5:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l5:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l5:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6 {mso-list-id:1118185413; mso-list-template-ids:-910670992;} @list l6:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l6:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l6:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7 {mso-list-id:1339385789; mso-list-template-ids:795880682;} @list l7:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l7:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l7:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8 {mso-list-id:1611160041; mso-list-template-ids:884238296;} @list l8:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l8:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l8:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9 {mso-list-id:1628664264; mso-list-template-ids:-1314080180;} @list l9:level1 {mso-level-number-format:bullet; mso-level-text:·ð; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l9:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l9:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} ol {margin-bottom:0in;} ul {margin-bottom:0in;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman";} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="1026"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body bgcolor=white lang=EN-US link=blue vlink=blue style='tab-interval:.5in'> <div class=WordSection1> <h1 align=center style='text-align:center'><span style='mso-no-proof:yes'><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"/> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"/> <v:f eqn="sum @0 1 0"/> <v:f eqn="sum 0 0 @1"/> <v:f eqn="prod @2 1 2"/> <v:f eqn="prod @3 21600 pixelWidth"/> <v:f eqn="prod @3 21600 pixelHeight"/> <v:f eqn="sum @0 0 1"/> <v:f eqn="prod @6 1 2"/> <v:f eqn="prod @7 21600 pixelWidth"/> <v:f eqn="sum @8 21600 0"/> <v:f eqn="prod @7 21600 pixelHeight"/> <v:f eqn="sum @10 21600 0"/> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/> <o:lock v:ext="edit" aspectratio="t"/> </v:shapetype><v:shape id="Picture_x0020_1" o:spid="_x0000_i1025" type="#_x0000_t75" alt="Description: CornellNYCTech-logo.jpg" style='width:3in;height:81pt; visibility:visible;mso-wrap-style:square'> <v:imagedata src="index_files/image001.jpg" o:title="CornellNYCTech-logo.jpg"/> </v:shape><![endif]--><![if !vml]><img width=218 height=83 src="index_files/image002.png" alt="Description: CornellNYCTech-logo.jpg" v:shapes="Picture_x0020_1"><![endif]></span><o:p></o:p></h1> <h1 align=center style='text-align:center'>Cryptography</h1> <h2 align=center style='text-align:center'>Computer Science 5830<br> <ns0:place><span><ns0:PlaceName><span>Cornell</ns0:PlaceName></span> <ns0:PlaceType><span>University</ns0:PlaceType></span></ns0:place></span> <br> Fall 2013</h2> <p class=MsoNormal><br> Instructor: <a href="http://www.cs.cornell.edu/~rafael">Rafael Pass</a><o:p></o:p></p> <p class=MsoNormal>Time: T 10:10-12.55<br> Place: Big Red, Cornell Tech <br> Course Web page: <a href="http://www.cs.cornell.edu/courses/cs5830/2013fa/">http://www.cs.cornell.edu/courses/cs5830/2013fa/</a><o:p></o:p></p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal>TA: <a href="https://sites.google.com/site/sidtelang/"><span class=SpellE>Sidharth</span> <span class=SpellE>Telang</span></a><o:p></o:p></p> <p class=MsoNormal>Office Hours: W 13:00 - 15:00 <o:p></o:p></p> <br> <p class=MsoNormal> <b> Homework 1 </b><a href="http://www.cs.cornell.edu/courses/cs5830/2013fa/hw1/hw1.pdf"> pdf</a> <p class =MsoNormal> Gwriter files <a href="http://www.cs.cornell.edu/courses/cs5830/2013fa/hw1/gwriter.rar"> rar </a> <a href="http://www.cs.cornell.edu/courses/cs5830/2013fa/hw1/gwriter.zip"> zip </a> <h2>Overview </h2> <p class=MsoNormal>The modern study of cryptography investigates techniques for facilitating interactions between distrustful entities. In our connected society, such techniques have become indispensable---enabling, for instance, automated teller machines, secure wireless networks, <span class=GramE>internet</span> banking, satellite radio/television and more. In this course we introduce some of the fundamental concepts of this study. Emphasis will be placed on precise definitions of security, precise assumptions and proofs of security. <o:p></o:p></p> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <p class=MsoNormal>Topics include: one-way functions, encryption, signatures, pseudo-random number generation, zero-knowledge and basic protocols.<o:p></o:p></p> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <p class=MsoNormal>Note: Although students will be expected to provide implementations of basic cryptographic primitives, this is largely a theory course. You will be expected to read and write formal definitions and mathematical proofs. This is not a course in security: you will not learn how to secure your system. Cryptography is only one (important) part of security. We will not study cryptographic acronyms or all cryptographic protocols in use today. Rather we focus on some of the fundamental design paradigms and on notions that will allow you to critically evaluate cryptographic protocols.</p> <h2>Prerequisites</h2> <p class=MsoNormal><span class=GramE>Equivalent of CS2800 (Discrete Mathematics) and comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times, or permission of instructor.</span><o:p></o:p></p> <p class=MsoNormal>The main skill that will be assumed is the ability to understand and write formal mathematical definitions and proofs. It is also important that you are familiar with basic probability (although we will recall some basic concepts); please refresh yourself by reading Chapter 5 in the following lecture notes: <a href="http://www.cs.cornell.edu/~rafael/discmath.pdf">[Pass-Tseng]</a></p> <h2><a name="Course_Administration">Course Administration</a></h2> <p>We are using the course management system, <b>CMS</b>.&nbsp; Please login to <a href="http://cms.csuglab.cornell.edu/">http://cms.csuglab.cornell.edu/</a> and check whether you are registered. There will be a list of courses you are registered for, and Com S 4830 should be one of them.&nbsp; If not, please send your full name and Cornell <span class=SpellE>netid</span> to the TA so they can register you.&nbsp; You can check your grades and submit homework in CMS.&nbsp; </p> <h2>Grading </h2> <p class=MsoNormal>There will be <b style='mso-bidi-font-weight:normal'>4 <span class=SpellE>homeworks</span>.</b><o:p></o:p></p> <p class=MsoNormal>Dates for HW (subject to change): HW1 is due on <b style='mso-bidi-font-weight:normal'>Sep 17, </b>HW2 on<b style='mso-bidi-font-weight: normal'> Oct 8</b>, HW3 on <b style='mso-bidi-font-weight:normal'>Nov 5</b>, <span class=GramE>HW4</span> on <b style='mso-bidi-font-weight:normal'>Nov 26.</b><o:p></o:p></p> <p class=MsoNormal><span class=SpellE>Homeworks</span> need to be handed in before the beginning of class. Additionally, you have a total of 4  late-days that you can use throughout the semester. <o:p></o:p></p> <p class=MsoNormal>The following <a href="notation.pdf">notation</a> might be useful.<o:p></o:p></p> <p class=MsoNormal><span style="mso-spacerun:yes"> </span></p> <h2>Homework Policy</h2> <p>You are free to collaborate with other students on the homework (in fact, I highly encourage you to work in pairs), but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff. Assignments will be posted in CMS. Submit hardcopy in class or to the TA by the due date, or as a .<span class=SpellE>pdf</span>, .<span class=SpellE>ps</span>, .doc, or .txt file in CMS. Typed problem sets are <b style='mso-bidi-font-weight:normal'>strongly</b> preferred. </p> <h2><ns0:City><span><ns0:place><span>Reading</ns0:place></span></ns0:City></span><span style='font-size:12.0pt'> </span></h2> <p class=MsoNormal>We will largely follow the following lecture notes: <a href="http://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf">[Pass-<span class=SpellE>Shelat</span>]</a> (although some of the advanced proofs in these lecture notes will not be required for this course).</p> <p class=MsoNormal><o:p>&nbsp;</o:p></p> <p class=MsoNormal>For additional background on probability theory, number theory and logic, please consult the following lecture notes on discrete mathematics: <a href="http://www.cs.cornell.edu/~rafael/discmath.pdf">[Pass-Tseng]</a><o:p></o:p></p> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <p class=MsoNormal>There is no other required text for the course other than lecture notes. You may find the following two books to be useful references. Note, however, that we will not always be following the same notational conventions as these books.<o:p></o:p></p> <p class=MsoNormal>&nbsp;&nbsp;<o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l2 level1 lfo1;tab-stops:list .5in'><span class=SpellE>Oded</span> <span class=SpellE>Goldreich</span>. <a href="http://www.wisdom.weizmann.ac.il/~oded/foc-book.html">Foundations of Cryptography</a>. This is a very comprehensive treatment of the theoretical foundations of cryptography. Volume <span class=GramE>I and II</span> include most of the material that we cover in class, but at a far greater depth and (at a more advanced level). This book is a great reference for students interested in more advanced studies in theoretical cryptography. <o:p></o:p></li> </ul> <p class=MsoNormal style='margin-left:.25in'><o:p>&nbsp;</o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l2 level1 lfo1;tab-stops:list .5in'><span lang=SV style='mso-ansi-language:SV'>Jonathan Katz and <span class=SpellE>Yehuda</span> Lindell. </span><a href="http://www.amazon.com/Introduction-Cryptography-Chapman-Network-Security/dp/1584885513/ref=pd_bbs_sr_1/002-7572143-2456067?ie=UTF8&amp;s=books&amp;qid=1187795126&amp;sr=8-1">An Introduction to Modern Cryptography.</a> This is an introductory textbook on cryptography. The level of the material and the mathematical treatment is similar to the one we will use in class. However, this book does not cover all of the material that we go through.<o:p></o:p></li> </ul> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <p class=MsoNormal>For a more applied treatment of cryptography, I suggest the following book which is available on-line.<o:p></o:p></p> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l6 level1 lfo2;tab-stops:list .5in'>Alfred J. <span class=SpellE>Menezes</span>, Paul C. van <span class=SpellE>Oorschot</span>, and Scott A. Vanstone. <a href="http://www.cacr.math.uwaterloo.ca/hac/">Handbook of Applied Cryptography.</a> <o:p></o:p></li> </ul> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <p class=MsoNormal>For background reading on probability, algorithms, and complexity theory, I recommend:<o:p></o:p></p> <p class=MsoNormal>&nbsp;<o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l7 level1 lfo3;tab-stops:list .5in'>Thomas H. <span class=SpellE><span class=GramE>Cormen</span></span><span class=GramE> ,</span> Charles E. <span class=SpellE>Leiserson</span> , Ronald L. <span class=SpellE>Rivest</span>, and Clifford Stein.<a href="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262032937/ref=pd_bbs_2/002-7572143-2456067?ie=UTF8&amp;s=books&amp;qid=1187795938&amp;sr=1-2"> Introduction to Algorithms</a>.<o:p></o:p></li> <li class=MsoNormal style='mso-list:l7 level1 lfo3;tab-stops:list .5in'>Michael <span class=SpellE>Sipser</span>.<a href="http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=pd_bbs_sr_1/002-7572143-2456067?ie=UTF8&amp;s=books&amp;qid=1187795343&amp;sr=8-1"> Introduction to the Theory of Computation</a>.<o:p></o:p></li> </ul> <h2>Topics Outline <span style='font-size:12.0pt;font-weight:normal;mso-bidi-font-weight: bold'>(subject to change)</span><span style='font-weight:normal;mso-bidi-font-weight: bold'><o:p></o:p></span></h2> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l4 level1 lfo4;tab-stops:list .5in'><b>Introduction: </b><o:p></o:p></li> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l4 level2 lfo4;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Introduction and Overview.<b> <br> </b><i style='mso-bidi-font-style:normal'>How to break WWII Ciphers.</i></span><o:p></o:p></li> <li class=MsoNormal style='mso-list:l4 level2 lfo4;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Information Theoretic Security. </span><br> <i style='mso-bidi-font-style:normal'><ns0:place><span>Shannon</ns0:place></span> s Definition of security. One-time Pads. Limitations of the Information Theoretic Approach. <o:p></o:p></i></li> </ol> </ul> <p class=MsoNormal style='margin-left:.25in'><b>&nbsp;</b><o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l8 level1 lfo5;tab-stops:list .5in'><b>Computational Hardness and One-<span class=SpellE>wayness</span>: </b><o:p></o:p></li> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l8 level2 lfo5;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>One-way Functions and Computationally bounded adversaries.</span><br> <i style='mso-bidi-font-style:normal'>Randomized Efficient Algorithms. One-way functions (OWF). Weak and Strong OWFs. <br> Collections of OWFs. <o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l8 level2 lfo5;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Computational Number Theory. </span><br> <i style='mso-bidi-font-style:normal'>Euclid s Algorithm, Modular Exponentiation, Basic group theory, Euler s and Fermat s Theorems.<br> Primes. Candidate OWFs based on the Factoring assumption and the <span class=GramE>Discrete</span> log assumption. <br> <span class=GramE>One way</span> permutations and Trapdoor permutations.<o:p></o:p></i></li> </ol> </ul> <p class=MsoNormal style='margin-left:.25in'><b>&nbsp;</b><o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l0 level1 lfo6;tab-stops:list .5in'><span class=SpellE><b>Indistinguishability</b></span><b> and <span class=SpellE>Pseudorandomness</span>: </b><o:p></o:p></li> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l0 level2 lfo6;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Computational <span class=SpellE>Indistinguishability</span> and Pseudorandom Generators (PRG) and Functions (PRF).</span><br> <i style='mso-bidi-font-style:normal'>Definitions of Computational <span class=SpellE>Indistinguishability</span> and <span class=SpellE>Pseudorandomness</span>. <br> Provable constructions <span class=GramE>of a</span> PRGs and PRFs. <br> Practical constructions of PRG and PRFs: stream and block-ciphers.<o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l0 level2 lfo6;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Private-Key Encryption. </span><br> <i style='mso-bidi-font-style:normal'>Definitions and Constructions<o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l0 level2 lfo6;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Stronger Attacks:</span><br> <i style='mso-bidi-font-style:normal'>Chosen challenge-text, <ns0:place><span>Chosen</ns0:place></span> <span class=GramE>plain-text</span>, Chosen cipher-text 1 and 2 (CCA1, CCA2). <br> Malleability. <o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l0 level2 lfo6;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Public-Key Encryption. </span><br> <i style='mso-bidi-font-style:normal'>Trap-door function model and problems with it. <br> Definitions and Constructions.<o:p></o:p></i></li> </ol> </ul> <p class=MsoNormal style='margin-left:.75in'>&nbsp;<o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l1 level1 lfo7;tab-stops:list .5in'><b>Zero-Knowledge:</b><o:p></o:p></li> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l1 level2 lfo7;tab-stops:list 1.0in'><span class=SpellE><span style='mso-bidi-font-weight:bold'>Semantical</span></span><span style='mso-bidi-font-weight:bold'> Security</span>: <br> <i style='mso-bidi-font-style:normal'>Zero knowledge-based definitions of encryption. Equivalence with <span class=SpellE>indistinguishability</span>-based definitions.<o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l1 level2 lfo7;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Zero-Knowledge Proofs:</span><br> <i style='mso-bidi-font-style:normal'>Definitions and construction of ZK proofs for Graph-Isomorphism and Graph 3-coloring. <o:p></o:p></i></li> </ol> </ul> <p class=MsoNormal style='margin-left:.25in'><i style='mso-bidi-font-style: normal'>&nbsp;</i><o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l9 level1 lfo8;tab-stops:list .5in'><b>Authentication:</b><o:p></o:p></li> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l9 level2 lfo8;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Digital Signatures.<br> </span><i style='mso-bidi-font-style:normal'>Definitions and Constructions<o:p></o:p></i></li> <li class=MsoNormal style='mso-list:l9 level2 lfo8;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Hash functions.</span><o:p></o:p></li> <li class=MsoNormal style='mso-list:l9 level2 lfo8;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Message Authentication Codes.</span><o:p></o:p></li> <li class=MsoNormal style='mso-list:l9 level2 lfo8;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Zero Knowledge-based <span class=GramE>Authentication</span><b>.</b></span><o:p></o:p></li> </ol> </ul> <p class=MsoNormal style='margin-left:.25in'><b>&nbsp;</b><o:p></o:p></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='mso-list:l3 level1 lfo9;tab-stops:list .5in'><b>Computing on Secret Inputs:</b><o:p></o:p></li> </ul> <ul style='margin-top:0in' type=disc> <ol style='margin-top:0in' start=1 type=1> <li class=MsoNormal style='mso-list:l5 level2 lfo10;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Secret Sharing.</span><o:p></o:p></li> <li class=MsoNormal style='mso-list:l5 level2 lfo10;tab-stops:list 1.0in'><span style='mso-bidi-font-weight:bold'>Secure Computation. </span><br> <i style='mso-bidi-font-style:normal'>Oblivious Transfer.<br> <ns0:place><span><ns0:city><span>Yao</ns0:city></span></ns0:place></span> s Garbled Circuit.</i><br> <i style='mso-bidi-font-style:normal'>Secure Multi-party Computation</i></li> </ol> </ul> <p class=MsoNormal><o:p>&nbsp;</o:p></p> </div> </body> </html>