Background and Abstract for Crypto Class Papers Fall 2004, Prof M. Anshel

Weekly Schedule (Subject to Change)

.	Topics/Conceptual Notes	Prof’s Handouts
08/27	Course overview: textbooks and appendix cryptovirology [doc, pdf] Handbook of Applied Cryptography, hac_chap1 Overview of Cryptography	1. Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, Jean-Sebastian.Coron@gemplus.com and Alexander May 2. How to Cheat at Chess: A Security Analysis of ICC, Black etal
09/03	Xu XiaoWei presents dress rehearsal on the limit of how bit commitment scheme of Zero Knowledge is quantum impossible and how word problem a la finitely presented matrix group may be possible in (non) quantum channel.	2. On Oleshchuk’s Public Key Cryptosystem, Heiko Stamer, Friedrich Otto 3. Conjugacy of finite subsets in hyperbolic groups, Martin R Bridson and James Howie
09/10	What makes some problem computationally hard and others easy? Deterministic Turing Machine vs Non Deterministic Turing Machine with respect to polynomial and decidable; complexity taxonomy: time complexity P(N^k), NP, BPP, EXPTIME (2^(n^k)), NP-hard, NP-complete ; twin-sibling space complexity PSPACE=IP, NPSPACE, EXPSPACE [pdf]	4. Shamir’s IP=PSPACE 5. Lenore Blum on “Computing over Reals: Where Turing Meets Newton” 6. Prof Anshel talked at MSRI on Arithmetica Key Exchange in 2000
09/17, 09/24	No Class Scheduled
10/01	Title: Privacy Protocol for Electronic Voting. The talk surveys history of voting, social choice function and voting procedure, and the system design challenge of moving secret ballot election to the Internet medium?	Andis Kwan’s Research Prof Anshel’s handout: 7. Jumbler Cruncher, New Scientist Vol183 Issue 2466 09/25/2005 pp36 8. Cover Story: Randomness, ibid, pp29-35 9. Securing Data in Storage, Paul Stanton, UIUC
10/08	Title: Quantum Security: BB84 Protocol and Quantum Network. The talk surveys the physics and mathematical foundation of BB84 protocol and the state of art Quantum network technology.	Ke Tang’s website Prof Anshel’s handout: 10. A survey of Public-Key Cryptosystems, Neal Koblitz, Alfred Menezes, SIAM Review 11. The Nonsecurity of Secrecy, Bruce Schneier, 10/2004 CACM
10/15	Semester projects and proposals discussion; first student group meeting on CUNY Secure Electronic Remote Voting Execution system (SERVE); brainstorming session	12. Fixing the Vote, Ted Selker, SCIAM Oct Issue 10/15/2004 minute
10/22	Group theory and low-dimensional topology, one-day conference at the City College, 9:30-4:30, North Academic Center, Room 0/201. Contact Sean Cleary cleary@sci.ccny.cuny.edu or Bernice Ravitz Bernice@rio.sci.ccny.cuny.edu Regular student meeting at GC 3^rd floor students’ agenda student’s skeleton request for proposal hac_chap2 & hac_chap3 mathematical background	10/22 students’ meeting @GC minute
10/29	Emil Post Correspondent Problem, Decision Problems for HNN Groups, Word Conjugacy Problems and Public Key Cryptography.	13. From Post-Markov Theorem Through Decision Problems to Public Key Cryptography, [Anshel & Anshel AMS1999] 14. Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Sybsystems of Peano Arithmetic, [Anshel & McAloon AMS1983]
11/05	Title: Homeair Security, EK	15.Polycyclic Groups: A New Platform for Cryptology? [Eick and Kahrobaei 2004]
11/12	Information Security Conferences and Workshops, e.g. IWAP2004 Complexity Journal: Notice of Retraction and Apology	16. Post-Quantum Signatures, Johannes Buchmann [talk, paper]
11/19	New Development on Conjugacy Search Problem and Braid Group Cryptography	17. Breaking Littlewood’s Cipher [Damien Stehle 2003] 18. The Conjugacy Search Problem in Public Key Cryptography: Unnecessary and Insufficient [V. Shpilrain etal 2004] An Efficient Implementation of Braid Groups [Cha et. al AsiaCrypto 2001] Length-based attacks for certain group based encryption rewriting system [J Hughes et al 2002] Length-based Conjugacy search in the Braid Group [Garber, et al 2004] 19. Braids: A Survey, [Joan Birman et al 2004]
11/24	Wednesday follows a Friday schedule; Title: Quantum Vs Conventional Algorithms to Chess Problems [Kahanda] Discussion: An Approach to Privacy-preserving Mobile Electronic Voting System	20. Studies in Cryptological Combinatorics, [Marc Zucker 2004]
12/03	Title: An Elementary Introduction of Group Law for Elliptic Curves [AK & XXu) Abstract: The main part of survey talk is to show the group addition law for an elliptic curve E in their algebraic field K, the relationship of K [X, Y] and K (X,Y). We sketch the main tools underlying our construction, some Galois group/field theory, introduce the general form of polynomial F (X,Y) =0, show by example that the associativity law holds under the construction of rational map and divisor. The talk is based on the “Elementary Introduction to Elliptic Curves” papers by Leonard Charlap & David Robbins. (we use many fundamental theorems without proofs.)
12/10	Title: RSA Hardware [Shana]/[Rescheduled] Title: Computing over the Reals: Where Turing Meets Newton [Yuqing Tang] Title: TBA [Malik]
12/17	Title: Braid Groups and the AAG Crypto-program [Buke]

Regarding paper #1

This experimental paper shows a coppersmith’s variant on LLL(Lenstra, Lenstra, Lovasz 1982) lattice reduction algorithm can be used to factor N =pq, given (N,e,d), in polynomial time. The generalized trick is to attack the selective high order bits on p and q offline.

Minute on Friday 09/10/2004

Tang volunteers to report on Lenore Blum’s article “Computing over the Reals: Where Turing Meets Newton” on August 2004 Notices of AMS.