September 23, Graduate Center: Alexei Miasnikov (McGill University), Modern Cryptanalysis: generic complexity and asymptotic algebra.
Abstract: In this talk I am going to discuss two recent developments in modern cryptanalysis: generic complexity and asymptotic dominance. The first one concerns behavior of algorithms on most typical, or "generic", inputs, while the second one deals with the asymptotically most dominant properties of algebraic objects. My focus will be on some new intriguing mathematical problems and ideas that are coming to algebra, and especially to group theory, from modern algebraic cryptography.

September 30, Graduate Center: Vladimir Shpilrain (City College), Using decision problems in public key cryptography.
Abstract: In this talk, we suggest to use decision problems from combinatorial group theory as the core of a public key cryptosystem. Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. We show that decision problems may be useful when one addresses the ultimate challenge of public key cryptography: to design a cryptosystem that would be secure against "brute force" attacks by an adversary with unlimited computational speed. By using a popular decision problem, the word problem in groups, we design a cryptosystem with the following features: (1) Bob transmits to Alice an encrypted binary sequence which Alice decrypts correctly with probability "very close" to 1; (2) the adversary, Eve, who is assumed to have unlimited computational speed (although limited memory), can positively identify those places in Bob's binary sequence where he intended to transmit a 1. However, there is no way for Eve (at least, in theory) to be sure that in the remaining places Bob intended to transmit a 0.
This is joint work with Gabriel Zapata.

October 21, Graduate Center: Benjamin Fine (Fairfield University), Algebraic Cryptosystems Using Linear Groups

October 28, Graduate Center: Nicholas Touikan (McGill University), A fast algorithm for Stallings' folding process
Abstract: In this talk I will present an algorithm that performs Stalling's folding process. In particular it takes as input a tuple of reduced words J_1,...,J_m from a free group and outputs a folded graph for the subgroup H generated by J_1,...,J_m. This graph can be seen as the "core" of the covering space of a bouquet of circles corresponding to the subgroup H, the automaton that accepts H etc. The main result is that it runs in time O(n log^*(n)) where log^* is a slowly growing function. After discussing some direct applications, I plan on showing the problems arising from a "naive" approach which will motivate the use of abstract data structures which, when used properly, enable us to construct an algorithm that runs in the advertised time. I will then discuss trivial modifications that will enable us to apply this algorithm to more general folding problems.

November 4, Stevens Institute: Jean-Camille Birget (Rutgers University), Graphical passwords
Abstract: Passwords are the most commonly used form of user authentication. They are also one of the weakest links of computer security systems. Graphical passwords are based on visual information and try to exploit the innate human ability to process images. An example of a system that we developed uses an image on the screen and lets the user choose a few click points; these click points are the ``password", and the user has to click closely to these points again in order to log in. There are some interesting implementation problems for this graphical password system. I'll also talk about usability, human factors, and the possibility of dictionary attacks. Another topic is the design of password systems that are resistant to ``shoulder surfing" (i.e., where the login is observed without the password being revealed).

December 9, Stevens Institute: Alexandra Boldyreva (Georgia Institute of Technology), Public-Key Encryption in a Multi-User Setting: Privacy, Anonymity and Efficiency.
Abstract: This talk is about using the provable security techniques and, in particular, having appropriate security models for the analysis and design of secure and efficient encryption schemes for various goals and settings. Encryption is a tool for achieving information privacy. It is usually analyzed in the single-user setting, where only a single recipient of encrypted data is considered. In the real word, however, there are many users sending each other encrypted data. We investigate the crucial question of whether protocols’ various security properties hold in the real “multi-user” setting. First, we address data-privacy of public-key encryption schemes in the multi-user setting, namely in the presence of attacks involving the encryption of related messages under different public keys, as exemplified by Hastad’s classical attacks on RSA. We provide a model for measuring the security in this setting and prove that security in the single-user setting implies security in the multi-user setting, as long as the former is interpreted in the strong sense. This reassuring result pinpoints many schemes guaranteed to be secure in the multi-user setting. We then highlight the importance in practice of considering and achieving better concrete security, and present improved concrete security results for two popular schemes. While hiding data was considered the only goal of encryption, the emerging concerns about the users’ privacy rights in the digital world highlighted the importance of another property, namely, hiding identities of intended recipients of encrypted data. Next, we study this property of encryption in the multi-user setting, which we call “anonymity” or “key-privacy”. Finally, we propose and explore an interesting technique that offers important performance and bandwidth benefits in scenarios where a sender needs to encrypt messages for several receivers. We also provide a general test that helps to determine when the technique can be securely applied.