Welcome to the Theory group's seminar series. You can subscribe to our mailing list cs-theory announcing seminars and events, and you can read more about our research activities. You can subscribe to our Google calendar. If you are interested in giving a research presentation, send an email to Peter Hoyer.
The CS Seminar Series will resume in the Fall 2012 semester. During the Winter 2012 semester, the Series ran on Fridays at 3:00pm-4:00pm in ICT 616.
Numerical computations using floating point arithmetic are affected by rounding errors leading to erroneous results and unstable computations. This is especially the case when the computations involve geometric objects.
Geometric computations are frequently composed of simple sub-computations called geometric primitives. An example of a geometric primitive is thetest in two dimensions to check if a point is on one side, on or on the other side of an oriented line. If this test can be executed efficiently and without error then the convex hull of a two dimensional point set can also be computed exactly. The practical uses of such computation can be found for example in GIS systems. Since they involve extensive computations of geometric objects inconsistencies that occur due to instabilities in the geometric primitives can lead to failures of the systems that are very difficult to diagnose.
In this talk we will explore interval arithmetic and a version of an exact computation as they can be implemented for geometric primitives.
In the problem of secure multi-party computation, there are n parties, where i-th party holds private input x_i, 1<=i<=n. The goal is for a subset (or all) of the parties to learn f(x_1,...,x_n) but nothing else. In some applications the function itself is proprietary and belongs to one of the parties who wants to keep it private. This variant of the problem is often referred to as ``private function evaluation''. There are two approaches to designing such protocols. First is to design general-purpose protocols which can be used for any function. Second is to take advantage of function structure to design more efficient customized protocol. We revisit the problem of designing general-purpose private function evaluation (PFE). In this talk I will talk about the two-party version of our protocol. An overview of our multi-party version will be given. Both solutions deviate from the traditional approach based on universal circuits and yield significantly more efficient constructions.
In the Diffie-Hellman protocol, two parties establish a common secret cryptographic key in one round of communication. The traditional Diffie-Hellman protocol can be extended to three parties where any pair of the three would have to establish a common key in one round, and pass the common keys to the third party in the second round. Now the question is: Is it possible to establish a three parties cryptographic key in one round by employing some additional arithmetic structure available for algebraic curves? This question has been answered positively by employing bilinear mappings, known as pairings. In this talk we present pairings on elliptic curves and discuss how it can be efficiently used to establish a secret among three parties.
In this talk, we present applications of computer algebra to decoding algorithms of certain codes. The computer algebra algorithm we will study essentially rely on manipulations of matrices. They allow us to find generating elements with good properties for some sets. We will show how to use these algorithms for the purpose of decoding certain codes. A general framework was proposed by Guruswami that could be applied to some standard codes such as Reed-Solomon codes, or Algebraic-Geometric codes. We will follow this approach to achieve polynomial time decoding for a class of codes described by Lenstra and Guruswami for which decoding was still an open problem.
Consider a system with multiple processors which can only communicate with each other by reading and writing shared variables. The processors are asynchronous: they run with arbitrary and constantly changing speeds. In such systems, even seemingly simple tasks cannot be solved with deterministic algorithms. For example, there is no deterministic Leader Election protocol, in which exactly one of the participating processes returns "win" and all other ones return "lose". This is unfortunate, as Leader Election and its linearizable counter part, Test-and-Set, are fundamental synchronization primitives that have many algorithmic applications. Fortunately, randomization can be a way out of this dilemma. In this talk I will discuss recent progress in the design of time- and space- efficient randomized Leader Election algorithms. In particular, I will present a simple algorithm that solves the problem with an expected step complexity of O(log* n), improving on a previous O(loglog n) bound.
Dice, clocks, or background in shared memory computing are not required. This is joint work with George Giakkoupis.
We consider the problem of reliable and secure message transmission in two settings: noisy channel with an eavesdropping adversary, and a network setting where some of the network nodes are controlled by the adversary. We show how reliability and security can be formalized in these two settings and outline a general construction for a1-round secure message transmission protocol for the network setting that provides provable reliability and perfect privacy. One of the main building blocks of this construction is list decodable codes that are used for providing reliability over noisy channels.
The talk emphasizes the underlying concepts and provides all the required definitions.
This talk explores models of computation in which every function has a differential. A concrete model in which it was possible to take the derivative of computations was first explored by Ehrhard in 2002. Since then, research has focused on a system, called the differential lambda calculus (DLC), and its semantics. Of particular interest has been its connection to a semantics for resource control and nondeterminism.
In 2010, Manzonetto began to study models of the DLC which are also full models of computability. However, the only known models were degenerate in the sense that the addition was idempotent and it seemed plausible that all such models might have to be degenerate. If this were true, it would lead to a disappointing theory.
In this talk, we will consider adding derivatives to more basic models of computability given by Turing categories and Partial Combinatory Algebras. We will make a key observation about the models of these systems that shows the model theory may be interesting after all. We will then sketch out the beginnings of constructing a non-degenerate model.
In this paper we are offering several optimization opportunities for implementing one of the most common operations in several public key cryptographic systems: the inversion over binary Galois fields. The optimizations are based on the combination between new inversion formulae and efficient use of the repeated squaring technique. Over some of the NIST recommended fields, our technique leads to the most economical---in terms of multiplications---inversion procedures. The main algorithm proposed is provably better than the Itoh-Tsujii algorithm for inversion. The inversion formulae proposed in this paper utilize better the advantages of the repeated squaring technique and offer additional computational savings in terms of the number of clock cycles used. The algorithms proposed are straightforwardly usable in both software and hardware implementations.
Mutual exclusion, also known as locking, is a fundamental and well studied problem in distributed computing. In this problem, N processes synchronize among themselves to access a Critical Section such that no two processes access the Critical Section at the same time. Recent research on mutual exclusion locks for the asynchronous shared-memory model has focused on local spin algorithms that use the remote memory references (RMRs) metric.
Local spin mutual exclusion locks do not meet a critical demand of many systems. Specifically, the locks employed in database systems and in real time systems must support a "timeout" capability, that is, it must be possible for a process that waits "too long" to abort its attempt to acquire the lock. Locks that allow a process to abort its attempt to acquire the lock are called abortable mutual exclusion locks. Jayanti presented an efficient deterministic abortable mutual exclusion lock with worst-case O(log N) RMR complexity. The problem of designing a randomized abortable mutual exclusion algorithm with sublogarithmic expected RMRs has remained open. This talk will present a solution to this problem, where we will present a randomized abortable mutual exclusion lock with O(log N/log log N) expected RMRs.
The problem of spreading a piece of information, or rumor, from a single node to all the other nodes in a network is a fundamental one, with a variety of applications. A classic randomized algorithm for rumor spreading is that every node establishes a connection with a random neighbor in each round, and the two nodes exchange the rumors they have. The number of rounds that this algorithm needs to disseminate a rumor to all nodes has been studied extensively, for several network topologies. In this talk I will present some recent results that relate the number of rounds needed for an arbitrary network, with some standard measures of how ``well-connected'' this network is, namely, conductance and vertex expansion.
A ball thrown at a wall returns to its origin with velocity equal in magnitude but opposite in direction (in an ideal setup). In other words the direction or sign associated with the velocity in the beginning and at the end is anti-correlated. This is a direct consequence of the laws of physics which serve as guiding principles for deriving physical consequences such as the correlations above. The example may seem mundane given that such correlations are part of our every day experience. The intriguing nature of correlations produced by quantum physcics (known as nonlocality) however defies such an intuitive explanation.
The talk will give an overview of recent work on obtaining strong nonlocal correlations from weaker correlation sources. The talk will appeal to a general audience by presenting emerging applications of the work in cryptography and quantum biology.
Multiprocessor and multicore machines incorporate sophisticated hardware components such as write-buffers, multiple busses, layers of caches, and elaborate interconnect topologies to more effectively exploit the potential efficiency of many computational units. The result can be blisteringly fast computation---of something! The features that enhance speed are precisely the ones that make it extremely challenging to assert correctness. The output of a program can be very different from what the algorithm designer expected. Because such machines have only "weak memory consistency" there is no guarantee, for example, of Lamport's Sequential Consistency or database's Serializability.
I will describe a modelling framework that helps us specify what guarantees such a machine does provide. Then I will illustrate its use by showing some possibility and impossibility results for familiar synchronization problems on a multiprocessor with X86-like architecture.
This is an introductory talk. No familiarity with even the terms above is needed.
In Facebook-style Social Network Systems (FSNSs), which are a generalization of the access control model of Facebook, an access control policy specifies a graph-theoretic relationship between the resource owner and resource accessor that must hold in the social graph in order for access to be granted. Pseudonymous identities may collude to alter the topology of the social graph and gain access that would otherwise be forbidden. We formalize Denning's Principle of Privilege Attenuation (POPA) as a run-time property, and demonstrate that it is a necessary and sufficient condition for preventing the above form of Sybil attacks. A static policy analysis is then devised for verifying that an FSNS is POPA compliant (and thus Sybil free). The static analysis is proven to be both sound and complete.
In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N^2, which is quadratically more than the legitimate effort. We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to N^{3/2} to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable.
We give two novel key establishment schemes in the spirit of Merkle's. The first one can be broken by a quantum adversary that makes an effort proportional to N^{5/3} to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis' quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.
NO prior knowledge of quantum computing will be assumed.
In the 1930s, the British mathematician Alan Turing developed a mathematical model of computation, now called the Turing Machine, which has encouraged many to give him credit for the invention of the computer as we know it today. Turing is perhaps best known for his contributions in breaking the Enigma cipher of the German military during World War II. He was also a pioneer in artificial intelligence and neural networks, and today the Turing Award serves as the computer scientist's version of the Nobel Prize.
Alan Turing was arrested for homosexuality in 1952 and forced to undergo hormone treatments; it is believed this led to his suicide by cyanide poisoning at the age of 42 in 1954. In this talk we will look at Turing's work, and discuss some of the controversies surrounding his life.
First, I will briefly introduce secure two-party computation (2PC), an interesting area of cryptography. Then, I will focus on a specific instance of secure 2PC, i.e. oblivious Automata evaluation. Oblivious Automata evaluation allows two parties -a client who holds an input string X and a server who holds an Automata G- to learn the result of evaluating G on X but nothing else. I will describe a simple and efficient, secure two-party construction for this problem. If there is time, I will also outline some applications of our construction to secure pattern matching and intrusion detection.
This survey talk provides an overview of elliptic and hyperelliptic curves in the context of their use in discrete logarithm based cryptography. After introducing the cryptographic key agreement problem and one of its major solutions, the celebrated Diffie-Hellman key establishment protocol, we give an overview of elliptic curves and their group law. We then move on to hyperelliptic curves and their associated group (the Jacobian), describing a representation of group elements as well as the group operation. If time permits, we will briefly summarize methods for extracting discrete logarithms on both elliptic and hyperelliptic curves, and touch on alternative curve models. The talk is targeted at an audience with no or minimal exposure to cryptography and no prior knowledge of algebraic curves.
In asynchronous shared memory systems, processes communicate by reading and by writing to shared registers. Such operations are called events, and it is in general impossible for processes to determine the exact order of all events in an execution. A time stamp object allows processes to obtain some information about the ordering of events. Time stamps have many applications, including in cache coherency protocols and to achieve fairness (e.g., first-come first-served) in scheduling algorithms. I will present tight bounds for the space complexity of one-shot time stamp objects.
Based on joint work with Lisa Higham, Eduardo Pacheco and Philipp Woelfel. Presented at PODC 2011.
Randomness is essential in many areas of computer science specifically in cryptography (for example to generate secret keys). We always assume that we have access to perfect randomness (unbiased independently generated random bits) but this is not a realistic assumption. Our sources of randomness (such as radioactive decay, thermal noise and weather) does not output perfect randomness. We want to understand if we can base our primitives on more practical assumption of having only imperfect random sources. In other words, for a particular primitive, is perfect randomness inherent? or we can modify it to tolerate imperfect randomness. In this talk, a classification of random sources based on their feasibility for a few cryptographic primitives is given.
Sometimes rather abstract problems -- like the complexity of determining the equality of maps in a linearly distributive category -- can be expressed as easy to explain puzzles. The internet then allows one to crowdsource such problems ... reducing one's work load!
The talk will explain the puzzle (in parts) and hopefully get you playing. The talk will try to avoid explaining the scientific significance of the puzzle. A solution to an interesting subproblem, which involves rope men in Tibet, will be explored.