Add to Calendar
2019-12-05 13:30:00
2019-12-05 14:30:00
America/New_York
Linear-sized circuits for compaction and selection
Abstract:In this talk, I will describe how to construct an O(n w (polylog* n - polylog* w))-sized circuit for solving1) selection, i.e., finding the median of n elements each of bit-length w;2) compaction, i.e., sorting an array of n elements each with a 1-bit key and a w-bit payload.For w >= log^{(c)} n where log^{(c)} denotes taking iterative logarithm any constant number of times, the circuit size is strictly linear and optimal, i.e., O(nw).We also show a non-trivial, non-comparison-based generalization of the AKS sorting network: sorting n elements each of w bits requires a circuit of O(n w log K) size (ignoring polylog* factors) assuming each element's key comes from [K]. For keys much shorter than log n-bits, our circuit size is asymptotically better than AKS. Results of such nature are long known to be impossible (see [Knuth'73]) in the comparator-based model which is adopted by known sorting networks; and we are the first to show non-trivial, non-comparison-based results in the circuit model of computation.Finally, I will briefly comment on the relations of this result to constructing optimal ORAM.
Seminar Room G449 (Patil/Kiva)
December 05
October 17
Practical proof systems: implementations, applications, and next steps
Dept. of Computer Science, Stanford University
Add to Calendar
2019-10-17 15:00:00
2019-10-17 16:00:00
America/New_York
Practical proof systems: implementations, applications, and next steps
This talk sketches the built proof systems landscape, and discussescurrent and potential future applications of these systems in practice.The focus is both on the relative strengths and weaknesses of existingapproaches and on the challenges common to all systems. We closewith a brief "wish list" of open problems that have the potential toreshape this exciting research area.
Seminar Room G882 (Hewlett Room)
May 22
Who Watches the Watchers in Web PKI?
Kat Joyce
Google
Add to Calendar
2019-05-22 14:00:00
2019-05-22 15:00:00
America/New_York
Who Watches the Watchers in Web PKI?
ABSTRACTSince the dawn of time (well, Web PKI), certificates have been used to ensure that internet users are actually talking to the websites they think they are. Since the dawn of time (a.k.a. the mid-90s) Certificate Authorities have been trusted to Do The Right ThingTM when issuing these certificates, and watch out for baddies trying to get their hands on certificates for domains they don’t own. But what if a CA makes issuance mistakes? What if a CA is hacked? What if a CA is run by the baddies themselves?! Who watches the watchers?Enter: Certificate Transparency.Certificate Transparency is the latest internet security superhero. Power: detecting certificate misissuance and certificate authority misbehaviour (oooh yeah). But seriously, capes and wearing-undies-over-skin-tight-lycra aside, what exactly is Certificate Transparency? How does it work? Why should you care? Is it even helping? Come along to this talk and find out!SPEAKER BIOKat is a Software Engineer on the Trust Fabric team at Google, where she is currently focusing on building infrastructure to ensure actors within the Certificate Transparency ecosystem are operating in line with the Chrome Certificate Transparency Log Policy.Prior to Google, Kat was a Research Engineer in the Networks and Systems research group at UCL. Kat has an MSc in Information Security from UCL, and a BSc (Hons) in Mathematics from Dalhousie University. In her spare time Kat loves to ski, swim, read, and play various musical instruments, with varying levels of success!
32-G882
February 21
Microarchitectural Attacks and Beyond
Graz University of Technology
Add to Calendar
2019-02-21 13:00:00
2019-02-21 14:00:00
America/New_York
Microarchitectural Attacks and Beyond
ABSTRACTMicroarchitectural Attacks recently got a lot of attention with thepublication of Meltdown and Spectre. In general, cache attacks havegained in popularity in the academic community over the past twodecades. In this talk we will first discuss what architecture andmicroarchitecture means. We will then discuss cache attacks as a primeexample of microarchitectural attacks, see how the work and how we canleak data from other processes. Then we will turn to another example onthe software level where abstraction similarly enables a new form ofcache attacks. The software cache that we target is a common conceptimplemented across various operating systems. By mounting a series ofattacks we can see that this hardware-agnostic kind of cache attack cancompete with state-of-the-art hardware cache attacks. Finally, wediscuss mitigations for Linux and Windows.SPEAKER BIODaniel Gruss (@lavados) is an Assistant Professor at Graz Universityof Technology. He finished his PhD with distinction in less than 3years. He has been involved in teaching operating system undergraduatecourses since 2010. Daniel's research focuses on software-basedside-channel attacks that exploit timing differences in hardware andoperating systems. He implemented the first remote fault attackrunning in a website, known as Rowhammer.js. He frequently speaks attop international venues, such as Black Hat, Usenix Security, IEEES&P, ACM CCS, Chaos Communication Congress, and others. His researchteam was one of the teams that found the Meltdown and Spectre bugspublished in early 2018.
32-G882