tag:blogger.com,1999:blog-41637508548902713542024-03-13T17:18:28.074-05:00Introduction to CryptographyNorthwestern EECS 395/495-0-21 Fall 2011Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger31125tag:blogger.com,1999:blog-4163750854890271354.post-70383211308769418292011-11-30T13:47:00.000-06:002011-11-30T14:56:03.354-06:00Lecture 30Assignment 7 (due Wednesday December 7 at 5 PM) and the solutions to Assignment 5 <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a>.<br />
<br />
<a href="http://db.tt/0vQukCdl">OT and Secure Computation</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-46344197153841699822011-11-28T15:59:00.001-06:002011-11-30T09:20:59.475-06:00Lecture 29<a href="https://www.dropbox.com/s/1mc7vtovb1woz47/Poker.pdf">Poker over the telephone</a>. Overview of Secure Computation results.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-39795134476747782372011-11-23T09:11:00.001-06:002011-11-23T12:42:56.472-06:00Lecture 28Secure Computation Examples<br />
<br />
Coin Flipping, <a href="http://jsaia.wordpress.com/2011/11/18/yaos-millionaire-problem/">Yao's Millionaire Problem</a>, PokerLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-2631781716808584452011-11-21T09:18:00.000-06:002011-11-22T09:21:40.650-06:00Lecture 27Private Information Retrieval<br />
<br />
2 databases n bits from Alice, 4 databases n<sup>1/2</sup> bits, 1 database n<sup>1/2</sup> bits using quadratic residues<br />
<br />
Gasarch <a href="http://www.cs.umd.edu/~gasarch/pir/pir.html">webpage</a> and <a href="http://www.cs.umd.edu/~gasarch/pir/mysurvey.pdf">survey</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-80012095290049717592011-11-18T10:26:00.001-06:002011-11-18T14:51:13.800-06:00Lecture 26Assignment 6 (due Wed Nov 30) and Assignment 4 solutions <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a>.<br />
<br />
<a href="http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing">Shamir Secret Sharing</a>, <a href="http://en.wikipedia.org/wiki/Homomorphic_encryption">Homomorphic Encryption</a><br />
<br />Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-72894408876002003612011-11-16T07:43:00.001-06:002011-11-16T07:44:41.126-06:00Lecture 25Assignment 3 solutions <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a>.<br />
<br />
<a href="http://en.wikipedia.org/wiki/Quantum_key_distribution">Quantum Key Distribution</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-81603601851237281132011-11-14T14:10:00.001-06:002011-11-14T14:11:13.671-06:00Lecture 24<a href="http://en.wikipedia.org/wiki/Shor's_algorithm">Shor's Quantum Factoring Algorithm</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-77182390420019238702011-11-11T14:41:00.001-06:002011-11-11T14:55:39.997-06:00Lecture 23<a href="http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html">Zero-Knowledge Sudoku</a>
<br />
<a href="http://en.wikipedia.org/wiki/Commitment_scheme">Bit Commitment</a><br />
<br />Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-60615435986518812602011-11-09T09:25:00.000-06:002011-11-09T18:02:30.755-06:00Lecture 22Assignment 5 <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a> due Friday, November 18.<br />
<br />
<a href="http://bitcoin.org/">Bitcoin</a><br />
<br />
<a href="http://bitcoin.org/bitcoin.pdf">Original Paper</a>, <a href="https://en.bitcoin.it/wiki/Transaction">Transactions</a>, <a href="https://en.bitcoin.it/wiki/Blocks">Blocks</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-78840852201337123892011-11-07T09:23:00.000-06:002011-11-08T09:23:37.058-06:00Lecture 21<a href="https://www.dropbox.com/s/bbvvhr75knbi2a5/digitalcash.pdf">Digital Cash</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-91268920474637844582011-11-04T17:10:00.002-05:002011-11-04T17:10:47.658-05:00Lecture 20Digital Signatures, Collision-Resistant Hash Functions, <a href="http://en.wikipedia.org/wiki/ElGamal_signature_scheme">El Gamal Scheme</a><br />
<br />
Sections 4.6.1, 12.3.2, 12.4Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-26712966595476206682011-11-02T11:20:00.000-05:002011-11-04T11:22:21.885-05:00Lecture 19El-Gamal Encryption, Digital Signatures, Textbook RSA signatures<br />
Sections 10.5, 12.1-12.3.1Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-26173327378668809812011-10-31T09:30:00.004-05:002011-11-02T11:43:14.597-05:00Lecture 18Assignment 4 <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a>.<br />
<br />
RSA and El Gamal Sections 10.4-10.5Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-34852582648390874342011-10-28T08:24:00.000-05:002011-10-29T12:45:15.510-05:00Lecture 17Assignment 2 solutions <a href="https://www.dropbox.com/s/73n27s7cufqff7g/solution2.pdf">posted</a>.<br />
<br />
<a href="http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator">Intel's New Random-Number Generator</a><br />
<br />
Problems with "Textbook RSA" Section 10.4.1Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-64368074938098475682011-10-26T16:36:00.000-05:002011-10-26T16:36:53.320-05:00Lecture 16Lecture by Arefin Huq<br />
<br style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;" /><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">* Definition and discussion of CDH and DDH (from 7.3.2)</span><br style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;" /><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">* Choosing a Random Group Element (B.2.4)</span><br style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;" /><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">* Finding a Generator of a Cyclic Group (B.3)</span><br style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;" /><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">* Baby-Step/Giant Step Algorithm (8.2.1)</span><br style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;" /><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">* overview of Pohlig-Hellman Algorithm (8.2.2)</span>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-31650142548200790552011-10-24T14:03:00.000-05:002011-10-24T14:03:03.391-05:00Lecture 15Some typos in problem 2 of assignment 3 have been fixed.<br />
<br />
Hybrid Encryption, Section 10.3Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-920237428532570202011-10-21T11:06:00.000-05:002011-10-22T11:06:54.543-05:00Lecture 14<div>
<span class="Apple-style-span" style="color: #222222; font-family: arial, sans-serif; font-size: x-small;">Lecturer: Arefin Huq</span></div>
<div>
<span class="Apple-style-span" style="color: #222222; font-family: arial, sans-serif; font-size: x-small;"><br /></span></div>
<span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">7.1.3 (Groups), 7.3.1 (Cyclic Groups and Generators), and </span><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">the discrete logarithm experiment (7.3.2 up to </span><span class="Apple-style-span" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Definition 7.59).</span>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-34506361311062830872011-10-19T14:06:00.002-05:002011-10-19T14:06:25.163-05:00Lecture 13Assignment 3 has been <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a> and is due Friday, October 28.<br />
<br />
Public-Key Encryptions, Chosen-Plaintext Attacks and Multiple Message Encryptions<br />
Textbook 10.1-10.2Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-67616648276408596972011-10-17T14:58:00.000-05:002011-10-17T14:58:08.778-05:00Lecture 12Factoring and RSA<br />
Textbook 7.2.3 and 7.2.4Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-72445718987984356462011-10-14T14:05:00.000-05:002011-10-14T14:05:07.491-05:00Lecture 11Chinese Remainder and Primality Testing<br />
Sections 7.1.5, 7.2.2Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-61642613305355020042011-10-12T15:32:00.000-05:002011-10-13T15:32:38.172-05:00Lecture 10Assignment 1 solutions <a href="https://www.dropbox.com/s/q3px45d6gy7w4v0/solution1.pdf">posted</a>.<br />
<br />
Chosen Ciphertext Attacks Section 3.7<br />
Introduction to Public Key Crypto<br />
Math Background Section 7.1.4Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-90632521944753235842011-10-10T16:35:00.001-05:002011-10-10T16:35:04.417-05:00Lecture 9Assignment 2 is <a href="http://nucrypto2011.blogspot.com/p/assignments.html">posted</a> and due Wednesday October 19. Assignment was updated at 4 PM on October 10.<br />
<br />
Constructing CPA-secure encryption schemes from pseudorandom functions<br />
Sections 3.6.1-3.6.2Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-91311071735591705352011-10-07T16:33:00.000-05:002011-10-10T16:35:11.822-05:00Lecture 8Indistinguishable encryptions in the presence of an eavesdropper from a pseudorandom generator.<br />
Sections 3.4.1-3.4.2<br />
Chosen Plaintext Attacks<br />
Section 3.5Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-66098461965990727482011-10-05T15:48:00.000-05:002011-10-06T15:48:50.409-05:00Lecture 7Lecture by Arefin Huq<br />
Modular Arithmetic and Exponentiation<br />
<br />
Chapter 7 through Section 7.1.2 and Appendix B through Section B.2.3<br />
Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0tag:blogger.com,1999:blog-4163750854890271354.post-72156486291163564322011-10-03T16:53:00.000-05:002011-10-03T16:55:27.987-05:00Lecture 6Pseudorandom generators<br />
Textbook Section 3.3<br />
<br />
Upcoming Seminars<br />
Tuesday Craig Mundie (Microsoft Research Chief) <a href="http://neweraofcomputing.eventbrite.com/">Converging Worlds: The New Era of Computing</a><br />
Thursday <a href="http://www.eecs.northwestern.edu/frontiers-in-computer-science-symposium.html">Frontiers in Computer Science Symposium</a>Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.com0