Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

UPCOMING SEMINARS

Series: CSA Distinguished Lecture
Title: Securing a World of Physically Capable Computers

  • Speaker: Bruce Schneier
  • Date and Time: Thursday, December 12, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computer security is no longer about data; it's about life and property. This change makes an enormous difference, and will shake up our industry in many ways. First, data authentication and integrity will become more important than confidentiality. And second, our largely regulation-free Internet will become a thing of the past. Soon we will no longer have a choice between government regulation and no government regulation. Our choice is between smart government regulation and stupid government regulation. Given this future, it's vital that we look back at what we've learned from past attempts to secure these systems, and forward at what technologies, laws, regulations, economic incentives, and social norms we need to secure them in the future.

Speaker Bio:
Bruce Schneier is an internationally renowned security technologist, called a security guru by the Economist. He is the New York Times best-selling author of 14 books -- including Click Here to Kill Everybody -- as well as hundreds of articles, essays, and academic papers. His influential newsletter Crypto-Gram and blog Schneier on Security are read by over 250,000 people. Schneier is a fellow at the Berkman Klein Center for Internet and Society at Harvard University; a Lecturer in Public Policy at the Harvard Kennedy School; a board member of the Electronic Frontier Foundation, AccessNow, and the Tor Project; and an advisory board member of EPIC and VerifiedVoting.org.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Signcryption in a Quantum World

  • Speaker: Mr. Shravan Kumar Parshuram Puria
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Friday, November 29, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
With recent advancements and research on quantum computers, it is conjectured that in the foreseeable future, sufficiently large quantum computers will be built to break essentially all public key cryptosystems currently in use. As a response, quantum-safe cryptography has recently garnered significant attention. The aim of quantum-safe cryptography is to design cryptosystems that are secure against both classical and quantum computers. This involves identifying computational problems that are believed to be secure against quantum adversaries and building cryptosystems based on such problems. A related problem of interest is arguing security of quantum-safe cryptosystems within the paradigm of provable security. Quantum security models for basic primitives like encryption and signature are gradually evolving and the security of different cryptosystems are being investigated in these models.

Signcryption is a public key primitive that ensures both confidentiality and authenticity of data. Signcryption security can be modeled in different ways depending on whether the adversary can corrupt an insider, i.e., the sender or receiver, or not. The aim of this work is a comprehensive treatment of signcryption against quantum adversaries that are allowed to make oracle queries on quantum superposition of classical input values. We formulate suitable quantum security definitions for confidentiality and authenticity of signcryption both in insider and outsider models. We investigate the quantum security of generic constructions of signcryption schemes based on three paradigms, viz., encrypt-then-sign (EtS), sign-then-encrypt (StE) and commit-then-encrypt-and-sign (CtE&S). We show that the quantum analogues of the classical results hold in the insider model with an exception in the StE paradigm. However, in outsider model we need to consider an intermediate setting in which the adversary is given quantum access to unsigncryption oracle but classical access to signcryption oracle. In two-user outsider model, as in the classical setting, we show that post-quantum CPA security of the base encryption scheme is amplified in the EtS paradigm if the base signature scheme satisfies a stronger notion of security. We prove an analogous result in the StE paradigm. Interestingly, in the multi-user setting, our results strengthen the known classical results.

Our results for the EtS and StE paradigms in the two-user outsider model also extend to the setting of authenticated encryption. We briefly discuss the difficulties in analyzing the full quantum security of signcryption in outsider model. Finally, we briefly discuss about some existing quantum secure encryption and signature proposals which can be used to instantiate signcryption schemes based on the above paradigms.

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Honest Majority and Beyond: Efficient Secure Computation over Small Population

  • Speaker: Ms. Swati Singla
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Thursday, November 21, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Secure Multi-Party Computation for small population has witnessed notable practically-efficient works in the setting of both honest majority and dishonest majority. While honest majority provides the promise of stronger security goals of fairness (either all parties get the output or none of them do) and guaranteed output delivery (honest parties always get the output irrespective of adversary’s behaviour), the best that dishonest majority can offer is unanimous abort (either all honest parties get the output or none of them do). In this work, we consider the computation among 4 parties in two different threat models. To avoid clutter and enable ease of understanding, we segregate the work into two parts (one for each threat model). Part I considers the standard honest majority (i.e. 1 corruption) where we provide constant round (low-latency) protocols in a minimal model of pairwise private channels. Improving over the state-of-the-art work of Byali et al. (ACM CCS ’18), we present two instantiations that efficiently achieve: (a) fairness in 3 rounds using 2 garbled circuits (GC) (b) guaranteed output delivery (GOD) in 3 rounds using 4 GCs. Further, improving the efficiency of 2-round 4PC feasibility result of Ishai et al. (CRYPTO ’15) that achieves GOD at the expense of 12 GCs, we achieve GOD in 2 rounds with 8 GCs, thus saving 4 GCs over that of Ishai et al. Under a mild one-time setup, the GC count can further be reduced to 6 which is half of what the prior work attains.

This widely-followed demarcation of the world of MPC into the classes of honest and dishonest majority suffers from a worrisome shortcoming: one class of protocols does not seem to withstand the threat model of the other. Specifically, an honest-majority protocol promising fairness or GOD violates the primary notion of privacy as soon as half (or more) parties are corrupted, while a dishonest-majority protocol does not promise fairness or GOD even against a single corruption, let alone a minority. The promise of the unconventional yet much sought-after brand of MPC, termed as Best-of-Both-Worlds (BoBW), is to offer the best possible security in the same protocol depending on the actual corruption scenario. With this motivation in perspective, part II presents two practically-efficient 4PC protocols in the BoBW model, that achieve: (1) guaranteed output delivery against 1 corruption and unanimous abort against 2 corruptions. (2) fairness against 1 corruption and unanimous abort against arbitrary corruptions. The thresholds are optimal considering the feasibility given in the work of Ishai et al. (CRYPTO ’06) that marks the inauguration of the BoBW setting. We provide elaborate empirical results through implementation that support the theoretical claims made in all our protocols. We emphasize that this work is the first of its kind in providing practically-efficient constructions with implementation in the BoBW model. Also, the quality of constant-rounds makes all protocols in this work suitable for high-latency networks such as the Internet.

Video Archive Go Top

 

Series: CSA Golden Jubilee Frontier Lecture Series
Title: State of Permissionless and Permissioned Blockchains: Myths and Reality

  • Speaker: Dr. C. Mohan
                   IBM Fellow
                   IBM Almaden Research Center, USA
                   and
                   Distinguished Visiting Professor
                   Tsinghua University, China
  • Date and Time: Thursday, November 21, 2019, 2:30 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
It has been a decade since the concept of blockchain was invented as the underlying core data structure of the permissionless or public Bitcoin cryptocurrency network. Since then, several cryptocurrencies, and associated concepts like tokens and ICOs have emerged. After much speculation and hype, significant number of them have become problematic or worthless, even though some countries have embraced them! The permissionless blockchain system Ethereum emerged by generalizing the use of blockchains to manage any kind of asset, be it physical or purely digital, with the introduction of the concept of Smart Contracts. Over the years, numerous myths have developed with respect to the purported utility and the need for permissionless blockchains. The adoption and further adaptation of blockchains and smart contracts for use in the permissioned or private environments is what I consider to be useful and of practical consequence. Hence, the technical aspects of only private blockchain systems will be the focus of my talk. Along the way, I will bust many myths associated with permissionless blockchains. I will also compare traditional database technologies with blockchain systems’ features and identify desirable future research topics. Extensive blockchain related collateral can be found at http://bit.ly/CMbcDB.

Speaker Bio:
Dr. C. Mohan is currently an IBM Fellow at the IBM Almaden Research Center in Silicon Valley and a Distinguished Visiting Professor at Tsinghua University in China. He has been an IBM researcher for 38 years in the database and related areas, impacting numerous IBM and non-IBM products, the research and academic communities, and standards, especially with his invention of the well-known ARIES family of database locking and recovery algorithms, and the Presumed Abort distributed commit protocol. This IBM (1997), ACM (2002) and IEEE (2002) Fellow has also served as the IBM India Chief Scientist (2006-2009). In addition to receiving the ACM SIGMOD Edgar F. Codd Innovations Award (1996), the VLDB 10 Year Best Paper Award (1999) and numerous IBM awards, Mohan was elected to the US and Indian National Academies of Engineering (2009) and named an IBM Master Inventor (1997). This Distinguished Alumnus of IIT Madras (1977) received his PhD at the University of Texas at Austin (1981). He is an inventor of 50 patents. He is currently focused on Blockchain, Big Data and HTAP technologies (http://bit.ly/CMbcDB, http://bit.ly/CMgMDS). For over 2 years, he has been an evangelist for permissioned blockchains and the myth buster of permissionless blockchains. Since 2016, Mohan has been a Distinguished Visiting Professor of China’s prestigious Tsinghua University. He has served on the advisory board of IEEE Spectrum, and on numerous conference and journal boards. Mohan is a frequent speaker in North America, Europe and Asia, and has given talks in 40 countries. He is very active on social media and has a huge network of followers. More information can be found in the Wikipedia page at http://bit.ly/CMwIkP

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Statistical Analysis for Uncertainty Quantification and Visualization of Scientific Data

  • Speaker: Dr. Tushar Athawale
                   University of Utah
  • Date and Time: Monday, November 18, 2019, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Data visualization has become indispensable for efficient interpretation of data generated across diverse scientific domains, such as biomedical imaging and meteorology. Many critical decisions directly rely on the quality of data visualizations. Inaccuracies in visualizations cannot be averted due to uncertainties inherent in underlying data and non-linear transformations of data caused by the stages of visualization pipeline. The uncertainty in the final visualizations can adversely impact the decision-making process. The accurate quantification of uncertainties in data visualizations has, therefore, been recognized as the top research challenge for minimizing risks associated with scientific decisions.

In this talk, I will present my contributions in the field of uncertainty visualization. My main topics of discussion are as follows: 1) Need for uncertainty visualizations, 2) abstract statistical methods for uncertainty quantification, 3) application of uncertainty visualization to level sets, specifically, the study of interaction of the marching cubes algorithm with uncertain data, 4) a few more applications of uncertainty visualization, 5) future work. Our uncertainty visualizations confirm the significance or need for incorporating statistical error analysis into computational models for visualization applications.

Speaker Bio:
Tushar Athawale was a postdoctoral fellow at the University of Utah's Scientific Computing & Imaging (SCI) Institute with Prof. Chris R. Johnson as his advisor since October, 2016. Soon he will join the Oak Ridge National Laboratory located in Tennessee as a Research Scientist. He received PhD in Computer Science from the University of Florida in May, 2015, and he worked with Prof. Alireza Entezari while pursuing his PhD. After his graduation, he worked as an application support engineer in MathWorks, the developer of the leading computing software MATLAB. His primary research interests are in uncertainty quantification and statistical analysis. (personal website: http://tusharathawale.info/home/)

Host Faculty: Prof. Vijay Natarajan

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Practically Efficient Secure Small Party Computation over the Internet

  • Speaker: Ms. Megha Byali
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Monday, November 18, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Secure Multi-party Computation with small population has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. Practically efficient constructions have been witnessed in the setting of both honest majority and dishonest majority. In this work, we investigate the efficiency of a wide range of security notions in the small party domain of 5 parties and 4 parties. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. All our constructions are backed with experimental results.

In the setting of five parties with honest majority, we present efficient instantiations with unanimous abort (where either all honest parties obtain the output or none of them do) and fairness (where the adversary obtains its output only if all honest parties also receive it) assuming a minimal setting of pairwise-private channels. With the presence of an additional broadcast channel (known to be necessary), we present a construction with the strongest security of guaranteed output delivery (where any adversarial behaviour cannot prevent the honest parties from receiving the output). The broadcast communication is minimal and independent of circuit size. In terms of performance (communication and run time), our protocols incur minimal overhead over the best known selective abort protocol of Chandran et al. (ACM CCS 2016) while retaining their round complexity. Further, our protocols for fairness and unanimous abort can be extended to n-parties with at most √n corruptions, similar to Chandran et al.

In the setting of four parties, surpassing the traditional model of honest majority, we aim to achieve stronger security goals in a mixed model where minority of the parties are actively corrupt and additionally some parties are passively corrupt, thus giving an overall dishonest majority. In this direction, we present the first efficient constructions that tolerate a mixed adversary corrupting 1 party actively and 1 party passively. Our constructions achieve the security goals of with guaranteed output delivery and fairness in a minimal setting of pairwise private channels and adhere to the feasibility result of Hirt et al. (CRYPTO’13).

Going beyond the most popular honest-majority setting of three parties with one corruption, our results demonstrate feasibility of attaining stronger security notions at an expense not too far from the least desired security of selective abort.

Video Archive Go Top

 

PAST SEMINARS

Series: Ph.D. Colloquium
Title: Neural Graph Embedding methods for Natural Language Processing

  • Speaker: Mr. Shikhar Vashishth
                   PhD Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Partha Pratim Talukdar & Prof. Chiranjib Bhattacharyya
  • Date and Time: Thursday, October 31, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Graphs are all around us, ranging from citation and social networks to Knowledge Graphs (KGs). They are one of the most expressive data structures which have been used to model a variety of problems. Knowledge graphs are structured representations of facts in a graph, where nodes represent entities and edges represent relationships between them. Recent research has resulted in the development of several large KGs; examples include DBpedia, YAGO, NELL, and Freebase. However, all of them tend to be sparse with very few facts per entity. For instance, NELL KG consists of only 1.34 facts per entity. In the first part of the thesis, we propose three solutions to alleviate this problem: (1) KG Canonicalization, i.e., identifying and merging duplicate entities in a KG, (2) Relation Extraction which involves automating the process of extracting semantic relationships between entities from unstructured text, and (3) Link prediction which includes inferring missing facts based on the known facts in a KG. For KG Canonicalization, we propose CESI (Canonicalization using Embeddings and Side Information), a novel approach that performs canonicalization over learned embeddings of Open KGs. The method extends recent advances in KG embedding by incorporating relevant NP and relation phrase side information in a principled manner. For relation extraction, we propose RESIDE, a distantly-supervised neural relation extraction method which utilizes additional side information from KGs for improved relation extraction. Finally, for link prediction, we propose InteractE which extends ConvE, a convolutional neural network-based link prediction method, by increasing the number of feature interaction through three key ideas – feature permutation, a novel feature reshaping, and circular convolution. Through extensive experiments on multiple datasets, we demonstrate the effectiveness of our proposed methods.

Traditional Neural Networks like Convolutional Networks and Recurrent Neural Networks are constrained to handle Euclidean data. However, graphs in Natural Language Processing (NLP) are prominent. Recently, Graph Convolutional Networks (GCNs) have been proposed to address this shortcoming and have been successfully applied for several problems. In the second part of the thesis, we utilize GCNs for Document Timestamping problem, which forms an essential component of tasks like document retrieval, and summarization.

For this, we propose NeuralDater which leverages GCNs for jointly exploiting syntactic and temporal graph structures of document for obtaining state-of-the-art performance on the problem. We also propose SynGCN, a flexible Graph Convolution based method for learning word embeddings which utilize dependency context of a word instead of linear context for learning more meaningful word embeddings. In this third part of the thesis, we address two limitations of existing GCN models, i.e., (1) The standard neighborhood aggregation scheme puts no constraints on the number of nodes that can influence the representation of a target node. This leads to a noisy representation of hub-nodes which coves almost the entire graph in a few hops. To address this shortcoming, we propose ConfGCN (Confidence-based GCN) which estimates confidences to determine the importance of a node on another during aggregation, thus restricting its influence neighborhood. (2) Most of the existing GCN models are limited to handle undirected graphs. However, a more general and pervasive class of graphs are relational graphs where each edge has a label and direction associated with it. Existing approaches to handle such graphs suffer from over-parameterization and are restricted to learning representation of nodes only. We propose CompGCN, a novel Graph Convolutional framework which jointly embeds entity and relations in a relational graph. CompGCN is parameter efficient and scales with the number of relations. It leverages a variety of entity-relation composition operations from KG Embedding techniques and achieves demonstrably superior results on node classification, link prediction, and graph classification tasks.

Video Archive Go Top

 

Series: Department Seminar
Title: Minicrypt Primitives with Algebraic Structure

  • Speaker: Dr. Sikhar Patranabis
                   Research Associate
                   Dept. of CSA
                   IISc
  • Date and Time: Tuesday, October 29, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: one-way functions, weak unpredictable functions and weak pseudorandom functions. The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We show that these structured primitives can be used to construct several Cryptomania primitives in a generic manner. A few examples of such primitives include hash encryption, hinting PRGs, lossy trapdoor functions and maliciously secure OT/MPC in the plain/CRS model.

Our results make it substantially easier to show the feasibility of building many cryptosystems from novel assumptions in the future. In particular, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner from input-homomorphic weak unpredictable/pseudorandom functions, and hence, from any concrete assumption that implies the existence of these structured primitives. Our results also allow us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In particular, endowing Minicrypt primitives with increasingly richer algebraic structure allows us to gradually build a wider class of cryptoprimitives. This seemingly provides a hierarchical classification of many Cryptomania primitives based on the "amount" of structure inherently necessary for realizing them.

Speaker Bio:
Sikhar Patranabis received his PhD in Computer Science with a specialization in cryptography from IIT Kharagpur, India. His research interests span all aspects of cryptography, with special focus on cryptographic complexity, encrypted analytics, and the design and implementation of real world cryptographic protocols. Sikhar is currently visiting the CrIS Lab as a research associate, hosted by Dr. Arpita Patra. He will be joining as a postdoctoral researcher in the Applied Cryptography group at ETH Zürich, hosted by Dr. Kenny Paterson. Sikhar was an IBM PhD fellow for the academic sessions 2016-17 and 2017-18. Prior to joining the PhD program, he completed his B.Tech from IIT Kharagpur, where he was the recipient of the President of India gold medal.

Host Faculty: Dr. Arpita Patra

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Relation Schema Induction using Tensor Factorization and Algorithms for Low-rank Tensor Completion

  • Speaker: Mr. Madhav Ram Nimishakavi
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Partha Pratim Talukdar
  • Date and Time: Monday, October 28, 2019, 10:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Many tasks in Machine Learning involve dealing with multidimensional data. The underlying structure of such multidimensional data is useful in many applications. Tensors, which are multi-way generalization of matrices, can be used to represent the multidimensional data. Tensor decomposition is extensively used for analyzing this type of data in various fields. In the first part of the thesis, we introduce two novel tensor decomposition based approaches for the problems of Relation Schema Induction (RSI) and Higher-order Relation Schema Induction (HRSI). RSI is the task of inducing schemata i.e., type signatures of arguments of relations from raw text. For example, capital_of(city, country) is a valid schema for the relation capital_of. This is an important first step in the construction of Knowledge Bases (or Knowledge Graphs) for a new domain. We propose a novel coupled Matrix-Tensor decomposition based approach called Schema Induction using Coupled Tensor Factorization (SICTF) for the task of RSI. Similarly, the task of HRSI is inducing type signatures of more arguments than just subject and object for relations. For this task, we propose a novel framework called Tensor Factorization with Back-off and Aggregation (TFBA). TFBA jointly factorizes multiple tensors as the first step and then performs aggregation for constructing higher-order (or $n$-ary) schemata. Through extensive experiments on multiple real world datasets, we demonstrate the effectiveness of SICTF and TFBA for the tasks of RSI and HRSI respectively.

Many real world multidimensional datasets are often incomplete and a lot of applications can benefit from predicting the missing values in these datasets. In this context, the problem of tensor completion is used, which is the task of predicting missing values in a partially observed tensor. A common assumption made for tensor completion is that the tensor is of low-rank. Two of the most popular approaches for low-rank tensor completion are trace norm based approaches and decomposition based approaches. In the second part of the thesis, we propose two novel frameworks for low-rank tensor completion. First, we consider the standard batch mode setting where the tensor data is static and does not change with time. The second setting we consider is the dynamic setting, where the tensor can grow along the dimensions dynamically with time. In the dynamic setting, we also incorporate additional side information matrices that can be available along different modes of the tensor.

For the first setting, we propose a novel regularizer based on the latent trace norm for the problem of low-rank tensor completion. This regularizer helps in learning a non-sparse combination of tensors, which helps in achieving better tensor completion results on multiple datasets. We propose two novel optimization formulations, variables in the proposed formulations are constrained to lie on a set which is a Cartesian product of smooth manifolds. We show the smooth manifolds are Riemannian spectrahedron manifolds. These formulations enable us to utilize the Riemannian optimization framework, using which we propose efficient trust region algorithms for solving the formulations.

For the second setting, we propose an inductive framework called Side Information infused Incremental Tensor Analysis (SIITA) for the problem of dynamic tensor completion. Most of the existing approaches for dynamic tensor completion make a restrictive assumption that the tensor grows only along one mode, but SIITA can handle the more general setting where the tensor is allowed to grow in all modes. The setting where the tensor is allowed to grow along any mode with time is referred to as Multi-aspect Streaming Setting. SIITA incorporates side information into dynamic tensor completion and can also model sparsity, first ever dynamic tensor completion algorithm to do so to the best of our knowledge. We also show how non-negative constraints can be incorporated into SIITA which is desirable for learning interesting clusters in an unsupervised setting, under certain data distributions. Through extensive experiments on multiple real world datasets across various tasks, we illustrate the efficacy of proposed low-rank tensor completion algorithms.

Video Archive Go Top

 

Series: Department Seminar
Title: Recent Progress in Code Obfuscation

  • Speaker: Dr Venkata Koppula,
                   Postdoctoral Research Fellow, Weizmann Institute
  • Date and Time: Friday, October 25, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Code obfuscation has been one of the main focal points of cryptographic research over the last few years. A code obfuscator is a compiler that hides the implementation of programs while preserving functionality. Barak et al showed that the most desirable definition of code obfuscation - virtual black box (VBB) obfuscation - is impossible for general functions. Therefore, we must either restrict our attention to weaker notions of obfuscation, or study obfuscation for restricted classes of functions. In this talk, I will first discuss one such weaker notion of obfuscation (called indistinguishability obfuscation) and its tremendous impact on cryptography.

Next, I will present a VBB obfuscation scheme for a restricted but useful function class. We call this notion `lockable obfuscation'. Our obfuscation scheme's security is based on standard cryptographic assumptions. At the same time, it has a number of applications, for upgrading security of encryption schemes as well as showing separations between different security notions. I will present one such application, followed by a brief discussion of how research related to indistinguishability obfuscation led to this result.

Based on joint work with Rishab Goyal and Brent Waters, and no prior background on obfuscation/crypto will be needed.

Speaker Bio:
Venkata Koppula is a postdoctoral researcher at the Weizmann Institute of Science, hosted by Zvika Brakerski. Prior to this, he was a graduate student at the University of Texas at Austin, where his advisor was Brent Waters. He is interested in the theoretical aspects of cryptography.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: Department Seminar
Title: Does PD Control Always Work for Robotic Systems?

  • Speaker: Dr Shishir N Y Kolathaya,
                   INSPIRE Faculty Fellow, RBCCPS, IISc
  • Date and Time: Tuesday, October 22, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In 2015, a committee created by the International Federation of Automatic Control (IFAC) surveyed its members to obtain their views on the impact of advanced control in industries. PID control was first with a 100% high-impact rating, and nonlinear control was tenth with a 22% rating. Clearly, despite great advances in the theory of nonlinear controls,PD and PID tracking control laws continue to be the most popular choice. This is true even for robotic systems. Therefore, the goal of the talk is to understand some of the stability guarantees provided by PD control laws in the context of robotic systems.

The talk is divided into two parts. First, we will discuss existing stability results for PD controlled robotic systems. Some of these results were established as early as the 1980's. Second, we will extend these stability properties to underactuated and hybrid robotic systems i.e., by introducing additional assumptions on the unactuated coordinates of the robot. We will demonstrate these results on bipedal walking robots, which are known to be textbook examples for hybrid robotic systems. Bipedal robots have the leg-swing as the continuous event, and the foot-strike as the discrete event, and these events alternate during walking. In addition, bipeds largely have underactuations due to the interactions between feet and ground. For each continuous event, we establish that the convergence rate of the tracking error can be regulated via appropriate tuning of the PD gains, and for each discrete event, we establish that this convergence rate sufficiently overcomes the nonlinear impacts by assumptions on the hybrid zero dynamics. Towards the end, we will validate these results on a 5-link bipedal walker in simulation.

Speaker Bio:
Shishir is an INSPIRE Faculty fellow in the Robert Bosch Center for Cyber Physical Systems (RBCCPS) in IISc Bangalore. He received his Ph.D. degree in Mechanical Engineering (2016) from the Georgia Institute of Technology, M.S. degree in Electrical Engineering (2012) from Texas A&M University, and B.Tech degree in Electrical & Electronics Engineering (2008) from National Institute of Technology Karnataka. His primary focus as a Ph.D. student was on stability and control of walking robots. Shishir is currently interested in safety-critical control, stability of hybrid systems, and deep reinforcement learning for all kinds of robotic platforms.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: Department Seminar
Title: Fault-Tolerant Reachability and Strong-connectivity Structures

  • Speaker: Dr Keerti Choudhary
  • Date and Time: Friday, October 18, 2019, 11:00 AM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most real-world networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute data-structures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, min-cuts, etc. in the domain of fault tolerance networks.

In this talk, I will discuss the following questions: 1. Can we compute a reachability tree in just linear time, after the occurrence of a small number of failures? 2. How fast can we compute the strongly connected components, again on the occurrence of failures? 3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?

The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.

Speaker Bio:
Keerti Choudhary is a postdoctoral fellow in the Computer Science department at Tel Aviv University, where she is hosted by Shiri Chechik. Prior to this, she was a postdoctoral fellow at the Weizmann Institute of Sciences (Oct 2017 - Sept 2019), where her host was David Peleg. Keerti completed her Ph.D. in Computer Science from IIT Kanpur in August 2017, where she was advised by Surender Baswana. She is also a 2013 graduate from the Mathematics department at IIT Kanpur. https://sites.google.com/view/keerti/

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Abstract Interpretation -- a framework for verifying correctness of programs

  • Speaker: Prof. K. V. Raghavan
                   Associate Professor
                   Dept. of CSA
                   IISc
  • Date and Time: Friday, October 04, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Abstract Interpretation is a technique for static analysis of programs. The objective of any static analysis technique is to identify whether a property of interest holds across all executions of a program without running the program at all. Abstract interpretation has certain unique advantages: (1) It is a framework, in that it can be customized by a user to analyze any property of interest. (2) It is safe, in that it declares a property as holding only if it provably holds in all possible runs of the program. (3) Implementations of it are provided by many tools, for various prevalent programming languages. (4) It is efficient in practice, even on very large programs. In this talk we will explore abstract interpretation by going over some examples involving it, by taking a look at the mathematical theory underlying it, and by looking at its usage in practical settings.

Speaker Bio:
K. V. Raghavan is an Associate Professor at the Department of Computer Science and Automation, Indian Institute of Science, Bangalore. His areas of interest are program analysis and verification, programming tools, and formal methods in software engineering.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Static Analysis for Detecting High-Level Races in RTOS Kernels

  • Speaker: Rekha Pai
  • Date and Time: Monday, September 30, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We propose a static analysis based approach for detecting high-level races in RTOS kernels popularly used in safety-critical embedded software. High-Level races are indicators of atomicity violations and can lead to erroneous software behaviour with serious consequences. Hitherto techniques for detecting high-level races have relied on model- checking approaches, which are inefficient and apriori unsound. In contrast we propose a technique based on static analysis that is both efficient and sound. The technique is based on the notion of disjoint blocks recently introduced in Chopra et al. We evaluate our technique on three popular RTOS kernels and show that it is effective in detecting races, many of them harmful, with a high rate of precision.

This is joint work with Abhishek Singh (IIIT Bangalore), Deepak D'Souza (IISc), and Meenakshi D'Souza (IIIT Bangalore). The work will be presented at the Formal Methods Symposium in Porto, Portugal, next month.

Speaker Bio:
Rekha Pai is a Kothari Post-Doctoral Fellow at the Computer Science and Automation department, IISc, Bangalore. Her interests are in Code Transformation and Static Race Detection.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Program Synthesis meets Machine Learning

  • Speaker: Sriram Rajamani
  • Date and Time: Friday, September 20, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We give a tutorial overview of program synthesis, from its first formulation by Church in 1957, through its pragmatic evolution through sketching and programing-by-examples, and compare program synthesis with supervised machine learning. We then present our recent efforts (together with colleagues) in combining program synthesis and machine learning techniques to solve the problem of synthesizing extractors from heterogeneous data, as well as in solving NLP problems. Finally, we explore several opportunities at the intersection of program synthesis (and more broadly the PL community) and machine learning, such as pruning and ranking programs during synthesis, neural program synthesis and automatic differentiation. Towards the end, we will briefly outline plans for a course we are planning with Prof. Deepak D’Souza and Prof. Chiranjib Bhattacharyya in the Jan 2020 semester on this broad topic.

Speaker Bio:
Sriram Rajamani is Distinguished Scientist and Managing Director of Microsoft Research India. His research interests are in designing, building and analyzing computer systems in a principled manner. Over the years he has worked on various topics including Hardware and Software Verification, Type Systems, Language Design, Distributed Systems, Security and Privacy. His current research interest is in combining Program Synthesis and Machine Learning.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Term modal logic

  • Speaker: Anantha Padmanabha
  • Date and Time: Thursday, September 19, 2019, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Modal logic has been ubiquitously used in many fields of computer science including verification, epistemic logic etc. Typically we have two modal operators "Box" and "Diamond" which in a broad sense refers to "necessity" and "possibility" respectively. For instance, (Box_i alpha) in an epistemic setting means that "Reasoner i knows that alpha". Similarly, (Diamond_i alpha) in the context of a system of processes is interpreted as "Process i can possibly change the system configuration to a state where alpha holds". These reasoners or process index are referred to as agents in general.

Classically, the number of agents is assumed to be fixed and finite. But in many settings like multi-process systems / client-server systems, we cannot fix the agent set beforehand. The active agents change not only from one model to the other but also from one state to the other in the same model. For instance, in multi-process systems, when the system configuration changes, some processes may be terminated and some new ones may be created.

Term modal logic introduced by Fitting et.al is suitable to study such settings, where we can state properties like "exists x Box_x alpha" which means "there exists some process x such that any state update by process x necessarily leads to a state where alpha holds".

In this talk we will look at term modal logic in some detail. This is a joint work with R. Ramanujam

Speaker Bio:
Anantha Padmanabha has recently submitted his PhD thesis in the Institute of Mathematical Sciences, Chennai.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Breaking the $2^n$ Barrier in Secret Sharing

  • Speaker: Professor Vinod Vaikuntanathan
                   Associate Professor at MIT EECS
                   and Co-Founder of Duality Technologies
  • Date and Time: Friday, September 13, 2019, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Information-theoretic cryptography is full of open problems with a communication-complexity flavor. One such problem arises in the context of secret sharing for general access structures where there is a huge (exponential) gap between the best known upper and lower bounds. We will describe some recent progress on resolving some of these long-standing gaps in the context of secret sharing, CDS and PSM.

Based on work with Tianren Liu and Hoeteck Wee, at Crypto 2017, Eurocrypt 2017 and STOC 2018.

Speaker Bio:
Professor Vinod Vaikuntanathan is an associate professor of computer science at MIT and the chief cryptographer at Duality Technologies. Vinod is the co-inventor of most modern fully homomorphic encryption systems and many other lattice-based (post-quantum secure) cryptographic primitives. His work has been recognized with a George M. Sprowls PhD thesis award (2009), an IBM Josef Raviv Fellowship (2008), a Sloan Faculty Fellowship (2013), a Microsoft Faculty Fellowship (2014), an NSF CAREER Award (2014), a DARPA Young Faculty Award (2018), and a Harold E. Edgerton Faculty Award (2018). He holds SM and PhD degrees from MIT and a BTech degree from the Indian Institute of Technology Madras.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Distributed algorithms for prototype selection and multi-label classification

  • Speaker: Dr. V. Susheela Devi
                   Principal Research Scientist
                   Dept. of CSA
  • Date and Time: Friday, September 06, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The Modified Condensed Nearest Neighbour (MCNN) algorithm is an algorithm for prototype selection which gives good performance but the time requirement is much higher than algorithms like Condensed Nearest Neighbour (CNN) algorithm. A distributed approach called Parallel MCNN (pMCNN) is proposed which cuts down the time required drastically. pMCNN has been used for prototype selection on large and streaming data and results are presented which shows good performance with saving in time.

The second part of the talk describes an algorithm for multilabel classification for discrete data. Two improvements are carried out to reduce the complexity. The first is feature selection which reduces both space and time complexity. The second is to use a distributed approach to this problem. Results show good performance as compared to standard techniques like ML-KNN (Multi label kNN). The use of feature selection and the distributed approach give saving in the time required which is helpful when the data sizes are large.

Speaker Bio:
V. Susheela Devi works in the Intelligent Systems group in the department. Her areas of interest include pattern recognition, machine learning and soft computing. She is the co-ordinator of the Pattern Analysis and Machine Intelligence lab. She has handled courses such as Pattern Recognition, Data Mining, Data Structures and Algorithms, Computational Methods of Optimization, Artificial Intelligence and Soft Computing.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Optimum Policy Adaptation Learning for uSD cards

  • Speaker: Mr. Abhinav Anand
                   M.Tech (Research)Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya
  • Date and Time: Thursday, September 05, 2019, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Machine Learning(ML) for Systems is a new and promising research area where performance of computer systems is optimized using machine learning methods. ML for Systems has outperformed traditional heuristics methods in various areas like learning memory access patterns in microarchitecture (Hashemi et. al), generating optimization heuristics using deep learning in compilers (Cummins et. al), avoiding unnecessary writes by efficient SSD caching using machine learning in storage systems (Wang et. al) etc. Systems for ML is another research area which is different from ML for Systems. In Systems for ML, focus is on designing specialized hardware for increasing computing capability for deep learning networks.

In this work, we apply machine learning to improve the performance and reliability of NAND flash based micro-SD(uSD) cards. In present scenario, NAND settings in uSD card are set heuristically to achieve desired performance. However manually tuning these configurations is very hard because of complex interactions between them and changing one can have a large and unexpected effect on another. This is where machine learning in storage systems is useful: manually it may not be possible to optimize thousands of NAND settings in uSD, but it's the type of exercise that machine learning systems excel at. However small storage devices like uSD cards are resource constrained. Therefore using ML algorithms on uSD card with low memory and computation power is in itself a challenge.

In comparison to SSDs, no workload characterization studies has been done for uSD cards. Thus we have no knowledge of existence of new patterns which in turn limits our understanding of policy space. Lot of research has been done to make SSDs firmware adaptive but current uSD firmware is non-adaptive in nature i.e it services all workloads using single policy. Another major issue is that uSD card is constrained on internal RAM and microprocessor, which restricts the use of computationally expensive ML algorithms.

To tackle these problem, we have proposed a machine learning based framework Optimum Policy Adaptation Learning(OPAL) to identify novel patterns and formulate targeted policies. The machine learning model in the controller of NAND flash will identify the incoming workload and map it to optimal policy thus making it adaptive for the incoming workloads. To the best our knowledge we are the first to collect workload data for uSD cards, categorize workloads into patterns, and design a computationally efficient adaptive firmware. Using OPAL we have achieved significant improvements in real world scenarios like 44 % reduction in file copy time and 54 % increase in the lifetime of card.

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Efficient and Secure Search over Encrypted Data

  • Speaker: Mr.Shah Akash Amritlal Rupa
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Friday, August 30, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Due to a variety of crucial benefits, enterprises outsource their data to cloud resident storage. The outsourced data needs to be stored in encrypted form on remote untrusted servers to preserve privacy. However, if the client has to retrieve the entire data and decrypt it in order to get results for a search query then that will defeat the purpose of outsourcing. A solution to this problem is Searchable Encryption that provides a reasonable trade-off between security and efficiency.

Our first contribution is in the context of Dynamic Searchable Symmetric Encryption (DSSE). DSSE schemes, apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. This work makes two contributions: (i) propose alternative formulations of information leakage for backward privacy after revisiting the existing ones [Bost et al. CCS'17], (ii) construct three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. Our first construction Π_BP-prime achieves a stronger notion of backward privacy whereas our next two constructions Π_BP and Π_WBP achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small.

Certain applications require some type of fuzzy searches like wildcard and edit-distance based search over encrypted data. In our second work, we investigate the problem of secure wildcard search over encrypted data in Outsourced Symmetric Private Information Retrieval (OSPIR) setting. The setting comprises of three entities, viz., the data owner, the server and the client. The data owner outsources the encrypted data to the server, who obliviously services the clients' queries. We propose two schemes, viz., Π_BS and Π_OTE to support secure wildcard search over encrypted data. Construction Π_BS reduces the problem of secure wildcard search to that of Boolean search. Π_BS is a sub-linear wildcard search protocol but it allows false positives. Our second construction Π_OTE utilizes Oblivious Transfer Extension protocols to obtain linear time wildcard search protocol with no false positives. Π_BS and Π_OTE can then be combined to obtain an efficient sub-linear solution with no false positives. We provide performance analysis based on our prototype implementation to depict the feasibility of our proposed constructions.

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2018      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits