CRYPTOGRAPHY BASED ON REALLY HARD

PROBLEMS

İbrahim Doğa Sarı

Middle East Technical University, Institute of Applied Mathematics,
Cryptography Department
[Link]@[Link]

February 4, 2024

1/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Introduction

Chapter Objectives

▶ Introducing the fundamental concepts of complexity theory essential

for delving into cryptography.
▶ Understanding the limitations of complexity theory in ensuring secure
cryptographic systems independently.
▶ Presenting the concept of random self-reductions.
▶ Explaining the weaknesses inherent in the Merkle-Hellman system.
▶ Outlining the concept of worst-case to average-case reductions for
lattices.
▶ Introducing the Learning with Errors problem and the Ring-Learning
with Errors problem, along with describing a public key encryption
scheme based on them.
▶ Providing an overview of how to expand this encryption scheme to
create a fully homomorphic encryption scheme.
2/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory

Introduction

In the section titled ”Cryptography and Complexity Theory” (17.1), we’ve

been focusing on building cryptography on problems believed to be
difficult, such as AES being a PRF, factoring large primes being
challenging, and finding discrete logarithms being hard. However, the
difficulty of these problems lacks a clear underlying reason. Computer
science offers a comprehensive theory for categorizing hard problems,
known as complexity theory. Yet, none of the problems we’ve discussed so
far seem to align with what complexity theorists consider difficult. In fact,
compared to the discussions in complexity theory, factoring and discrete
logarithms seem relatively manageable.

3/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory

Moving Forward

To move forward, we’ll need to revisit some fundamental concepts of

complexity theory, most of which are covered in basic computer science
undergraduate courses or can be found in the book by Goldreich
mentioned in the Further Reading section of this chapter.

4/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Decision Problems (DP)

A decision problem (DP) is defined as a problem with a binary (yes/no)

answer, where inputs (instances) denoted as ι are encoded in some
manner, such as a binary string of a specified size n. Typically, one has a
defined set S of instances and asks, ”Is ι in S”?
▶ If ι represents an integer and S is the set of all primes, the decision
problem is: Given an integer N, determine whether it is prime or not.
▶ If ι represents a graph and S is the subset of all graphs that can be
colored using only k colors, the decision problem is: Given a graph G ,
ascertain whether it is colorable using k colors, with no two connected
vertices sharing the same color.

5/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Transformation of Computational Problems

Although we’ve concentrated on decision problems, it’s common to

transform a standard computational problem into a decision problem. For
instance, consider the cryptographically significant knapsack problem as an
example of this transformation.

6/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Decision Knapsack Problem

Given a collection of n items with varying weights wi , the question is

whether it’s feasible to select items to fill a knapsack to achieve a
particular weight S. In essence, we’re inquiring if there exist binary values
bi in {0, 1} such that S = b1 · w1 + b2 · w2 + . . . + bn · wn .
As defined, the knapsack problem falls under the category of decision
problems.

7/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Active Search for Values

However, we might also be interested in an algorithm that actively seeks

out the values of bi .

8/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Knapsack (Search) Problem

When provided with a set of n items each with distinct weights wi , the
objective is to determine if it’s feasible to select items for a knapsack to
reach a precise weight S. If such a selection is possible, the question
further asks whether it’s plausible to find binary values bi in {0, 1} such
that S = b1 · w1 + b2 · w2 + . . . + bn · wn . It’s important to note that we
assume there exists only one feasible combination of weights.
In summary, the Knapsack (Search) Problem delves into the feasibility of
assembling items into a knapsack to achieve a target weight S, along with
the potential to discover the binary values bi corresponding to this
configuration.

9/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity of Knapsack Problems

It’s worth noting that the time required to solve either version of the
knapsack problem appears to increase exponentially in the worst-case
scenario with the number of weights involved.
Interestingly, we can transform an oracle designed for the decision
knapsack problem into one suitable for the full knapsack problem.
To understand this transformation, let’s examine Algorithm 17.1, which
operates under the assumption of having an oracle O(w1 , . . . , wn , S) for
the decision knapsack problem.

10/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class P

A decision problem DP, defined by a set S, falls into the complexity class
P if there exists an algorithm capable of taking any instance ι and
determining whether ι ∈ S or not in polynomial time. Time complexity
here is measured in terms of bit operations, and polynomial time implies
that the number of bit operations is limited by some polynomial function
of the input size of ι.
Problems within complexity class P are those for which we possess an
”efficient” solution algorithm. Essentially, elements in complexity class P
are considered to be easily computable. For instance:
▶ Given integers x, y , and z, can we determine if z = x · y ? In other
words, is multiplication an easy operation?
▶ Given a ciphertext c, a key k, and a plaintext m, can we ascertain if c
represents the encryption of m under your preferred encryption
algorithm?
11/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class PP

A decision problem DP, defined by a set S, falls into the complexity class
PP if there exists an algorithm capable of taking any instance ι and
determining whether ι ∈ S or not in polynomial time. Time complexity
here is measured in terms of bit operations, and polynomial time implies
that the number of bit operations is limited by some polynomial function
of the input size of ι.

12/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class PP

Problems within complexity class PP are those for which we possess an

”efficient” solution algorithm. Essentially, elements in complexity class PP
are considered to be easily computable. For instance:
▶ Given integers x, y , and z, can we determine if z = x · y ? In other
words, is multiplication an easy operation?
▶ Given a ciphertext c, a key k, and a plaintext m, can we ascertain if c
represents the encryption of m under your preferred encryption
algorithm?

13/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class PP

Problems within complexity class PP are those for which we possess an

”efficient” solution algorithm. Essentially, elements in complexity class PP
are considered to be easily computable. For instance:
▶ Given integers x, y , and z, can we determine if z = x · y ? In other
words, is multiplication an easy operation?
▶ Given a ciphertext c, a key k, and a plaintext m, can we ascertain if c
represents the encryption of m under your preferred encryption
algorithm?
▶ In the last example, I’ve assumed that your preferred encryption
algorithm features an encryption/decryption process that operates
within polynomial time. If your preferred encryption algorithm doesn’t
conform to this criterion, then it prompts a significant question: How
have you managed to progress this far into the book?

14/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class NP

The class NP, known as non-deterministic polynomial time, encompasses

decision problems for which, if the answer is affirmative (yes), there exists
a witness that can validate this assertion within polynomial time.
However, in cases where the answer is negative (no), we don’t assume the
algorithm necessarily concludes. Nevertheless, if it does, it must answer
no. The notion of a witness can be likened to a proof demonstrating that
the instance ι indeed belongs to the subset S.
Examples of such problems include:

15/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Class NP
The class NP, known as non-deterministic polynomial time, encompasses
decision problems for which, if the answer is affirmative (yes), there exists
a witness that can validate this assertion within polynomial time.
However, in cases where the answer is negative (no), we don’t assume the
algorithm necessarily concludes. Nevertheless, if it does, it must answer
no. The notion of a witness can be likened to a proof demonstrating that
the instance ι indeed belongs to the subset S.
Examples of such problems include:
▶ The problem ”Is N composite?” belongs to NP because a non-trivial
prime factor can serve as a witness, and this witness can be verified in
polynomial time through division.
▶ The problem ”Is G k-colourable?” is in NP since a witness can be
provided in the form of a valid coloring.
▶ The problem ”Does this knapsack problem have a solution?” is in NP
because the values bi can serve as a witness for the existence of a
solution. 16/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity Classes co-NP and NP ∩ co-NP

The class co-NP consists of problems for which a witness exists for every
instance with a negative response, and this witness can be checked in
polynomial time. The prevailing conjecture is that NP ̸= co-NP. If a
problem belongs to NP ∩ co-NP, it is viewed as evidence that the problem
cannot be NP-complete.
For instance, the problem of determining whether a number n has a prime
factor less than m can be demonstrated to lie in NP ∩ co-NP, indicating
that this problem is not considered NP-complete. In other words, factoring
is not deemed a highly challenging problem from a complexity-theoretic
perspective.

17/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Size of Witnesses in NP

One can explore the question of how small a witness for belonging to the
class NP can be. Consider the problem COMPOSITES, where the task is
to determine whether a given integer N is composite. As mentioned
earlier, this problem is evidently in the class NP. Different ways to prove
that N is composite include:
▶ Providing a factor: In this case, the size of the witness is O(log N).
▶ Supplying a Miller–Rabin witness a: Assuming the Generalized
Riemann Hypothesis (GRH), the size of the witness can be bounded
by O(log log N), as a ≤ O((log N)2 ).

18/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

NP-Complete and NP-Hard Problems

A decision problem DP in the class NP is deemed NP-complete if every

other problem in class NP can be reduced to this problem in polynomial
time. In simpler terms, if DP is NP-complete, then the statement DP ∈ P
implies P = NP.
In a sense, NP-complete problems represent the most challenging problems
for which we can reasonably seek solutions. Among the plethora of
NP-complete problems, two noteworthy ones are:
▶ The 3-colouring problem.
▶ The knapsack problem.
A problem DP is labeled NP-hard if DP ∈ P implies P = NP, but we are
uncertain whether DP ∈ NP. Consequently, an NP-hard problem is at
least as challenging as every problem in NP and could potentially be even
more difficult.
19/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Average vs Worst-Case Complexity in Cryptography

The distinction between average and worst-case complexity is crucial in
understanding cryptographic problems. While problems like factoring and
discrete logarithms, which lie in class NP, are not considered equivalent to
an NP-complete problem, they are widely used in cryptography. This
implies that factoring and discrete logarithms may not be exceptionally
difficult problems compared to NP-complete problems like the knapsack
problem or the 3-colouring problem.
The reason for not using NP-complete problems as the basis for
cryptographic schemes lies in the track record and practical considerations.
The theory of NP-completeness primarily deals with worst-case complexity.
However, for cryptographic purposes, the goal is to select problems that
are hard on average for suitably chosen parameters. Interestingly, the
knapsack problems proposed for cryptography in the past are always
”average,” and efficient algorithms can often be found to solve them,
making them less suitable for cryptographic use.
20/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Hard vs Average Problems: k-Colouring Example

The distinction between hard and average problems can be illustrated

using the k-colouring problem, specifically when k = 3. While determining
whether a graph is 3-colourable is generally NP-complete in the worst
case, it is relatively easy on average. This is due to the fact that the
average graph, regardless of its size, is unlikely to be 3-colourable. In fact,
for almost all input graphs, the following algorithm will terminate and
conclude that the graph is not 3-colourable in a constant number of
iterations.

21/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Algorithm for 3-Colourability of a Graph

The algorithm to determine whether a graph is 3-colourable follows these
steps:
1. Take a graph G and order the vertices in any order v1 , . . . , vt .
2. Define the colours as {1, 2, 3}.
3. Traverse the graph in the order of the vertices just decided.
4. On visiting a new vertex, select the smallest possible colour (i.e., one
from the set {1, 2, 3}) that does not appear as the colour of an
adjacent vertex. Set this as the colour of the current vertex.
5. If you get stuck (i.e., no such colour exists), traverse back up the
graph to the most recently coloured vertex and use the next available
colour. Then continue down again.
6. If at any point you run out of colours for the first vertex, terminate
and declare that the graph is not 3-colourable.
7. If you successfully colour the last vertex, terminate and output that
the graph is 3-colourable. 22/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Average-Case Complexity: Graph Colouring and Factoring

The intriguing aspect of the algorithm described above is that it can be

demonstrated that, for a random graph with t vertices, the average
number of vertices traversed by the algorithm is less than 197, regardless
of the number of vertices t in the graph.
When considering factoring, it’s important to note that factoring is
generally easy on average. For a given large number, a factor can often be
found quickly, especially considering that, for approximately fifty percent
of large numbers, a factor can be identified by just examining one digit
(given that half of large numbers are even).

23/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Average-Case Complexity: Graph Colouring and Factoring

In cryptography, when we refer to factoring, we are implicitly referring to

the construction of a hard instance by multiplying two large primes
together. The question arises: Can we construct similarly challenging
instances for NP-complete problems? Can we efficiently generate instances
that we know are among the most difficult for such problems, akin to the
graph colouring example? This task seems inherently challenging.
Later, we will explore instances in hard problems related to lattices where
we can choose parameters to make the average case as challenging as the
worst case of another (related) hard lattice problem.

24/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Average-Case Hardness in Cryptography

In the context of cryptographic security, it’s crucial to select a problem

that is as hard as possible as the foundation. While we often avoid obvious
attacks based on factoring and discrete logarithms, we don’t typically
directly base cryptographic schemes on these problems. Instead, we often
use problems like the RSA problem or the Decisional Diffie-Hellman
(DDH) problem.
To assess the hardness of these problems, we need to determine whether
they are hard on average and in what sense. Random self-reductions are
one way to explore and understand the average-case hardness of
cryptographic problems like RSA and DDH. This involves investigating
whether instances of the problem can be efficiently transformed into other
instances of the same problem, shedding light on their inherent difficulty
on average.

25/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Random Self-Reduction in Cryptographic Problems

Consider the RSA problem as an example. Given an RSA modulus N and a

public exponent e, it might be challenging to solve c ≡ me (mod N) for a
specific c in the worst case. However, it could be relatively easy on average
for most values of c. It has been proven that problems like the RSA
problem for a fixed modulus N or the Decisional Diffie-Hellman (DDH)
problem for a fixed group G are hard on average. The technique used to
establish this is based on a random self-reduction from one given problem
instance to another random problem instance of the same problem.
In simple terms, if we can solve the problem on average, then we can solve
the problem in the worst case. If we had a worst-case problem, we could
randomize it until we encounter an easy average-case problem. As a result,
the worst-case behavior of the problem and the average-case behavior of
the problem must exhibit similarity.

26/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Lemma 17.4: Random Self-Reduction of RSA Problem

Lemma 17.4: The RSA problem is random self-reducible.

Explanation and Proof: Suppose we are given c and are asked to solve
c ≡ me (mod N), where this is considered a ”hard” problem instance.
The goal is to reduce this to an ”average” problem instance. This is
achieved by choosing s randomly from (Z/NZ)∗ and setting c ′ ≡ s · c. We
then attempt to solve c ′ ≡ m′e (mod N).
If we are unsuccessful in solving this new instance, we choose another
value of s and repeat the process until we encounter an ”average” type
problem that can be easily solved. If the average case was indeed easy, we
could solve c ′ ≡ m′e (mod N) for m′ and then set m ≡ m′ · s to find the
solution to the original problem c ≡ me (mod N).

27/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Decisional Diffie-Hellman (DDH) Problem: Random

Self-Reduction
The DDH problem, or Decisional Diffie-Hellman problem, is also random
self-reducible. In this context, testing whether (A, B, C ) = (g a , g b , g ab ) is
a valid Diffie–Hellman triple, i.e., whether C = a · b, does not depend on
the specific choices of a, b, and c.
′ ′ ′ ′
Proof Outline: Consider a related triple (A′ , B ′ , C ′ ) = (g a , g b , g a b )
generated by multiplying each element of the original triple (A, B, C ) by a
random factor u and v . Mathematically, (A′ , B ′ , C ′ ) = (Au , B v , C uv ) for
random u and v . Now, if (A, B, C ) is a valid Diffie–Hellman triplet, then
(A′ , B ′ , C ′ ) is also a valid Diffie–Hellman triplet, and vice versa.
Moreover, it can be shown that the distribution of (A′ , B ′ , C ′ ) will be
uniform over all valid Diffie–Hellman triples if the original triple is a valid
Diffie–Hellman triple. Conversely, the distribution will be uniform over all
triples (and not just Diffie–Hellman ones) in the case where the original
triple was not a valid Diffie–Hellman triple. 28/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Post-Quantum Cryptography: Complexity-Theoretic Hard

Problems

The concept of using complexity-theoretic hard problems, rather than

number-theoretic ones, has been present since the early days of public key
cryptography. This has gained significance in recent times due to the
vulnerability of existing number-theoretic constructions to potential
quantum computers. The search is ongoing for secure and efficient public
key primitives that can withstand the capabilities of future quantum
computers.

29/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Post-Quantum Cryptography: Complexity-Theoretic Hard

Problems

One of the initial attempts in this direction was a public key cryptosystem
based on the knapsack or subset sum problem, known to be NP-complete.
However, it has been revealed that this knapsack-based scheme, along
with many others, is insecure. The underlying idea involves creating two
instances of the problem: a public one believed to be a general knapsack
problem and considered hard, and a private one designed to be easy.
Additionally, there should exist private trapdoor information that
transforms the hard problem into the easy one.

30/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Super-Increasing Knapsack Problem: Example

As an example, one could consider the set {2, 3, 6, 13, 27, 52}, or
alternatively, {1, 2, 4, 8, 16, 32, 64, . . .}. In a super-increasing knapsack
problem, characterized by an ordered set of such super-increasing weights
{w1 , . . . , wn }, along with a target weight S, the task of determining which
weights to place in the sack is a linear operation.

31/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Figure: Enter Caption

32/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Key Generation

Key Generation: In the Merkle–Hellman encryption scheme, the private

key is formed by a super-increasing knapsack problem. Through a private
transformation, a ”hard knapsack” problem is generated, and this difficult
problem serves as the public key. The transformation involves selecting
two private integers, N and M, satisfying gcd(N, M) = 1, and multiplying
all values in the super-increasing sequence by N mod M.

For instance, consider the private key as the super-increasing knapsack

{2, 3, 6, 13, 27, 52}, with N = 31 and M = 105. The resulting public key is
represented by the ”hard” knapsack {62, 93, 81, 88, 102, 37}. The public
key, the hard knapsack problem, is then disclosed, with the expectation
that only individuals aware of N and M can reverse the transformation to
retrieve the easy super-increasing knapsack.

32/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Encryption

Encryption: To encrypt a message for us, Bob begins by dividing the
plaintext into blocks sized according to the weight set. The ciphertext is
then formed by summing the weights corresponding to the set bits in each
block. For instance, if the message is:

Message = 011000 110101 101110,

and our public knapsack is {62, 93, 81, 88, 102, 37}, then the ciphertext
would be:

Ciphertext = 174, 280, 333,

as follows:
▶ 011000 corresponds to 93 + 81 = 174,
▶ 110101 corresponds to 62 + 93 + 88 + 37 = 280,
▶ 101110 corresponds to 62 + 81 + 88 + 102 = 333.
33/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Decryption

Decryption Process: The legitimate recipient possesses the private key

N, M, and the super-increasing knapsack {2, 3, 6, 13, 27, 52}. By
multiplying each ciphertext block by N −1 mod M, the hard knapsack is
transformed back into the original easy knapsack problem.

174 · 61 ≡ 9 ≡ 3 + 6 ≡ 011000,
280 · 61 ≡ 70 ≡ 2 + 3 + 13 + 52 ≡ 110101,
333 · 61 ≡ 48 ≡ 2 + 6 + 13 + 27 ≡ 101110.
Therefore, the decryption process successfully yields the original blocks of
the plaintext message.

34/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Vulnerabilities and

Lattice Attacks (Contd.)

Final Decoding: The final decoding is done using the simple easy
knapsack, {2, 3, 6, 13, 27, 52}, and our earlier linear-time algorithm for
super-increasing knapsack problems.
Implementation Details: In a typical implementation, the knapsack
problem involves a larger number of items, often around 250, and the
values of N and M are usually chosen to be around 400 bits. However,
even with such parameters, the Merkle–Hellman encryption scheme can be
vulnerable to attacks using lattice-based techniques.

35/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Vulnerabilities and

Lattice Attacks (Contd.)

Lattice Attack: Suppose we wish to solve the knapsack problem given by

the weights {w1 , . . . , wn } and the target S. We can consider the lattice L
of dimension n + 1 generated by the columns of the following matrix A:
 
1 0 0 ... 0 1
2 0 1 . . . 0 1
 
2 0 0 . . . 0 1
A= . ..  .
 
. .. .. . . ..
 .
 . . . . .
0 0 0 . . . 1 1
w1 w2 w3 . . . wn S

36/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Vulnerabilities and

Lattice Attacks (Contd.)

Lattice Attack (Contd.): Assuming there is a solution to our knapsack

problem given by the bit vector (b1 , . . . , bn ), we know that the vector
y = A · x is in our lattice, where x = (b1 , . . . , bn , −1). The components of
y are given by:
(
bi −1
2 if 1 ≤ i ≤ n
yi =
0 if i = n + 1.
Hence, the vector y is very short, with its length bounded by:
r
n
q
2 2
∥y ∥ = y1 + . . . + yn+1 < .
2

37/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Encryption Scheme: Vulnerabilities and

Lattice Attacks (Contd.)

If {w1 , . . . , wn } is a set of knapsack weights, then we define the density of

the knapsack to be:
n
d= .
max{log2 (wi ) : 1 ≤ i ≤ n}

38/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Cryptosystem
Key Generation

In the Merkle–Hellman encryption scheme, the private key is formed by a

super-increasing knapsack problem. Through a private transformation, a
”hard knapsack” problem is generated, and this difficult problem serves as
the public key. The transformation involves selecting two private integers,
N and M, satisfying gcd(N, M) = 1, and multiplying all values in the
super-increasing sequence by N (mod M). For instance, consider the
private key as the super-increasing knapsack {2, 3, 6, 13, 27, 52}, with
N = 31 and M = 105. The resulting public key is represented by the
”hard” knapsack {62, 93, 81, 88, 102, 37}. The public key, the hard
knapsack problem, is then disclosed, with the expectation that only
individuals aware of N and M can reverse the transformation to retrieve
the easy super-increasing knapsack.

39/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Cryptosystem

If a knapsack has low density, it becomes susceptible to easy solutions

through lattice basis reduction. A knapsack with low density typically
leads to a lattice with a notably large discriminant, making the vector y
exceptionally short within the lattice. Applying the LLL algorithm to
matrix A yields a new reduced basis matrix A′ . The initial vector a′1 of
this reduced basis, obtained through LLL, is likely to be the smallest vector
in the lattice, making a′1 comparable to y. With y in hand, we can then
determine x and uncover the solution to the original knapsack problem.
This vulnerability undermines the Merkle–Hellman scheme, as its
construction consistently results in a low-density public knapsack.

40/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Merkle–Hellman Cryptosystem
Decryption

The legitimate recipient possesses the private key N, M, and the

super-increasing knapsack {2, 3, 6, 13, 27, 52}. By multiplying each
ciphertext block by N −1 (mod M), the hard knapsack is transformed back
into the original easy knapsack problem. In this case, N −1 = 61 (mod M),
and the decryptor performs the following operations:

174 · 61 ≡ 9 ≡ 3 + 6 ≡ 011000,
280 · 61 ≡ 70 ≡ 2 + 3 + 13 + 52 ≡ 110101,
333 · 61 ≡ 48 ≡ 2 + 6 + 13 + 27 ≡ 101110.
Therefore, the decryption process yields the original blocks of the plaintext
message.

41/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Complexity-Theoretic Hard Problems

If we aim to make progress with complexity-theoretic hard problems,

ensuring the selection of instances from the set of worst cases becomes
crucial. Similar to the approaches taken for the RSA and DDH problems,
we achieve this by establishing a reduction from a worst-case problem to
an average-case problem. However, in contrast to the number-theoretic
scenarios mentioned earlier, our reduction won’t be from the same problem
type. Instead, it will involve transforming an instance of a worst-case
problem of type X into an average-case instance of a problem of type Y.

42/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Pursuing Complexity-Theoretic Hard Problems

In pursuing this goal, our objective is to demonstrate that problem Y
remains consistently hard, regardless of its setup. We aim to establish that
Y is hard on average. To achieve this, we select a problem X known to be
hard in the worst case. Subsequently, we illustrate how any instance,
including worst-case instances, of problem X can be solved using an oracle
designed to handle average-case instances of problem Y. The crucial
insight lies in the belief that if an algorithm for the worst case of problem
X is deemed implausible, it implies the non-existence of an algorithm for
solving the average case of problem Y.
Focusing on a lattice-based problem, consider the input public basis matrix
B representing a challenging problem (e.g., solving the shortest vector
problem in the lattice generated by the columns of B). B might not
generate a ”random lattice”; in fact, it could be a lattice for which solving
the shortest vector problem is maximally complex. Our aim is to construct
another lattice problem derived from B that exhibits an ”average”
appearance. 43/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Frame Title

The fundamental concept here is to create a lattice basis, denoted as A,

for a new lattice, ensuring that this new lattice basis has a ”relationship”
with the basis B. This relationship is crucial for mapping solutions from a
problem in the lattice generated by A to a problem in the lattice generated
by B. Simultaneously, we desire the lattice generated by A to possess a
”uniformly random” characteristic in some sense. The generation of a
random lattice involves the random selection of vectors, requiring a
process to create vectors that are random enough to confound an
algorithm designed for solving average-case problems.

44/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Frame Title

To achieve this, we initiate the process by considering the lattice L(B) and
selecting a random vector x from this lattice, with the understanding that
L(B) contains infinitely many vectors. Subsequently, we introduce a
non-lattice vector close to x, specifically choosing an error vector e with a
Gaussian distribution featuring a mean of zero and a ”small” standard
deviation. Refer to Figure 17.1 for an illustrative example of the resulting
probability distribution in a two-dimensional lattice. As the standard
deviation increases progressively, we ultimately attain a distribution that
appears ”uniform” but maintains a connection to the original lattice basis
B, as depicted in Figure 17.2.

45/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

46/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Frame Title

The methodology outlined above serves as the foundation for

demonstrating how an oracle can be employed to address the small integer
solution problem in the average case, consequently enabling the solution of
any approximate shortest vector problem, even potentially in the worst
case. For a more comprehensive understanding, it may be beneficial to
revisit the discussions around Definitions 5.4 and 5.8 to refresh basic
concepts.

46/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

47/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Recap: SIS and Oracle

To recap, the SIS (Short Integer Solution) problem involves finding a short
vector z ∈ Zm such that A · z ≡ 0 (mod q), where A is a matrix with
coefficients in Z/qZ and q is a prime. Let β represent the bound on the
norm of z for a specific SIS instance, and OSIS(A, q, β) denote the oracle
that solves SIS in the average case.
As mentioned in Chapter 5, solving SIS is equivalent to finding an
equivalently short vector in the lattice Λq⊥ (A) = {z ∈ Zm : A · z ≡ 0
(mod q)}. The lattice Λq⊥ (A) has a determinant of q n . By choosing
√
β = m · q n/m , the SIS oracle OSIS(A, q, β) is guaranteed to output a
solution.
The goal is to utilize this oracle to solve any approximate shortest vector
problem. Specifically, finding short vectors in the lattice Λq⊥ (A) for a
matrix A chosen uniformly at random from (Z/qZ)n×m would enable the
discovery of short vectors in any lattice. This process involves considering
another problem related to the shortest vector problem, known as the
shortest independent vectors problem. 47/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

SIVP and Transference Theorem

In Definition 17.5, the Shortest Independent Vectors Problem (SIVP) is

described as follows: Given a lattice L and an integer γ, the SIVP problem
SIVPγ is to find a basis B of a full-rank sub-lattice such that the length of
all vectors in B is less than γ · λn (L), where λn (L) is the nth successive
minimum of the lattice.
Recall the transference theorem of Banaszczyk from Chapter 5, which
states that for all n-dimensional lattices, the product of the first and nth
successive minima of the lattice and its dual satisfies
1 ≤ λ1 (L) · λn (L∗ ) ≤ n. Therefore, if one can approximate the nth
successive minimum of a lattice (which is achieved by a solution to the
SIVP problem), it is possible to approximate the Shortest Vector Problem
(SVP) for its dual lattice, and vice versa.

48/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

SIVP and Transference Theorem (Continued)

Continuing from the previous message, in the context of the SIVP problem,
√
the focus is on solving the problem for γ = 16 · n · m · c2 , where c2 is a
constant to be defined later. The input matrix for the SIVP problem is
denoted by B, where B consists of n column vectors {b1 , . . . , bn }. The
notation ∥B∥ represents the maximum norm of any column vector in B,
and the objective is to find a lattice basis with ∥B∥ ≤ γ · λn (L).
The strategy is to iteratively replace B with a basis B ′ having
∥B ′ ∥ ≤ ∥B∥/2. This replacement involves finding a vector y in the lattice
of size bounded by ∥B∥/2. If the output vector y is not independent of
the largest vector in B, the largest vector in B is replaced with the new
vector. This process results in a basis with a reduced value of ∥B∥, and
the procedure is repeated. The crucial observation is that the probability
of the output vector not being independent of the largest vector in B is
very small.
49/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Step-by-Step Method for Oracle-Based Solution

1. Choose m as c1 · n · log q, where c1 is a constant between 0 and 1.
The specific constants are not emphasized in this overview.
√ √
2. Set β as m · q n/m = m · c2 , where c2 is introduced.
3. Select q approximately as 4 · n1.5 · β.
4. For each 1 ≤ i ≤ m, do the following:
▶ Choose ei as an n-dimensional vector with coefficients from an
n-dimensional
√ Gaussian distribution with standard deviation
σ = n · ∥B∥/(2 · q).
▶ Define vi = (ei mod B) − ei , where ei mod B reduces ei into the
fundamental parallelepiped defined by the basis B. Note that vi
belongs to L(B).
▶ Compute ui = (ei mod B) − (1/q) · B · ai for some integer vector ai ,
rounding ei mod B to the nearest lattice point of L(1/q · B).
5. Assemble the matrix A using a1 , . . . , am .
6. Use the oracle P
OSIS(A, q, β) to find z.
7. Compute y = zi · (ei + ui ).
8. Output y . 50/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Frame Title

We have to demonstrate that y is a lattice vector, has a norm smaller than

‖B‖/2, and that the SIS oracle OSIS(A, q, ) functions as anticipated.
Let’s examine each of these aspects step by step.

51/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Proof Continuation
9. y ∈ L(B): The vector z obtained from the OSIS(A, q, β) oracle
satisfies A · z = 0 mod q. Thus, there exists w ∈ Zn such that
A · z = q · w . By rearranging terms, we have:
1 1 1 X X
B ·w = ·B ·(q·w ) = ·B ·A·z = ·B · ai ·zi = (ei +ui +vi )·zi .
q q q
Since B · w and vi are lattice vectors, y is also a lattice vector.
10. ∥y ∥ ≤ ∥B∥/2: This bound is established by combining two facts:
▶ ∥ui ∥ ≤ n · ∥B∥/q, as (ai , ei , ui , vi ) satisfies ei + ui + vi = q1 · B · ai .
√ √ √
▶ With high probability, ∥ei ∥ ≤ 2 · σ · n, where σ = n · ∥B∥/(2 · q).
Combining
P these facts and 1.5utilizing the fact that ∥z∥ ≤ β, we can
show ∥ (ei + ui ) · zi ∥ ≤ n · β · 2 · ∥B∥/q ≤ ∥B∥/2, based on the
chosen value of β.
This completes the explanation of the proof regarding y being a lattice
vector with a norm less than ∥B∥/2. The specific parameters and choices,
such as β, are crucial in ensuring the success of this reduction. 52/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Analysis of the SIS Oracle OSIS(A, q, β)

▶ The SIS oracle OSIS(A, q, β) is deemed ”well-behaved”: The
selection of β ensures a solution to the SIS problem for the input
matrix A. Our expectation is that the oracle successfully discovers a
solution. The SIS oracle is considered well-behaved under the
assumption that the input resembles a random SIS instance, implying
that the matrix A appears to be chosen randomly from the set of all
matrices modulo q.
▶ Intricate Analysis: This is where the intricate analysis becomes
essential. The core concept revolves around the fact that, with the
standard deviation σ intentionally chosen to be relatively large
compared to the lattice basis B, the statistical gap between the
vectors ei modulo L(B) and the uniform distribution of Rn modulo
L(B) becomes minute. Subsequently, as ai essentially represents the
rounding of these values to a grid point, they exhibit behavior similar
to uniformly random vectors. It is also imperative to demonstrate
that the new vector is linearly independent of the other vectors, a 53/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Determining the Value of σ in the Analysis

How large should σ be? The analysis indicates that the SIS oracle will
√
function effectively if we choose σ = n · ∥B∥ 2·q to be greater than or equal
to 2 · λn (L). However, this requirement implies that our input matrix B
must satisfy ∥B∥ > 4 · q · λ√n (L)
n
= γ · λn (L). Therefore, our reduction
approach will succeed as long as the basis adheres to this condition.
Consequently, the reduction process will conclude once we achieve
∥B∥ ≤ γ · λn (L), signifying the resolution of the input SIVPγ problem.

54/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

In the context of lattice-based cryptography, another problem that exhibits

a connection between worst-case and average-case scenarios is the
Learning With Errors (LWE) problem. The resolution of the average-case
complexity of LWE through an oracle can be leveraged to solve the
Bounded-Distance Decoding (BDD) problem in a related lattice. However,
it’s important to note that this reduction is considerably more intricate
than the simplified description provided for the SIS to SVP reduction.
Before delving into the details of the LWE problem, it’s necessary to
introduce an error distribution denoted by DZn ,σ . This distribution
generates n-dimensional integer vectors with coefficients that follow an
approximate normal distribution, characterized by a mean of zero and a
standard deviation of σ. The elements produced with high probability by
DZn ,σ can be conceptualized as having ”small” coefficients. There are two
variants of the LWE problem: the search problem and the decision
problem, each having corresponding advantages that adversaries can
exploit, following the conventional approach.
55/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Definition 17.6 (LWE Search Problem): Select a vector s randomly

from (Z/qZ)m , generate a vector e from the error distribution DZn ,σ , and
create a matrix A from (Z/qZ)n×m , where n > m. Set b as A multiplied
by s, added to e modulo q. The search problem involves receiving the pair
(A, b) as input and outputting the vector s.
Definition 17.7 (LWE Decision Problem): Given the pair (A, b), where
A is from (Z/qZ)n×m with n > m and b is from (Z/qZ)n , determine
which of the following two cases is true:
1. b is uniformly selected at random from (Z/qZ)n .
2. b is obtained as A multiplied by s, added to e modulo q, where e is
from DZn ,σ , and s is randomly chosen from (Z/qZ)m .
Let’s examine the search problem. If the error vector e were zero, we
would be dealing with the linear system of equations A · s = b(mod q),
where the matrix has more rows than columns. This system is consistent
due to our construction, and finding a solution involves matrix inversion,
making it a computationally easy problem. The addition of a small error
vector e makes the problem significantly more challenging. In a way, we
are decoding a random linear code over Z/qZ, where the error vector is e. 55/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

We can connect the search problem to q-ary lattices from Chapter 5,

specifically letting L = Λq (AT ).
It’s important to note that recovering e is equivalent to recovering s. The
LWE problem is essentially about finding a vector x ∈ L such that
b − x = e. To transform this into a Bounded-Distance Decoding problem,
we need to constrain the size of the error vector e. Since e is chosen from
a distribution approximating the Gaussian distribution, we can demonstrate
that its norm is not too large with
√ high probability. Specifically, it can be
√
shown that ∥e∥ ≤ 2 · σ · m/( 2 · π). √ Therefore, our goal is to solve a
√
BDDα problem where α = 2 · σ · m/( 2 · π · λ1 (L)).

56/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Fundamental Facts about LWE

1. The decision and search problems in LWE are equivalent. Possessing

an oracle to solve the decision problem allows us to address the search
problem.
2. The secret vector s, as per the definition, can be chosen to follow the
error distribution DZm ,σ without compromising the problem’s difficulty.
3. While the worst-case to average-case hardness result specifies the
error distribution as DZn ,σ , in practical applications, any distribution
that generates vectors deemed ”small” and possesses high entropy
can be chosen.

56/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

beamer []beamerthemedefault

57/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Fundamental Facts about LWE

1. The decision and search problems in LWE are equivalent. In other

words, possessing an oracle to solve the decision problem allows us to
address the search problem.
2. The secret vector s, as per the definition, can be chosen to follow the
error distribution DZm ,σ without compromising the problem’s difficulty.
3. While the worst-case to average-case hardness result specifies the
error distribution as DZn ,σ , in practical applications, any distribution
that generates vectors deemed ”small” and possesses high entropy
can be chosen.

57/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

beamer []beamerthemedefault

58/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Public Key System Based on LWE

We can now introduce a public key cryptosystem whose security is closely

tied to the worst-case complexity of the Bounded-Distance Decoding
problem. Currently, there are no known attacks that can be effectively
executed with a quantum computer against this scheme.

The system is parameterized by integer values n, m, and q, with m

approximately equal to n times the logarithm of q, and q being a prime
number greater than 2. In the subsequent explanations throughout this
chapter, when reducing something modulo q, we choose a representative
in the range  q qi
− ,...,
2 2
meaning we consider representatives centered around zero.

58/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Key Generation

Private Key:  n
−q q
s← ,...,
2 2
Public Key:

For i = 1 to m :
q n
 
−q
ai ← ,...,
2 2
ei ← DZ 1,σ (Error values)
bi ← ai · s − 2 · ei mod q
Public key: pk ← {(a1 , b1 ), . . . , (am , bm )}

59/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Encryption
Encryption:
To encrypt a message (a single bit m ∈ {0, 1}), the encryptor selects a
subset of indicator bits in {1, . . . , ℓ}, i.e., θi ∈ {0, 1} for i = 1, . . . , ℓ. The
ciphertext is then the pair of values (consisting of a vector c and an
integer d):

For i = 1 to ℓ :
θi ← {0, 1}
Compute:
ℓ
X
c← θi · ai
i=1
ℓ
X
d ←m− θi · b i
i=1
60/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Decryption

Decryption:
Decryption of (c, d) is performed by evaluating
ℓ
!
X
( θi · ai · s + θi · bi ) + m mod q mod 2,
i=1

which simplifies to
ℓ
! !
X
2 · θi · ai · bi +m mod q mod 2,
i=1

given the definition of bi . The sum η = m

P
i=1 2 · θi · ei is deemed ”small”
modulo q and does not ”wrap around” since the ei are appropriately
chosen to be small.
61/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

The term η is referred to as the ”noise” associated with the ciphertext.

The decryption works because this noise is small relative to the modulus q,
ensuring that taking the inner modulo q operation yields the value of
m + η over the integers. The choice of reduction centered around zero
ensures this. Since η is divisible by two, we can recover the message m by
reducing the result modulo two.

62/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Scheme Design: Public Key Structure

General Design:
The public key contains numerous encryptions of zero. To encrypt a
message m, a subset of these zero encryptions is chosen and added to the
message, resulting in an encryption of m, provided that the ”noise” does
not become too large.
Security Assumption:
It can be demonstrated that the above scheme is IND-CPA
(Indistinguishability under Chosen-Plaintext Attack) assuming the hardness
of the LWE decision problem.

63/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS
Cryptography and Complexity Theory Decision and Search Problems (17.1.1)

Chapter Summary:
- Complexity theory focuses on the worst-case behavior of algorithms in
solving a given decision problem. Some problems are easy on average, but
there exist instances that are exceptionally challenging. - Problems like
RSA and DDH are hard on average, benefitting from random
self-reductions from a specific instance to a random instance of the
problem. - Cryptographic systems based on knapsack problems have faced
challenges, as lattice basis reduction techniques can often be employed to
break them. - For secure lattice-based systems, it is crucial to choose
lattice problems with worst-case to average-case reductions. - The
Learning With Errors (LWE) problem and the closely related Ring-LWE
problem are examples of such lattice problems that enable the construction
of fully homomorphic encryption schemes and schemes seemingly resistant
to quantum attacks.

64/64
İbrahim Doğa Sarı (METU-IAM) CRYPTOGRAPHY BASED ON REALLY HARD PROBLEMS