Blog

authored by Premmi and Beguène Previous Topic: An Axiomatic Study of Natural Numbers – Peano’s Axioms Introduction Building upon the foundational principles of Peano’s Axioms, we now turn our attention to a critical tool in number theory: proof by induction. How can we rigorously establish that a property holds true for all natural numbers? The answer… Read more: Number Theory Primer : Proving Properties of Natural Numbers Using Proof by Induction

authored by Premmi and Beguène Previous Topic: An Axiomatic Study of Numbers Introduction Thinking of numbers intuitively brings to mind the simplest and most fundamental set of numbers, namely the set of natural numbers. These are the numbers we first encounter when learning to count discrete objects like cars, books, pens, etc. If we associate natural… Read more: Number Theory Primer : An Axiomatic Study Of Natural Numbers – Peano’s Axioms

authored by Premmi and Beguène We will now briefly discuss the terms formula and free variables that we encountered during our discussion of the substitution axiom which is one of the two Axioms of Equality. We can think of language as being comprised of a set of symbols or letters called the alphabet of the language,… Read more: Formulas and Free Variables

authored by Premmi and Beguène Introduction In mathematics, the relation “equals” is a foundational concept that can be applied to any two mathematical objects to indicate that these objects represent the same mathematical entity. Since the concept of equality pertains to all mathematical objects, it is universal across mathematics and transcends its specific branches, situating itself… Read more: Equality

authored by Premmi and Beguène Introduction Number theory involves an extensive study of the properties of integers. Before embarking on this study, it is only natural to ask the question: “What is a number?” since integers are just one type of number. Intuitively, we often associate numbers with counting objects like books and pencils or measuring… Read more: Number Theory Primer : An Axiomatic Study Of Numbers

authored by Premmi and Beguène Previous Topic: The Euclidean Algorithm Introduction A Diophantine equation is any equation in one or more unknowns that is to be solved in the integers. The simplest type of Diophantine equation that we shall consider is the linear Diophantine equation in two unknowns: where are given integers and are not both zero.… Read more: Number Theory Primer : The Diophantine Equation ax + by = c

authored by Premmi and Beguène Previous Topic : The Greatest Common Divisor Introduction We have already seen a situation that necessitated the calculation of the greatest common divisor of two integers. We calculated the greatest common divisor of the two integers by listing all their positive divisors and choosing the largest one common to each. This method of… Read more: Number Theory Primer : The Euclidean Algorithm

authored by Premmi and Beguène Previous Topic : The Division Algorithm It is worthwhile to study in detail the case wherein the remainder in the Division Algorithm turns out to be zero. Such a study leads to some very interesting insights that form the cornerstone of number theory. Divisibility of Integers Definition An integer is said… Read more: Number Theory Primer : The Greatest Common Divisor

authored by Premmi and Beguène Previous Topic : Well-Ordering Principle Division Algorithm The Division Algorithm establishes a relationship between two integers by asserting that an integer can be divided by a positive integer in such a way that the remainder is lesser than . The usefulness of the Division Algorithm lies in its ability to allow… Read more: Number Theory Primer : The Division Algorithm

authored by Premmi and Beguène Well-Ordering Principle Every nonempty set of nonnegative integers contains a least element, i.e., there is some integer in such that for all belonging to . Since we cannot prove the well-ordering principle by using properties that the nonnegative integers satisfy under the operations of addition and multiplication, we will consider the… Read more: Number Theory Primer : Well-Ordering Principle

authored by Premmi and Beguène We will briefly discuss some topics from set theory which we will encounter during our study of number theory and cryptography. Mathematical Object A mathematical object is an abstract entity, precisely defined, often in terms of other mathematical objects, and ultimately grounded in a set of axioms—fundamental assumptions that are taken… Read more: Set Theory Primer

authored by Premmi and Beguène A cipher defines the mechanism through which a message is transformed into a ciphertext using a key such that only the entities sharing this key could use it to decrypt the ciphertext and recover the message. A cipher, , comprises of a pair of functions, namely, the encryption and decryption functions.… Read more: Definition of Cipher

authored by Premmi and Beguène Prerequisite : Probability Primer Follow up to : What is Security? Now that we have defined a secrecy system and discussed how to evaluate it, let us construct one based on the first and most important criterion, namely, a secrecy system that optimizes for secrecy i.e., a system that provides maximum… Read more: Perfect Secrecy

authored by Premmi and Beguène Related to : Semantic Security implies Message Recovery Security We will answer this question using the proof by counterexample method. We will construct a cipher that is secure against message recovery but is not semantically secure. Let be a semantically secure cipher defined over , where and . We will construct… Read more: Does security against  message recovery imply  semantic security?

authored by Premmi and Beguène A cipher that is semantically secure is also secure against message recovery. Prerequisites : Probability Primer, Attack Games In Cryptography, Proof Techniques in Cryptography Theorem Let be a cipher defined over . If is semantically secure then is secure against message recovery. Intuitively, this theorem means that if an efficient adversary… Read more: Security Proof : Semantic Security implies Message Recovery Security

authored by Premmi and Beguène Prerequisite : Logic Primer We prove that a cryptographic construct is secure under certain assumptions using mathematical proofs called security proofs. Following is a list of various techniques used in constructing such proofs. Proving Conditional Statements Oftentimes, security proofs in cryptography involve proving the truth of some conditional statement. We will… Read more: Proof Techniques in Cryptography

Propositional Logic or Zero-Order Logic authored by Premmi and Beguène This is a work in progress. Introduction Cryptography involves the design of systems called cryptosystems that possess one or more security properties. For example, a cryptosystem might be designed to enable entities to communicate in such a way that, even if an eavesdropper intercepts their communication,… Read more: Logic Primer

authored by Premmi and Beguène Introduction We prove the security of a cryptographic construct for some specific notion of security through adversarial games played between an entity, called the challenger, that uses the cryptographic construct to produce an output and another entity called the adversary, that uses this output to break the specific notion of… Read more: Attack Games in Cryptography

Knowing to count is an integral part of having a good grasp of probability. And being comfortable in probability is a sine qua non for understanding cryptography. Aside from making sense of cryptography, learning to count is really fun 😃. In this primer we will learn to count starting from “scratch” i.e., we will start… Read more: Counting Primer

Secrecy Systems authored by Premmi and Beguène Introduction Alice, a celebrated American actor, finds herself hounded by the paparazzi on every public appearance. Craving a respite, she plans a discreet Parisian sojourn, yet longs for the companionship of her friend Bob, who resides in Rome. Alice must find a way to tell Bob to meet her… Read more: What is Security ?

authored by Premmi and Beguène Summary of results with respect to Total Variation Distance You can read Part 1 of the story here and Part 2 here. For proofs of all results enumerated in this post refer to Part 3. Total Variation Distance In probability theory, the total variation distance is a distance measure for… Read more: Distinguishing in a Probabilistic World-Part 4

authored by Premmi and Beguène Total Variation Distance, Distinguishing Advantage & Distinguishing Distance Mathematical Treatment of Total Variation Distance You can read Part 1 of the story here and Part 2 here. Introduction In probability theory, the total variation distance is a distance measure for probability distributions. It is also called statistical distance, statistical difference… Read more: Distinguishing in a Probabilistic World-Part 3

authored by Premmi and Beguène By definition, For a deep intuitive understanding of advantage refer to this and this. Why is the advantage an absolute value? It suggests that even when the adversary loses more than it wins, it has an advantage. Why is this so? Let us consider the following example to answer these questions. Suppose we have a… Read more: Why is Advantage An Absolute Value ?

authored by Premmi and Beguène In Simple Settings Annie is on her summer vacation and she decides to take a break from reading. Her neighbor Marie is her nemesis and so Annie devises a game to outsmart her. Annie has two bears, one blue and the other yellow. Annie’s game is as follows: She devises… Read more: Advantage Calculation

An Intuitive Example Let us return to the story of John and his identical twin sisters Ann and Kelly. John has kg of gold which he would like to divide between his two sisters. We will consider two possible scenarios. In one, John loves both his sisters equally and hence is unbiased towards them; in… Read more: Bias and Advantage

The Story of Total Variation Distance. You can read Part 1 of the story here. Ann’s hedge fund decides to invest in movies and Ann has to move to Los Angeles for 6 months to meet with Hollywood production houses and make deals. Meanwhile Kelly is growing immensely successful as a fashion influencer and has… Read more: Distinguishing in a Probabilistic World-Part 2

authored by Premmi The Story of Total Variation Distance. Part 1 Introduction Before we dive into cryptography, we need to understand the concept of distance as a way to distinguish between entities. In the first part, we will explore how we can use distance to differentiate between entities in a deterministic world. In the next… Read more: Distinguishing in a Probabilistic World

authored by Premmi and Beguène This is a refresher on some basic concepts in probability theory which are often encountered while studying cryptography. We have deliberately tried to keep the discussion simple and hence will not be discussing Sigma Algebra, measurable space, probability measure etc. Introduction Since cryptography is about building secure systems, we need… Read more: Probability Primer