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

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".

  1. On (t, L)-fold perfect authentication and secrecy codes with arbitration. Miao Liang, Lijun Ji. Designs Codes and Cryptography online (pre-publication).
  2. Nearly optimal robust secret sharing. Mahdi Cheraghchi. Designs Codes and Cryptography online (pre-publication).
  3. Maximal contrast color visual secret sharing schemes. Sabyasachi Dutta, Avishek Adhikari, Sushmita Ruj. Designs Codes and Cryptography online (pre-publication).
  4. Secret sharing on large girth graphs. Laszlo Csirmaz, Peter Ligeti. Cryptography and Communications, online (pre-publication).
  5. Improved bounds on 2-frameproof codes with length 4. Minquan Cheng, Jing Jiang, Qiang Wang. Designs Codes and Cryptography 87 (2017)
  6. New upper bounds for parent-identifying codes and traceability codes. Chong Shangguan, Jingxue Ma, Gennian Ge. Designs Codes and Cryptography 86 (2017)
  7. A construction for optimal c-splitting authentication and secrecy codes. Mingchao Li, Miao Liang, Beiliang Du, Jingyuan Chen. Designs Codes and Cryptography 86 (2017)
  8. Constructions of almost secure frameproof codes with applications to fingerprinting schemes. Jose Moreira, Marcel Fernandez, Grigory Kabatiansky. Designs Codes and Cryptography 86 (2017)
  9. 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.
  10. 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.
  11. Visual Cryptography. P D'Arco, R De Prisco. SECITC 2016, LNCS vol. 10006.
  12. 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.
  13. 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)
  14. A case study in almost-perfect security for unconditionally secure communication. Esteban Landerreche, David Fernandez-Duque. Designs Codes and Cryptography 83 (2017).
  15. 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).
  16. 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

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:
  1. Please form groups of two and inform me by email as to the membership of your group by June 17.
  2. Please send me a 1-2 page outline by June 24. I will try to provide quick feedback on the suitability of the project.
  3. In-class presentations (20-25 minutes) will take place on July 24 and July 29.
  4. 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:

Grades

Grades will be based on paper presentations and the project, using the following formula: