Talks Abstract
Title: How to Live and Prosper with Insecure Cyberinfrastructure
Andrew Odlyzko
University of Minnesota
USA
Abstract: Mathematics has contributed immensely to the development of secure cryptosystems and protocols. Yet our networks are terribly insecure, and we are constantly threatened with the prospect of imminent doom. Furthermore, even though such warnings have been common for the last two decades, the situation has not gotten any better. On the other hand, there have not been any great disasters either. To understand this paradox, we need to consider not just the technology, but also the economics, sociology, and psychology of security. Any technology that requires care from millions of people, most very unsophisticated in technical issues, will be limited in its effectiveness by what those people are willing and able to do. This imposes strong limits on what formal mathematical methods can accomplish, and suggests that we will have to put up with the equivalent of baling wire and chewing gum, and to live on the edge of intolerable frustration.
Title: Hall Algebras in Representation Theory
Jie Xiao
Tsinghua University
P. R. China
Abstract: Hall algebras introduced first by C. M. Ringel build up a bridge to connect the representation
theory of algebras, infinite dimensional Lie algebras and quantum groups. We will report
some recent progress for the Hall algebra approach in algebraic and geometric aspect to
realize the infinite dimensional Lie algebras and quantum groups, including Hall algebras
arising from triangulated categories and Lie algebras from derived categories.
Title: Proof of Kedlaya's Conjecture
Bernhard Schmidt
Nanyang Technological University
Singapore
Abstract: A cyclotomic integer is a (finite) sum of complex roots of unity. Two cyclotomic integers X and Y are called equivalent if there is a complex root of unity B such that Y = B X. An n-Weil number in a cyclotomic field is a cyclotomic integer X with |X|^2 = n. Gauss and Jacobi sums are examples of such Weil numbers which have been studied intensively. Kiran S. Kedlaya has conjectured that, for any fixed positive integer n, there are only finitely many nonequivalent n-Weil numbers in the union of all cyclotomic fields. We present a proof of this conjecture.
Title: Sparse Recovery using Sparse Random Matrices
Piotr Indyk
MIT
USA
Abstract: Over the recent years, a new linear method for compressing high-dimensional data (e.g., images) has been discovered. For any high-dimensional vector X, its sketch is equal to A X, where A is an m * n matrix (possibly chosen at random). Although typically the sketch length m is much smaller than the number of dimensions n, the sketch contains enough information to recover an approximation to X. At the same time, the linearity of the sketching method is very convenient for many applications, such as data stream computing and compressed sensing.
The major sketching approaches can be classified as either combinatorial (using sparse sketching matrices) or geometric (using dense sketching matrices). They achieve different trade-offs between various parameters of interest. Thus, it is desirable to understand the connections between them, with the goal of obtaining the "best of both worlds" solution.
In this talk, we show that, in a sense, the combinatorial and geometric approaches are based on different manifestations of the same phenomenon. This connection will enable us to obtain several novel algorithms and constructions, which inherit advantages of sparse matrices, such as lower sketching and recovery times.
Title: Boolean Functions with Many Optimal Cryptographic Properties
Keqin Feng
Tsinghua University
P. R. China
Abstract: In order to resist (linear, correlation, algebraic,...) attack methods, successively invented in stream cipher systems, Boolean functions have been required to have a variety of cryptographic properties (balanced, correlation immunity, large algebraic degree, nonlinearity, algebraic immunity,...). There are remarkable achievements in researching the best bounds and constructing the optimal Boolean functions for INDIVIDUAL cryptographic property. But it is a difficult challenge to find functions achieving all of necessary criteria and the research of such functions has taken a significant delay with respect to cryptanalysis. In this talk we present a construction of balanced Boolean functions with optimal algebraic immunity, optimal algebraic degree and good nonlinearity which is better than known examples. Moreover, it might be surprising that the construction is very simple.
Title: A survey on the security of RSA cryptography
Sze Ling Yeo
Institute for Infocomm Research
Singapore
Abstract: In 1977, a breakthrough in cryptography was achieved with the invention of the RSA cryptosystem by Ron Rivest, Adi Shamir and Leonard Adleman. Due to its simplicity, the RSA encryption scheme has progressed to become among the most popular public-key encryption systems used in modern day applications where security is a concern. As such, over the past thirty years, much effort has been devoted to analyze its security as well as vulnerabilities.
In this talk, we will seek to present a survey of the RSA cryptography from different perspectives. In particular, we will review some of the factoring algorithms that have a direct impact on the security of the RSA encryption function and highlight some attacks that exploit weaknesses in either the implementation or special instances of the RSA cryptosystem.
Title: Derandomization of Space-Bounded Computational Classes
Elad Verbin
Tsinghua University
P. R. China
Abstract: An outstanding question in computer science is the "L=RL?" question: whether any computation that uses logarithmic space and random bits, can be equivalently performed without any random bits, but still in logarithmic space. This question is one of the only questions in complexity theory that does not necessarily depend on getting an answer to the P vs. NP question.
In this talk, I will discuss the two major approaches for proving L=RL. The first approach is to try to get a deterministic logspace algorithm for checking whether in an input directed well-mixing graph there is a path from vertex s to vertex t. This approach gained a big moral boost lately by Reingold's groundbreaking algorithm for checking connectivity in undirected graphs, and by subsequent works.
The second approach is to try to build a pseudorandom generator for read-once polynomial-width branching programs, using logarithmic seed. The best results in this approach are Nisan's generator on the one hand and espilon-biased generators on the other hand. This approach seems to have been less successful so far, compared to the first approach.
In this talk, I will outline both approaches, sketch what is known, and try to give an idea of the techniques involved. The talk is aimed at a broad mathematical audience. I will try to present several "self-contained" problems on the mathematics of computation, which are important in the context of the L=RL problem, and where background in computer science does not seem to be strictly necessary.
Title: Applying Time-Memory-Data Trade-Off to Meet-in-the-Middle Attack
Khoong Ming Khoo
DSO National Laboratories
Singapore
Abstract: In this talk, we present several new attacks on multiple encryption block ciphers based on the meet-in-the-middle attack. In the first attack (GDD-MTM), we guess a certain number of secret key bits and apply the meet-in-the-middle attack on multiple ciphertexts. The second attack (TMTO-MTM) is derived from applying the time-memory trade-off attack to the meet-in-the-middle attack on a single ciphertext. We may also use rainbow chains in the table construction to get the Rainbow-MTM attack.
The fourth attack (BS-MTM) is defined by combining the time-memory-data trade-off attack proposed by Biryukov and Shamir to the meet-in-the-middle attack on multiple ciphertexts. Lastly, for the final attack (TMD-MTM), we apply the TMTO-Data curve, which demonstrates the general methodology for multiple data trade-offs, to the meet-in-the-middle attack. GDD-MTM requires no pre-processing, but the attack complexity is high while memory requirement is low.
In the last four attacks, pre-processing is required but we can achieve lower (faster) online attack complexity at the expense of more memory in comparison with the GDD-MTM attack. To illustrate how the attacks may be used, we applied them in the cryptanalysis of triple DES. In particular, for the BS-MTM attack, we managed to achieve pre-computation and data complexity which are much lower while maintaining almost the same memory and online attack complexity, as compared to a time-memory-data trade-off attack by Biryukov et al. at SAC 2005. In all, our new methodologies offer viable alternatives and provide more flexibility in achieving time-memory-data trade-offs.
Title: Cryptography: The State of the Art
Yvo Desmedt
University College London
United Kingdom
Abstract: Thirty years ago the knapsack was proposed for public key cryptography. It was broken roughly 5 years afterwards. 25 years later one would expect to have a much better understanding of the cryptographic assumptions we use to make cryptographic systems. Unfortunately we have not made that much progress. Indeed, the best factoring schemes we use in essence go back to the number field sieve proposed 18 years ago! So, cryptography is based on computational complexity primitives that are no longer well studied!
20-30 years ago, the design of cryptosystems was ad hoc. Theoreticians will claim that this has changed and that we have proven secure cryptography. However, a more careful analysis will show that most cryptosystems used are designed ad hoc and have no proven security. Examples are SHA and AES! Fast hybrid encryption schemes may bring us in the near future to have proven secure cryptosystems being used in real life. However,
cryptanalyst have adapted! They currently use side-channel attacks and there are no cryptosystems proven secure against side-channels!
The two above examples demonstrate that although many cryptographers are very upbeat about all progress we have made, a more balanced viewpoint is required. The lecture will survey the progress we have made and not made. We will show that not everything in modern cryptography is rosy. Besides above examples, we will also talk about the discrepancy between the massive number of applications of cryptography studied by academics and the fact most of these are being viewed as completely irrelevant to the real world.
Title: Complexity of Matroid Isomorphism Problem
Jayalal Sarma M. N.
Tsinghua University
P. R. China
Abstract: Testing isomorphism of mathematical structures is a source of computational problems with intriguing complexity. In this talk, we consider the complexity of testing if two given matroids are isomorphic. After giving some general results about the problem we consider various sub-classes of matroids and we present a series of reductions to show that the above problem for graphic matroids and bounded rank matroids are in fact equivalent to the well-studied graph isomorphism problem. We also study the corresponding automorphism problem and give a polynomial time membership test algorithm for the automorphism group for some class of matroids.
Title: Envy-Free Pricing with Revenue Maximization
Ning Chen
Nanyang Technological University
Singapore
Abstract: We will discuss the envy-free pricing problem in a combinatorial structure. The notion of envy-free captures the fairness condition of equilibrium pricing. We will first review the recent studies with a focus on revenue maximization. While the general envy-free pricing problem is hard to approximate, we next consider a special case with metric substitutability, motivated by pricing gas-stations, and derive a polynomial time algorithm by reducing it an instance of weighted independent set on a perfect graph.
Title: Linear Size Optimal q-ary Constant-Weight Codes and Constant-Composition Codes
Son Hoang Dau
Nanyang Technological University
Singapore
Abstract: An optimal constant-composition code or constant-weight code of weight w has linear size if and only if its distance d is at least 2w – 1. When d ≥ 2w, the determination of the size of such a constant-composition or constant-weight code is trivial, but the case of d = 2w – 1 has been solved previously only for ternary constant-composition and constant-weight codes and for some sporadic instances. In this talk, we provide a construction for quasicyclic optimal constant-composition codes and constant-weight codes of weight w and distance 2w – 1 based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes of weight w and distance 2w – 1 are determined for all such codes of sufficiently large lengths, and the sizes of optimal constant-weight codes of weight w and distance 2w – 1 are determined for all such codes of sufficiently large lengths satisfying w | (q – 1)n. This is joint work with Prof. Yeow Meng Chee and Prof. San Ling.
Title: Can Data be Released with Privacy?
Moni Naor
Weizmann Institute of Science
Israel
Abstract: Consider a private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set. The challenge is to simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst.
In this talk, I will survey some recent developments in the area, including a general impossibility result concerning the issue of side information, the notion of Differential Privacy and various algorithms for achieving it.
Based on joint works with Cynthia Dwork, Omer Reingold, Guy Rothblum and Salil Vadhan.
Title: New measures of approximate volume of polytopes using solid angles
Sinai Robins
Nanyang Technological University
Singapore
Abstract: Using lattices in R^d, we compute the local contributions (solid angles) at each lattice point and find an interesting new Fourier series for their global sum over any real polytope, extending a few known results of I.G. Macdonald and A. Barvinok.
The global sums that we encounter form a different kind of discrete measure for the volume for any given real polytope. When p=2, the usual L^p norm retrieves for us we the classical solid angle polynomial of Macdonald, which turns out to be an integral of a classical theta function over a polytope. For this norm we get a new approximate formula for the volume of a real polytope as well. For other p’s we have new variations on the theme of discrete volumes. These variations on a theme also extend the notion of a spherically symmetric solid angle to an L^p-ball solid angle, computed locally at each integer point inside a convex polytope. Most of the geometric notions that we require will be defined in this talk, which is joint work with David DeSario.
Title: Kolmogorov complexity and algorithmic randomness
Guohua Wu
Nanyang Technological University
Singapore
Abstract: The concept of Kolmogorov, or program size, complexity of strings was introduced by Solomono, Kolmogorov and Chaitin in the sixties. For infinite strings (sequences) this concept is strongly related to Martin-Loef's definition of random sequences. In this talk, I will introduce three well-known approaches to algorithmic randomness --- in terms of algorithmic predictability (“a random real should have bits that are hard to predict”), algorithmic compressibility (“a random real should have segments that are hard to describe with short programs”), and measure theory (“a random real should pass all reasonable algorithmic statistical tests”) respectively. I will also introduce recent progress in the study of research in this area, where techniques from computability theory play an important role in the constructions.
Title: A lattice-based minimal partial realization algorithm in the multivariable case
Liping Wang
Tsinghua University
P. R. China
Abstract: We extend a minimal partial realization algorithm for vector sequences to matrix sequences by means of a lattice basis reduction algorithm in function fields. The different ways of transforming a given basis into a reduced one lead to different partial realization algorithms and so our technique provides a unified approach to the minimal partial realization problem.
Title: Representations of semidefinite program algebras and bounds for combinatorial optimization problems
Dmitrii V. Pasechnik
Nanyang Technological University
Singapore
Abstract: Linear optimization over the intersection of the cone of positive semidefinite matrices with an affine subspace, usually called semidefinite programming (SDP), provides an important modeling tool in combinatorial optimization, optimal control, etc. The matrix data of the SDP generates a subalgebra of the full matrix algebra, and its representations can be used to solve the SDP more efficiently -- a far-reaching generalization of the approach pioneered by Delsarte's work on bounds for codes. We discuss recent applications of this technique to various combinatorial problems, such as lower bounds for crossing numbers of complete graphs, upper bounds on codes (e.g. permutation codes), approximation schemes for TSP, etc.
Title: The Gauss Sums in Index 2 Case and Two-Weight Irreducible Cyclic Codes
Yang Jing
Tsinghua University
P. R. China
Abstract: Gauss sums are one of the most important and fundamental objects and tools in number theory and arithmetical geometry. The explicit evaluation of Gauss sums is one of the important and difficult problems which has not only theoretical value in number theory and arithmetical geometry, but also important practical applications in computer science, information theory, combinatorics and experimental designs. This talk is devoted to the study of explicit evaluation for Gauss sums in the case of "index 2" and its applications. Firstly, the complete classifications of the Gauss sums in index 2 case is presented, where the order of the Gauss sum may be not only odd integers but also general even integers. Secondly, the explicit evaluation of the Gauss sums for all the cases above will be given. And then, using the evaluation of the Gauss sums, we prove the conjecture of B. Schmidt and C. White about the non-existence for two-weight irreducible cyclic codes in more general index 2 case with the assumption of the GRH. Some cases of the Gauss sums in index 4 are also concerned.
Title: Applying Time-Memory-Data Trade-Off to Meet-in-the-Middle Attack
Khoong Ming Khoo
DSO National Laboratories
Singapore
Abstract: We present several new attacks on multiple encryption block ciphers based on the meet-in-the-middle attack. In the first attack (GDD-MTM), we guess a certain number of secret key bits and apply the meet-in-the-middle attack on multiple ciphertexts. The second attack (TMTO-MTM) is derived from applying the time-memory trade-off attack to the meet-in-the-middle attack on a single ciphertext. We may also use rainbow chains in the table construction to get the Rainbow-MTM attack. The fourth attack (BS-MTM) is defined by combining the time-memory-data trade-off attack proposed by Biryukov and Shamir to the meet-in-the-middle attack on multiple ciphertexts. Lastly, for the final attack (TMD-MTM), we apply the TMTO-Data curve, which demonstrates the general methodology for multiple data trade-offs, to the meet-in-the-middle attack. GDD-MTM requires no pre-processing, but the attack complexity is high while memory requirement is low.
In the last four attacks, pre-processing is required but we can achieve lower (faster) online attack complexity at the expense of more memory in comparison with the GDD-MTM attack. To illustrate how the attacks may be used, we applied them in the cryptanalysis of triple DES. In particular, for the BS-MTM attack, we managed to achieve pre-computation and data complexity which are much lower while maintaining almost the same memory and online attack complexity, as compared to a time-memory-data trade-off attack by Biryukov et al. at SAC 2005. In all, our new methodologies offer viable alternatives and provide more flexibility in achieving time-memory-data trade-offs.
