^March April – 2011 ^May

Bellare and Rogaway [ACM CCS ’93] introduced the famous random oracle model as a “paradigm for designing efficient protocols”. This paradigm has led to several highly efficient and widely used in practice constructions, such as the RSA Ful l Domain Hash signature scheme (RSA-FDH). Unfortunately, little is known about the security of the resulting schemes in the standard model, when the random oracle is replaced by a concrete function. In particular, it is unknown whether we can reduce their (standard model) security to any “natural” assumption. Prior work has shown several “uninstantiability” results for various abstractions of RSA- based schemes, where the RSA function was replaced by a random permutation. These ab- stractions, however, do not allow either the reduction or the hash function instantiation to use any algebraic properties of RSA function, such as the multiplicative group structure of Z*n . In this work we develop new techniques which rule out such algebraic instantiations, focusing specifically on the case of RSA-FDH. We show that it is impossible to reduce the security of RSA-FDH to any natural assumption, provided that the construction and the reduction treat the multiplicative RSA group Z*n in a black-box way. To the best of our knowledge, this restriction is satisfied by all positive results for RSA-based signatures, including standard model constructions of Gennaro et al. [EUROCRYPT ’99], Cramer and Shoup [ACM TISS ’00] and Hohenberger and Waters [CRYPTO ’09]. As our main technical (and conceptual) contribution, we show how to adapt the powerful “short description” paradigm of Gennaro and Trevisan [FOCS ’00] to the “generic group” setting. This paradigm is typically used to rule out one-way permutations based reductions, showing that their security proofs would imply a (provably impossible) way to “compress” a random permutation. In our setting, the reduction has access to a random group G isomorphic to Z*n , and can use the algebraic properties of G. Still, we show that such a reduction must “know” the factorization of n (and, hence, does not “benefit” from the signature forger), since otherwise it can be used to “compress” our group G. We demonstrate the optimality of our negative result, at least in some sense, by showing that the RSA-FDH signatures can be proven secure in the standard model, under the standard RSA assumption, provided the number of signing queries is a-priori bounded.

Significant progress has been made in the past two decades in the construction of software systems that relate directly to mathematics: computer algebra systems, theorem provers,proof assistants, mathematical knowledge bases and so forth. A variety of powerful algorithms have been implemented in general-purpose symbolic algebra systems, special purpose systems, and state of the art numerical libraries. I will discuss how computational tools and computationalthinking influence science and engineering and demonstrate several accessible examples carried out in the spiritof experimental mathematics.

A k-spanner of a given graph is a subgraph that preserves all distances within factor k. This notion is useful in several contexts, from distributed computing to property testing. From an algorithmic viewpoint, the goal is to find a k-spanner with as few edges as possible. In this talk I will examine two variants of graph spanners: directed spanners and fault-tolerant spanners. In the directed setting we design an O(n^{2/3})-approximation algorithm for the directed k-spanner problem that works for all k. This is the first approximation independent of k, as well as being the first to handle arbitrary edge lengths. In the fault-tolerant setting we give a new construction of fault-tolerant spanners of undirected graphs that is both simpler than previous work and improves the dependence on the number of faults from exponential to polynomial. For the special case of k=2, we also provide an O(log n)-approximation algorithm for the smallest fault-tolerant 2-spanner. This approximation ratio is, notably, independent of the number of faults. Our main tool in both the directed and fault-tolerant settings is a new flow-based linear programming relaxation.

Joint work with Robert Krauthgamer.