## CSE Seminar

#### 2021 talks

**Upgrading Security of Encryption Schemes****Speaker:**Venkata Koppula

**Date:**2021-01-15 **Time:**12:00:00 (IST) **Venue:**Microsoft teams **Abstract:**What does it mean for an encryption scheme to be secure? Perhaps the most basic definition, given in the seminal work of Goldwasser-Micali, states that an encryption scheme is secure if no adversary, given a ciphertext, can learn anything about the underlying message. But this only offers security against "passive attacks". For example, suppose Alice sends an encryption of message 'm' to Bob. An active adversary can intercept this ciphertext, and tamper the ciphertext in such a way that it is now an encryption of a different message 'm'. The adversary still doesn't learn anything about the underlying message, but this is a valid attack (and such attacks have been shown in the real-world). Therefore, security against active adversaries should be the "gold standard" definition of secure encryption.

It is generally easier to construct encryption schemes that are secure against passive attacks. Can we upgrade any passively secure scheme to one that is actively secure? This question is still open. In this talk, I will present two approaches[1,2] towards achieving adaptive security, and on the way, discuss how they relate to the aforementioned open question.

[1] Chosen Ciphertext Security from Injective Trapdoor Functions. [Hohenberger, K, Waters]

[2] Realizing Chosen Ciphertext Security Generically in Attribute-Based Encryption and Predicate Encryption. [K, Waters]

No crypto background will be required for this talk.

Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1610201184560?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d

#### 2020 talks

**Two easy-looking yet poorly understood problems****Speaker:**Ashish Chiplunkar

**Date:**2020-12-31 **Time:**12:00:00 (IST) **Abstract:**I will be talking about two easy-looking yet poorly understood problems, namely, the weighted k-server problem and the Bayesian online selection problem. Both problems are online in nature: an algorithm gets its input as a sequence of requests, and must respond to a request before it gets the next one. The challenge is to compete with the offline optimum, that is, the optimum solution considering the entire input, and the loss in optimality is captured by a quantity called competitive ratio.

The weighted k-server problem is a generalization of the caching problem with the following modification: the cost of page replacement varies with the cache location where the page replacement takes place. While the optimal competitive ratio of caching has been already known for decades, the competitive ratio of weighted k-server isn't. In particular, after the seminal paper by Fiat and Ricklin in 1993, it was only in 2017 that the deterministic competitive ratio was established by Bansal et al., while finding the randomized competitive ratio is still an open problem.

In the Bayesian online selection problem, an algorithm gets as input the realizations of some independent random variables and must pick one of them irrevocably, with the goal of maximizing the expectation of the value picked. When the arrival order of the values of the random variables is adversarial, it is known since 1977 that the optimal competitive ratio is 1/2. However, the natural cases of random arrival order and algorithmically chosen arrival order remain open.

For each problem, I plan to discuss the literature, give an overview of techniques, point out open questions, and highlight the recent contributions of our students towards answering those questions. (This talk should be especially relevant to students who wish to work with me.)

**Relaxed Memory Concurrency: Overview and Challenges****Speaker:**Soham Chakraborty

**Date:**2020-12-16 **Time:**12:00:00 (IST) **Abstract:**In most analysis/verification techniques, the behavior of concurrent programs is understood in terms of thread interleavings, a model formally known as sequential consistency (SC). For performance reasons, modern hardware implementations allow some executions which cannot be explained by thread interleavings. Similarly, standard compiler optimizations can affect the outcome of a concurrent program in ways that cannot be understood by SC. Therefore, to program concurrent systems correctly and effectively, it is important to come up with a programming language semantics that accounts for all the non-SC behaviors that hardware and compilers produce. Defining such a "relaxed" memory model is challenging due to conflicting requirements: the model should not only enable efficient compilation, but also provide programmability guarantees.

**Discovering and Mitigating Security Vulnerabilities in Bluetooth Low Energy****Speaker:**Vireshwar Kumar

**Date:**2020-12-02 **Time:**12:00:00 (IST) **Abstract:**The Bluetooth Low Energy (BLE) protocol ubiquitously enables energy-efficient wireless communication among resource-constrained devices. To ease its adoption, the BLE requires limited or no user interaction to establish a connection between two devices. Unfortunately, this simplicity is the root cause of several security issues. In this talk, we analyze the security of the BLE focusing on the scenario in which two previously paired device reconnect. In the first half of the talk, we demonstrate the systematic approach that allows us to uncover critical security vulnerabilities in the BLE. We exploit these vulnerabilities to develop the BLE Spoofing Attack (BLESA) that enables an attacker to impersonate a BLE device and feed spoofed data to another previously paired device. BLESA can be easily carried out against the BLE stack implementations used by Linux, Android, and iOS. Defending the BLE against spoofing attacks, such as BLESA, is extremely difficult as security patches to mitigate them may not be adopted across vendors promptly; not to mention the millions of legacy BLE devices with limited I/O capabilities that do not support firmware updates. We address these challenges in the second half of the talk by presenting BlueShield, a legacy-friendly, non-intrusive monitoring system as the first line of defense against spoofing attacks. BlueShield is motivated by the observation that all spoofing attacks result in anomalies in certain cyber-physical features of the advertising packets containing the BLE device’s identity. BlueShield leverages a unique combination of these features to detect spoofed packets generated by an attacker. We conclude the talk with a discussion on the potential directions for discovering and mitigating security vulnerabilities in the BLE.

**Can we preserve large distances?****Speaker:**Keerti Choudhary

**Date:**2020-11-18 **Time:**12:00:00 (IST) **Abstract:**In the area of graph sparsification, the distance spanners are sparse subgraphs preserving all-pairs distances up to a small stretch. These structures have been well studied for undirected graphs over the past three decades. However, for directed graphs, sparse (subquadratic-sized) distance approximating spanners are not possible in general. We thus focus on the notion of extremal distance spanners in directed graphs. For a directed graph G = (V, E), a subgraph H = (V, E') is said to be a "t"-diameter spanner if the diameter of H is at most "t" times the diameter of G. Similarly, a "t"-eccentricity spanner, is a subgraph that approximately preserves all vertex eccentricities of the original graph, up to a stretch factor t. In this talk, we will look at the existence of (and algorithms to compute) various t-diameter and t-eccentricity spanners with a sparse set of edges for stretch t at most 2.