Department of Computer Science and Engineering

Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

Technology scaling into the nano-scale CMOS regime has resulted in increased leakage and roadblock on voltage scaling, which has led to several issues like high power density and elevated on-chip temperature. This consequently aggravates device aging, compromising lifetime reliability of the manycore systems. This paper proposes HiMap, a dynamic hierarchical mapping approach to maximize lifetime reliability of manycore systems while satisfying performance, power, and thermal constraints. HiMap is process variation- and aging-aware. It comprises of two levels: (1) it identifies a region of cores suitable for mapping, and (2) it maps threads in the region and intersperses dark cores for thermal mitigation while considering the current health of the cores. Both the levels strive to reduce aging variance across the chip. We evaluated HiMap for 64-core and 256-core systems. Results demonstrate an improved system lifetime reliability by up to 2 years at the end of 3.25 years of use, as compared to the state-of-the-art. © 2018 EDAA.

World University root node

Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018

HiMap: A hierarchical mapping approach for enhancing lifetime reliability of dark silicon manycore systems

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, ?ai=1Ei), where the edge set of G is partitioned into a color classes, is called an a-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F1, . . ., Fa)-Deletion problem. In the latter problem, we are given an a-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi - S, where Gi = (V, Ei) and 1 = i = a, is in Fi. Recently, a subset of the authors considered the aforementioned problem with F1 = . . . = Fa being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and a and can be solved in O(2O(ak)) time1. In this work, we initiate the investigation of the complexity of Simultaneous (F1, . . ., Fa)-Deletion with di erent families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the Fis is the class of bipartite graphs and the rest (if any) are forests. We show that if F1 is the family of all bipartite graphs and each of F2 = F3 = . . . = Fa is the family of all forests then the problem is fixed-parameter tractable parameterized by k and a. However, even when F1 and F2 are both the family of all bipartite graphs, then the Simultaneous (F1, F2)-Deletion problem itself is already W[1]-hard. © Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan.

Leibniz International Proceedings in Informatics, LIPIcs

On the parameterized complexity of simultaneous deletion problems

Cryptographic primitives need high-speed implementations that are also resistant to side channel attacks. The absolute control over instructions and registers that such implementations demand makes assembly language programming a necessity. In this article, we describe Verse, a typed low-level language embedded in Coq designed specifically to generate assembly language programs for cryptographic primitives. Despite being a low-level language, the programming experience is markedly high-level: • The type system of Verse is rich enough to even prevent errors in array indexing and endian conversion. • Being embedded in Coq, we have at our disposal Gallina, the underlying functional programming language, as a macro assembler for code generation, and Ltac, the tactic language, as an automation tool for proof obligations inherent to our type system. We also provide a generic framework to formulate semantic aspects of Verse. This framework has value beyond providing an interpretation of Verse in Coq. We demonstrate this versatility by using it to localise uninitialised/clobbered variable use, and arithmetic overflows. © 2018 Association for Computing Machinery.

ACM International Conference Proceeding Series

Verse: An EDSL for cryptographic primitives

Let σ be some positive integer and (formula presented). The theory behind finding a lower bound on the number of distinct blocks P 1 , …, P σ ∈ {0, 1} n satisfying a set of linear equations {P i ⊕ P j = c i,j : (i, j) ∈ C} for some c i,j ∈ {0, 1} n , is called mirror theory. Patarin introduced the mirror theory and provided a proof for this. However, the proof, even for a special class of equations, is complex and contains several non-trivial gaps. As an application of mirror theory, XORP[w] (known as XOR construction) returning (w − 1) block output, is a pseudorandom function (PRF) for some parameter w, called width. The XOR construction can be seen as a basic structure of some encryption algorithms, e.g., the CENC encryption and the CHM authenticated encryption, proposed by Iwata in 2006. Due to potential application of XORP[w] and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of PRF-security of XORP[w] would be much desired. Recently (in Crypto 2017) Dai et al. introduced a tool, called the χ 2 method, for analyzing PRF-security. Using this tool, the authors have provided a proof of PRF-security of XORP[2] without relying on the mirror theory. In this paper, we resolve the general case; we apply the χ 2 method to obtain a simpler security proof of XORP[w] for any w ≥ 2. For w = 2, we obtain a tighter bound for a wider range of parameters than that of Dai et al.. Moreover, we consider variable width construction XORP[∗] (in which the widths are chosen by adversaries adaptively), and also provide variable output length pseudorandom function (VOLPRF) security analysis for it. As an application of VOLPRF, we propose an authenticated encryption which is a simple variant of CHM or AES-GCM and provides much higher security than those at the cost of one extra blockcipher call for every message. © 2018, Ruhr-Universitat Bochum. All rights reserved.

IACR Transactions on Symmetric Cryptology

Revisiting variable output length XOR pseudorandom function

Very recently (in CRYPTO 2017) Dai, Hoang, and Tessaro have introduced the Chi-square method (χ2 method) which can be applied to obtain an upper bound on the statistical distance between two joint probability distributions. The authors have applied this method to prove the pseudorandom function security (PRF-security) of sum of two random permutations. In this work, we revisit their proof and find a non-trivial gap in the proof. We plug this gap for two specific cases and state the general case as an assumption whose proof is essential for the completeness of the proof by Dai et al. A complete, correct, and transparent proof of the full security of the sum of two random permutations construction is much desirable, especially due to its importance and two decades old legacy. The proposed χ2 method seems to have potential for application to similar problems, where a similar gap may creep into a proof. These considerations motivate us to communicate our observation in a formal way. On the positive side, we provide a very simple proof of the PRF-security of the truncated random permutation construction (a method to construct PRF from a random permutation) using the χ2 method. We note that a proof of the PRF-security due to Stam is already known for this construction in a purely statistical context. However, the use of the χ2 method makes the proof much simpler. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Cryptography and Communications

A note on the chi-square method: A tool for proving cryptographic security

The construction XORP (bitwise-xor of outputs of two independent n-bit random permutations) has gained broad attention over the last two decades due to its high security. Very recently, Dai et al. (CRYPTO’17), by using a method which they term the Chi-squared method (X2 method), have shown n-bit security of XORP when the underlying random permutations are kept secret to the adversary. In this work, we consider the case where the underlying random permutations are publicly available to the adversary. The best known security of XORP in this security game (also known as indifferentiable security) is 2n/3-bit, due to Mennink et al. (ACNS’15). Later, Lee (IEEE-IT’17) proved a better (k-1)n/k -bit security for the general construction XORP[k] which returns the xor of k (≥2) independent random permutations. However, the security was shown only for the cases where k is an even integer. In this paper, we improve all these known bounds and prove full, i.e., n-bit (indifferentiable) security of XORP as well as XORP[k] for any k. Our main result is n-bit security of XORP, and we use the X2 method to prove it. © International Association for Cryptologic Research 2018.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Full indifferentiable security of the Xor of two or more random permutations using the X2 method

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function (Formula presented), block sensitivity of f is polynomially related to sensitivity of f (denoted by s(f)). From the complexity theory side, the Xor Log-Rank Conjecture states that for any Boolean function, (Formula presented) the communication complexity of a related function (Formula presented), (defined as (Formula presented)) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f, denoted by sparsity(f). Both the conjectures play a central role in the domains in which they are studied. A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures it suffices to upper bound alternation of f (denoted alt(f)) for all Boolean functions f by polynomial in s(f) and logarithm of sparsity(f), respectively. In this context, we show the following results: We show that there exists a family of Boolean functions for which alt(f) is at least exponential in s(f) and alt(f) is at least exponential in log sparsity(f). Enroute to the proof, we also show an exponential gap between alt(f) and the decision tree complexity of f, which might be of independent interest.As our main result, we show that, despite the above exponential gap between alt(f) and logsparsity(f), the Xor Log-Rank Conjecture is true for functions with the alternation upper bounded by poly(log n). It is easy to observe that the Sensitivity Conjecture is also true for this class of functions.The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function f, (Formula presented) where deg(f) and (Formula presented) are the degrees of f over R and F2. We give two further applications of this bound: (1) We show that Boolean functions with bounded alternation have high sparsity (Formula presented), thus partially answering a question of Kulkarni and Santha (2013). (2) We observe that the above relation improves the upper bound for influence to (Formula presented) improving Guo and Komargodski (2017). © Springer International Publishing AG 2018.

Communications in Computer and Information Science

Alternation, sparsity and sensitivity: Combinatorial bounds and exponential gaps

We consider the problem of link scheduling in multihop wireless networks subject to interference constraints. We consider a graph-based representation of wireless networks where scheduled links adhere to the $K$-hop link interference model. For this scheduling problem, we develop an asynchronous and distributed greedy heuristic. Furthermore, we show that this distributed heuristic computes the exact same schedule as the well-known centralized greedy link scheduling algorithm. © 1967-2012 IEEE.

IEEE Transactions on Vehicular Technology

Asynchronous Distributed Greedy Link Scheduling in Multihop Wireless Networks

Wireless and Social Networks: Some Challenges and Insights

The Connected Vertex Cover problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixed-parameter tractable (FPT), and is unlikely to have a polynomial sized kernel (under complexity theoretic assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et al. [STOC 2017], have shown an α-approximate kernel for the problem for every α &gt; 1, in the framework of approximate or lossy kernelization. In this work, we exhibit lossy kernels and FPT algorithms for Connected Vertex Cover for parameters that are more natural and functions of the input, and in some cases, smaller than the solution size. Our first result is a lossy kernel for Connected Vertex Cover parameterized by the size of a split deletion set. Let n denote the number of vertices in the input graph. We show that Connected Vertex Cover parameterized by the size k of a split deletion set admits an α-approximate kernel with O(k+(2k+⌈2α−1α−1⌉)⌈2α−1α−1⌉) vertices and an algorithm with O(3 knO ( 1 )) running time.For the special case when the split deletion set is a clique deletion set, the algorithm runs in O(2 knO ( 1 )) time and the lossy kernel has O(k+⌈2α−1α−1⌉) vertices. To the best of our knowledge, this (approximate) kernel is one of the few lossy kernels for problems parameterized by a structural parameter (that is not solution size). We extend this lossy kernelization to Connected Vertex Cover parameterized by an incomparable parameter, and that is the size of a clique cover. We show that Connected Vertex Cover parameterized by the size k of a clique cover is W[1]-hard but admits an α-approximate kernel with O(k⌈2α−1α−1⌉) vertices for every α &gt; 1. This is one of the few problems that are not FPT but admit a lossy kernel. Finally, we consider the size of a cluster deletion set as parameter. We show that Connected Vertex Cover parameterized by the size k of a cluster deletion set is FPT via an algorithm with running time O(4 knO ( 1 )). It also admits an α-approximate kernel with O(k2+⌈2α−1α−1⌉⋅kα−1+⌈αα−1⌉⋅k⌈αα−1⌉) vertices for every α &gt; 1.For the special case when the cluster deletion set is a degree-1 modulator, the FPT algorithm runs in O(3 knO ( 1 )) time and the lossy kernel has O(k2+kα−1+⌈αα−1⌉⋅k⌈αα−1⌉) vertices. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.