Lecture materials, November 22-26

Topics in Combinatorial Computing and Cryptography
Gdańsk, November 22-26, 2010
Stanisław P. Radziszowski

http://www.cs.rit.edu/~spr/gdn2010

Crash Overview of Cryptography (full page pdf) (two-up pdf),
Demise of MD5 and SHA-1, Emerging New Hash SHA-3 (full page pdf) (four-up pdf), background on hashing, MD5 and SHA-family, NIST SHA-3 competition, current status. Shorter and updated (March 2011) versions of the same (full page pdf) (four-up pdf).
SHA-3 finalists, March 2011 (full page pdf) (two-up pdf).
Some SHA-3 candidates in detail: Skein by John Hicks (2010), Groestl by Joel Lathrop (2009), Hamsi (2009) and more Hamsi (2010) by the author Ozgul Kucuk, BMW by Liliya Andreicheva, ... and some more brief comments (full page pdf) (two-up pdf). Keccak animation (in German) by Marko Krause.
Cube Attacks on Cryptographic Hash Functions (slides) by Joel Lathrop, MS-CS thesis at RIT, May 21, 2009, includes reduced-round cube attacks on Keccak and ESSENCE.
Update on Luffa by Dai Watanabe, Hisayoshi Sato and Christophe de Carnniere presented at the SHA-3 conference, Santa Barbara, CA, August 24, 2010.
Advanced Encryption Standard (AES) - history and algorithm. AES animation ( swf in English) by Enrique Zabala, Uruguay 2003/2008 (or swf in Spanish). A Stick Figure Guide to the AES by Jeff Moser, 2009, a cartoon explaining it all.
Overview of Cryptanalysis of the AES, joint work with Alan Kaminsky and Michael Kurdziel, overview of attacks on AES, prognosis. Link to paper from MILCOM '2010, San Jose, CA, November 2, 2010.

SHA-1 broken (2005), hm, not so fast ... so far no collision has been found.
NIST SHA-3 Competition main website, call for submissions on January 23, 2007.
Tentative timeline until conclusion in 2012.
All submissions are gathered at the SHA-3 Zoo website at Graz University of Technology.
Round 1 , 51 candidates announced on December 9, 2008.
First SHA-3 Candidate Conference, KU Leuven, Belgium, February 25-28, 2009.
Round 2 , 14 candidates announced on July 24, 2009.
Second SHA-3 Candidate Conference, Santa Barbara, CA, August 23-24, 2010.
eBASH/SUPERCOP, cryptographic software benchmarking website by Daniel Bernstein.
SHA-3 Hardware Implementations, hardware benchmarking of candidates at the Graz University of Technology.
Round 3 finalists BLAKE, Grøstl, JH, Keccak, and Skein, December 9, 2010.
Final tweaked packages , January 31, 2011.
Status Report on the Second Round, how finalists were chosen, February 2011.
The SHA-3 Song lyrics and video.
BLAKE animation, September 2011.
SHA-3 Winner, October 2012.
SHA-3 Standardization, February 2013.
Draft FIPS 202, May 2014.

Some Ramsey Problems - Computational Approach (full page pdf) (two-up pdf), background on Ramsey and Folkman numbers, asymptotics of Ramsey numbers, focus on triangle-avoiding cases and computational techniques.
Ramsey Numbers Involving Quadrilateral (full page pdf) (two-up pdf), joint work with Xiaodong Xu and Zehui Shao. Link to paper.
Progress on Hendry's Tables, joint work with Kevin Black, Daniel Leven (REU 2009), Jesse Calvert, Mike Schuster (REU 2010), the quest of computing Ramsey numbers for all pairs of graphs on up to 5 vertices. Links to papers to appear: REU 2009, REU 2010.
General Lower Bound Constructions for Ramsey Numbers, joint work with Xiaodong Xu. Links to papers: JGT 47 (2004) 231-239 (with Xu Xiaodong and Xie Zheng), ElJC 11(1) (2004) #R35 (with Xu Xiaodong, Xie Zheng and Geoffrey Exoo), to appear (with Xiaodong Xu and Zehui Shao).
Reconstruction Numbers of Small Graphs, joint work with David Rivshin, graph reconstruction conjecture, existential and universal reconstruction numbers, computational results. Links to papers: JCMCC 62/63 (2007) 85-96, 93-95 (with Brian McMullen), AJC 45 (2009) 175-188 (with David Rivshin), to appear in JCMCC (with David Rivshin).
Complexity Results in Graph Reconstruction, joint work with Edith Hemaspaandra, Lane Hemaspaandra and Rahul Tripathi. Link to paper: URCS Technical Report, journal version in Discrete Applied Mathematics, 152(2) (2007), 103-118.

Small Ramsey Numbers, revision #13, August 2011, dynamic survey of known values, bounds and computational results on various types of Ramsey numbers at the Electronic Journal of Combinatorics.
On the Most Wanted Folkman Graph, joint work with Xiaodong Xu, Geombinatorics, Vol. XVI (4) (2007) 367-381, the quest for the smallest K₄-free graph which is not a union of two triangle-free graphs.
Learn all about Ramsey numbers from Paul Erdös himself. Part 5 of the documentary "N Is a Number: A Portrait of Paul Erdös" even presents some proofs. Watch all 9 parts!
Links to all other Ramsey theory papers by spr.