CS 858 Topics in Cryptography, Security and Privacy: Unconditionally Secure Cryptography

last updated March 16, 2010

This page contains information about the Computer Science graduate course "CS 858 Topics in Cryptography, Security and Privacy: Unconditionally Secure Cryptography". This course is being offered in the Winter Semester, 2010 by Doug Stinson.

Student Talk Schedule

Catalin-Alexandru Avram, Tuesday January 26, paper #2.
Alexandre Anzala-Yamajako, Thursday February 11, paper #13.
Vladimir Soukharev, Tuesday February 23, paper #6.
Ryan Henry, Thursday February 25, paper #10.
Kimiisa Oshikoji, Tuesday March 2, paper #3
Francis Chen, Thursday March 4, paper #7.
Dave Steiner, Thursday, March 11, paper #5.

All students should read each presented paper prior to the lecture in which it is presented.

Project Presentation Schedule

Ryan Henry (with Greg and Jalaj), Tuesday, March 30.
Catalin-Alexandru Avram and Vladimir Soukharev, Tuesday, March 30.
Alexandre Anzala-Yamajako and Francis Chen, Thursday April 1.
Kimiisa Oshikoji and Dave Steiner, Thursday, April 1.

Course Information

class time: 1:00 - 2:30 T/Th
class location: MC 2036A
first lecture: Tuesday, January 5
instructor: Doug Stinson
office: DC 3522
email: dstinson"at"uwaterloo.ca
Note: please use University of Waterloo accounts when sending me email.
telephone: (519)-888-4567 ext. 35590
consultation: I am often available for consultation in my office without an appointment. If you wish to make an appointment, please send me email or telephone me.
There is no textbook, although some introductory material will be taken from my textbook Cryptography Theory and Practice, Third Edition. A copy of this book has been placed on three-hour reserve in the Davis Centre library (Call number UWD 1529).

Course Description

The security of many cryptographic protocols depends on the (presumed) difficulty of solving computational problems such as factoring and discrete logarithm. However, it is also possible to design cryptographic protocols that can be proven secure without recourse to any computational assumptions. These protocols are termed "unconditionally secure".

Basically, unconditional security can be achieved through the use of shared secret information (the one-time pad is the most famous example) or through distributed information (e.g., secret-sharing schemes). In this course, we will examine recent research trends in several areas of unconditionally secure cryptography by reading and analyzing recent research papers.

Topics to be investigated can be from any area of unconditionally secure cryptographhy. The following list includes several suitable topics (there are other appropriate topics as well):

secret sharing schemes
key distribution
authentication codes
signature schemes
oblivious transfer reductions
tracing schemes
commitment schemes
perfectly secure message transmission
broadcast encryption
secure multiparty computation
chaffing-and-winnowing schemes

Research Papers

I have prepared a list of relevant papers from ICITS 2007, 2008 and 2009, as well as the journal Designs, Codes and Cryptography (DCC). The journal and the proceedings of ICITS 2007 and 2008 can be accessed on UW machines (or from remote machine using a proxy). The ICITS 2009 papers have not yet been published, so I have placed links to .pdf files temporarily on this web page. We will study a subset of the following papers:

Survey: Leakage Resilience and the Bounded Retrieval Model. Joel Alwen, Yevgeniy Dodis, and Daniel Wichs, ICITS 2009. The .pdf file is available here.
A Lower Bound on the Key Length of Information-Theoretic Forward-Secure Storage Schemes. Stefan Dziembowski, ICITS 2009. The .pdf file is available here.
Cryptanalysis of Secure Message Transmission Protocols with Feedback. Qiushi Yang and Yvo Desmedt, ICITS 2009 (also IACR eprint 2009/632). The .pdf file is available here.
Linear Threshold Multisecret Sharing Schemes? Oriol Farras, Ignacio Gracia, Sebastia Martin and Carles Padro, ICITS 2009. The .pdf file is available here.
Traitor-Tracing on Binary Strings. Michael J. Collins, IACR eprint 2009/633.
Commitment and authentication systems. Alexandre Pinto, Andre Souto, Armando Matos and Luis Antunes, DCC vol. 53, 2009 (also ICITS 2007, LNCS vol. 4883).
An impossibility result on graph secret sharing. Laszlo Csirmaz, DCC vol. 53, 2009.
On proper secrets, (t , k)-bases and linear codes. Tamir Tassa and Jorge L. Villar, DCC vol. 52, 2009.
Ideal secret sharing schemes whose minimal qualified subsets have at most three participants. Jaume Marti-Farre and Carles Padro, DCC vol. 52, 2009.
Detection and identification of cheaters in (t, n) secret sharing scheme. Lein Harn and Changlu Lin, DCC vol. 52, 2009.
Establishing the broadcast efficiency of the Subset Difference Revocation Scheme. Thomas Martin, Keith M. Martin and Peter Wild, DCC vol. 51, 2009.
Upper bounds for parent-identifying set systems. Michael J. Collins, DCC vol. 51, 2009.
Unconditionally Secure Blind Signatures. Yuki Hara, Takenobu Seito, Junji Shikata and Tsutomu Matsumoto, ICITS 2007, LNCS vol. 4883.
Almost Secure (1-Round, n-Channel) Message Transmission Scheme. Kaoru Kurosawa and Kazuhiro Suzuki, ICITS 2007, LNCS vol. 4883.
On Exponential Lower Bound for Protocols for Reliable Communication in Networks. K. Srinathan, C. Pandu Rangan and R. Kumaresan, ICITS 2007, LNCS vol. 4883.
Unconditionally Secure Chaffing-and-Winnowing for Multiple Use. Wataru Kitada, Goichiro Hanaoka, Kanta Matsuura and Hideki Imai, ICITS 2007, LNCS vol. 4883.
Almost Secure 1-Round Message Transmission Scheme with Polynomial-Time Message Decryption. Toshinori Araki, ICITS 2008, LNCS vol. 5155.
Upper Bounds for Set Systems with the Identifiable Parent Property. Michael J. Collins, ICITS 2008, LNCS vol. 5155.
Simple Direct Reduction of String (1,2)-OT to Rabin's OT without Privacy Amplification. Kaoru Kurosawa and Takeshi Koshiba, ICITS 2008, LNCS vol. 5155.

If there is a paper not in the above list that is relevant to the course and which you would like to study, just let me know.

Prerequisites

There are no formal prerequisites. A previous course in cryptography or security would be helpful, especially for establishing a context for the topics to be studied in the course. The techniques used in the course will primarily be mathematical, based on undergraduate level combinatorics, probability and algebra.

Lectures

I will give some introductory lectures on the topics to be studied. I will also present some of my own work at various times in the course. In each remaining lectures, a students will present a research paper and lead a discussion on the paper. The presentation should take about 45 minutes so that the paper can be covered in a reasonable amount of depth and detail. This will leave about 30 minutes for discussion. Each student is expected to give at least one presentation during the course. Students can give additional presentations if they wish to do so.

Project

Students will work in groups of two on a project in which they will undertake research in a topic relevant to this course. Possible ideas for projects will be mentioned in class. Students will have to submit a proposal, present their work in class at the end of the term, and write a workshop-quality report of at least 10-15 pages in length.

Grades

Grades will be based on paper presentations, paper reviews, class participation (including presentation feedback) and the project, using the following formula:

presentation: 35%
class participation and presentation feedback 15%
project 50%