Online Public Access Catalogue (OPAC)
Library,Documentation and Information Science Division

“A research journal serves that narrow

borderland which separates the known from the unknown”

-P.C.Mahalanobis


Image from Google Jackets

A Few Selected Topics on Boolean Functions/ Animesh Roy

By: Material type: TextTextPublication details: Kolkata: Indian Statistical Institute, 2024Description: 202 pagesSubject(s): DDC classification:
  • 23rd 511.324 R888
Online resources:
Contents:
Introduction -- Background -- How do the Arbiter PUFs Sample the Boolean Function Class? -- On Combining Arbiter-based PUFs -- Priority Arbiter PUF: Analysis -- Revisiting BoolTest { On Randomness testing using Boolean functions -- Analysis of Boolean Functions Related to Two-party Nonlocal Games -- Conclusion
Production credits:
  • Guided by Prof. Subhamoy Maitra
Dissertation note: Thesis (Ph.D) - Indian Statistical Institute, 2024 Summary: In 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.
Tags from this library: No tags from this library for this title. Log in to add tags.

Thesis (Ph.D) - Indian Statistical Institute, 2024

Includes bibliography

Introduction -- Background -- How do the Arbiter PUFs Sample the Boolean Function Class? -- On Combining Arbiter-based PUFs -- Priority Arbiter PUF: Analysis -- Revisiting BoolTest { On Randomness testing using Boolean functions -- Analysis of Boolean Functions Related to Two-party Nonlocal Games -- Conclusion

Guided by Prof. Subhamoy Maitra

In 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.

There are no comments on this title.

to post a comment.
Library, Documentation and Information Science Division, Indian Statistical Institute, 203 B T Road, Kolkata 700108, INDIA
Phone no. 91-33-2575 2100, Fax no. 91-33-2578 1412, ksatpathy@isical.ac.in