etd@IISc Collection:
http://hdl.handle.net/2005/18
2015-05-23T01:54:40ZNew Approaches And Experimental Studies On - Alegebraic Attacks On Stream Ciphers
http://hdl.handle.net/2005/2436
Title: New Approaches And Experimental Studies On - Alegebraic Attacks On Stream Ciphers
Authors: Pillai, N Rajesh
Abstract: Algebraic attacks constitute an effective class of cryptanalytic attacks which have come up recently. In algebraic attacks, the relations between the input, output and the key are expressed as a system of equations and then solved for the key. The main idea is in obtaining a system of equations
which is solvable using reasonable amount of resources. The new approaches proposed in this work and experimental studies on the existing algebraic attacks on stream ciphers will be presented.
In the first attack on filter generator, the input-output relations are expressed in conjunctive normal form. The system of equations is then solved using modified Zakrevskij technique. This was one of the earliest algebraic attacks on the nonlinear filter generator.
In the second attack, we relaxed the constraint on algebraic attack that
the entire system description be known and the output sequence extension problem where the filter function is unknown is considered. We modeled the problem as a multivariate interpolation problem and solved it. An advantage of this approach is that it can be adapted to work for noisy output sequences where as the existing algebraic attacks expect the output sequence to be error free.
Adding memory to filter/combiner function increases the degree of system of equations and finding low degree equations in this case is computeintensive. The method for computing low degree relations for combiners
with memory was applied to the combiner in E0 stream cipher. We found that the relation given in literature [Armknecht and Krause] was incorrect.
We obtained the correct equation and verified its correctness.
A time-data size trade off attack for clock controlled filter generator was developed. The time complexity and the data requirements are in between the two approaches used in literature.
A recent development of algebraic attacks - the Cube attack was studied.
Cube attack on variants of Trivium were proposed by Dinur and Shamir where linear equations in key bits were obtained by combining equations for output bit for same key and a set of Initialization Vectors (IVs). We investigated the effectiveness of the cube attack on Trivium. We showed
that the linear equations obtained were not general and hence the attack succeeds only for some specific values of IVs. A reason for the equations not being general is given and a modification to the linear equation finding step suggested.2015-02-04T18:30:00ZVisual Analysis Of Interactions In Multifield Scientific Data
http://hdl.handle.net/2005/2407
Title: Visual Analysis Of Interactions In Multifield Scientific Data
Authors: Suthambhara, N
Abstract: Data from present day scientific simulations and observations of physical processes often consist of multiple scalar fields. It is important to study the interactions between the fields to understand the underlying phenomena. A visual representation of these interactions would assist the scientist by providing quick insights into complex relationships that exist between the fields.
We describe new techniques for visual analysis of multifield scalar data where the relationships can be quantified by the gradients of the individual scalar fields and their mutual alignment. Empirically, gradients along with their mutual alignment have been shown to be a good indicator of the relationships between the different scalar variables.
The Jacobi set, defined as the set of points where the gradients are linearly dependent, describes the relationship between the gradient fields. The Jacobi set of two piecewise linear functions may contain several components indicative of noisy or a feature-rich dataset. For two dimensional domains, we pose the problem of simplification as the extraction of level sets and offset contours and describe a robust technique to simplify and create a multi-resolution representation of the Jacobi set.
Existing isosurface-based techniques for scalar data exploration like Reeb graphs, contour spectra, isosurface statistics, etc., study a scalar field in isolation. We argue that the identification of interesting isovalues in a multifield data set should necessarily be based on the interaction between the different fields. We introduce a variation density function that profiles the relationship between multiple scalar fields over isosurfaces of a given scalar field. This profile serves as a valuable tool for multifield data exploration because it provides the user with cues to identify interesting isovalues of scalar fields.
Finally, we introduce a new multifield comparison measure to capture relationships between scalar variables. We also show that our measure is insensitive to noise in the scalar fields and to noise in their gradients. Further, it can be computed robustly and efficiently. The comparison measure can be used to identify regions of interest in the domain where interactions between the scalar fields are significant. Subsequent visualization of the data focuses on these regions of interest leading to effective visual analysis.
We demonstrate the effectiveness of our techniques by applying them to real world data from different domains like combustion studies, climate sciences and computer graphics.2014-11-13T18:30:00ZRainbow Connection Number Of Graph Power And Graph Products
http://hdl.handle.net/2005/2383
Title: Rainbow Connection Number Of Graph Power And Graph Products
Authors: Arunselvan, R
Abstract: The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.2014-09-08T18:30:00ZA Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions Reduction
http://hdl.handle.net/2005/2361
Title: A Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions Reduction
Authors: Shelke, Sunil Sitaram
Abstract: Global warming is currently a major challenge facing the world. There are widespread ongoing efforts in the form of summits, conferences, etc., to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in global warming related problems. This dissertation explores for the first time the use of voting mechanisms in the context of solving the central problems, namely, allocation of emission caps and reduction quotas to strategic emitting agents (countries).
The contribution of this dissertation is two-fold. The first contribution is to develop an elegant game theoretic model that accurately captures the strategic interactions among different emitting agents in a global warming setting. This model facilitates a convenient way of exploring a mechanism design approach for solving important allocation problems in the global warming context. The second contribution is to propose and explore a novel approach, based on voting mechanisms, to solve two problems: (1) allocating emission caps and (2) allocating reduction quotas to strategic agents.
Our work investigates the use of voting mechanisms that satisfy four desirable properties:
(1) non-dictatorship, (2) strategy-proofness, (3) efficiency, and (4) anonymity. In particular, we explore the median selection, maximum order statistic selection, and general Kth order statistic selection voting mechanisms. Our results clearly show that only trivial allocations satisfy all the above properties simultaneously. We next investigate the use of voting mechanisms for the dual problem, namely, allocation of emission reductions to emitting agents. Here, we show that non-trivial allocations are possible, however an important property, individual rationality, might be compromised.
The investigations in the thesis bring out certain limitations in applying voting mechanisms that satisfy all the four properties above. Nevertheless, the insights obtained provide valuable guidelines for solving emission allocation related problems in a principled and informed way.2014-08-06T18:30:00Z