Background and Abstract for Crypto Class Papers Spring 20005, Prof M. Anshel

(A link to Fall 2004 course page is here.)

GC office: 4307 | Email: MikeAt11440@aol.com

Teaching :: CCNY M-W 5-6:15 ; 2-3:15 ; office hour M-W 4-4:50 | GC F 2-4; office 5:15-6

Newest courses Friday Fall 2005, interdisciplinary: biology, computer science, mathematics, and physics

Topics in Quantum Cryptography CS 85030 Code 92319 jointly by Prof XiangDong Li (email) and Prof Michael Anshel

Classical and Quantum Computing IDS 81610, Code 92291, jointly by Prof XiangDong Li and Prof Anshel

Course description [pdf, doc]

Weekly Schedule (Subject to Change)

.	Topics/Conceptual Notes	Prof Anshel’s Handouts/Fun Readings
01/28	Course overview; Quantum Mechanics for Cryptography	1. Revision A survey of Public-Key Cryptosystems, Neal Koblitz, Alfred Menezes, SIAM Review 2. Quantum Cryptography, Karl Svozil 3. Overview of Braid Cryptography (student paper), Carl Mahlburg
02/04		3a. On Diffie-Hellman problem over GL, A.A. Kalele and V.R. Sule [2005 iacr] 3b. The Vector Decomposition Problem for Elliptic Curve and Hyperelliptic Curve, Iwan Duursma and Negar Kiyavash [ 2005 iacr]
02/18	ForNet—A distributed Network Forensics System Prof Nasir Memon Polytechnic University. @ John Jay CUNY [html] Abstract: In this talk we introduce ForNet, a distributed network logging mechanism to aid digital forensics over wide area networks. We describe the need for such a system, review related work, present the architecture of the system, and discuss key research issues. We then describe the design and implementation of a prototype system that processes packets in a network and is able to attribute query payloads to source and destination hosts in the local network. It is based on a novel data structure called a Hierarchical Bloom Filter (HBF). An HBF allows us to form compact digests of payloads and provide probabilistic answers to membership queries. Our system is robust against certain packet transformations and flexible enough to be used if the query string is spread across several packets. Performance analysis and experimental results of the prototype system are also presented demonstrating its practicality and efficacy.
02/25	Key Establishment Schemes, Data Discovery	4. Road to Quantum Computing, Hans Mooij, Science Vol 307 Number 5713 Issue 25 Feb 2005, pp.1210-1211 5. Simultaneous State Measurement of Coupled Josephson Phase Qubits, R McDermott et al, ibid 1299-1302 6. Geometric key Establishment, Arkady Berenstein and Leon Chernyak [2004 iacr] 7. A note on Shor’s Quantum Algorithm for Prime Factorization, Zhengjun Cao [2005 iacr] 8. Automatic Meaning Discovery Using Google, Rudi Cilibrasi and Paul Vitanyi [pdf] 9. It is easy to determine whether a given integer is prime, Andrew Granville [AMS Bulletin V42N1 pp3-38] 10. Adversarial Model for Radio Frequency Identification, Gildas Avoine [2005 iacr abs]
03/05	Hash function & Digital Signature	11a. Promising the Impossible: Classical Certification in Quantum World, Adrian Kent, arXiv [2005 abs] 11.b No Signalling and Quantum Key Distribution, Adrian Kent, arXiv [2005 abs] 11. On Public-Key cryptosystems based on combinatorial group theory, jean-camille Birget et al [2005 iacr] 12. Colliding X.509 Certificates, Arjen Lenstra, Xiaoyun Wang, Benne de Weger [2005 iacr] 13. RSA Group is Pseudo-free, Daniele Micciancio [Eurocrypt2005] 14. Flaw found in data-protection method, Charles Seife, [Science Vol 307, 03/04/2005 pp1389] 15. Collision Search Attacks on SHA-1, Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu [2005 pdf]
03/11		16. Experimental One Way Quantum Computing, P Walther, et al [Nature Vol 434 03/10/05 pdf] 17. Computing Igusa’s Local Zeta Functions of Univariate Polynomials, and Linear Feedback Shift Registers, W. A. Zuniga-Galindo [JIS Vol6(2003) abstract]
03/18
03/24	Title: Quantum Cryptography, Ker Tang [url]	18. (History) Solved: Trithemius’s Steganographia, Jim Reeds, Cryptologia, 22 (October, 1998), pp. 291-319 [pdf]
04/01	Title: Discussions on recent development: message authentication and hash functions, Andis [pdf] Abstract: We recently notice new cryptographic developments on a family of hash collision, MD5, RIPEMD, and SHA-1. In this talk, we review the basic building blocks of hash functions and survey on the recent advances in hash collision. Joint work with Prof Anshel and Severin Ngnossse. W3C: http://www.w3.org/PICS/DSig/SHA1_1_0.html	19. Entity authentication schemes using braid word reduction, Herve Sibert, Patrick Dehornoy, Marc Girault [iacr, 12/2002, abs, patent] 20. Physics of factorization, Revens, Mann, Zak [ arxiv, 03/2005 abs] 21. Quantum factoring, discrete logarithms, and the hidden subgroup problem, Richard Jozsa [ arxiv, 2000, abs] 22. Quantum algorithhms in group theory, Batty, etal [arxiv, 2003 abs] 23. (Diversions) Quantum Lecture, David Deutsch
04/08	Title: Principle of Quantum Computing, Stoytcho Stoev [url] Abstract: in this survey we introduce the foundation of quantum computation and show a simplified version of Deutsh-Jozca algorithm. In the spirit of Feynman’s first principle, we define the basic building blocks of quantum physic that have corresponding representation to mathematical objects, i.e. states, and observables, Dirac bra – ket notation, eigenstates, and Hilbert space (complex vector space), entanglement and unitary matrix on the eigenstates of orthonormal basis of H space etc. The talk exposition by examples aims to show the quantum physics corresponding to the interpretation on a model of mathematical system.	24. General Dynamics AIM hardware INFOSEC programmable chip [url]
04/15
04/22
05/06	Dissertation Defense
05/13	Title: Financial Cryptography : A Survey, Severin [url]
05/20	Discussion
05/27	Discussion	25. Quantum Fingerprinting [abstract, Field Institute 2004 ppt ], Barry Sanders 26. Quantum Computing and Zeroes of Zeta Functions, Van Dam (Q-kickboxer ??) [url], [abs]
05/31	Quantum Seminar @ Hunter College Place: Hunter North, Room 1246 Time: 2 PM Title: Quantum Fingerprinting, Barry Sanders, University of Calgary Abstract: Fingerprinting provides an efficient means for comparing large objects (long strings of numbers) by creating short versions. We will see that quantum fingerprinting can improve this scheme exponentially, and we will discuss few-qubit fingerprinting and experimental realizations.

Supplementary Text:

Malicious Cryptography: Exposing Cryptovirology, Young and Moti, 2004

Modern Cryptography: Theory and Practice, Wenbo Mao, 2004

Students’ diversion corner (AMS, MAA, SCIAM etc ): (nomination of exposition is welcome here)

[SZ, 04/01 Chaos by illustration ] What is a horseshoe? Shub et al [AMS Notices 05/2005, pdf]

[DK, 04/01 Chess by example ] N-Queens Problem, Rivin, Zimmerman, pp629-639 08/1994, pdf] --- the terse poem pp639 ‘Prince of Algebra’ by Joanne Growney is a crackoff.

[AK 04/01 Language ] Morphisms, squarefree strings, and tower of hanoi puzzles, Allouche, Shallit [AMM, 08/1994, pdf]