Theses

Permanent URI for this collectionhttp://164.52.219.250:4000/handle/10263/2744

Browse

Now showing 1 - 20 of 656

A Study of the SHA-2 Cryptographic Hash Family
(Indian Statistical Institute, Kolkata, 2009-02-01) Sanadhya Somitra Kumar
A1-homotopy types of A2 and A2 \ {(0, 0)}
(Indian Statistical Institute, Kolkata, 2024-12) Roy, Biman
Morel-Voevodsky developed A^1-homotopy theory which is a bridge between algebraic geometry and algebraic topology. In this thesis we study the A^1-connected component of a smooth variety in great detail. We have shown that the A^1-connected component of a smooth variety contains the information about the existence of affine lines in the variety. Using this and Miyanishi-Sugie's algebraic characterisation, we determine that the affine plane is the only A^1-contractible smooth affine surface over the field of characteristic zero. In the other part of the thesis, we studied the A^1-homotopy type of A^2-{(0,0)}. We showed that over the field of characteristic zero, if an open subvariety of a smooth affine surface is A^1-weakly equivalent to A^2-{(0,0)}, then it is isomorphic to A^2-{(0,0)}.
ABO blood-group gene frequencies in the Indian sub-continent: a statistical study of patterns of variation
(Indian Statistical Institute, Kolkata, 1980) Majumder, Partha P
Adaptation-Based Classi ers for Handling Some Problems with Multi-Label Data
(Indian Statistical Institute, Kolkata, 2022-06) Law, Anwesha
The concept of multi-label (ML) data generalizes the association of instances to classes by labelling each data sample with more than one class simultaneously. Since this data can belong to more than one class at the same time, instances that are multi-label in nature, should not be forcefully assigned a single label. It needs to be handled in its original form. However, various problems arise while dealing with multi-label data. In this thesis, four such issues have been highlighted and dealt with. The first problem is the large input dimension that sometimes occurs in multi-label data. Dimensionality reduction of the features helps to strike a balance between the feature size, the number of samples and the output dimension. The next limitation is that of a complex decision space with overlapping class boundaries. This occurs due to the instances belonging to multiple classes simultaneously. Various approaches such as improving the feature to class mapping, increasing the class separability and simplifying the decision space have been implemented. The third drawback arises due to a large number of classes and label-sets in multi-label data, most of which are under-represented. This emphasizes the problem of class imbalance that widely prevails in multi-label data. This imbalance has been handled through the usage of customized classifiers suitable for the data at hand. Finally, the problem of class correlation is to be handled in this thesis. Multiple classes simultaneously assigned to every instance indicates a possibility of a few classes co-occurring on numerous occasions. These frequently co-occurring classes might have some correlation among them which have been identified and utilized to improve the multi-label classification performance.This thesis addresses the above-mentioned issues to perform efficient multi-label classification. Smaller components that target the individual issues have been incorporated to build large classification models. The first work aims to reduce feature dimensions and learn a better feature to class mapping for the complex decision space. A shallow but fast network known as extreme learning machines (ELMs) has been cascaded with autoencoders (AEs) to propose a network that can handle both issues. Two variations of the network have been proposed. To further explore the overlapping boundaries of ML data, the second contribution increases the separability of the complex decision space and also incorporates dimensionality reduction. Functional link artificial neural network (FLANN) has been adopted here for the unique functional expansion capability that transforms the features to a higher dimension thus making it considerably more separable. After identifying the best configuration of the network, it has then been integrated with autoencoders to reduce the functionally expanded feature dimension and bring additional transformation into the multi-label data. While these classifiers display improved performance, they do not consider the problems of class imbalance or label correlation. Hence, the third work builds a tree of classifiers that handles the problem of class imbalance, simplifies decision space for the ease of learning and preserves label correlations. A novel label-set proximity-based technique has been devised that simplifies boundaries and splits the data while preserving label correlations. Every split is learned by a classifier suited for the balanced or imbalanced data at hand. While handling multiple issues together successfully, this classifier tree model preserves label correlations but does not explicitly use them to improve classification performance. In this regard, the final contribution specifically extracts underlying label correlations from the data and associates them with predictions of existing multi-label classifiers to improve the overall performance. A novel frequent label-set mining technique generates rules that help to improve scores predicted by the existing multi-label algorithms. This thesis incorporates various elements to handle the problems of multi-label data and converges them to create cohesive models for multi-label classification.
Advanced Techniques in Symmetric Key Cryptanalysis
(Indian Statistical Institute, Kolkata, 2024-07) Chakraborty, Debasmita
Symmetric key cryptographic primitives are essential tools used extensively in daily digital interactions. These primitives are mainly designed to provide three key services: ensuring data confidentiality, maintaining data integrity, and verifying the authenticity of data sources. The primary types of symmetric key primitives that deliver these services include block ciphers, stream ciphers, hash functions, message authentication codes, and authenticated encryption with associated data. This thesis mainly explores the security analysis of hash functions, several block ciphers, and stream ciphers using some advanced cryptanalytic techniques. We begin by examining the collision security of a hash function, specifically under the assumption that the underlying compression functions are collision-resistant. This characteristic is termed the collision-resistance preserving property of a hash function. Notably, both the Merkle-Damgård and Merkle tree hash structures exhibit this property, prompting the question of whether it is possible to reduce the number of underlying compression function calls while maintaining the collision-resistance preserving property. In pursuit of this question, we prove that for an ℓn-to-sn-bit collision-preserving hash function, designed using r tn-to-n-bit compression function calls, it must hold that r ≥ ⌈(ℓ − s)/(t − 1)⌉, assuming all operations other than the compression function are linear. Shifting our focus, we delve into advanced techniques for enhanced cryptanalysis of block and stream ciphers. Initially, we concentrate on the impossible differential (ID) and zero correlation (ZC) attacks, which are pivotal cryptanalytic methods for block ciphers. We introduce an advanced, unified constraint programming (CP) approach based on satisfiability for identifying ID distinguishers in ARX and AndRX ciphers alongside a similar method for identifying ZC distinguishers. Furthermore, we extend our novel model to formulate a unified optimization problem that incorporates the distinguisher and key recovery for AndRX designs. Our approach not only enhances ID attacks but also unveils new distinguishers for various ciphers, including SIMON, SPECK, Simeck, ChaCha, Chaskey, LEA, and SipHash. Another significant cryptanalytic technique, particularly applicable to the analysis of block and stream ciphers, is the division property—an advanced version of integral cryptanalysis. Here, we explore the feasibility of the MILP method for the bit-based division property using three subsets (BDPT) propagation in ciphers with complex linear layers. We apply our novel method to discover integral distinguishers based on BDPT for the SIMON, SIMON(102), PRINCE, MANTIS, PRIDE, and KLEIN block ciphers. The integral distinguishers identified by our method are superior to or consistent with the longest existing distinguishers. Finally, we investigate the cube attack, a powerful cryptanalytic technique against stream ciphers. We study the NIST lightweight 3rd round candidate Grain-128AEAD through the lens of division property-based cube attacks. Initially, we introduce some effective cubes and construct an algorithm to identify conditional key bits for these cubes in Grain-128AEAD. Subsequently, we employ the three-subset division property without unknown subsets based cube attacks to recover exact superpolies for Grain-128AEAD in the weak-key setting, yielding improved results.
Agricultural tenancy in palanpur
(Indian Statistical Institute,Delhi, 1992) Sharma, Naresh Kumar
Agriculture trade and protectionism
(Indian Statistical Institute, Kolkata, 2013-07) Basu, Debasmita
Alfsen-errors structure topology in the theory of complex L1-preduals
(Indian Statistical Institute, Kolkata, 1981) Rao, T S S R K
Algorithms and Applications in Complex Network Representation, Classification and Manipulation
(Indian Statistical Institute, Kolkata, 2024-07) Chowdhury, Anjan
A complex network is a useful model for many real-world systems. Recently, much effort has been put into studying the insights of the complex network. This thesis is all about the study of complex networks. Based on the study, this thesis can be broadly divided into three parts: The first one involves analysing a complex network to find a crucial network structure called constant community by extracting and applying some features called graph representations. The second part involves the study of the quality of the graph representations on a downstream task, i.e., the node classification task. In the third part, we tried to apply the handcrafted and automatically learned graph features to some real-world scenarios, i.e., in brain networks. While detecting the constant community, we developed two strategies to construct and use the graph representations: semi-supervised and unsupervised. In the semi-supervised approach, we converted the original graph to its corresponding line graph, where a node in the line graph represents an edge in the original graph. We then applied a graph neural network (GNN) as a graph representation learning tool to classify the nodes in the line graph, which in turn was used to capture the constant communities in the original graph. In the unsupervised approach, using some hand-crafted features for each edge in the original network, we developed some novel algorithms inspired by image threshold algorithms to filter out the non-constant community edges and hence find the constant communities. In the semi-supervised approach, we noticed that when we reduced the number of training nodes, the representational capability of GNN decreased, and as a result, the classification accuracy of GNN drastically dropped. This phenomenon led us to develop input and output intervention methods to improve the accuracy of the GNN. In the input intervention, we extend the training nodes’ set using random walk and some machine learning methods to agnostically capture similar nodes from various non-contiguous sub-networks in a whole network. In the output intervention, we used random walk methods to correctly relabel the possibly misclassified nodes by the GNN as its output. The last part of the thesis deals with applications of network representation, classification, and finally manipulation in dealing with complex human brain networks. The brain regions and their interrelationships can be modelled using complex network. Utilising the complex network and its representation, in this part we contributed to neuroscience in two ways: first, we devised a methodology to diagnose a neurodevelopmental disease called Attention Deficit Hyperactivity Disorder (ADHD) using some extracted network features and applied them to various deep learning-based models. Then in the second work, we built a probabilistic model using anatomical and topological similarities to generate synthetic brain networks and track down the progression of a neurodegenerative disease called Alzheimer’s disease (AD) in human brains. The results are promising enough to establish the use of complex network analysis in computational neurology
Algorithms for Feature Selection
(Indian Statistical Institute, Kolkata, 2022-12) Lall, Snehalika
With the advancement of science and technology, data has increased both in sam- ple size and dimension. Examples of high-dimensional data include genomic data, text data, image retrieval, bioinformatics, etc. One of the major problems in handling such data is that all the features are not equally important. Hence, fea- ture engineering, feature selection and feature reduction are considered important pre-processing tasks to discard redundant, irrelevant features while preserving the prominent features of the data as much as possible. Feature selection, in practice, often improves the accuracy of down-stream machine learning problems, including clustering and classification. In this thesis, we aim to devise some novel and robust feature selection mecha- nisms in diverse domains of applications with a special focus on high dimensional biological data such as gene expression and single cell transcriptomic data. We develop a series of feature selection techniques equipped with structure-aware data sampling at its core. We adopt several concepts from statistics (e.g. copula and its variant), information theory (entropy), and advanced machine learning domain (variational graph autoencoder, generative adversarial network, and its variant) to design the feature selection models for high dimensional and noisy data. The proposed models perform extremely well both in supervised and unsu- pervised cases, even if the sample size is very low. Important outcomes from all the proposed methods are discussed in chapters. Moreover, an overall discussion about the applicability along with a brief mention of the shortcomings of all the discussed methods is provided. Some suggestions and guidance are provided to overcome the disadvantages which direct the future scope of improvement of all the devised methods.
Algorithms for some geometric facility location and path planning problems
(Indian Statistical Institute, Kolkata, 2007-06) Roy, Sasanka
Analysis and Design of Quantum Secure Communication System
(Indian Statistical Institute, Kolkata, 2022-08) Das, Nayana
Quantum secure direct communication (QSDC) is an important branch of quantum cryptog- raphy, where one can transmit a secret message securely without encrypting it by a prior key. Quantum dialogue (QD) is a process of two way secure and simultaneous communication using a single channel and quantum conference (Q.Conf) is a process of securely exchanging messages between three or more parties, using quantum resources. Deterministic secure quan- tum communication (DSQC) is another class of quantum secure communication protocol, to transmit secret message without any shared key, where at-least one classical bit is required to decrypt the secret message. In the practical scenario, an adversary can apply detector-side- channel attacks to get some non-negligible amount of information about the secret message. Measurement-device-independent (MDI) quantum protocols can remove this kind of detector- side-channel attack, by introducing an untrusted third party (UTP), who performs all the measurements in the protocol with imperfect measurement devices. For secure communica- tion, identity authentication is always important as it prevents an eavesdropper to impersonate a legitimate party. The celebrated Clauser, Horne, Shimony, and Holt (CHSH) game model helps to perform the security analysis of many two-player quantum protocols. In this thesis, we perform analysis of several existing QSDC and QD protocols, and also design some new efficient protocols. We present new approaches of QSDC, QD and DSQC protocols with user authentication, some of them are MDI protocols. We analyze the security of a QSDC protocol, an MDI-QSDC protocol, and an MDI-QD protocol. We improve the previous protocols and propose some modifications of the above protocols. We also present a Q.Conf protocol by generalizing the previous MDI-QD protocol and using the algorithm of the Q.Conf protocol, we propose a quantum multi-party computation protocol to calculate the XOR value of multiple secret numbers. Next, we generalize the CHSH game, and we demonstrate how to distinguish between dimensions two and three for some special form of maximally entangled states using the generalized version of the CHSH game.
Analysis of a few Quantum Algorithms and Circuits related to Boolean Functions
(Indian Statistical Institute, Kolkata, 2026-01-15) Dutta, Suman
Boolean functions are fundamental to computation and presently play a crucial role in quantum information processing. This thesis presents two facets of Boolean functions in the context of quantum computing: (I) extending and applying the theoretical framework of Forrelation to cryptographic analysis, and (II) designing efficient quantum circuits for multi-controlled Toffoli gates and Boolean circuit implementations. Given two Boolean functions $f$ and $g$, Forrelation, introduced by Aaronson (2010), measures the correlation between the truth table of $f$ and the Walsh-Hadamard transform of $g$ at the corresponding points. Here, we revisit the Forrelation framework to study several cryptographically significant spectra of Boolean functions, namely, the Walsh-Hadamard, the crosscorrelation, and the autocorrelation spectra. We begin with adapting the 3-fold Forrelation formulation to sample the Walsh transform values, achieving a constant-factor improvement in query complexity over the Deutsch-Jozsa algorithm. This has direct applications in resiliency checking. Building on this, we propose a technique to estimate the crosscorrelation (and thereby the autocorrelation) at any desired point. Furthermore, we present, to the best of our knowledge, the first constant-query algorithm for sampling from the complete spectrum of crosscorrelation (and consequently, autocorrelation) using Forrelation. Next, we introduce nega-Forrelation, a variant based on the nega-Hadamard transform, and develop efficient quantum algorithms to estimate and sample from the nega-Hadamard and nega-crosscorrelation spectra. We further connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it to the case of negabent functions. Later, we generalize these cryptographic spectra and the Forrelation formulations for any natural number $m$, identifying the Forrelation and nega-Forrelation as special cases, and propose quantum algorithms towards their estimation. In a related direction, we focus on the efficient implementation of multi-controlled Toffoli (MCT) gates, specifically optimizing the T depth, which is a crucial parameter for reducing circuit latency on near-term quantum devices with limited coherence times. We present an explicit trade-off between the Toffoli depth and the number of clean ancilla qubits, extending the conditionally clean ancilla technique. Further, we prove that the T depth in the Clifford+T decomposition of an $n$-MCT gate, via Toffoli, is lower bounded by $\lceil \log_2 n \rceil$, achieved through a complete binary tree structure. Later, we generalize the result to show that any arbitrary $n$-input, $m$-output Boolean function (specified by its Algebraic Normal Form) can be implemented with a quantum circuit having optimal T depth $\lceil \log_2 k \rceil$, where $k$ represents the algebraic degree of the function, which is upper bounded by the number of input variables $n$. This result has significant implications in S-box design and quantum implementations of block ciphers, such as AES.
Analysis of poverty in rural West Bengal : a spatial approach
(Indian Statistical Institute, Kolkata, 2010-12) Chattopadhyay, Somnath
An analysis of spatial patterns and growth of Indian agricultural activities
(Indian Statistical Institute,Calcutta, 1988) Mukhopadhyay, Rabindranath
Application of combinatorial structures in wireless communication
(Indian Statistical Institute, Kolkata, 2015-01) Bag, Samiran
Application of combinatorial structures to key predistribution in sensor networks and traitor tracing
(Indian Statistical Institute,Calcutta, 2009-02) Ruj, Sushmita
Applications of combinatorial designs in Key pre-distribution in sensor networks
(Indian Statistical Institute, Kolkata, 2007-09) Chakrabarti, Dibyendu
Applications of Exponential Maps to Epimorphism and Cancellation Problems
(Indian Statistical Institute, Kolkata, 2023) Ghosh, Parnashree
Throughout this talk k will denote a field. The talk is primarily divided into two parts. In the first part we will discuss one of the formidable open problems in the area of Affine Algebraic Geometry, called the Epimorphism Problem. Question 1. If k[X1,...,Xn] (H) = k[n−1], then is k[X1, . . . , Xn] = k[H][n−1]? For n = 2, the answer to above question is affirmative when k is a field of characteristic zero. This result is known as the Epimorphism Theorem proved by Abhyankar-Moh and independently by Suzuki. However, in positive characteristic there are counter examples due to Segre-Nagata. The famous Abhyankar-Sathaye conjecture asserts affirmative answer to Question 1 for n ⩾ 3 over fields of char- acteristic zero. So far we only have partial answers to this conjecture. The first affirmative result for n = 3 is due to Sathaye for linear planes over fields of char- acteristic zero. Later, Russell extended this result over fields of arbitrary character- istic. In this talk we consider the following varieties. Let m a positive integer, V an affine subvariety of Am+3 defined by a linear relation of the form xr1 1 · · · xrm m y = F (x1, . . . , xm, z, t), A the coordinate ring of V and G = Xr1 1 · · · Xrm m Y −F (X1, . . . , Xm, Z, T ). We name these varieties as “Generalised Asanuma varieties”. Earlier, Gupta had studied the case m = 1, and had obtained several necessary and sufficient con- ditions for V to be isomorphic to the affine 3-space and G to be a coordinate in k[X1, Y, Z, T ]. We study the general higher-dimensional variety V for each m ⩾ 1 and obtain analogous conditions for V to be isomorphic to Am+2 and G to be a coordinate in k[X1, . . . , Xm, Y, Z, T ], under a certain hypothesis on F . Our main theorem immediately yields a family of higher-dimensional linear hyperplanes for which the Abhyankar-Sathaye Conjecture holds. We also describe the isomorphism classes and automorphisms of integral do- mains of the type A under certain conditions. These results show that for each d ⩾ 3, there is a family of infinitely many pairwise non-isomorphic rings which are counterexamples to the Zariski Cancellation Problem for dimension d in positive characteristic. We further give complete description of two important invariants called Makar- Limanov and Derksen invariants of a certain subfamily of Generalised Asanuma varieties. In the second part of this talk we discuss about another major problem called the Cancellation Problem which investigates the following: Question 2. Let D and E be two affine domains over a field k such that D[1] =k E[1]. Does this imply D ∼=k E? The answer to Question 2 is affirmative for one dimensional affine domains. This result is due to Abhyankar, Eakin and Heinzer. However, there are coun- terexamples in dimensions greater than or equal to two. Danielewski constructed 1 a family of two dimensional pairwise non-isomorphic smooth complex varieties which are counterexamples to the Cancellation Problem. A. J. Crachiola further extended Danielewski’s examples over arbitrary characteristic. Dubouloz con- structed higher dimensional (⩾ 2) analogues of the Danielewski varieties over the field of complex numbers, which are counterexamples to this problem. Over fields of arbitrary characteristic, we establish an infinite family of a higher dimensional varieties which are pairwise non-isomorphic and are counter examples to the Can- cellation Problem. Moreover, this family accommodates the counter examples due to Dubouloz over C.
Applications of the calculus for factorial arrangements and allied topics
(Indian Statistical Institute, Kolkata, 1988-03) Bose, Mausumi