| Name: | Eli Goldin |
|---|---|
| Email: | (first name).(last name) (at) rutgers.edu |
| Home Institution: | Columbia University |
| Project: | AES and Expander Graphs |
About My Project
AES (Advanced Encryption Standard) is one of the most common cryptographic tools used today. It is a blockcipher, which one can think of as a collection of permutations which are hard to distinguish from a random permutation when composed enough times. However, it's security mainly comes from the fact that nobody has broken it, and there are not many meaningful arguments as to why this particular set of permutations is indeed indistinguishable from random. The goal of this project is to explore more mathematically the security of AES in order to find an attack or an argument of security. Alternatively, these explorations could lead to a more rigorously secure blockcipher.
In particular, we can view AES as a generating set for the symmetric group, and we can then look at the corresponding Cayley graph. If AES is indeed secure, we would expect this Cayley graph to be an expander graph. Several things to explore here are how exactly the expansion of the corresponding Cayley graph is connected to the security of any blockcipher, and whether AES does indeed create an expander graph.
Research Log
Week 1
This week was orientation. I set up this website, as well as worked on my understanding of Kassabov's paper on an explicit finite generating set of the symmetric group for which the Cayley graphs form a family of expanders. I also came up with a fairly week yet non-trivial lower bound on the expansion of a variant of AES I call AES(1 2).
Week 2
This week I presented my project to the REU. I also formalized and presented my proof from the previous week to Periklis. After that, I read Friedman's paper on the expansion of sets of transpositions. This gave me a more thorough understanding of the graph theory side of things, as I was unused to working with the Laplacian of a graph. I also began to tackle some of the key questions for this project. In particular I tried to upper bound the Kazhdan constant for AES(1 2) by looking at the standard representation. I also started a running document of notes and ideas for my own use.
Week 3
I succesfully computed a weak (i.e. constant) upper bound for the Kazhdan constant for AES(1 2) by finding a specific witness in the standard representation. I wrote a script to give an upper bound for the Kazhdan constant for any generating set of Sym(N) by randomly sampling vectors in the standard representation. I also proved that a combinatorial expander has a high Kazhdan constant, although the relationship I found is too weak to be of use with the bounds on the Kazhdan constant I found. I also read the original AES proposal.
Week 4
I applied simple optimization techniques to find a "better" witness vector to upper bound the Kazhdan constants for generating sets of Sym(N). However, I was not able to get a bound for AES(1 2) below the square root of 2. Troubling, when applying these techniques to a collection of random permutations, I achieved similar bounds. I also presented more of the Kassabov paper to my mentor, and attended a group meeting at which I explained my approach to the question at a high level.
Week 5
I have been working with a more accurate definition of AES(1 2), which it turns out does not generate the symmetric group. I found an explicit permutation which is not generated by AES(1 2). I also used the result from the paper by Babai and Hayes to show that AES_pi does in fact generate the symmetric group/alternating group with high probability when pi is sampled randomly from all permutations.
Week 6
Discussion with Chin prompted a more generalized argument to show that AES_pi can not generate the symmetric group for pi the composition of sufficiently few (less than n/2) permutations. Further group discussion helped identify candidates for several explicit permutations pi for which AES_pi may indeed generate Sym(N). For example, (a b)(1 2 ... N)(a b) for any transposition (a b). I also began playing around with using GAP to test these hypotheses explicitly before attempting to prove them. I also continued presenting more technical details of the Kassabov paper, and I will finish these presentations next week.
Week 7
This week I wrote code in GAP and Python to explicitly calculate the spectral gap for Cay(Sym(N), AES_pi) for very low values of n. This was too slow, so instead I focused on calculating the spectral gap for a much smaller Schreier graph. Any bound on the expansion of this graph should also bound the expension of Cay(Sym(N), AES_pi). From the very preliminary results, it appears that for random sigma, this graph is NOT an expander. Thus, one would hope that this simpler graph is powerful enough to bound expansion on Cay(Sym(N), AES). The next steps are to both run this program on higher values of n and to attempt to prove some bound on the expansion of this graph.
Week 8
This week Gleb Posobin noticed an issue with my code for defining AES_pi. Thus, the results from last week are inaccurate. I fixed this code and reran it. The new results seem to imply that the Schreier graph is an expander, although this does not necessarily mean that Cay(Sym(N), AES_pi) is. I repeated the experiment for a slightly larger Schreier graph for which we think this implication does hold, and based on these preliminary results this also appears to be an expander. I also performed a similar experiment on the ideal cipher, for which the spectral gaps were much larger and increased muchb faster. I also improved the speed of my code, although there is still work to be done in that regard.
Week 9
This is the final week of the REU! I presented my project to my peers and I wrote up my final paper. In terms of research, Lazaros kindly gave me access to one of DIMACS machines, which I began to use to perform some experiments. I also worked with Garrison Grogan on constructing a new generalization of AES which is slightly more specified. Perhaps this will have worse expansion than the generalization we are currently using.
References & Links
Here are the papers I have read for my project:- Symmetric Groups and Expander Graphs, Martin Kassabov - arXiv.
- On Cayley Graphs on the Symmetric Group Generated by Transpositions, Joel Friedman - Springer
- AES Proposal: Rijndael, Joan Daemen, Vincent Rijmen - NIST.
- The Probability of Generating the Symmetric Group when one of the Generators is Random, Laszlo Babai, Thomas P. Hayes - Publicationes Mathematicae Debrecen.