Dissertation and Thesis
Permanent URI for this communityhttp://164.52.219.250:4000/handle/10263/2146
Browse
7 results
Search Results
Item A Few Selected Topics on Boolean Functions(Indian Statistical Institute, Kolkata, 2024) Roy, AnimeshIn this thesis, we use the techniques of Boolean functions in di erent applications. More speci cally, our focus is on the properties of Boolean functions that hold cryptographic signi cance. The employed techniques primarily revolve around combinatorial methods, yielding fresh insights into the enumeration and construction of such functions. Initially, our e ort is on exploring functions generated through an Arbiter-based Physically Unclonable Function (PUF) construction with random delay parameters. We observe that, under speci c constraints on input weights, such a straightforward model of Arbiter PUFs yields favourable cryptographic parameters in terms of di erential analysis. In this context, we theoretically address the autocorrelation properties issue within a restricted space of input variables with xed weights. While investigating this aspect independently, we have concentrated on the connection between Arbiter PUFs and Threshold functions. Subsequently, we delve into the study of the combination of such Arbiter-based PUFs, speci cally examining the scenario involving the XOR operation of two devices with arbitrary inputs of equal length. Based upon extensive computations, we identify several interesting properties. Beyond addressing the counting problem, we also derive the general formula to calculate the probability of the occurrence of identical outputs from a combiner model PUF corresponding to two distinct challenge inputs. We further note that the collection of Boolean functions produced by Priority Arbiter PUF (PA-PUF) is larger than the set of Boolean functions generated by the traditional Arbiter-based PUFs. Lastly, we investigate the bias estimation of the response bit generated by PA-PUF concerning the in uence of altering speci c bits in the challenge input. Next, we assess whether a seemingly random stream exhibits any underlying nonrandom patterns. In this context, we highlight speci c constraints of the BoolTest strategy proposed by S ys et al (2017) and introduce combinatorial ndings related to the identi cation of optimal Boolean functions in this regard. Our results identify the most e ective Boolean function in this context, one that yields the maximum Z-score. Subsequently, we conducted a thorough examination of all Boolean functions involving four variables to formulate binary input-binary output two-party nonlocal games and assess their e cacy in both classical and quantum contexts. Our investigation identi es certain games other than the CHSH game (which is naturally the provably best example) that exhibit a better (may be sub-optimal compared to the best case) success probability in quantum scenarios compared to classical scenarios. Additionally, we extend the framework of the classical strategies to encompass other n-party nonlocal games.Item Effects of symmetry in combinatorial complexity measures of Boolean functions(Indian Statistical Institute, Kolkata, 2024-05) Kayal, ChandrimaBoolean functions are one of the central objects in the study of Computer Science. Any decision problem can be expressed as a Boolean function that takes an $n$-bit string as input and gives a single-bit output. Its versatility in capturing various problems in a simple form makes it crucial to understand the different properties of Boolean functions. There are various aspects to understanding Boolean functions. In this thesis, we will be focusing on the study of Boolean functions using the query complexity model. Various complexity measures are motivated and generated from the query complexity world, for example, Deterministic query complexity, Randomized query complexity, Quantum query complexity, sensitivity, block sensitivity, and many more. Investigating the interplay among these measures has been an active area of research in computational complexity theory for over three decades, with implications reaching across different areas of theoretical computer science. Exploring specialized classes of Boolean functions enhances our understanding of their inherent complexities. Analyzing complexity measures within specific function classes illuminates broader patterns and aids in identifying critical properties essential for general study. Among these classes, those characterized by complete symmetry have gotten significant attention for their widespread applicability across diverse domains. Symmetry, as a defining property, influences the behavior of Boolean functions. While 'Symmetric Boolean functions' that is the Boolean functions that are invariant under any permutation of the input string, have undergone extensive study and are nearly well understood, functions exhibiting partial symmetry remain less understood. Our investigation navigates through the landscape of partial symmetry, focusing on the following: 1. UNDERSTANDING THE IMPACT OF PARTIAL SYMMETRY ON COMBINATORIAL MEASURES: Examining the relationship between various combinatorial measures and their behavior under partial symmetry. Precisely, we prove separation results for the classes of transitive functions. 2. EXPLORING COMPLEXITY MEASURES UNDER FUNCTION COMPOSITION: In particular, two big open problems in this area are that it is not known how randomized query complexity and approximate degree behave under composition. We made some progress towards the main open problems as well, and we have proved the composition theorem for both the complexity measures for the functions with partial symmetry.Item Boolean Function Approximation by a Flat Polynomial(Indian Statistical Institute, Kolkata., 2021-07) Gupta, AnkitBoolean functions f : {−1, 1} n → {−1, 1} arise in many areas of theoretical computer science and mathematics, for example: complexity theory, quantum computing and graph theory etc and Fourier analysis is a powerful technique used to analyze problems in these areas. One of the most important and longstanding open problems in this field is the Fourier Entropy-Influence (FEI) conjecture [EG96], first formulated by Ehud Friedgut and Gil Kalai; The FEI conjecture connects two fundamental properties of boolean function f, i.e. influence and entropy. FEI conjecture says, for all boolean functions f : {−1, 1} n → {−1, 1}, H[ ˆf 2 ] ≤ CI[f] where H[ ˆf 2 ] is the spectral entropy of f and if we fix = 1 3 and consider polynomials p such that |p(x) − f(x)| ≤ 1 3 where f is boolean function then these polynomials have many applications in theoretical computer science. In particular, this work attempts to address the following problem: Suppose, the FEI conjecture is true, what can be said about the approximating polynomials. We have a flat polynomial of degree d and sparsity 2 ω(d) . The proposed conjecture [SSM+20] says that No flat polynomial of degree d and sparsity 2 ω(d) can 1 3− approximate a boolean function.[The degree of a function is the maximum d such that ˆf(S) 6= 0 for some set S of size d]. It is useful to understand better the structure of polynomials that −approximate Boolean functions on the Boolean cube. Such polynomials have proved to be powerful and found diverse applications in theoretical computer science. Here, we restrict ourselves to a class of polynomials called flat polynomials over {−1, 1}, i.e., polynomials whose non-zero coefficients have the same magnitude. This conjecture is true by assuming FEI conjecture and it is also true for a class of polynomials without assuming FEI conjecture.Item Enumeration of correlation immune boolean functions(Indian Statistical Institute, Kolkata, 2001) Sharma, KaushikItem Boolean functions with important cryptographic properties(Indian Statistical Institute, Kolkata, 2000) Subhamoy, MaitraItem Cryptographic and combinatorial properties of boolean functions and s-boxes(Indian Statistical Institute,Calcutta, 2004) Gupta, Kishan ChandItem Some necessary conditions of boolean functions to resist algebraic attacks(Indian Statistical Institute, 2006-08) Dalai, Deepak Kumar