CS 858:
Unconditionally Secure Cryptography / Combinatorial Cryptography
last updated July 6, 2019
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 Spring Semester, 2019
by
Doug Stinson.
Course Information
- class time: 12:30 - 2:30 MW
- class location: DC 2568
- first lecture: Monday, May 6
- instructor: Doug Stinson
- office: DC 3522
- email: dstinson"at"uwaterloo.ca
Note: please use University of Waterloo accounts when sending me email.
- If you wish to make an appointment to see me, please send me
email or speak to me after class.
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" (also "information-theoretically 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.
We are also interested in the combinatorial techniques used to design and analyze these schemes. Combinatorial structures such as designs, codes, and extremal set systems play an essential role.
Below is a (preliminary) list of recent research papers on unconditionally secure cryptography.
These papers are examples of suitable papers that could be presented and discussed in class.
Note: LNCS denotes "Lecture Notes in Computer Science".
-
On (t, L)-fold perfect authentication and secrecy codes with arbitration.
Miao Liang, Lijun Ji.
Designs Codes and Cryptography online (pre-publication).
-
Nearly optimal robust secret sharing.
Mahdi Cheraghchi.
Designs Codes and Cryptography online (pre-publication).
- Maximal contrast color visual secret sharing schemes.
Sabyasachi Dutta, Avishek Adhikari, Sushmita Ruj.
Designs Codes and Cryptography online (pre-publication).
- Secret sharing on large girth graphs.
Laszlo Csirmaz, Peter Ligeti.
Cryptography and Communications, online (pre-publication).
- Improved bounds on 2-frameproof codes with length 4.
Minquan Cheng, Jing Jiang, Qiang Wang.
Designs Codes and Cryptography 87 (2017)
- New upper bounds for parent-identifying codes and traceability codes.
Chong Shangguan, Jingxue Ma, Gennian Ge.
Designs Codes and Cryptography 86 (2017)
- A construction for optimal c-splitting authentication and secrecy codes.
Mingchao Li, Miao Liang, Beiliang Du, Jingyuan Chen.
Designs Codes and Cryptography 86 (2017)
- Constructions of almost secure frameproof codes with applications to fingerprinting schemes.
Jose Moreira, Marcel Fernandez, Grigory Kabatiansky.
Designs Codes and Cryptography 86 (2017)
- On the Equivalence of 2-Threshold Secret Sharing Schemes and Prefix Codes.
P D'Arco, R De Prisco, A De Santis.
Cyberspace Safety and Security, CSS 2018, LNCS vol. 11161.
- Probabilistic Secret Sharing.
P D'Arco, R De Prisco, A De Santis, A Perez del Pozo, U Vaccaro.
43rd International Symposium on Mathematical Foundations of Computer Science , MFCS 2018.
- Visual Cryptography.
P D'Arco, R De Prisco.
SECITC 2016, LNCS vol. 10006.
- Hadamard Modulo Prime Matrices and Their Application in Cryptography: A Survey of Some Recent Works.
Yuri L. Borissov.
Proceedings of International Ethical Hacking Conference 2018.
- Improved user-private information retrieval via finite geometry.
Oliver W. Gnilke, Marcus Greferath, Camilla Hollanti, Guillermo Nunez Ponasso, Padraig O Cathain, Eric Swartz.
Designs Codes and Cryptography 87 (2019)
- A case study in almost-perfect security for unconditionally secure communication.
Esteban Landerreche, David Fernandez-Duque.
Designs Codes and Cryptography 83 (2017).
- Secure aggregation of distributed information: How a team of agents can safely share secrets in front of a spy.
David Fernandez-Duquea, Valentin Gorankob.
Discrete Applied Math. 198 (2016).
- Efficient and Secure Multiparty Computations Using a Standard Deck of Playing Cards.
Takaaki Mizuki.
Cryptology and Network Security, CANS 2016, LNCS vol 10052
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 combinatorics (designs, codes, extremal set systems) as well as some probability and algebra.
Lectures
I will first give some introductory lectures on the topics
to be studied.
To begin with, I will give a couple of lectures on combinatorial structures,
followed by a couple of lectures on unconditionally secure cryptography.
Giving oral presentations is an important skill that grad students
should develop during graduate school. Therefore,
in the remaining lectures, one or two students will each present a
research paper and lead a short discussion on the paper.
The presentation should be conference-style and take about
20-30 minutes, which will leave additional time for discussion.
Each presenter should submit their slides or notes to me before the lecture.
Each student is expected to give (at least) two presentations during
the course. All students should read the assigned papers prior to the lecture.
It is expected that students will attend all lectures. If you are going to miss a lecture for any reason,
please let me know.
Lecture Summaries
- Lecture 1 (May 6): Combinatorial background: Introduction to balanced incomplete block designs (BIBDs).
- Lecture 2 (May 8): Combinatorial background: Introduction to BIBDs and orthogonal arrays.
- Lecture 3 (May 13): Combinatorial background: Introduction to codes.
- Lecture 4 (May 15): Information-theoretic cryptography.
- There is no lecture on May 20, which is a holiday.
- Lecture 5 (May 22): Information-theoretic cryptography (continued).
- There are no lectures on May 27 or May 29, as I will be attending the CanaDAM 2019 discrete math conference.
- Lecture 6 (June 3): I presented a talk on Ideal Ramp Schemes and Related Combinatorial Objects
as well as the first part of Combinatorial Aspects of Key Distribution
for Sensor Networks. Slides can be found below.
- Lecture 7 (June 5): Paper presentations (first round) begin. Presentations by Chelsea Komlo and Thomas Lu.
- Lecture 8 (June 10): Presentations by Shannon Veitch and Kyle Tilbury.
- Lecture 9 (June 12): Presentations by Ahmed Zawia and Dimcho Karakashev.
- Lecture 10 (June 17): Presentation by Changsheng Chen (at 1:30 PM).
- Lecture 11 (June 19): Presentation by Ankith Arun Prabhu.
- Lecture 12 (June 26): Paper presentations (second round) begin. Presentation by Chelsea Komlo.
I also presented the rest of my talk on
Combinatorial Aspects of Key Distribution for Sensor Networks.
- Tuesday July 2: Presentation by Ahmed Zawia.
- July 3. Presentations by Kyle Tilbury and Thomas Lu.
- July 8: Presentations by Dimcho Karakashev and Shannon Veitch.
- July 10: Presentations by Changsheng Chen and Ankith Arun Prabhu.
- July 15: TBD
- July 17: TBD
- July 22: TBD
- July 24: Project presentations begin. Project presentations by (1) Ahmed Zawia and Dimcho Karakashev; and by ???
- July 29: Project presentations by (1) Chelsea Komlo and Shannon Veitch; and by ???
Notes and Slides
Project
Students will work in groups of two on a project in which they will
undertake research in a topic relevant to this course. 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.
A suggested timeline for the course project is as follows:
- Please form groups of two and inform me by email as to the membership of your group by June 17.
- Please send me a 1-2 page outline by June 24.
I will try to provide quick feedback on the suitability of the project.
- In-class presentations (20-25 minutes) will take place on
July 24 and July 29.
- The written report will not be due until sometime in the exam period.
The project could study one research paper in depth, or provide a survey/comparison of 2-3 related papers. The topic can be anything related to the course content, i.e., any aspect of unconditionally secure cryptography.
Your project should strive to add some significant content to a paper or papers. This could include one or more of the following:
- Including proof details (if they are omitted from the paper)
- Doing additional analysis or computations.
- Extending the results of the paper in some way.
- Implementing one or more protocols or crypto systems or providing a comparison of implementations.
Grades
Grades will be based on paper presentations and the project,
using the following formula:
- presentations: 40%
- project 60%