CSC 85030 Quantum Cryptography

Friday 2-4 Room 3212

Dr. Michael Anshel

CCNY email anshel@cs.ccny.cuny.edu ; Office NAC 8/202-C; Voice mail 212-650-6164

GC Office: Room 4307; Office hours at GC: Friday 1:00-1:50pm Room#4307 and by appointment

AOL email: MikeAt1140@aol.com

Web Page http://www-cs.engr.ccny.cuny.edu/~csmma/

IDS 81610: Classical and Quantum Computing

Friday 4:15-6:15 Room 8404 (may change to Room 3212);  Dr. Michael Anshel and Dr. XiangDong Li

 

Note: You can find informal listings of various interests in cryptography and quantum information computation at the seminar in Spring 2005, and Fall 2004.

 

Student Roaster [pdf, xls] for CSC 85030 and IDS 81610

 

Weekly Schedule (Subject to Change)

.

Topics/Conceptual Notes

Class Handouts/Fun Readings

09/02

CSC 85030 Course overview; Syllabus and References; objective for the class is for each student/team to take a stab on part of [1] survey paper, write a survey, and then aggregate the pieces into a collective survey paper on Quantum Cryptography.

IDS 81610 Course overview; syllabus and references; take a brief tour at [3] and highlight some recent works on quantum computing.

1.        Quantum Cryptography,

http://www.arxiv.org/abs/quant-ph/0101098

Authors: Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, Hugo Zbinden

2.        Practical Issues
http://www.arxiv.org/abs/quant-ph/0406147
Title: Why Quantum Cryptography?
Authors: Kenneth G. Paterson, Fred Piper, Ruediger Schack

3.        ACM Survey: An Introduction to Quantum Computing for Non-Physicists
http://www.arxiv.org/PS_cache/quant-ph/pdf/9809/9809016.pdf

 

09/09

CSC 85030 Introduction to Braid Group Cryptography

IDS 81610 Quantum Circuit, Solovay-Kitaev algorithm one-way functions in reversible computation, quantum algorithms in group theory

4.        Reading list 1: Non-commutative Braid Group Cryptography

5.        Reading list 2:  Quantum Mathematical Physics

 

09/16

Reference: #4

6.        From non-abelian anyons to quantum computation to coin-flipping by telephone [url], Mochon, Carlos. [Thesis 05/11/2005]

7.        Bloch Sphere Talk [pdf], Ian Glendinning, [Europe VCPC 02/16/2005]

 

09/23

CSC 85030 Algebra and Cryptography Seminar (Room 8405 || 2-3 PM )

Modern Cryptanalysis: Generic Complexity and Asymptotic Algebra, Alexei Miasnikov, McGill University/Graduate Center http://www.math.mcgill.ca/~alexeim/

Abstract: In this talk I am going to discuss two recent developments in modern cryptanalysis: generic complexity and asymptotic dominance. The first one concerns with behavior of algorithms on most typical or generic inputs, while the second one deals with the asymptotically most dominant properties of algebraic objects. My focus will be on some new intriguing mathematical problems and ideas that are coming to algebra, and especially, to group theory, from modern algebraic cryptography. The talk should be accessible to anyone who is interested in group theory and cryptography.

8.        Lattice attacks on RSA-encrypted IP and TCP [pdf], Paul Crouch and James Davenport

9.        Structural Quantum Programming [2003 Thesis], Bernhard Oemer.  (Singh’s choice)

 

 

09/30

 Class paper: Post-quantum Diffie-Hellman Key Exchange

10.     Title: Topological Quantum Computing with Only One Mobile Quasiparticle, quant-ph/0509175 [abs, ps, pdf, other]

Authors: S. H. Simon, N.E. Bonesteel, M. H. Freedman, N. Petrovic, L. Hormozi

11.     Title: Braid Topologies for Quantum Computation, quant-ph/0505065 [abs, ps, pdf, other]

Authors: N.E. Bonesteel, Layla Hormozi, Georgios Zikos, Steven H. Simon

10/07

Class paper: Post-Quantum Diffie-Hellman Key Exchange

Selected topic: Quantum information processing courses

 

12.     Staging Quantum Cryptography with Chocolate Balls, Karl Svozil 2005 [abs] (Public performance at TU Vienna)

13.     Quantum Clock Synchronization and Quantum Error Correction (NASA-DoD workshop) pp8, John Preskill 2000 [abs, pdf]

14.     PKCS#3 RSA Technote: Diffie-Hellman Key Agreement Standard [abs]

15.     Cryptomathic Newsonink: Simple Deterministic Prime Test 32 bits P,  2000, [abs, article]

16.     Ivan Damgard at Denmark, Fall 2005 QIP course, Quantum Mechanics Quick Reference [ pdf ], Note on Quantum Fourier Transforms [ pdf ]

17.     David Mermin, Quantum Computation Lecture Notes and Homeworks at Cornell, chapter 1 Fundamental Properties of Cbits and Qbits pp45  [pdf] ; Chapter 2 The General Computation Process pp37, i.e quantum register, CNOT, gate etc [pdf] ; Chapter 3 Breaking RSA with Quantum Computer pp28, i.e. elementary number theory, quantum fourier transform, and elementary group theory [pdf] ; Chapter 4 Searching with Quantum Computer pp14, i.e. Grover’s algorithm [pdf] ;  Chapter 6 Quantum Cryptography pp20, i.e. quantum entanglement, teleportation [pdf]

10/14

[Tang Ker] Title:  Quantum Entanglement:

In this talk we review the historical development of quantum entanglement, from the Plank constant, notion of black body, i.e. dark clouds, leading to Bohr’s atomic structure (electron, quantum discrete orbit/photon), Einstein’s relativity, Schrodinger’s wave equation,  E y = H y, Heisenberg Uncertainty Principle Dx Dp ³ h (x is the position and p momentum), a.k.a. wave-particle duality that a measurement induces wave function collapse, the 1935 EPR paradox, controversy of quantum mechanics non-locality principle and locality principle?, and lastly Bell’s inequality theorem on local hidden variable theory and the possible violation by QM in the 80’s experiment of Clauser, Horne, and Shimony CHSH Bell test, -2 £ S £ 2 where S are terms of quantum correlations of particle pairs.

18.     Title: Startup to use IBM tech for optical cryptography, John Walko, EETimes, 10/10/2005 [url] 

19.     Title:  Implementation of Grover's Quantum Search Algorithm in a Scalable System, K.-A. Brickman, P. C. Haljan, P. J. Lee, M. Acton, L. Deslauriers, C. Monroe [abs]

10/21

CSC 85030 Algebra and Cryptography Seminar (Room 8405 || 2-3 PM )

Benjamin Fine (Fairfield University), Algebraic Cryptosystems Using Linear Groups

 

[Prof Li]  IDS 81610 (4:15-6:15) Title: TBA

http://search.cpan.org/~ajgough/Quantum-Entanglement/

http://tph.tuwien.ac.at/~oemer/qcl.html

http://www.enyo.de/libquantum/

http://rugth30.phys.rug.nl/compphys0/qcedownload.htm

http://www.qc.fraunhofer.de/doc/Manual/13graphapp

http://www.senko-corp.co.jp/qcs/download.html

http://www.robots.ox.ac.uk/~charles/phd/qcf.doc

 

Invited topics for students’ talk: Fourier transform , Hadamard Transforms, Parseval’s Theorem, Plancherel’s Theorem, Duality, Abelian groups, non-abelian groups, Shor’s factoring algorithm, Grover’s search algorithm, Deutsch-Jozsa discrete function recognizer, hidden subgroup recognition

 

20.     Title: Classical Cryptography in a Quantum Setting, Waterloo master thesis 2004, Michael Stephen Brown,[abs]

21.     Conference at TAMU: Mathematics of Quantum Computation and Quantum Technology (11/13 Schedule ) e.g. introduction to quantum computing & algorithms [url] S. Lomonaco etc

22.     Cryptography and Computer Algebra at Darmstadt [url] and tech report:

22.1.Polynomial Time Quantum Algorithm for the Computation of the Unit Group of a Number Field [pdf], Schmidt and Vollmer, Mai 2004

22.2.A Faster Lattice Reduction Method Using Quantum Search [pdf], Ludwig, Feb 2003

23.     Springtime Attraction at Cornell Math: from topology (geometric group theory) to cryptography, e.g. braid, conjugacy search problem, matrix groups, Miasnikov's black holes etc [URL]

24.     Quantum Key Distribution Protocol with User Authentication, Lee, Lee, Lee, Lim, Yang [2005 abs]

25.     Implementation of Quantum Maps by Programmable Processors, Hillery, Ziman, and Buzek [2005 abs]

26.     Dedekind Zeta Functions and the Complexity of Hilbert’s Nullstellensatz, J. Maurice Rojas [abs]

27.     Lattice Problems in NP È coNP, Dorit Aharonov, Oded Regev [JACM 10/2005,  cached abs]

10/28

Prof Anshel will participate in a conference at John Hopkin. 

CSC 85030 student seminar day

[naïve andis] Tentative title: Braid October – a brief introduction to non-commutative group theoretic cryptography in classical and in quantum?

 

[Prof Li]  IDS 81610 (4:15-6:15) Title: TBA

 

 

 

11/04

 

28.     Quantum Theory Looks at Time Travel, Greenberger, Svozil, Chapter 4 of Quo Vadis QM? 2005 [abs, pdf], talk [abs] at CCNY, Physics Colloquium Nov 02

11/11

 

29.     A Polynomial Quantum Algorithm for Approximating the Jones Polynomial Authors: Dorit Aharonov, Vaughan Jones, Zeph Landau  [abs]

30.     CCNY Conference:

30.1.Asymptotic Group Theory Conference at CCNY

11/18

[Sadat , pdf, abs ] title: Fabric of Reality by David Deutsch – a view of parallel universe and quantum phenomena, 4 theories into 1 coherent theory, i.e. quantum physics, computation, evolution, and knowledge(epistemology)

31.     Workshop and Conference:

31.1.IBM-Columbia-NYU Theory Day @Nov 18[Fall 05 schedule]

31.2.Algebraic Methods in Cryptography @ Nov 17-18 Bochum.De [url]

31.3.Le Calcul des Tresses (Braids), Dehornoy [ artistic slides pdf ]

32.     Quantum Watermarking by Frequency of Error When Observing Qubits in Dissimiliar bases, G. G. Wolley III [abs] [ Elbasi’s choice ]

33.     Anonymous Signature Schemes, Guomin Yang, Duncan S. Wong, Xiaotie Deng, and Huaxiong Wang [ abs ]

34.     Integration and Conjugacy in Knot Theory, Iain Moffatt, Nov 2005 [ Thesis abs ]

35.     Group-Theoretic Algorithms for Matrix Multiplication, H Cohn, R Kleinberg, B. Szegedy, and C. Umans [ abs url ]

                                                                                                      

 

11/25

Thanksgiving Recess

36.     Le Calcul Des Tresses, Patrick Dehornoy, 2005 [talks]

37.     Combinatorial Group Cryptography Bulletin Vol 1 Dec 2005 @ Hebrew University, Boaz Tsaban, [info]

12/02

 

38.     Crypto Farm by Lipmaa, Braid Groups [ url  ]

39.     Schrodinger’s Atomic Cats and Creation of a Six-atom Schrodinger Cat State, D. Leibfried et. al. Nature 2005, [ url , pdf  ]

40.     ACM conference on Electronic Commerce, 2006 [ url ]

41.     Forest diagrams for elements of Thompson’s group F, Jim Belk, 2003-05 [arxiv.org, abs ], Ph.D. thesis 2005 [ pdf  ]

42.     The Simultaneous Conjugacy Problem for Thompson's Group F is Solvable, Francesco Matucci,  Cornell seminar 2005 [ abs ]

43.     IEEE Security & Privacy (free article on Nov, 2005)

43.1.Signaling Vulnerabilities in Wiretapping Systems, Micah Sherr, Eric Cronin, Sandy Clark, Matt Blaze [ url ]

43.2.Security, Wiretapping, and the Internet, Susan Landau, [ url ]

12/09

[ Mike Carlisle] Title: Quantum Factoring and Quantum Fourier Transform [abs]

[James Ulrich] Title: Thesis Defense Dress Rehearsal: Ore Revisted: An Algorithmic Investigation of the Simple Commutator Promise Problem [abs] Time 4:00 PM

[Mike Laufer] Title: Quantum Circuit [abs]

[Roger Stovell ] Title: Visual Passwords [abs, url ]

 

1.        Spin networks, quantum automata, and link invariants, Silvano Garnerone, et al [abs]

2.        Locking of accessible information and implications for the security of quantum cryptography, andor bariska, et al [abs]

3.        Combinatorial Group Cryptography Bulletin Vol2, Dec 2005 @ Hebrew University, Boaz Tsaban, [info]

4.        A New Key Exchange Protocol Based on the Decomposition problem, Vladimir Shpilrain, Alexander Ushakov, Nov 6, 2005 [abs]

12/16

Exam Week

5.        Linear Optical Quantum Computing, Pieter Kok, et. al. [ abs ]

 

Reference for CSC 85030 is online monograph at http://www.cacr.math.uwaterloo.ca/hac/
Title: Handbook of Applied Cryptography
Authors A.J.Menezes,Paul C.van Oorschot and Scott A. Vanstone

 

Reference for IDS 81610

§         Yorick Hardy and Willi-Hans Steeb, Classical and Quantum Computing: With C++ and Java Simulations, Birkhauser 2002

§         --, Problems and Solutions in Quantum Computing and Quantum Information, World Scientific 2004

§         Michael A Nielsen and Isaac L Chuang, Quantum Computation and Quantum Information, Cambridge University Press 2000

§         Mika Hirvensalo, Quantum Computing, 2nd edition, Springer 2003

 

Course Flyer Description [pdf, doc]

Supplementary Text:

TBD

 
Previous workshops of interest: 
1.              Workshop Frontiers in Electronic Elections (FEE 2005) http://www.win.tue.nl/%7Eberry/fee2005/program.html
2.             Low-cost and Lattice-based cryptology http://users.info.unicaen.fr/~dabosvil/CAEN2005/

 

Students’ diversion corner (AMS, MAA, SCIAM, Phys of Letters etc ): (nomination of exposition is welcome here, copyright law is by fair use principle)

·                AMS Notices Dec 2005, Science in the Looking Glass, and What is …a Random Matrix [ url ]  
·                [AK]  Ever wonder? “The Library is a sphere whose exact center is any of one of its hexagons and whose circumference is inaccessible.”  
-Jorge Luis Borges, c.f. AMS Notices Nov 2005 [ url , pdf  ]
·                [AK] “Freedom is for Science what air is for animal; deprived of this freedom…. because, for science, to be subordinated means to die.” 
-Henri Poincare, A Life in the Service of Science,  AMS Notices Oct 2005 [url, pdf]
·                [AK] Mathematics, Biology, and Physics: Interactions and Interdependence [ url , pdf ], AMS Notices Sep 2005