NAME:MAYANK YADAV

REG. NO20BCE2114

THEORY ASSIGNMENT

CSE3501
INFORMATION SECURITY ANALYSIS AND AUDIT

SLOT:G1

SUBMITTED TO-- SUBMITTED BY--

Prof. SARITHA MURALI MAYANK YADAV
(20BCE2114)
NAME:MAYANK YADAV
REG. NO20BCE2114

QUAD: SYMMETRIC ENCRYPTION ALGORITHM:

1) INTRODUCTION
We are going to discuss about the QUAD encryption algorithm which is a practical stream cipher
with provable security. The deduced intractability of the MQ problem, which is the solution of a
multivariate system of quadratic equations, is demonstrably reducible to the security of the
keystream generation of QUAD.

Before we move on, we will first discuss about some of the terms that are going to be used further
below:

1.1)Stream ciphers

A stream cypher is an encryption method that converts plain text into code that is unintelligible
to anyone without the right key by working byte by byte.

The same key is used to encrypt and decrypt messages with stream cyphers because they are
linear. And although it can be challenging to penetrate them, hackers have succeeded.

Because of this, experts believe stream cyphers are not secure enough for broad use. However,
many individuals continue to rely on technology to transmit information via the internet.
The two primary kinds of stream cyphers function a little bit differently from one another.

Synchronous stream cyphers: Keystreams are created independently of the ciphertext and the
plaintext using a hidden key.
Self-synchronizing stream cyphers: To make hacking more difficult, they use a secret key and an
additional randomization method.

There are other options besides stream cyphers that you can use. Block ciphers could also be
applied. Block cyphers fragment communications, and each fragment goes through an
encryption process.

Real world example of stream cipher:

The effectiveness of stream cyphers has probably already been demonstrated in the past by the
Germans during World War 2. It took years for English experts to decipher the code employed by
German leaders to communicate directives to their troops.

The Germans employed a complex device that resembled a typewriter somewhat. Over the keys,
a row of 26 lights made the transformation obvious. A transformed letter was represented by
one light. They frequently changed the keys, and by pressing a button, the Enigma was updated
to transcribe notes in the new code.

You can experiment with the Enigma with a web-based model (complete with authentic
sounds). On the simulation, tapping the word "HELLO" produced the encoded message "VIC3T"
NAME:MAYANK YADAV
REG. NO20BCE2114

Screenshot of online Enigma model:

1.2)Multivariate Quadratic Problem(MQ)

Multivariate polynomials over a finite field serve as the foundation for asymmetric cryptographic
primitives, which are collectively referred to as multivariate cryptography. These polynomials
may in some circumstances be defined over both a ground and an extension field. Multivariate
quadratics are what we refer to when the polynomials have a degree of two. It has been
established that solving systems of multivariate polynomial equations is NP-complete. Because
of this, those systems are frequently regarded as viable options for post-quantum cryptography.
Design and cryptanalysis of multivariate cryptography have produced a lot of useful results.
Overall, things are more stable now, and the most effective plans have endured the test of time.
Commonly acknowledged, multivariate cryptography proved to be more successful as a method
of creating signature schemes due to the fact that multivariate schemes offer the smallest
signatures aiming the post-quantum algorithms.

1.3)Galois field(GF)
A field with a finite number of elements is referred to as a "Galois field," after Evariste Galois, also
known as a finite field. As binary forms are used to represent computer data, it is especially
helpful in translating those forms. In other words, computer data is a combination of the two
NAME:MAYANK YADAV
REG. NO20BCE2114

numbers 0 and 1, which make up the two elements in a Galois field. Data can be simply and
efficiently scrambled by mathematical operations when it is represented as a vector in a Galois
Field.

1.4) Initialization vector:

An input to a cryptographic primitive that is used to establish the beginning state is known as an
initialization vector (IV) or starting variable (SV). Normally, the IV must be random or
pseudorandom, but on occasion, it merely needs to be unpredictable or distinct. For some
encryption techniques to ensure semantic security—a quality that prevents an attacker from
inferring connections between (perhaps similar) portions of the encrypted message—
randomization is essential. The modes of operation for block cyphers outline how an IV is used.

The cryptographic method utilised affects the properties of an IV. Uniqueness is a fundamental
condition, which states that no IV may be used more than once under the same key. Repeated IV
values for block cyphers force the encryption method into electronic codebook mode, where an
equal IV and an equal plaintext yield an equal ciphertext. Uniqueness is critical in stream cypher
encryption because else plaintext could be easily deciphered.

IV in stream ciphers:

In stream cyphers, IVs are fed into the cipher's keyed internal secret state. Next, a number of
cypher rounds are carried out before the first bit of output is released. Although stream cypher
designers aim to reduce that number of rounds to a minimum for performance reasons, doing so
is not straightforward due to other factors like entropy loss, which is specific to each cypher
construction, related-IVs, and other IV-related attacks, which are a known security risk for
stream cyphers.

Now we can define the QUAD :Encryption Algorithm:

We will now discuss the QUAD stream cypher :

S = (Q1,...,Qkn) denotes a multivariate quadratic system of kn randomly chosen equations in n

variables over GF(q), and S0 and S1 denote two (k times smaller) additional multivariate
systems of n randomly chosen equations in n variables over GF(q). S, S0 and S1 are fixed and
publicly known. During the key and IV loading and the keystream generation, the internal
register state is a x = (x1,...,xn) n-tuple of GF(q) values.

QUAD is a contemporary stream cypher that creates a keystream sequence using a key and an
initialization value (IV). Additionally defined Key and IV configuration also dependent on the
multivariate quadrate system.
NAME:MAYANK YADAV
REG. NO20BCE2114

2) WORKING OF THE ALGORITHM

The QUAD Encryption algorithm works in two parts which are described below:

2.1) Keystream Generation and Encryption

The keystream generation process simply consists in iterating the three following steps in order
to produce (k − 1)n GF(q) keystream values at each iteration.

– Compute the kn-tuple of GF(q) values S(x)=(Q1(x),...,Qkn(x)) where x is the current value of the
internal state;

– Output the sequence Sout(x)=(Qn+1(x),...,Qkn(x)) of (k − 1)n GF(q) keystream values

– Update the internal state x with the sequence of n GF(q) first generated values
Sit(x)=(Q1(x),...,Qn(x))

2.2) Key and IV Setup

The key K and the initialization vector IV, which are respectively represented by a sequence of
GF(q) elements of length |K| and a binary sequence of 0, 1 values of length |IV|, must be used to
initialise the internal state x before creating any keystream. For the time being, we'll make the
simplifying assumption that |K| is arbitrarily chosen to be precisely equal to n.

INITIALISATION:

 We select two arbitrarily selected multivariate quadratic systems, S0 and S1, each
consisting of n equations with n unknowns.
 The internal state variable x was first set to the n-bit value K.
 The internal state x is then updated as follows for each of the |IV | bits IV1 to IV|IV | of
the IV value: If IVi = 0, the GF(q)n value S0(x) is substituted for x; if |V| = 1, the GF(q)n
value S1 is substituted for x. (x).
 A key and IV reliant internal state value x is provided by these |IV | steps.
 In order to further change the internal state value x, we clock the cypher |IV| a further
number of times as previously explained, but without outputting the keystream. Next, we
switch to the keystream creation mode to create the keystream
NAME:MAYANK YADAV
REG. NO20BCE2114

3) APPLICATION OF THE QUAD ALGORITHM (REAL WORLD USAGE)

3.1) Defending against algebraic assaults:

QUAD was created to withstand algebraic attack methods. QUAD's key and IV loading and
keystream generating procedures are actually based on the iteration of quadratic systems
with corresponding equations that are hypothesised to be computationally intractable .
Specifically, returning the system to its initial condition x.
It is more challenging to retrieve a keystream generator from the entire keystream.
Such that solving a difficult quadratic system of kn equations to derive x from S(x)

3.2 Distinguishing attacks and correlation attacks:

With the exception of incredibly unlikely degenerate instances of the quadratic system S,
such as when one of the n-bit to 1-bit quadratic forms of S out or a linear combination of
these (k 1)n quadratic forms has an incredibly low rank and consequently (for even values
of n) a detectable bias, we expect QUAD to be immune to such attacks.

3.3 Resynchronization Attack Resistance Using Selected IVs:

Only the keystream generation is covered by our evidence; the Key and IV setup is not.
However, they do not offer assurances regarding the independence of the sequences
resulting from multiple chosen IVs or the resistance of QUAD against resynchronization
attacks. Instead, they provide a compelling argument against the conjecture that the
keystream sequence resulting from any single known or chosen IV value cannot be
distinguished from a random sequence.

3.4) Dual Ciphers:

Because of the structure of the QUAD equations, it is easy to find dual ciphers of QUAD,
i.e. simple (e.g. linear) transformations f and g of the key K and the keystream as to ensure
that for each triplet of quadratic systems (S, S0, S1) there exist quadratic systems (S , S 0, S
1) such that for any key K and any IV value IV , the keystream associated with (f(K), IV, S , S
0, S 1) is the image by g of the keystream associated with (f(K), IV, S, S0, S1). We do not
expect this property to represent a security threat for QUAD.
NAME:MAYANK YADAV
REG. NO20BCE2114

4) CONCLUSION

Software or hardware implementation of QUAD fundamentally involves computing a

set of quadratic functions in n variables over GF (q). This is true for the key and IV
setup, runup, and keystream generation phases of QUAD. The fundamental
distinction between the two phases is the number of quadratic functions that must
be computed at each iteration, which is n for the key and IV setup and m > n for the
runup and keystream creation.

At first look, it could appear that QUAD is not well suited for hardware
implementations since managing a sizable random system of quadratic polynomials
in hardware is problematic. However, if one chooses to use a straightforward non-
linear number generator to pseudo-randomly generate the fixed multivariate
quadratic function S iterated by QUAD rather than randomly generate S, this yields
unexpectedly good hardware performance:
 NAME:MAYANK YADAV
REG. NO20BCE2114

5) REFERENCES

1) Galois fields:https://sites.math.washington.edu/~morrow/336_12/papers/juan.pdf

2) Stream cipher:https://www.okta.com/identity-101/stream-cipher/

3) Multivariate cryptography:https://en.wikipedia.org/wiki/Multivariate_cryptography

4) Post-quantum cryptography:https://en.wikipedia.org/wiki/Post-quantum_cryptography

5) QUAD ENCRYPTION ALGORITHM:

5.3) https://iacr.org/archive/eurocrypt2006/40040110/40040110.pdf

5.4) https://en.wikipedia.org/wiki/QUAD_(cipher)

Ref Journal and Paper name Research paper link Objective

. publication
No

1 Journal of symbolic QUAD: A https://core.ac.uk/download/pdf/82613387.pdf In this paper we present

computation multivariate the stream cipher QUAD
stream and the provable security
Authors: cipher with arguments supporting its
1) Côme Berbain provable conjectured strength for
2) Henri Gilbert security suitable parameter values.
3) Jacques Patarin
2 Academia Sinica and Analysis of https://cr.yp.to/streamciphers/antiquad- This paper discusses both
Taiwan Information QUAD 20070303.pdf theoretical and practical
Security aspects of attacking QUAD
and of attacking the
Authors - underlying hard problem.
1) Bo-Yin Yang
2) Owen Chia-Hsin
Chen
3) Jiun-Ming Chen
4) Daniel J. Bernstein