# Preimage Selective Trapdoor Function: How to Repair an Easy Problem

Authors: Baocang Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Public key cryptosystems are constructed by embedding a trapdoor into a one-way function. So, the one-wayness and the trapdoorness are vital to public key cryptography. In this paper, we propose a novel public key cryptographic primitive called preimage selective trapdoor function. This scenario allows to use exponentially many preimage to hide a plaintext even if the underlying function is not one-way. The compact knapsack problem is used to construct a probabilistic public key cryptosystem, the underlying encryption function of which is proven to be preimage selective trapdoor one-way functions under some linearization attack models. The constructive method can guarantee the noninjectivity of the underlying encryption function and the unique decipherability for ciphertexts simultaneously. It is heuristically argued that the security of the proposal cannot be compromised by a polynomial-time adversary even if the compact knapsack is easy to solve. We failed to provide any provable security results about the proposal; however, heuristic illustrations show that the proposal is secure against some known attacks including brute force attacks, linearization attacks, and key-recovery attacks. The proposal turns out to have acceptable key sizes and performs efficiently and hence is practical.


---

## Body

## 1. Introduction

### 1.1. Background

Public key cryptosystem (PKC) is an important cryptographic primitive in the area of network and information security. The basic idea to construct a PKC is to embed a trapdoor into a mathematically intractable problem. The trapdoor helps the trapdoor holder reverse the underlying one-way function. However, without the trapdoor, one should attack a presumed intractable problem in order to reconstruct the plaintext corresponding to a given ciphertext. So the existence of mathematically hard problems is vital in public key cryptography. This explains why we say bad news in computational complexity is good news for cryptography.In the cryptographic community, a PKC is always considered as synonymous with the so-called trapdoor one-way function. Bellare et al.’s observation [1] provides a better understanding of the two concepts. On one hand, a probabilistic public key encryption does not necessarily imply a trapdoor one-way function. For example, the underlying encryption function f
(
m
,
r
)
=
(
c
1
,
c
2
)
=
(
g
r
,
m
h
r
) of ElGamal [2] is not one-way in that the auxiliary key r randomly chosen by the encrypter cannot be recovered knowing the trapdoor x satisfying h
=
g
x. On the other hand, in some cases, noninjective trapdoor one-way functions cannot be used to construct PKCs because a PKC is required to recover a unique plaintext from any valid ciphertext. So the encryption function underlying a PKC should be injective. Bellare et al. showed that any one-way function implies a highly noninjective trapdoor one-way function. However, the authors derived no PKCs from their universal constructions. They only showed that if the image of a trapdoor one-way function has polynomially bounded number of preimages, the trapdoor one-way function can be used to derive a PKC.In this paper, we propose a probabilistic public key encryption algorithm from a highly noninjective one-way function. We think that our construction not only enriches the cryptographic basket and deepens our insights into public key cryptographic designs but also provides weaker cryptographic assumptions. Our confidence in the hardness of noninjective one-way functions rests on the proven fact that it is not easier to reverse a given one-way function equipped with an additional noninjectivity property than an injective one-way function [3]. More importantly, what we observed in this paper is that it remains possible to develop a secure PKC by fully exploiting the noninjectivity property of functions even if these functions turn out to be not one-way.


### 1.2. Our Contribution

In this paper, we firstly formalize a novel public key cryptographic scenario called preimage selective trapdoor one-way function (PSTOF, for short) and then use the compact knapsack problem to realize such a scenario.


#### 1.2.1. Preimage Selective Trapdoor One-Way Function (See Figure1)

Figure 1
Preimage selective trapdoor one-way function.A PSTOFT is in fact a noninjective public key encryption function. When encrypting a message m in the message space 𝕄, the encrypter firstly encodes the message into a plaintext x
=
F
(
m
) in the plaintext space 𝕊
P and then derives a ciphertext c
=
T
(
x
) in the ciphertext space ℂ. When decrypting a ciphertext c, the decrypter utilizes the trapdoor σ to decrypt a valid ciphertext into a unique plaintext x
∈
𝕊
P and then uniquely decodes x into a message m
∈
𝕄.The scenario allows us to base the security of a PKC on the high noninjectivity rather than the one-wayness of a function (an intractable problem). In this scenario,𝕊
P is a subset of the equivalent plaintext space 𝕊
E, and the ciphertext space ℂ
=
T
(
𝕊
E
)
=
{
T
(
x
)
∣
x
∈
𝕊
E
}. For any valid ciphertext c
∈
ℂ, c will have many preimages in 𝕊
E, which are called equivalent ciphertexts in that all of them can be mapped into c under the function T, and a unique preimage (the plaintext) x
∈
𝕊
P with respect to the function T, which is a valid plaintext and hence can be further decoded into a meaningful message. The message encoding function F simulates the process of randomly selecting a subset as the plaintext space 𝕊
P from the whole preimage domain 𝕊
E, from which the name PSTOF comes. In other words, the message encoding function imposes some restrictions on the preimage set 𝕊
E to get a subset with a predesignated special structure as the plaintext space 𝕊
P. The equivalent plaintexts in 𝕊
E are used to hide a (valid) plaintext in 𝕊
P. If T is preassumed one-way, any polynomial-time adversary cannot obtain a preimage in 𝕊
E given a c
∈
ℂ; let alone the unique preimage (the plaintext) x
∈
𝕊
P
⊂
𝕊
E. If the underlying function T is not one-way and when a c
∈
ℂ has exponentially many preimages in 𝕊
E, the corresponding plaintext in 𝕊
P is hidden by these exponentially many preimages. A polynomial-time adversary only obtains polynomially many preimages, which can be seen as randomly output from all the exponentially many preimages and hence include the target plaintext with a negligible probability.


#### 1.2.2. Probabilistic Compact Knapsack PKC

By using the concept of PSTOF and from the compact knapsack problem, a probabilistic public key encryption scheme is designed. An easy compact knapsack-type problem is defined, and an algorithm calledOnion Algorithm is developed to peel off the solutions to the easy problem. The easy problem is used to construct a probabilistic PKC. The main results are that the trapdoor one-way function underlying the proposal is PSTOFs under different linear attack models (See Theorems 25, 26, and 30), and the images of the PSTOFs have exponentially many preimages (see Table 3). Some design tricks are adopted to make the PKC immune from some known key-recovery attacks such as GCD attack [4, 5], Diophantine approximation attack [6, 7], and orthogonal lattice attack [8, 9].


### 1.3. Organization

The rest of the paper is organized as follows. In Section2, we formalize the definition of PSTOF and use the cryptographic scenario to explain some known PKCs. Section 3 provides a concrete probabilistic public key encryption scheme to realize the PSTOF. Sections 4 and 5 discuss the performance and security related issues, respectively. Section 6 gives some concluding remarks.


## 1.1. Background

Public key cryptosystem (PKC) is an important cryptographic primitive in the area of network and information security. The basic idea to construct a PKC is to embed a trapdoor into a mathematically intractable problem. The trapdoor helps the trapdoor holder reverse the underlying one-way function. However, without the trapdoor, one should attack a presumed intractable problem in order to reconstruct the plaintext corresponding to a given ciphertext. So the existence of mathematically hard problems is vital in public key cryptography. This explains why we say bad news in computational complexity is good news for cryptography.In the cryptographic community, a PKC is always considered as synonymous with the so-called trapdoor one-way function. Bellare et al.’s observation [1] provides a better understanding of the two concepts. On one hand, a probabilistic public key encryption does not necessarily imply a trapdoor one-way function. For example, the underlying encryption function f
(
m
,
r
)
=
(
c
1
,
c
2
)
=
(
g
r
,
m
h
r
) of ElGamal [2] is not one-way in that the auxiliary key r randomly chosen by the encrypter cannot be recovered knowing the trapdoor x satisfying h
=
g
x. On the other hand, in some cases, noninjective trapdoor one-way functions cannot be used to construct PKCs because a PKC is required to recover a unique plaintext from any valid ciphertext. So the encryption function underlying a PKC should be injective. Bellare et al. showed that any one-way function implies a highly noninjective trapdoor one-way function. However, the authors derived no PKCs from their universal constructions. They only showed that if the image of a trapdoor one-way function has polynomially bounded number of preimages, the trapdoor one-way function can be used to derive a PKC.In this paper, we propose a probabilistic public key encryption algorithm from a highly noninjective one-way function. We think that our construction not only enriches the cryptographic basket and deepens our insights into public key cryptographic designs but also provides weaker cryptographic assumptions. Our confidence in the hardness of noninjective one-way functions rests on the proven fact that it is not easier to reverse a given one-way function equipped with an additional noninjectivity property than an injective one-way function [3]. More importantly, what we observed in this paper is that it remains possible to develop a secure PKC by fully exploiting the noninjectivity property of functions even if these functions turn out to be not one-way.


## 1.2. Our Contribution

In this paper, we firstly formalize a novel public key cryptographic scenario called preimage selective trapdoor one-way function (PSTOF, for short) and then use the compact knapsack problem to realize such a scenario.


### 1.2.1. Preimage Selective Trapdoor One-Way Function (See Figure1)

Figure 1
Preimage selective trapdoor one-way function.A PSTOFT is in fact a noninjective public key encryption function. When encrypting a message m in the message space 𝕄, the encrypter firstly encodes the message into a plaintext x
=
F
(
m
) in the plaintext space 𝕊
P and then derives a ciphertext c
=
T
(
x
) in the ciphertext space ℂ. When decrypting a ciphertext c, the decrypter utilizes the trapdoor σ to decrypt a valid ciphertext into a unique plaintext x
∈
𝕊
P and then uniquely decodes x into a message m
∈
𝕄.The scenario allows us to base the security of a PKC on the high noninjectivity rather than the one-wayness of a function (an intractable problem). In this scenario,𝕊
P is a subset of the equivalent plaintext space 𝕊
E, and the ciphertext space ℂ
=
T
(
𝕊
E
)
=
{
T
(
x
)
∣
x
∈
𝕊
E
}. For any valid ciphertext c
∈
ℂ, c will have many preimages in 𝕊
E, which are called equivalent ciphertexts in that all of them can be mapped into c under the function T, and a unique preimage (the plaintext) x
∈
𝕊
P with respect to the function T, which is a valid plaintext and hence can be further decoded into a meaningful message. The message encoding function F simulates the process of randomly selecting a subset as the plaintext space 𝕊
P from the whole preimage domain 𝕊
E, from which the name PSTOF comes. In other words, the message encoding function imposes some restrictions on the preimage set 𝕊
E to get a subset with a predesignated special structure as the plaintext space 𝕊
P. The equivalent plaintexts in 𝕊
E are used to hide a (valid) plaintext in 𝕊
P. If T is preassumed one-way, any polynomial-time adversary cannot obtain a preimage in 𝕊
E given a c
∈
ℂ; let alone the unique preimage (the plaintext) x
∈
𝕊
P
⊂
𝕊
E. If the underlying function T is not one-way and when a c
∈
ℂ has exponentially many preimages in 𝕊
E, the corresponding plaintext in 𝕊
P is hidden by these exponentially many preimages. A polynomial-time adversary only obtains polynomially many preimages, which can be seen as randomly output from all the exponentially many preimages and hence include the target plaintext with a negligible probability.


### 1.2.2. Probabilistic Compact Knapsack PKC

By using the concept of PSTOF and from the compact knapsack problem, a probabilistic public key encryption scheme is designed. An easy compact knapsack-type problem is defined, and an algorithm calledOnion Algorithm is developed to peel off the solutions to the easy problem. The easy problem is used to construct a probabilistic PKC. The main results are that the trapdoor one-way function underlying the proposal is PSTOFs under different linear attack models (See Theorems 25, 26, and 30), and the images of the PSTOFs have exponentially many preimages (see Table 3). Some design tricks are adopted to make the PKC immune from some known key-recovery attacks such as GCD attack [4, 5], Diophantine approximation attack [6, 7], and orthogonal lattice attack [8, 9].


## 1.2.1. Preimage Selective Trapdoor One-Way Function (See Figure1)

Figure 1
Preimage selective trapdoor one-way function.A PSTOFT is in fact a noninjective public key encryption function. When encrypting a message m in the message space 𝕄, the encrypter firstly encodes the message into a plaintext x
=
F
(
m
) in the plaintext space 𝕊
P and then derives a ciphertext c
=
T
(
x
) in the ciphertext space ℂ. When decrypting a ciphertext c, the decrypter utilizes the trapdoor σ to decrypt a valid ciphertext into a unique plaintext x
∈
𝕊
P and then uniquely decodes x into a message m
∈
𝕄.The scenario allows us to base the security of a PKC on the high noninjectivity rather than the one-wayness of a function (an intractable problem). In this scenario,𝕊
P is a subset of the equivalent plaintext space 𝕊
E, and the ciphertext space ℂ
=
T
(
𝕊
E
)
=
{
T
(
x
)
∣
x
∈
𝕊
E
}. For any valid ciphertext c
∈
ℂ, c will have many preimages in 𝕊
E, which are called equivalent ciphertexts in that all of them can be mapped into c under the function T, and a unique preimage (the plaintext) x
∈
𝕊
P with respect to the function T, which is a valid plaintext and hence can be further decoded into a meaningful message. The message encoding function F simulates the process of randomly selecting a subset as the plaintext space 𝕊
P from the whole preimage domain 𝕊
E, from which the name PSTOF comes. In other words, the message encoding function imposes some restrictions on the preimage set 𝕊
E to get a subset with a predesignated special structure as the plaintext space 𝕊
P. The equivalent plaintexts in 𝕊
E are used to hide a (valid) plaintext in 𝕊
P. If T is preassumed one-way, any polynomial-time adversary cannot obtain a preimage in 𝕊
E given a c
∈
ℂ; let alone the unique preimage (the plaintext) x
∈
𝕊
P
⊂
𝕊
E. If the underlying function T is not one-way and when a c
∈
ℂ has exponentially many preimages in 𝕊
E, the corresponding plaintext in 𝕊
P is hidden by these exponentially many preimages. A polynomial-time adversary only obtains polynomially many preimages, which can be seen as randomly output from all the exponentially many preimages and hence include the target plaintext with a negligible probability.


## 1.2.2. Probabilistic Compact Knapsack PKC

By using the concept of PSTOF and from the compact knapsack problem, a probabilistic public key encryption scheme is designed. An easy compact knapsack-type problem is defined, and an algorithm calledOnion Algorithm is developed to peel off the solutions to the easy problem. The easy problem is used to construct a probabilistic PKC. The main results are that the trapdoor one-way function underlying the proposal is PSTOFs under different linear attack models (See Theorems 25, 26, and 30), and the images of the PSTOFs have exponentially many preimages (see Table 3). Some design tricks are adopted to make the PKC immune from some known key-recovery attacks such as GCD attack [4, 5], Diophantine approximation attack [6, 7], and orthogonal lattice attack [8, 9].


## 1.3. Organization

The rest of the paper is organized as follows. In Section2, we formalize the definition of PSTOF and use the cryptographic scenario to explain some known PKCs. Section 3 provides a concrete probabilistic public key encryption scheme to realize the PSTOF. Sections 4 and 5 discuss the performance and security related issues, respectively. Section 6 gives some concluding remarks.


## 2. Preimage Selective Trapdoor One-Way Function

### 2.1. Symbols and Notations

The notations listed at the end of the paper will be used throughout the paper.


### 2.2. Message Encoding Function

When encrypting a message using a PKC, we need to firstly encode a binary string message into a plaintext (an element in the algebraic structure underlying the PKC) in order that the PKC can deal with the message. However, sometimes, it is not necessary to explicitly specify the encoding algorithm. For example, it is more convenient to just look a message as a binary integer inℤ
N than to develop an algorithm to transform a message into an element in ℤ
N in case of RSA [10]. Formally, we define a message encoding function as follows.Definition 1.
A functionF
:
𝕄
↦
𝕊
P with 𝕊
P
=
F
(
𝕄
)
=
{
F
(
m
)
∣
m
∈
𝕄
} is called a message encoding function if it satisfies the following conditions.(1)
The functionF is injective.
(2)
It can be efficiently performed to computeF
(
m
) for a given m
∈
𝕄, and F
-
1
(
p
) for a given p
∈
𝕊
P.


### 2.3.  Preimage Selective Trapdoor One-Way Function

The PSTOF is formalized as follows.Definition 2.
A functionT
:
𝕊
E
↦
ℂ
=
T
(
𝕊
E
) is called a PSTOF if it satisfies the following conditions. (1)
For an arbitraryx
∈
𝕊
E, it is easy to compute c
=
T
(
x
).
(2)
T is noninjective.
(3)
Given anyc
∈
ℂ, there exists at most an x
∈
𝕊
P such that T
(
x
)
=
c.
(4)
Given anyc
∈
ℂ and the trapdoor, there is a polynomial-time algorithm to output a unique x
∈
𝕊
P with T
(
x
)
=
c or the invalid ciphertext symbol ⊥.
(5)
Given anyc
∈
ℂ and without knowing the trapdoor, anyone cannot efficiently compute a preimage x
∈
𝕊
E such that T
(
x
)
=
c.Remark 3.
The third and the forth conditions in Definition2 guarantee that when viewed as a public key encryption function, the PSTOF is inverted according to the knowledge of the trapdoor σ to derive a unique preimage (the plaintext) in 𝕊
P, and both conditions in Definition 1 mean that the plaintext can be uniquely decoded into the original message. If we remove the last requirement in Definition 2, we just call T a preimage selective trapdoor (not non-way) function.Definition 4.
The preimage densityP
d of a noninjective function T is defined as the ratio of the cardinality of the preimage set 𝕊
E to that of the image set ℂ:
(1)
P
d
=
|
𝕊
E
|
|
ℂ
|
.
On average, a ciphertext will have P
d preimages in 𝕊
E.Remark 5.
WhenP
d is exponentially large, we can use the high noninjectivity of the underlying function T to hide a plaintext. On average, for a valid ciphertext c
=
T
(
x
) for a plaintext x
∈
𝕊
P, c will have exponentially many P
d preimages in 𝕊
E. So a polynomial-time adversary only can obtain polynomially many p preimages in 𝕊
E of c, which contains the targeted unique valid plaintext x
∈
𝕊
P with a negligible probability p
/
P
d. One may doubt that the function T is indeed a trapdoor one-way function mapping from 𝕊
P to ℂ. So if one breaks the one-wayness of T
:
𝕊
P
↦
ℂ, he also recovers the unique x
∈
𝕊
P such that c
=
T
(
x
). However, if the plaintext space 𝕊
P can be seen as randomly chosen from the whole equivalent plaintext space 𝕊
E, the adversary cannot use the special structure of 𝕊
P to develop an efficient algorithm for reversing the function T
:
𝕊
P
↦
ℂ. We will explain this point later on by using an example.


### 2.4.  Examples

#### 2.4.1. High-Density Knapsack PKCs

To illustrate the aforementioned definitions, we consider high-density 0-1 knapsack (subset sum) PKCs Chor-Rivest [11] and Okamoto-Tanaka-Uchiyama [12]. In both cryptosystems, a bit-string message is encoded into an n-dimensional 0-1 plaintext vector with a fixed k Hamming weight (the so-called predesignated special plaintext structure) by using the source encoding algorithm (message encoding function) [13]:
(2)
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}
⊂
{
0,1
}
n
=
𝕊
E
.
Let the public key a
=
(
a
1
,
…
,
a
n
). The underlying PSTOF is T
:
𝕊
E
↦
ℂ
=
{
0,1
,
…
,
∑
i
=
1
n
‍
a
i
}; that is, for x
∈
𝕊
E,
(3)
T
(
x
)
=
〈
a
,
x
〉
=
∑
i
=
1
n
‍
a
i
x
i
=
c
.
The density of both PKCs defined as d
=
n
/
lo
g
2
max
⁡
a can be made sufficiently high (>1), in which case asymptotically (3) will have more than one (i.e., P
d
>
1) binary solution [14]:
(4)
P
d
=
|
𝕊
E
|
|
ℂ
|
≥
2
n
n
max
⁡
a
=
2
n
n
2
n
/
d
=
2
(
1
-
1
/
d
)
n
-
lo
g
2
n
.The illustrations say that whend
>
1, a valid ciphertext will have exponentially many 2
(
1
-
1
/
d
)
n
-
lo
g
2
n preimages in 𝕊
E and a unique preimage in 𝕊
P. In other words, the plaintext is hidden by exponentially many preimages. Even if a polynomial-time adversary conquers the one-wayness of the underlying subset sum problem and hence the underlying encryption function is only a preimage selective trapdoor (not one-way) function; the adversary just obtains polynomially many preimages to (3) which contain the plaintext with a negligible probability. High-density subset sum PKCs can base their security on the noninjectivity of the underlying function, which is a weaker intractability assumption.Remark 6.
There exist two ways to break Chor-Rivest [11] and the Okamoto-Tanaka-Uchiyama [12] cryptosystems: recovering the secret key [15] and solving the underlying knapsack problem. Some work still was done to make Chor-Rivest immune from key-recovery attacks [16–18]. However, some known cryptanalytic algorithms [14, 19–21] only can solve the preimages x
∈
𝕊
E
=
{
0,1
}
n but not necessarily the unique plaintext x
∈
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}. So in the adversary’s point of view, the underlying problem remains the knapsack problem. This explains why we say in Remark 5 that the adversary cannot use the special structure of 𝕊
P to efficiently reverse the function T
:
𝕊
P
↦
ℂ.


#### 2.4.2.  Rabin Cryptosystem

We also can view Rabin cryptosystem [22] as a PSTOF. For convenience of discussions, we just set Rabin encryption function as c
=
x
2
(
mod
⁡
N
) with N
=
p
q being the product of two primes, and 𝕊
E
=
ℤ
N
*. So, the ciphertext space ℂ consists of the quadratic residues modulo N; that is, ℂ
=
ℚ
ℝ
N. In order to uniquely recover a plaintext, we need to embed some redundant information in 𝕊
E. The redundant information forms the special structure of 𝕊
P. The PSTOF underlying Rabin cryptosystem is T
:
ℤ
N
*
↦
ℚ
ℝ
N; for x
∈
ℤ
N
*, T
(
x
)
=
c
=
x
2
(
mod
⁡
N
). We note that each of the ϕ
(
N
)
/
4 quadratic residues modulo N has four roots, from which we use the redundant information to pick out the exact plaintext. Hence, the noninjectivity of the PSTOF for Rabin is given as
(5)
P
d
=
|
𝕊
E
|
|
ℂ
|
=
|
ℤ
N
*
|
|
ℚ
ℝ
N
|
=
ϕ
(
n
)
ϕ
(
n
)
/
4
=
4
.


## 2.1. Symbols and Notations

The notations listed at the end of the paper will be used throughout the paper.


## 2.2. Message Encoding Function

When encrypting a message using a PKC, we need to firstly encode a binary string message into a plaintext (an element in the algebraic structure underlying the PKC) in order that the PKC can deal with the message. However, sometimes, it is not necessary to explicitly specify the encoding algorithm. For example, it is more convenient to just look a message as a binary integer inℤ
N than to develop an algorithm to transform a message into an element in ℤ
N in case of RSA [10]. Formally, we define a message encoding function as follows.Definition 1.
A functionF
:
𝕄
↦
𝕊
P with 𝕊
P
=
F
(
𝕄
)
=
{
F
(
m
)
∣
m
∈
𝕄
} is called a message encoding function if it satisfies the following conditions.(1)
The functionF is injective.
(2)
It can be efficiently performed to computeF
(
m
) for a given m
∈
𝕄, and F
-
1
(
p
) for a given p
∈
𝕊
P.


## 2.3.  Preimage Selective Trapdoor One-Way Function

The PSTOF is formalized as follows.Definition 2.
A functionT
:
𝕊
E
↦
ℂ
=
T
(
𝕊
E
) is called a PSTOF if it satisfies the following conditions. (1)
For an arbitraryx
∈
𝕊
E, it is easy to compute c
=
T
(
x
).
(2)
T is noninjective.
(3)
Given anyc
∈
ℂ, there exists at most an x
∈
𝕊
P such that T
(
x
)
=
c.
(4)
Given anyc
∈
ℂ and the trapdoor, there is a polynomial-time algorithm to output a unique x
∈
𝕊
P with T
(
x
)
=
c or the invalid ciphertext symbol ⊥.
(5)
Given anyc
∈
ℂ and without knowing the trapdoor, anyone cannot efficiently compute a preimage x
∈
𝕊
E such that T
(
x
)
=
c.Remark 3.
The third and the forth conditions in Definition2 guarantee that when viewed as a public key encryption function, the PSTOF is inverted according to the knowledge of the trapdoor σ to derive a unique preimage (the plaintext) in 𝕊
P, and both conditions in Definition 1 mean that the plaintext can be uniquely decoded into the original message. If we remove the last requirement in Definition 2, we just call T a preimage selective trapdoor (not non-way) function.Definition 4.
The preimage densityP
d of a noninjective function T is defined as the ratio of the cardinality of the preimage set 𝕊
E to that of the image set ℂ:
(1)
P
d
=
|
𝕊
E
|
|
ℂ
|
.
On average, a ciphertext will have P
d preimages in 𝕊
E.Remark 5.
WhenP
d is exponentially large, we can use the high noninjectivity of the underlying function T to hide a plaintext. On average, for a valid ciphertext c
=
T
(
x
) for a plaintext x
∈
𝕊
P, c will have exponentially many P
d preimages in 𝕊
E. So a polynomial-time adversary only can obtain polynomially many p preimages in 𝕊
E of c, which contains the targeted unique valid plaintext x
∈
𝕊
P with a negligible probability p
/
P
d. One may doubt that the function T is indeed a trapdoor one-way function mapping from 𝕊
P to ℂ. So if one breaks the one-wayness of T
:
𝕊
P
↦
ℂ, he also recovers the unique x
∈
𝕊
P such that c
=
T
(
x
). However, if the plaintext space 𝕊
P can be seen as randomly chosen from the whole equivalent plaintext space 𝕊
E, the adversary cannot use the special structure of 𝕊
P to develop an efficient algorithm for reversing the function T
:
𝕊
P
↦
ℂ. We will explain this point later on by using an example.


## 2.4.  Examples

### 2.4.1. High-Density Knapsack PKCs

To illustrate the aforementioned definitions, we consider high-density 0-1 knapsack (subset sum) PKCs Chor-Rivest [11] and Okamoto-Tanaka-Uchiyama [12]. In both cryptosystems, a bit-string message is encoded into an n-dimensional 0-1 plaintext vector with a fixed k Hamming weight (the so-called predesignated special plaintext structure) by using the source encoding algorithm (message encoding function) [13]:
(2)
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}
⊂
{
0,1
}
n
=
𝕊
E
.
Let the public key a
=
(
a
1
,
…
,
a
n
). The underlying PSTOF is T
:
𝕊
E
↦
ℂ
=
{
0,1
,
…
,
∑
i
=
1
n
‍
a
i
}; that is, for x
∈
𝕊
E,
(3)
T
(
x
)
=
〈
a
,
x
〉
=
∑
i
=
1
n
‍
a
i
x
i
=
c
.
The density of both PKCs defined as d
=
n
/
lo
g
2
max
⁡
a can be made sufficiently high (>1), in which case asymptotically (3) will have more than one (i.e., P
d
>
1) binary solution [14]:
(4)
P
d
=
|
𝕊
E
|
|
ℂ
|
≥
2
n
n
max
⁡
a
=
2
n
n
2
n
/
d
=
2
(
1
-
1
/
d
)
n
-
lo
g
2
n
.The illustrations say that whend
>
1, a valid ciphertext will have exponentially many 2
(
1
-
1
/
d
)
n
-
lo
g
2
n preimages in 𝕊
E and a unique preimage in 𝕊
P. In other words, the plaintext is hidden by exponentially many preimages. Even if a polynomial-time adversary conquers the one-wayness of the underlying subset sum problem and hence the underlying encryption function is only a preimage selective trapdoor (not one-way) function; the adversary just obtains polynomially many preimages to (3) which contain the plaintext with a negligible probability. High-density subset sum PKCs can base their security on the noninjectivity of the underlying function, which is a weaker intractability assumption.Remark 6.
There exist two ways to break Chor-Rivest [11] and the Okamoto-Tanaka-Uchiyama [12] cryptosystems: recovering the secret key [15] and solving the underlying knapsack problem. Some work still was done to make Chor-Rivest immune from key-recovery attacks [16–18]. However, some known cryptanalytic algorithms [14, 19–21] only can solve the preimages x
∈
𝕊
E
=
{
0,1
}
n but not necessarily the unique plaintext x
∈
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}. So in the adversary’s point of view, the underlying problem remains the knapsack problem. This explains why we say in Remark 5 that the adversary cannot use the special structure of 𝕊
P to efficiently reverse the function T
:
𝕊
P
↦
ℂ.


### 2.4.2.  Rabin Cryptosystem

We also can view Rabin cryptosystem [22] as a PSTOF. For convenience of discussions, we just set Rabin encryption function as c
=
x
2
(
mod
⁡
N
) with N
=
p
q being the product of two primes, and 𝕊
E
=
ℤ
N
*. So, the ciphertext space ℂ consists of the quadratic residues modulo N; that is, ℂ
=
ℚ
ℝ
N. In order to uniquely recover a plaintext, we need to embed some redundant information in 𝕊
E. The redundant information forms the special structure of 𝕊
P. The PSTOF underlying Rabin cryptosystem is T
:
ℤ
N
*
↦
ℚ
ℝ
N; for x
∈
ℤ
N
*, T
(
x
)
=
c
=
x
2
(
mod
⁡
N
). We note that each of the ϕ
(
N
)
/
4 quadratic residues modulo N has four roots, from which we use the redundant information to pick out the exact plaintext. Hence, the noninjectivity of the PSTOF for Rabin is given as
(5)
P
d
=
|
𝕊
E
|
|
ℂ
|
=
|
ℤ
N
*
|
|
ℚ
ℝ
N
|
=
ϕ
(
n
)
ϕ
(
n
)
/
4
=
4
.


## 2.4.1. High-Density Knapsack PKCs

To illustrate the aforementioned definitions, we consider high-density 0-1 knapsack (subset sum) PKCs Chor-Rivest [11] and Okamoto-Tanaka-Uchiyama [12]. In both cryptosystems, a bit-string message is encoded into an n-dimensional 0-1 plaintext vector with a fixed k Hamming weight (the so-called predesignated special plaintext structure) by using the source encoding algorithm (message encoding function) [13]:
(2)
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}
⊂
{
0,1
}
n
=
𝕊
E
.
Let the public key a
=
(
a
1
,
…
,
a
n
). The underlying PSTOF is T
:
𝕊
E
↦
ℂ
=
{
0,1
,
…
,
∑
i
=
1
n
‍
a
i
}; that is, for x
∈
𝕊
E,
(3)
T
(
x
)
=
〈
a
,
x
〉
=
∑
i
=
1
n
‍
a
i
x
i
=
c
.
The density of both PKCs defined as d
=
n
/
lo
g
2
max
⁡
a can be made sufficiently high (>1), in which case asymptotically (3) will have more than one (i.e., P
d
>
1) binary solution [14]:
(4)
P
d
=
|
𝕊
E
|
|
ℂ
|
≥
2
n
n
max
⁡
a
=
2
n
n
2
n
/
d
=
2
(
1
-
1
/
d
)
n
-
lo
g
2
n
.The illustrations say that whend
>
1, a valid ciphertext will have exponentially many 2
(
1
-
1
/
d
)
n
-
lo
g
2
n preimages in 𝕊
E and a unique preimage in 𝕊
P. In other words, the plaintext is hidden by exponentially many preimages. Even if a polynomial-time adversary conquers the one-wayness of the underlying subset sum problem and hence the underlying encryption function is only a preimage selective trapdoor (not one-way) function; the adversary just obtains polynomially many preimages to (3) which contain the plaintext with a negligible probability. High-density subset sum PKCs can base their security on the noninjectivity of the underlying function, which is a weaker intractability assumption.Remark 6.
There exist two ways to break Chor-Rivest [11] and the Okamoto-Tanaka-Uchiyama [12] cryptosystems: recovering the secret key [15] and solving the underlying knapsack problem. Some work still was done to make Chor-Rivest immune from key-recovery attacks [16–18]. However, some known cryptanalytic algorithms [14, 19–21] only can solve the preimages x
∈
𝕊
E
=
{
0,1
}
n but not necessarily the unique plaintext x
∈
𝕊
P
=
{
x
∣
x
∈
{
0,1
}
n
,
H
w
(
x
)
=
k
}. So in the adversary’s point of view, the underlying problem remains the knapsack problem. This explains why we say in Remark 5 that the adversary cannot use the special structure of 𝕊
P to efficiently reverse the function T
:
𝕊
P
↦
ℂ.


## 2.4.2.  Rabin Cryptosystem

We also can view Rabin cryptosystem [22] as a PSTOF. For convenience of discussions, we just set Rabin encryption function as c
=
x
2
(
mod
⁡
N
) with N
=
p
q being the product of two primes, and 𝕊
E
=
ℤ
N
*. So, the ciphertext space ℂ consists of the quadratic residues modulo N; that is, ℂ
=
ℚ
ℝ
N. In order to uniquely recover a plaintext, we need to embed some redundant information in 𝕊
E. The redundant information forms the special structure of 𝕊
P. The PSTOF underlying Rabin cryptosystem is T
:
ℤ
N
*
↦
ℚ
ℝ
N; for x
∈
ℤ
N
*, T
(
x
)
=
c
=
x
2
(
mod
⁡
N
). We note that each of the ϕ
(
N
)
/
4 quadratic residues modulo N has four roots, from which we use the redundant information to pick out the exact plaintext. Hence, the noninjectivity of the PSTOF for Rabin is given as
(5)
P
d
=
|
𝕊
E
|
|
ℂ
|
=
|
ℤ
N
*
|
|
ℚ
ℝ
N
|
=
ϕ
(
n
)
ϕ
(
n
)
/
4
=
4
.


## 3. The Proposed Probabilistic Public Key Encryption Scheme

### 3.1. Knapsack Problems

Definition 7 (knapsack problem).
Given a positive integral vectora
=
(
a
1
,
…
,
a
n
) and an integer s
∈
ℤ, the knapsack or subset sum problem is to find a binary vector x
∈
{
0,1
}
n such that 〈
a
,
x
〉
=
s. A knapsack problem is denoted as KP
(
a
,
s
). The density of the knapsack problem KP
(
a
,
s
) is defined as d
=
n
/
lo
g
2
max
⁡
a.The density of a compact knapsack problemKP
(
a
,
s
) imposes an important effect on the hardness of the problem. It was shown that if the density d
<
0.9408, the knapsack problem KP
(
a
,
s
) can be solved with an overwhelming probability [23, 24].Definition 8 (compact knapsack problem).
Given a positive integral vectora
=
(
a
1
,
…
,
a
n
), an integer 2
≤
K
∈
ℤ
+, and an integer s
∈
ℤ, the compact or general knapsack problem is to find a vector x
=
(
x
1
,
…
,
x
n
) with 0
≤
x
i
≤
K
-
1 such that 〈
a
,
x
〉
=
s. A compact knapsack problem is denoted as CK
P
K
(
a
,
s
). The density of a compact knapsack problem CK
P
K
(
a
,
s
) is defined as d
=
n
lo
g
2
K
/
lo
g
2
max
⁡
a.
If the density of a compact knapsack problemCK
P
K
(
a
,
s
) is d
<
1, it was shown that the compact knapsack problem can almost always be efficiently solved with lattice reduction algorithms [25]. In this paper, we consider the compact knapsack problem with K
=
192.


### 3.2. The Proposed Message Encoding Function

The message space𝕄 consists of n blocks with each block 3 bit long; namely, 𝕄
=
ℤ
8
n. For a message m
=
(
m
1
,
…
,
m
n
)
∈
𝕄, we firstly define a message encoding function that maps the message m into a vector in Z
192
n under an auxiliary key r
=
(
r
1
,
…
,
r
n
)
∈
{
0,1
}
n, which is randomly chosen by the encrypter. We define F
i
:
ℤ
8
×
{
0,1
}
↦
ℤ
192 for i
=
1
,
…
,
n as
(6)
F
i
(
m
i
,
r
i
)
=
〈
5
8
(
i
-
1
)
+
m
i
-
1
〉
97
+
96
r
i
∈
ℤ
192
.Remark 9.
We note that 97 is a prime and 5 is a primitive root modulo 97, so the function0
≤
〈
5
x
-
1
〉
97
≤
95 forms a permutation when x runs through ℤ
96 and hence F
i
(
x
,
r
) permutates ℤ
192 when x and r run through ℤ
96 and {
0,1
}, respectively. We denote
(7)
F
i
=
{
F
i
(
m
i
,
r
i
)
∣
m
i
∈
ℤ
8
,
r
i
∈
{
0,1
}
}
.
It is easy to verify that ⋃
i
=
1
12
‍
F
i forms a partition of ℤ
192. So we can deduce that if i, m
i, and r
i are uniformly distributed over {
1
,
…
,
n
}, ℤ
8 and {
0,1
}, respectively, F
i
(
m
i
,
r
i
) is uniformly distributed over ℤ
192. This means that the generating of each F
i
(
m
i
,
r
i
)
∈
F
i can simulate the process of randomly choosing an integer from ℤ
192, which allows the predesignated special structure of 𝕊
P defined in (9) as random as possible.The message encoding function is defined asF
:
𝕄
×
{
0,1
}
n
↦
𝕊
P:
(8)
F
(
m
,
r
)
=
(
F
1
(
m
1
,
r
1
)
,
…
,
F
n
(
m
n
,
r
n
)
)
,
where the plaintext space is
(9)
𝕊
P
=
{
F
(
m
,
r
)
∣
m
∈
𝕄
,
r
∈
{
0,1
}
n
}
=
F
1
×
⋯
×
F
n
.
In the rest of the paper, we also define the equivalent plaintext space 𝕊
E
=
ℤ
192
n including the plaintext space 𝕊
P
⊂
𝕊
E.Remark 10.
Another fact aboutF
i is
(10)
F
i
(
m
,
r
)
=
F
i
+
12
(
m
,
r
)
,
for m
∈
ℤ
8 and r
∈
{
0,1
} because 5
96
=
1
(
mod
⁡
97
). Hence, we have that if i
=
j
(
mod
⁡
12
), F
i
=
F
j.Remark 11.
Now we remark on how to encode a message and decode a plaintext with respect toF. We can construct n tables similar to truth-value tables to show the functions F
j. By observing (10), we see that the tables have a periodic structure with period 12. That is to say those j sharing a common residue modulo 12 have a same table. So only 12 tables suffice to list the values of F
(
m
,
r
). See Table 1. Here, we spend some more words on the message encoding function and Table 1. At present, we only consider the preceding three columns of the 12 subtables in Table 1, which list the values of r
j, m
j, and the corresponding F
j
(
m
j
,
r
j
), respectively. To encode a message m
∈
𝕄 and given a randomly chosen auxiliary key r
∈
{
0,1
}
n, for i
=
1
,
…
,
n, we determine the F
i
(
m
i
,
r
i
) one by one by looking up the subtable indexed by i
=
〈
j
〉
12
(
mod
⁡
12
) in Table 1 denoted as Sub-T〈
j
〉
12. When r
i
=
0 (or  1, resp.), we only search the 8 rows covered by r
i
=
0 (or 1, resp.) in Sub-T〈
j
〉
12, and output the integer in the column marked by F
i that lies in the same row with m
i as the value of F
i
(
m
i
,
r
i
). For example, to encode m
=
(
5,4
,
7,6
) under the control of r
=
(
0,1
,
1,0
), by looking up Sub-T1, we determine F
1
(
m
1
,
r
1
)
=
20. Similarly, we get F
2
(
m
2
,
r
2
)
=
159, F
3
(
m
3
,
r
3
)
=
177, F
4
(
m
4
,
r
4
)
=
78. So, we encode (
5,4
,
7,6
) as F
(
m
,
r
)
=
(
20,159,177,78
). On the contrary, we can decode a plaintext x
∈
𝕊
P by looking up the table. For example, x
=
(
100,101,76,6
). We search the third column of Sub-T1 for 100 which lies in the same line with m
1
=
1, so m
1
=
1. Similarly, we get m
2
=
0, m
3
=
5, m
2
=
7. Hence, m
=
(
1,0
,
5,7
).Table 1
The values ofF
i
(
M
i
,
r
i
) and their associated integer pairs.
(a)
i
=
1 (mod 12)
r
i
m
i
F
i
mod (1, 34)
mod (2, 17)
0
0
0
(0, 0)
(0, 0)
1
4
(0, 4)
(1, 4)
2
24
(0, 24)
(0, 7)
3
27
(0, 27)
(1, 10)
4
42
(0, 8)
(0, 8)
5
20
(0, 20)
(0, 3)
6
7
(0, 7)
(1, 7)
7
39
(0, 5)
(1, 5)
1
0
96
(0, 28)
(0, 11)
1
100
(0, 32)
(0, 15)
2
120
(0, 18)
(0, 1)
3
123
(0, 21)
(1, 4)
4
138
(0, 2)
(0, 2)
5
116
(0, 14)
(0, 14)
6
103
(0, 1)
(1, 1)
7
135
(0, 33)
(1, 16)
(b)
i
=
2 (mod 12)
r
i
m
i
F
i
mod (1, 33)
mod (3, 11)
0
0
5
(0, 5)
(2, 5)
1
29
(0, 29)
(2, 7)
2
52
(0, 19)
(1, 8)
3
70
(0, 4)
(1, 4)
4
63
(0, 30)
(0, 8)
5
28
(0, 28)
(1, 6)
6
47
(0, 14)
(2, 3)
7
45
(0, 12)
(0, 1)
1
0
101
(0, 2)
(2, 2)
1
125
(0, 26)
(2, 4)
2
148
(0, 16)
(1, 5)
3
166
(0, 1)
(1, 1)
4
159
(0, 27)
(0, 5)
5
124
(0, 25)
(1, 3)
6
143
(0, 11)
(2, 0)
7
141
(0, 9)
(0, 9)
(c)
i
=
3 (mod 12)
r
i
m
i
F
i
mod (1, 31)
mod (1, 37)
0
0
35
(0, 4)
(0, 35)
1
82
(0, 20)
(0, 8)
2
26
(0, 26)
(0, 26)
3
37
(0, 6)
(0, 0)
4
92
(0, 30)
(0, 18)
5
76
(0, 14)
(0, 2)
6
93
(0, 0)
(0, 19)
7
81
(0, 19)
(0, 7)
1
0
131
(0, 7)
(0, 20)
1
178
(0, 23)
(0, 30)
2
122
(0, 29)
(0, 11)
3
133
(0, 9)
(0, 22)
4
188
(0, 2)
(0, 3)
5
172
(0, 17)
(0, 24)
6
189
(0, 3)
(0, 4)
7
177
(0, 22)
(0, 29)
(d)
i
=
4 (mod 12)
r
i
m
i
F
i
mod (1, 46)
mod (2, 23)
0
0
21
(0, 21)
(1, 21)
1
12
(0, 12)
(0, 12)
2
64
(0, 18)
(0, 18)
3
33
(0, 33)
(1, 10)
4
72
(0, 26)
(0, 3)
5
73
(0, 27)
(1, 4)
6
78
(0, 32)
(0, 9)
7
6
(0, 6)
(0, 6)
1
0
117
(0, 25)
(1, 2)
1
108
(0, 16)
(0, 1)
2
160
(0, 22)
(0, 22)
3
129
(0, 37)
(1, 14)
4
168
(0, 30)
(0, 7)
5
169
(0, 31)
(1, 8)
6
174
(0, 36)
(0, 13)
7
102
(0, 10)
(0, 10)
(e)
i
=
5 (mod  12)
r
i
m
i
F
i
mod (1, 29)
mod (1, 47)
0
0
34
(0, 5)
(0, 34)
1
77
(0, 19)
(0, 30)
2
1
(0, 1)
(0, 1)
3
9
(0, 9)
(0, 9)
4
49
(0, 20)
(0, 2)
5
55
(0, 26)
(0, 8)
6
85
(0, 27)
(0, 38)
7
41
(0, 12)
(0, 41)
1
0
130
(0, 14)
(0, 36)
1
173
(0, 28)
(0, 32)
2
97
(0, 10)
(0, 3)
3
105
(0, 18)
(0, 11)
4
145
(0, 0)
(0, 4)
5
151
(0, 6)
(0, 10)
6
181
(0, 7)
(0, 40)
7
137
(0, 21)
(0, 43)
(f)
i
=
6 (mod 12)
r
i
m
i
F
i
mod (1, 39)
mod (3, 13)
0
0
15
(0, 15)
(0, 2)
1
79
(0, 1)
(1, 1)
2
11
(0, 11)
(2, 11)
3
59
(0, 20)
(2, 7)
4
8
(0, 8)
(2, 8)
5
44
(0, 5)
(2, 5)
6
30
(0, 30)
(0, 4)
7
57
(0, 18)
(0, 5)
1
0
111
(0, 33)
(0, 7)
1
175
(0, 19)
(1, 6)
2
107
(0, 29)
(2, 3)
3
155
(0, 38)
(2, 12)
4
104
(0, 26)
(2, 0)
5
140
(0, 23)
(2, 10)
6
126
(0, 9)
(0, 9)
7
153
(0, 36)
(0, 20)
(g)
i
=
7 (mod 12)
r
i
m
i
F
i
mod (1, 34)
mod (2, 17)
0
0
95
(0, 27)
(1, 10)
1
91
(0, 23)
(1, 6)
2
71
(0, 3)
(1, 3)
3
68
(0, 0)
(0, 0)
4
53
(0, 19)
(1, 2)
5
75
(0, 7)
(1, 7)
6
88
(0, 20)
(0, 3)
7
56
(0, 22)
(0, 5)
1
0
191
(0, 21)
(1, 4)
1
187
(0, 17)
(1, 0)
2
167
(0, 31)
(1, 14)
3
164
(0, 28)
(0, 11)
4
149
(0, 13)
(1, 13)
5
171
(0, 1)
(1, 1)
6
184
(0, 14)
(0, 14)
7
152
(0, 16)
(0, 16)
(h)
i
=
8 (mod 12)
r
i
m
i
F
i
mod (1, 33)
mod (3, 11)
0
0
90
(0, 24)
(0, 2)
1
66
(0, 0)
(0, 0)
2
43
(0, 10)
(1, 10)
3
25
(0, 25)
(1, 3)
4
32
(0, 32)
(2, 10)
5
67
(0, 1)
(1, 1)
6
48
(0, 15)
(0, 4)
7
50
(0, 17)
(2, 6)
1
0
186
(0, 21)
(0, 10)
1
162
(0, 30)
(0, 8)
2
139
(0, 7)
(1, 7)
3
121
(0, 22)
(1, 0)
4
128
(0, 29)
(2, 7)
5
163
(0, 31)
(1, 9)
6
144
(0, 12)
(0, 1)
7
146
(0, 14)
(2, 3)
(i)
i
=
9 (mod 12)
r
i
m
i
F
i
mod (1, 31)
mod (1, 37)
0
0
60
(0, 29)
(0, 23)
1
13
(0, 13)
(0, 13)
2
69
(0, 7)
(0, 32)
3
58
(0, 27)
(0, 21)
4
3
(0, 3)
(0, 3)
5
19
(0, 19)
(0, 19)
6
2
(0, 2)
(0, 2)
7
14
(0, 14)
(0, 14)
1
0
156
(0, 1)
(0, 8)
1
109
(0, 16)
(0, 35)
2
165
(0, 10)
(0, 17)
3
154
(0, 30)
(0, 6)
4
99
(0, 6)
(0, 25)
5
115
(0, 22)
(0, 4)
6
98
(0, 5)
(0, 24)
7
110
(0, 17)
(0, 36)
(j)
i
=
10  (mod 12)
r
i
m
i
F
i
mod (1, 46)
mod (2, 23)
0
0
74
(0, 28)
(0, 5)
1
83
(0, 37)
(1, 14)
2
31
(0, 31)
(1, 8)
3
62
(0, 16)
(0, 16)
4
23
(0, 23)
(1, 0)
5
22
(0, 22)
(0, 22)
6
17
(0, 17)
(1, 17)
7
89
(0, 43)
(1, 20)
1
0
170
(0, 32)
(0, 9)
1
179
(0, 41)
(1, 18)
2
127
(0, 35)
(1, 12)
3
158
(0, 20)
(0, 20)
4
119
(0, 27)
(1, 4)
5
118
(0, 26)
(0, 3)
6
113
(0, 21)
(1, 21)
7
185
(0, 1)
(1, 1)
(k)
i
=
11 (mod 12)
r
i
m
i
F
i
mod (1, 29)
mod (1, 47)
0
0
61
(0, 3)
(0, 14)
1
18
(0, 18)
(0, 18)
2
94
(0, 7)
(0, 0)
3
86
(0, 28)
(0, 39)
4
46
(0, 17)
(0, 46)
5
40
(0, 11)
(0, 40)
6
10
(0, 10)
(0, 10)
7
54
(0, 25)
(0, 7)
1
0
157
(0, 12)
(0, 16)
1
114
(0, 27)
(0, 20)
2
190
(0, 16)
(0, 2)
3
182
(0, 8)
(0, 41)
4
142
(0, 26)
(0, 1)
5
136
(0, 20)
(0, 42)
6
106
(0, 19)
(0, 12)
7
150
(0, 5)
(0, 9)
(l)
i
=
0 (mod 12)
r
i
m
i
F
i
mod (1, 39)
mod (3, 13)
0
0
80
(0, 2)
(2, 2)
1
16
(0, 16)
(1, 3)
2
84
(0, 6)
(0, 6)
3
36
(0, 36)
(0, 10)
4
87
(0, 9)
(0, 9)
5
51
(0, 12)
(0, 12)
6
65
(0, 26)
(2, 0)
7
38
(0, 38)
(2, 12)
1
0
176
(0, 20)
(2, 7)
1
112
(0, 34)
(1, 11)
2
180
(0, 24)
(0, 11)
3
132
(0, 15)
(0, 2)
4
183
(0, 27)
(0, 1)
5
147
(0, 30)
(0, 4)
6
161
(0, 5)
(2, 5)
7
134
(0, 17)
(2, 4)


### 3.3. Onion Algorithm

#### 3.3.1. Indistinguishability and Associated Integer Pairs

Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2 and f
i
∈
F
i, we define f
i
(
mod
⁡
(
a
,
b
)
)
=
(
f
i
(
mod
⁡
a
)
,
f
i
(
mod
⁡
b
)
) and the set F
i
(
mod
⁡
(
a
,
b
)
)
=
{
f
i
(
mod
⁡
(
a
,
b
)
)
∣
f
i
∈
F
i
}. In fact, we can look F
i
(
mod
⁡
(
a
,
b
)
) as a transformation on F
i. If the two cardinalities are identical, |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, the transformation forms a bijection.Definition 12.
Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2, if |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, we call F
i to be distinguishable modulo (
a
,
b
), or (
a
,
b
) is an associated integer pair with F
i.Example 13.
Decide whetherF
61 is distinguishable modulo (
1,34
) and (
2,19
) or not, respectively. We note that F
61
=
F
1 contains the integers listed in the third column of  Sub-T1. Calculations show that |
F
61
|
=
|
F
61
(
mod
⁡
(
1,34
)
)
|
=
16. The 16 values in F
61
(
mod
⁡
(
1,34
)
) are listed in the forth column of Sub-T1. So, F
61 is distinguishable modulo (
1,34
). However, |
F
61
|
=
16
≠
|
F
61
(
mod
⁡
(
2,19
)
)
|
=
14 in that 4 and 42 modulo (
2,19
) produce a same integer pair (
0,4
), and 24 and 138 modulo (
2,19
) produce a same integer pair (
0,5
). So F
61 is not distinguishable modulo (
2,19
).Remark 14.
WhenF
i is distinguishable modulo (
a
,
b
), there is a bijection between the integers in F
i and the integer pairs in F
i
(
mod
⁡
(
a
,
b
)
). For example, the third and the forth columns of Sub-T1 listed the integers in F
1 and the integer pairs in F
1
(
mod
⁡
(
1,34
)
). For example, if we know an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
), we search the forth column generated by F
1
(
mod
⁡
(
1,34
)
) for (
0,32
) in Sub- T1 and find that (
0,32
) lies in the same line with 100, so f
1
=
100.Remark 15.
From Remark10, we have that, for congruent indices j’s modulo 12, we get a same set F
j
(
mod
⁡
(
a
,
b
)
). For each i
=
〈
j
〉
12
(
mod
⁡
12
), we give two integer pairs (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
) associated with F
i, and the corresponding integer pairs modulo (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
), respectively, in the forth and fifth column of Sub-T〈
j
〉
12. We denote the set consisting of the two integer pairs (
a
j
1
,
b
j
1
) and (
a
j
2
,
b
j
2
) as AIP〈
j
〉
12. For example, AIP〈
73
〉
12=AIP1
=
{
(
1,34
)
,
(
2,17
)
}. In Table 2, we list all the 12 sets of AIP〈
j
〉
12.Table 2
Associated integer pairs withF
i.
Set
Associated integer pairs
AIP1
{
(
1,34
)
,
(
2,17
)
}
AIP2
{
(
1,33
)
,
(
3,11
)
}
AIP3
{
(
1,31
)
,
(
1,37
)
}
AIP4
{
(
1,46
)
,
(
2,23
)
}
AIP5
{
(
1,29
)
,
(
1,47
)
}
AIP6
{
(
1,39
)
,
(
3,13
)
}
AIP7
{
(
1,34
)
,
(
2,17
)
}
AIP8
{
(
1,33
)
,
(
3,11
)
}
AIP9
{
(
1,31
)
,
(
1,37
)
}
AIP10
{
(
1,46
)
,
(
2,23
)
}
AIP11
{
(
1,29
)
,
(
1,47
)
}
AIP0
{
(
1,39
)
,
(
3,13
)
}Table 3
Suggested security parameters.
Security level
Moderate
Higher
Highest
n
60
90
120
Public key size
21282
47025
82796
Information rate
0.49
0.50
0.51
Costs for BFA I
2
240
2
360
2
480
Costs for BFA II
2
125.9
2
186.5
2
246.9
P
d
1
2
86.9
2
146.1
2
205.7
P
d
2
2
587.8
2
899.4
2
1211.6
P
d
3
2
111.4
2
183
2
255.1Remark 16.
Note thatF
i is distinguishable modulo (
a
,
b
) if and only if F
i is distinguishable modulo (
b
,
a
)
=
(
a
,
b
)
T. For example, AIP
1
T
=
{
(
34,1
)
,
(
17,2
)
} also contains integer pairs associated with F
1. If we know that an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
), we also can determine the value of f
1 by searching the forth column generated by F
1
(
mod
⁡
(
1,34
)
) in Sub-T1 for (
0,32
), and we find a unique f
1
=
100 with f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
). So the unique integer f
1
∈
F
1 is f
1
=
100 such that f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
).


#### 3.3.2. Simultaneous Diophantine Equation

Now, we consider a simultaneous Diophantine equation problem as follows; given integerss
1 and s
2 and positive integer sequences u
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
), find x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P defined in (9) such that
(11)
s
1
=
〈
u
,
x
〉
,
s
2
=
〈
v
,
x
〉
.
It is pointed out that if max
⁡
u
≤
2
d
u
n and max
⁡
v
≤
2
d
v
n, for some constants d
u and d
v subject to d
u
+
d
v
<
lo
g
2
192, (
s
1
,
s
2
) will have exponentially many preimages in 𝕊
E
=
ℤ
192
n satisfying (11); namely,
(12)
P
d
≥
|
𝕊
E
|
(
191
max
⁡
u
)
(
191
max
⁡
v
)
≥
19
2
n
19
1
2
2
d
u
+
d
v
,
which is 𝒪
(
2
lo
g
2
192
-
d
u
-
d
v
). What we mean is that if we require x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
E and d
u
+
d
v
<
lo
g
2
192, (11) will be a many-to-one function. In the subsequent contents, we will define a condition such that (11) will have at most one solution in 𝕊
P (to guarantee the unique decipherability for ciphertexts) and propose an algorithm to solve (11). Besides, some transformations will be introduced in the construction of the proposed PKC to derive a compact knapsack problem equipped with noninjectivity, a trapdoor, and one-wayness natures.


#### 3.3.3. An Easy Problem and the Algorithm Solving It

For some specialu and v, we can efficiently determine f
n in (11) as stated in the following lemma.Lemma 17.
Assuming that (11) has solutions in 𝕊
P, g
c
d
n
u
=
g
c
d
n
v
=
1, and (
g
c
d
n
-
1
u
,
g
c
d
n
-
1
v
)
∈
A
I
P
〈
n
〉
12
∪
A
I
P
〈
n
〉
12
T, then f
n
∈
F
n can be efficiently and uniquely determined.Proof.
We first note thatgc
d
n
-
1
u
∣
u
i and gc
d
n
-
1
v
∣
v
i, for i
=
1
,
…
,
n
-
1, so the two equations in (11) modulo gc
d
n
-
1
u and gc
d
n
-
1
v, respectively, give s
1
=
u
n
f
n
(
mod
⁡
gc
d
n
-
1
u
) and s
2
=
v
n
f
n
(
mod
⁡
gc
d
n
-
1
v
). Observing that gc
d
n
u
=
gcd
(
gc
d
n
-
1
u
,
u
n
)
=
1, we can invert u
n and similarly v
n:
(13)
(
f
n
1
,
f
n
2
)
=
f
n
(
mod
⁡
(
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
)
=
(
u
n
-
1
s
1
(
mod
⁡
gc
d
n
-
1
u
)
,
v
n
-
1
s
2
(
mod
⁡
gc
d
n
-
1
v
)
)
.
If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12, we determine the unique corresponding value f
n according to Remark 14. If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
T, we use the method given in Remark 16 to determine the unique f
n.The above lemma says that for some specialu and v, we can determine the solution f
n
,
…
,
f
1 to (11) one by one as if we peel off an onion, so the nameOnion Algorithm comes.Theorem 18.
Assuming that (11) has solutions in 𝕊
P:
(14)
g
c
d
n
u
=
g
c
d
n
v
=
1
,
and that, for i
=
2
,
…
,
n,
(15)
(
g
c
d
i
-
1
u
g
c
d
i
u
,
g
c
d
i
-
1
v
g
c
d
i
v
)
∈
A
I
P
〈
i
〉
12
∪
A
I
P
〈
i
〉
12
T
,
the solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11) can be efficiently and uniquely determined.Proof.
From Lemma17, f
n can be efficiently and uniquely determined.
Fori
=
n
-
1
,
…
,
2, assuming that f
i
+
1
,
…
,
f
n have been uniquely determined, we know that
(16)
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
=
∑
j
=
1
i
‍
u
j
f
j
.
We note that gc
d
i
u
∣
u
j for 1
≤
j
≤
i, so gc
d
i
u divides the right side and hence the left side of (16). We set
(17)
s
i
1
=
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
gc
d
i
u
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
.
A similar analysis also applies to the second equation of (11), so we set s
i
2
=
(
s
2
-
∑
j
=
i
+
1
n
‍
v
j
f
j
)
/
gc
d
i
v to obtain
(18)
s
i
1
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
,
s
i
2
=
∑
j
=
1
i
‍
v
j
gc
d
i
v
f
j
.
If we view (18) as a new simultaneous Diophantine equation problem with integer sequences (
u
1
/
gc
d
i
u
,
…
,
u
i
/
gc
d
i
u
) and (
v
1
/
gc
d
i
v
,
…
,
v
i
/
gc
d
i
v
), what follows shows that the new problem satisfies the conditions in Lemma 17.
Firstly, (11) has solutions, and f
i
+
1
,
…
,
f
n have been uniquely determined, so (18) must have solutions.
Secondly, recalling the meaning ofgc
d
i
u, we claim that these entries divided by their gcd must be relatively prime:
(19)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
gc
d
i
u
)
=
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
gc
d
i
v
)
=
1
.
Thirdly,(20)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
-
1
gc
d
i
u
)
=
gc
d
i
-
1
u
gc
d
i
u
,
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
-
1
gc
d
i
v
)
=
gc
d
i
-
1
v
gc
d
i
v
.
From (15) and the previous two proven things, we know that (18) indeed satisfies the conditions in Lemma 17. So we can efficiently determine a unique f
i
∈
F
i.
Finally, oncef
2
,
…
,
f
n have been uniquely determined, it is a trivial thing to determine a unique f
1 just by computing
(21)
f
1
=
s
1
-
∑
i
=
2
n
‍
u
i
f
i
u
1
or
s
2
-
∑
i
=
2
n
‍
v
i
f
i
v
1
.
Both values on the right side of the above equation must be not only identical but also in F
1 because (11) has solutions in 𝕊
P and f
2
,
…
,
f
n have been uniquely determined.Given the problem (11), satisfying the conditions presented in Theorem 18, theOnion Algorithm for solving (11) is summarized as shown in Algorithm 1.Algorithm 1:
Onion Algorithm.
(1) Compute(
f
n
1
,
f
n
2
) according to (13).
(2)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12  then
(3)  Search for(
f
n
1
,
f
n
2
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
)
=
(
f
n
1
,
f
n
2
). Store f
n.
(4)end if
(5)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12
T  then
(6)  Search for(
f
n
2
,
f
n
1
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
)
=
(
f
n
2
,
f
n
1
). Store f
n.
(7)end if
(8)for  i
=
n
-
1
,
…
,
2  do
(9) Compute (18) and
(
f
i
1
,
f
i
2
)
=
(
s
i
1
(
u
i
gcd
i
u
)
-
1
(
mod
⁡
gcd
i
-
1
u
gcd
i
u
)
,
s
i
2
(
v
i
gcd
i
v
)
-
1
(
mod
⁡
gcd
i
-
1
v
gcd
i
v
)
)
. (*)
(10)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12  then
(11)Search the column in Sub-T
〈
i
〉
12  generated
byF
i modulo (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
for(
f
i
1
,
f
i
2
) such that (
f
i
1
,
f
i
2
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
). Store
f
i.
(12)
end if
(13)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12
T  then
(14)Search the column in Sub-T
〈
i
〉
12 generated
byF
i modulo (
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
for(
f
i
2
,
f
i
1
) such that (
f
i
2
,
f
i
1
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
). Store
f
i.
(15)
end if
(16)end for
(17) Compute and storef
1
=
(
s
1
-
∑
i
=
2
n
‍
u
i
f
i
)
/
u
1.
(18)return  x
=
(
f
1
,
…
,
f
n
).Now we use a toy example to illustrate what we discuss in this subsection about theOnion Algorithm.Example 19.
Assume that the following equations have solutions in𝕊
P; find the solution x
=
(
f
1
,
f
2
,
f
3
) to 11
f
1  +  9
f
2  +  13
f
3
=
2926, 93
f
1  +  62
f
2  +  89
f
3
=
20783. We can verify that (
gc
d
3
u
,
gc
d
3
v
)
=
(
1,1
), (
gc
d
2
u
,
gc
d
2
v
)
=
(
1,31
), (
gc
d
1
u
,
gc
d
1
v
)
=
(
11,93
), and (
gc
d
2
u
/
gc
d
3
u
,
gc
d
2
v
/
gc
d
3
v
)
=
(
1,31
)
∈
AI
P
3
,
(
gc
d
1
u
/
gc
d
2
u
,
gc
d
1
v
/
gc
d
2
v
)
=
(
11,3
)
∈
AI
P
2
T, so (14) and (15) are satisfied. Hence, we use theOnion Algorithm to compute (
f
31
,
f
32
)
=
(
2926
×
1
3
-
1
(
mod
⁡
1
)
,
20783
×
8
9
-
1
(
mod
⁡
31
)
)
=
(
0,20
). We look up  Sub-T3 and find that f
3
=
82
(
mod
⁡
(
1,31
)
)
=
(
0,20
). So f
3
=
82. We compute s
21
=
(
2926
-
13
×
82
)
/
1
=
1860, s
22
=
(
20783
-
89
×
82
)
/
31
=
435. Then we compute (
f
21
,
f
22
)
=
(
1860
×
9
-
1
(
mod
⁡
11
)
,
435
×
(
62
/
31
)
-
1
(
mod
⁡
93
/
31
)
)
=
(
5,0
). We search Sub-T2 for (
0,5
) and find that f
2
=
159
(
mod
⁡
(
3,11
)
)
=
(
0,5
). So we determine f
2
=
159. Finally, we get f
1
=
(
2926
-
9
×
159
-
13
×
82
)
/
11
=
39. Thus, a unique x
=
(
39,159,82
) is determined.


### 3.4.  The Proposed Probabilistic Public Key Encryption

In this subsection, we use the results obtained in previous subsections to derive a probabilistic public key encryption.


#### 3.4.1. Key Generation

Randomly choose two sequencesu
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
)
∈
(
ℤ
+
)
n, satisfying conditions (14) and (15) given in Theorem 18, and a two-dimensional invertible square matrix with positive integer entries upper bounded by a constant,
(22)
Δ
=
(
δ
11
δ
12
δ
21
δ
22
)
,
δ
i
j
=
𝒪
(
1
)
,
1
≤
i
,
j
≤
2
.
Compute
(23)
(
g
h
)
=
(
g
1
⋯
g
n
h
1
⋯
h
n
)
=
Δ
(
u
v
)
.
Randomly choose two primes p
≠
q such that
(24)
p
>
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
>
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.
Let N
=
p
q. Compute the vector b
=
(
b
1
,
…
,
b
n
) using the Chinese remainder theorem,
(25)
b
i
≡
g
i
(
mod
⁡
p
)
,
b
i
≡
h
i
(
mod
⁡
q
)
.
Randomly choose an integer w
∈
ℤ
N
* and compute
(26)
a
i
=
w
b
i
(
mod
⁡
N
)
,
i
=
1
,
…
,
n
.
The public key is a
=
(
a
1
,
…
,
a
n
). The secret key consists of p, q, and w
-
1
(
mod
⁡
N
), Δ
-
1. When decrypting a ciphertext, the decrypter also needs to store the values of gc
d
i
u, gc
d
i
v, i
=
1
,
…
,
n, and Table 1.


#### 3.4.2. Encryption

To encrypt a messagem
=
(
m
1
,
…
,
m
n
)
∈
𝕄
=
ℤ
8
n, the encrypter randomly chooses an auxiliary key r
=
(
r
1
,
…
,
r
n
)
∈
{
0,1
}
n and computes the plaintext x
=
(
f
1
,
…
,
f
n
)
=
F
(
m
,
r
) and the ciphertext using the public key a,
(27)
c
=
〈
a
,
x
〉
.


#### 3.4.3. Decryption

To decipher a ciphertextc, the decrypter firstly computes c
N
=
〈
w
-
1
c
〉
N
=
w
-
1
c
(
mod
⁡
N
), and then c
p
=
〈
c
N
〉
p, c
q
=
〈
c
N
〉
q. Secondly, the decrypter computes
(28)
(
s
1
s
2
)
=
Δ
-
1
(
c
p
c
q
)
.
Thirdly, the decrypter uses theOnion Algorithm to determine a unique solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11). Finally, the decrypter decodes x into the corresponding message m by using the method illustrated in Remark 11.


#### 3.4.4.  Why Decryption Works

To illustrate why the decryption works, we observe thatc
N
=
〈
b
,
x
〉
(
mod
⁡
N
) from (26), so c
p
=
〈
g
,
x
〉
(
mod
⁡
p
) and c
q
=
〈
h
,
x
〉
(
mod
⁡
q
) according to (25). From (23), we know that g
i
=
δ
11
u
i
+
δ
12
v
i
>
0, so 0
≤
c
p
<
p from (24). Now we conclude that c
p
=
〈
g
,
x
〉 and similarly c
q
=
〈
h
,
x
〉. Hence, we have
(29)
(
s
1
s
2
)
=
Δ
-
1
(
g
h
)
(
f
1
⋮
f
n
)
=
(
u
v
)
(
f
1
⋮
f
n
)
,
from which (11) is derived. It is easy to verify that (11) satisfies the conditions listed in Theorem 18, and hence can be efficiently solved withOnion Algorithm to give a unique solution x
∈
𝕊
P. Then x is decoded into the original message m.


#### 3.4.5. On Generatingu and v

Now, we give an algorithm to generate then-dimensional positive integer sequences u and v satisfying conditions (14) and (15) in Theorem 18.Theorem 20.
The generatedu and v satisfy (14) and (15).Proof.
We note that, fori
=
1
,
…
,
n,
(30)
gc
d
i
u
=
gcd
(
u
1
,
…
,
u
i
)
=
gcd
(
ζ
1
∏
j
=
1
n
‍
α
j
,
…
,
ζ
i
∏
j
=
i
n
‍
α
j
)
=
gcd
(
∏
j
=
1
n
‍
α
j
,
…
,
∏
j
=
i
n
‍
α
j
)
=
∏
j
=
i
n
‍
α
j
.
Similarly, gc
d
i
v
=
gcd
(
v
1
,
…
,
v
i
)
=
∏
j
=
i
n
‍
β
j. We immediately have gc
d
n
u
=
α
n
=
gc
d
n
v
=
β
n
=
1. Thus, (14) is satisfied. For i
=
2
,
…
,
n, we have
(31)
(
gc
d
i
-
1
u
gc
d
i
u
,
gc
d
i
-
1
v
gc
d
i
v
)
=
(
∏
j
=
i
-
1
n
‍
α
j
∏
j
=
i
n
‍
α
j
,
∏
j
=
i
-
1
n
‍
β
j
∏
j
=
i
n
‍
β
j
)
=
(
α
i
-
1
,
β
i
-
1
)
∈
AI
P
〈
i
〉
12
∪
AI
P
〈
i
〉
12
T
,
so (15) is satisfied, as desired.Now we use an example to illustrate Algorithm2.Algorithm 2:Generating u and v.
(1) Fori
=
1
,
…
,
n
-
1, randomly choose (
α
i
,
β
i
)
∈
AIP
〈
i
+
1
〉
12
∪
AIP
〈
i
+
1
〉
12
T with repetition permitted.
(2) Randomly choose2
(
n
-
1
) numbers ζ
2
,
…
,
ζ
n and
η
2
,
…
,
η
n and set ζ
1
=
η
1
=
α
n
=
β
n
=
1 such that
gcd
(
ζ
i
,
α
j
)
=
gcd
(
η
i
,
β
j
)
=
1 for 1
≤
i
,
j
≤
n, and
gcd
(
ζ
i
,
ζ
i
+
1
)
=
gcd
(
η
i
,
η
i
+
1
)
=
1 for i
=
1
,
…
,
n
-
1.
(3)for  i
=
1
,
…
,
n  do
(4)u
i
=
ζ
i
∏
j
=
i
n
‍
α
j,  v
i
=
η
i
∏
j
=
i
n
‍
β
j.   (★)
(5)end for
(6)return  u
=
(
u
1
,
…
,
u
n
), v
=
(
v
1
,
…
,
v
n
).Example 21.
We randomly choose(
α
1
,
β
1
)
=
(
11,3
)
∈
AI
P
2
∪
AI
P
2
T, (
α
2
,
β
2
)
=
(
1,31
)
∈
AI
P
3
∪
AI
P
3
T and ζ
2
=
9, ζ
3
=
13, η
2
=
2, η
3
=
89, and set ζ
1
=
η
1
=
α
3
=
β
3
=
1, so we can compute u
1
=
ζ
1
α
1
α
2
α
3
=
11, u
2
=
ζ
2
α
2
α
3
=
9, u
3
=
ζ
3
α
3
=
13, and v
1
=
η
1
β
1
β
2
β
3
=
93, v
2
=
η
2
β
2
β
3
=
62, v
3
=
η
3
β
3
=
89, which are the coefficients in Example 19.


#### 3.4.6.  Remarks and Suggested Security Parameters

The suggested parametersn are listed in Table 3.We provide some remarks on the proposed PKC as follows.Remark 22.
We can choose a 2-dimensional square matrixΔ with determinant equal to ±
1 because the inverse Δ
-
1 can be easily represented when |
Δ
|
=
±
1.Remark 23.
We should choosep and q slightly greater than ∑
i
=
1
n
‍
g
i
max
⁡
F
i and ∑
i
=
1
n
‍
h
i
max
⁡
F
i, respectively. See (24). So for convenience of discussions, we always assume that
(32)
p
≈
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
≈
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.Remark 24.
In Algorithm2, we suggest choosing ζ
i and η
i with some special lengths in order that the generated u
i’s (v
i’s, resp.) share an almost same binary length; that is,
(33)
|
ζ
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
-
|
∏
j
=
i
n
‍
α
j
|
2
,
|
η
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
-
|
∏
j
=
i
n
‍
β
j
|
2
,
So, for i
=
1
,
…
,
n
-
1, we have
(34)
|
u
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
=
|
u
1
|
2
,
|
v
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
=
|
v
1
|
2
.
For convenience of discussions, we also assume that u
1 and v
1 have an almost same binary length, so from (34), we have
(35)
|
u
i
|
2
≈
|
u
1
|
2
≈
|
v
i
|
2
≈
|
v
1
|
2
.


## 3.1. Knapsack Problems

Definition 7 (knapsack problem).
Given a positive integral vectora
=
(
a
1
,
…
,
a
n
) and an integer s
∈
ℤ, the knapsack or subset sum problem is to find a binary vector x
∈
{
0,1
}
n such that 〈
a
,
x
〉
=
s. A knapsack problem is denoted as KP
(
a
,
s
). The density of the knapsack problem KP
(
a
,
s
) is defined as d
=
n
/
lo
g
2
max
⁡
a.The density of a compact knapsack problemKP
(
a
,
s
) imposes an important effect on the hardness of the problem. It was shown that if the density d
<
0.9408, the knapsack problem KP
(
a
,
s
) can be solved with an overwhelming probability [23, 24].Definition 8 (compact knapsack problem).
Given a positive integral vectora
=
(
a
1
,
…
,
a
n
), an integer 2
≤
K
∈
ℤ
+, and an integer s
∈
ℤ, the compact or general knapsack problem is to find a vector x
=
(
x
1
,
…
,
x
n
) with 0
≤
x
i
≤
K
-
1 such that 〈
a
,
x
〉
=
s. A compact knapsack problem is denoted as CK
P
K
(
a
,
s
). The density of a compact knapsack problem CK
P
K
(
a
,
s
) is defined as d
=
n
lo
g
2
K
/
lo
g
2
max
⁡
a.
If the density of a compact knapsack problemCK
P
K
(
a
,
s
) is d
<
1, it was shown that the compact knapsack problem can almost always be efficiently solved with lattice reduction algorithms [25]. In this paper, we consider the compact knapsack problem with K
=
192.


## 3.2. The Proposed Message Encoding Function

The message space𝕄 consists of n blocks with each block 3 bit long; namely, 𝕄
=
ℤ
8
n. For a message m
=
(
m
1
,
…
,
m
n
)
∈
𝕄, we firstly define a message encoding function that maps the message m into a vector in Z
192
n under an auxiliary key r
=
(
r
1
,
…
,
r
n
)
∈
{
0,1
}
n, which is randomly chosen by the encrypter. We define F
i
:
ℤ
8
×
{
0,1
}
↦
ℤ
192 for i
=
1
,
…
,
n as
(6)
F
i
(
m
i
,
r
i
)
=
〈
5
8
(
i
-
1
)
+
m
i
-
1
〉
97
+
96
r
i
∈
ℤ
192
.Remark 9.
We note that 97 is a prime and 5 is a primitive root modulo 97, so the function0
≤
〈
5
x
-
1
〉
97
≤
95 forms a permutation when x runs through ℤ
96 and hence F
i
(
x
,
r
) permutates ℤ
192 when x and r run through ℤ
96 and {
0,1
}, respectively. We denote
(7)
F
i
=
{
F
i
(
m
i
,
r
i
)
∣
m
i
∈
ℤ
8
,
r
i
∈
{
0,1
}
}
.
It is easy to verify that ⋃
i
=
1
12
‍
F
i forms a partition of ℤ
192. So we can deduce that if i, m
i, and r
i are uniformly distributed over {
1
,
…
,
n
}, ℤ
8 and {
0,1
}, respectively, F
i
(
m
i
,
r
i
) is uniformly distributed over ℤ
192. This means that the generating of each F
i
(
m
i
,
r
i
)
∈
F
i can simulate the process of randomly choosing an integer from ℤ
192, which allows the predesignated special structure of 𝕊
P defined in (9) as random as possible.The message encoding function is defined asF
:
𝕄
×
{
0,1
}
n
↦
𝕊
P:
(8)
F
(
m
,
r
)
=
(
F
1
(
m
1
,
r
1
)
,
…
,
F
n
(
m
n
,
r
n
)
)
,
where the plaintext space is
(9)
𝕊
P
=
{
F
(
m
,
r
)
∣
m
∈
𝕄
,
r
∈
{
0,1
}
n
}
=
F
1
×
⋯
×
F
n
.
In the rest of the paper, we also define the equivalent plaintext space 𝕊
E
=
ℤ
192
n including the plaintext space 𝕊
P
⊂
𝕊
E.Remark 10.
Another fact aboutF
i is
(10)
F
i
(
m
,
r
)
=
F
i
+
12
(
m
,
r
)
,
for m
∈
ℤ
8 and r
∈
{
0,1
} because 5
96
=
1
(
mod
⁡
97
). Hence, we have that if i
=
j
(
mod
⁡
12
), F
i
=
F
j.Remark 11.
Now we remark on how to encode a message and decode a plaintext with respect toF. We can construct n tables similar to truth-value tables to show the functions F
j. By observing (10), we see that the tables have a periodic structure with period 12. That is to say those j sharing a common residue modulo 12 have a same table. So only 12 tables suffice to list the values of F
(
m
,
r
). See Table 1. Here, we spend some more words on the message encoding function and Table 1. At present, we only consider the preceding three columns of the 12 subtables in Table 1, which list the values of r
j, m
j, and the corresponding F
j
(
m
j
,
r
j
), respectively. To encode a message m
∈
𝕄 and given a randomly chosen auxiliary key r
∈
{
0,1
}
n, for i
=
1
,
…
,
n, we determine the F
i
(
m
i
,
r
i
) one by one by looking up the subtable indexed by i
=
〈
j
〉
12
(
mod
⁡
12
) in Table 1 denoted as Sub-T〈
j
〉
12. When r
i
=
0 (or  1, resp.), we only search the 8 rows covered by r
i
=
0 (or 1, resp.) in Sub-T〈
j
〉
12, and output the integer in the column marked by F
i that lies in the same row with m
i as the value of F
i
(
m
i
,
r
i
). For example, to encode m
=
(
5,4
,
7,6
) under the control of r
=
(
0,1
,
1,0
), by looking up Sub-T1, we determine F
1
(
m
1
,
r
1
)
=
20. Similarly, we get F
2
(
m
2
,
r
2
)
=
159, F
3
(
m
3
,
r
3
)
=
177, F
4
(
m
4
,
r
4
)
=
78. So, we encode (
5,4
,
7,6
) as F
(
m
,
r
)
=
(
20,159,177,78
). On the contrary, we can decode a plaintext x
∈
𝕊
P by looking up the table. For example, x
=
(
100,101,76,6
). We search the third column of Sub-T1 for 100 which lies in the same line with m
1
=
1, so m
1
=
1. Similarly, we get m
2
=
0, m
3
=
5, m
2
=
7. Hence, m
=
(
1,0
,
5,7
).Table 1
The values ofF
i
(
M
i
,
r
i
) and their associated integer pairs.
(a)
i
=
1 (mod 12)
r
i
m
i
F
i
mod (1, 34)
mod (2, 17)
0
0
0
(0, 0)
(0, 0)
1
4
(0, 4)
(1, 4)
2
24
(0, 24)
(0, 7)
3
27
(0, 27)
(1, 10)
4
42
(0, 8)
(0, 8)
5
20
(0, 20)
(0, 3)
6
7
(0, 7)
(1, 7)
7
39
(0, 5)
(1, 5)
1
0
96
(0, 28)
(0, 11)
1
100
(0, 32)
(0, 15)
2
120
(0, 18)
(0, 1)
3
123
(0, 21)
(1, 4)
4
138
(0, 2)
(0, 2)
5
116
(0, 14)
(0, 14)
6
103
(0, 1)
(1, 1)
7
135
(0, 33)
(1, 16)
(b)
i
=
2 (mod 12)
r
i
m
i
F
i
mod (1, 33)
mod (3, 11)
0
0
5
(0, 5)
(2, 5)
1
29
(0, 29)
(2, 7)
2
52
(0, 19)
(1, 8)
3
70
(0, 4)
(1, 4)
4
63
(0, 30)
(0, 8)
5
28
(0, 28)
(1, 6)
6
47
(0, 14)
(2, 3)
7
45
(0, 12)
(0, 1)
1
0
101
(0, 2)
(2, 2)
1
125
(0, 26)
(2, 4)
2
148
(0, 16)
(1, 5)
3
166
(0, 1)
(1, 1)
4
159
(0, 27)
(0, 5)
5
124
(0, 25)
(1, 3)
6
143
(0, 11)
(2, 0)
7
141
(0, 9)
(0, 9)
(c)
i
=
3 (mod 12)
r
i
m
i
F
i
mod (1, 31)
mod (1, 37)
0
0
35
(0, 4)
(0, 35)
1
82
(0, 20)
(0, 8)
2
26
(0, 26)
(0, 26)
3
37
(0, 6)
(0, 0)
4
92
(0, 30)
(0, 18)
5
76
(0, 14)
(0, 2)
6
93
(0, 0)
(0, 19)
7
81
(0, 19)
(0, 7)
1
0
131
(0, 7)
(0, 20)
1
178
(0, 23)
(0, 30)
2
122
(0, 29)
(0, 11)
3
133
(0, 9)
(0, 22)
4
188
(0, 2)
(0, 3)
5
172
(0, 17)
(0, 24)
6
189
(0, 3)
(0, 4)
7
177
(0, 22)
(0, 29)
(d)
i
=
4 (mod 12)
r
i
m
i
F
i
mod (1, 46)
mod (2, 23)
0
0
21
(0, 21)
(1, 21)
1
12
(0, 12)
(0, 12)
2
64
(0, 18)
(0, 18)
3
33
(0, 33)
(1, 10)
4
72
(0, 26)
(0, 3)
5
73
(0, 27)
(1, 4)
6
78
(0, 32)
(0, 9)
7
6
(0, 6)
(0, 6)
1
0
117
(0, 25)
(1, 2)
1
108
(0, 16)
(0, 1)
2
160
(0, 22)
(0, 22)
3
129
(0, 37)
(1, 14)
4
168
(0, 30)
(0, 7)
5
169
(0, 31)
(1, 8)
6
174
(0, 36)
(0, 13)
7
102
(0, 10)
(0, 10)
(e)
i
=
5 (mod  12)
r
i
m
i
F
i
mod (1, 29)
mod (1, 47)
0
0
34
(0, 5)
(0, 34)
1
77
(0, 19)
(0, 30)
2
1
(0, 1)
(0, 1)
3
9
(0, 9)
(0, 9)
4
49
(0, 20)
(0, 2)
5
55
(0, 26)
(0, 8)
6
85
(0, 27)
(0, 38)
7
41
(0, 12)
(0, 41)
1
0
130
(0, 14)
(0, 36)
1
173
(0, 28)
(0, 32)
2
97
(0, 10)
(0, 3)
3
105
(0, 18)
(0, 11)
4
145
(0, 0)
(0, 4)
5
151
(0, 6)
(0, 10)
6
181
(0, 7)
(0, 40)
7
137
(0, 21)
(0, 43)
(f)
i
=
6 (mod 12)
r
i
m
i
F
i
mod (1, 39)
mod (3, 13)
0
0
15
(0, 15)
(0, 2)
1
79
(0, 1)
(1, 1)
2
11
(0, 11)
(2, 11)
3
59
(0, 20)
(2, 7)
4
8
(0, 8)
(2, 8)
5
44
(0, 5)
(2, 5)
6
30
(0, 30)
(0, 4)
7
57
(0, 18)
(0, 5)
1
0
111
(0, 33)
(0, 7)
1
175
(0, 19)
(1, 6)
2
107
(0, 29)
(2, 3)
3
155
(0, 38)
(2, 12)
4
104
(0, 26)
(2, 0)
5
140
(0, 23)
(2, 10)
6
126
(0, 9)
(0, 9)
7
153
(0, 36)
(0, 20)
(g)
i
=
7 (mod 12)
r
i
m
i
F
i
mod (1, 34)
mod (2, 17)
0
0
95
(0, 27)
(1, 10)
1
91
(0, 23)
(1, 6)
2
71
(0, 3)
(1, 3)
3
68
(0, 0)
(0, 0)
4
53
(0, 19)
(1, 2)
5
75
(0, 7)
(1, 7)
6
88
(0, 20)
(0, 3)
7
56
(0, 22)
(0, 5)
1
0
191
(0, 21)
(1, 4)
1
187
(0, 17)
(1, 0)
2
167
(0, 31)
(1, 14)
3
164
(0, 28)
(0, 11)
4
149
(0, 13)
(1, 13)
5
171
(0, 1)
(1, 1)
6
184
(0, 14)
(0, 14)
7
152
(0, 16)
(0, 16)
(h)
i
=
8 (mod 12)
r
i
m
i
F
i
mod (1, 33)
mod (3, 11)
0
0
90
(0, 24)
(0, 2)
1
66
(0, 0)
(0, 0)
2
43
(0, 10)
(1, 10)
3
25
(0, 25)
(1, 3)
4
32
(0, 32)
(2, 10)
5
67
(0, 1)
(1, 1)
6
48
(0, 15)
(0, 4)
7
50
(0, 17)
(2, 6)
1
0
186
(0, 21)
(0, 10)
1
162
(0, 30)
(0, 8)
2
139
(0, 7)
(1, 7)
3
121
(0, 22)
(1, 0)
4
128
(0, 29)
(2, 7)
5
163
(0, 31)
(1, 9)
6
144
(0, 12)
(0, 1)
7
146
(0, 14)
(2, 3)
(i)
i
=
9 (mod 12)
r
i
m
i
F
i
mod (1, 31)
mod (1, 37)
0
0
60
(0, 29)
(0, 23)
1
13
(0, 13)
(0, 13)
2
69
(0, 7)
(0, 32)
3
58
(0, 27)
(0, 21)
4
3
(0, 3)
(0, 3)
5
19
(0, 19)
(0, 19)
6
2
(0, 2)
(0, 2)
7
14
(0, 14)
(0, 14)
1
0
156
(0, 1)
(0, 8)
1
109
(0, 16)
(0, 35)
2
165
(0, 10)
(0, 17)
3
154
(0, 30)
(0, 6)
4
99
(0, 6)
(0, 25)
5
115
(0, 22)
(0, 4)
6
98
(0, 5)
(0, 24)
7
110
(0, 17)
(0, 36)
(j)
i
=
10  (mod 12)
r
i
m
i
F
i
mod (1, 46)
mod (2, 23)
0
0
74
(0, 28)
(0, 5)
1
83
(0, 37)
(1, 14)
2
31
(0, 31)
(1, 8)
3
62
(0, 16)
(0, 16)
4
23
(0, 23)
(1, 0)
5
22
(0, 22)
(0, 22)
6
17
(0, 17)
(1, 17)
7
89
(0, 43)
(1, 20)
1
0
170
(0, 32)
(0, 9)
1
179
(0, 41)
(1, 18)
2
127
(0, 35)
(1, 12)
3
158
(0, 20)
(0, 20)
4
119
(0, 27)
(1, 4)
5
118
(0, 26)
(0, 3)
6
113
(0, 21)
(1, 21)
7
185
(0, 1)
(1, 1)
(k)
i
=
11 (mod 12)
r
i
m
i
F
i
mod (1, 29)
mod (1, 47)
0
0
61
(0, 3)
(0, 14)
1
18
(0, 18)
(0, 18)
2
94
(0, 7)
(0, 0)
3
86
(0, 28)
(0, 39)
4
46
(0, 17)
(0, 46)
5
40
(0, 11)
(0, 40)
6
10
(0, 10)
(0, 10)
7
54
(0, 25)
(0, 7)
1
0
157
(0, 12)
(0, 16)
1
114
(0, 27)
(0, 20)
2
190
(0, 16)
(0, 2)
3
182
(0, 8)
(0, 41)
4
142
(0, 26)
(0, 1)
5
136
(0, 20)
(0, 42)
6
106
(0, 19)
(0, 12)
7
150
(0, 5)
(0, 9)
(l)
i
=
0 (mod 12)
r
i
m
i
F
i
mod (1, 39)
mod (3, 13)
0
0
80
(0, 2)
(2, 2)
1
16
(0, 16)
(1, 3)
2
84
(0, 6)
(0, 6)
3
36
(0, 36)
(0, 10)
4
87
(0, 9)
(0, 9)
5
51
(0, 12)
(0, 12)
6
65
(0, 26)
(2, 0)
7
38
(0, 38)
(2, 12)
1
0
176
(0, 20)
(2, 7)
1
112
(0, 34)
(1, 11)
2
180
(0, 24)
(0, 11)
3
132
(0, 15)
(0, 2)
4
183
(0, 27)
(0, 1)
5
147
(0, 30)
(0, 4)
6
161
(0, 5)
(2, 5)
7
134
(0, 17)
(2, 4)


## 3.3. Onion Algorithm

### 3.3.1. Indistinguishability and Associated Integer Pairs

Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2 and f
i
∈
F
i, we define f
i
(
mod
⁡
(
a
,
b
)
)
=
(
f
i
(
mod
⁡
a
)
,
f
i
(
mod
⁡
b
)
) and the set F
i
(
mod
⁡
(
a
,
b
)
)
=
{
f
i
(
mod
⁡
(
a
,
b
)
)
∣
f
i
∈
F
i
}. In fact, we can look F
i
(
mod
⁡
(
a
,
b
)
) as a transformation on F
i. If the two cardinalities are identical, |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, the transformation forms a bijection.Definition 12.
Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2, if |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, we call F
i to be distinguishable modulo (
a
,
b
), or (
a
,
b
) is an associated integer pair with F
i.Example 13.
Decide whetherF
61 is distinguishable modulo (
1,34
) and (
2,19
) or not, respectively. We note that F
61
=
F
1 contains the integers listed in the third column of  Sub-T1. Calculations show that |
F
61
|
=
|
F
61
(
mod
⁡
(
1,34
)
)
|
=
16. The 16 values in F
61
(
mod
⁡
(
1,34
)
) are listed in the forth column of Sub-T1. So, F
61 is distinguishable modulo (
1,34
). However, |
F
61
|
=
16
≠
|
F
61
(
mod
⁡
(
2,19
)
)
|
=
14 in that 4 and 42 modulo (
2,19
) produce a same integer pair (
0,4
), and 24 and 138 modulo (
2,19
) produce a same integer pair (
0,5
). So F
61 is not distinguishable modulo (
2,19
).Remark 14.
WhenF
i is distinguishable modulo (
a
,
b
), there is a bijection between the integers in F
i and the integer pairs in F
i
(
mod
⁡
(
a
,
b
)
). For example, the third and the forth columns of Sub-T1 listed the integers in F
1 and the integer pairs in F
1
(
mod
⁡
(
1,34
)
). For example, if we know an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
), we search the forth column generated by F
1
(
mod
⁡
(
1,34
)
) for (
0,32
) in Sub- T1 and find that (
0,32
) lies in the same line with 100, so f
1
=
100.Remark 15.
From Remark10, we have that, for congruent indices j’s modulo 12, we get a same set F
j
(
mod
⁡
(
a
,
b
)
). For each i
=
〈
j
〉
12
(
mod
⁡
12
), we give two integer pairs (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
) associated with F
i, and the corresponding integer pairs modulo (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
), respectively, in the forth and fifth column of Sub-T〈
j
〉
12. We denote the set consisting of the two integer pairs (
a
j
1
,
b
j
1
) and (
a
j
2
,
b
j
2
) as AIP〈
j
〉
12. For example, AIP〈
73
〉
12=AIP1
=
{
(
1,34
)
,
(
2,17
)
}. In Table 2, we list all the 12 sets of AIP〈
j
〉
12.Table 2
Associated integer pairs withF
i.
Set
Associated integer pairs
AIP1
{
(
1,34
)
,
(
2,17
)
}
AIP2
{
(
1,33
)
,
(
3,11
)
}
AIP3
{
(
1,31
)
,
(
1,37
)
}
AIP4
{
(
1,46
)
,
(
2,23
)
}
AIP5
{
(
1,29
)
,
(
1,47
)
}
AIP6
{
(
1,39
)
,
(
3,13
)
}
AIP7
{
(
1,34
)
,
(
2,17
)
}
AIP8
{
(
1,33
)
,
(
3,11
)
}
AIP9
{
(
1,31
)
,
(
1,37
)
}
AIP10
{
(
1,46
)
,
(
2,23
)
}
AIP11
{
(
1,29
)
,
(
1,47
)
}
AIP0
{
(
1,39
)
,
(
3,13
)
}Table 3
Suggested security parameters.
Security level
Moderate
Higher
Highest
n
60
90
120
Public key size
21282
47025
82796
Information rate
0.49
0.50
0.51
Costs for BFA I
2
240
2
360
2
480
Costs for BFA II
2
125.9
2
186.5
2
246.9
P
d
1
2
86.9
2
146.1
2
205.7
P
d
2
2
587.8
2
899.4
2
1211.6
P
d
3
2
111.4
2
183
2
255.1Remark 16.
Note thatF
i is distinguishable modulo (
a
,
b
) if and only if F
i is distinguishable modulo (
b
,
a
)
=
(
a
,
b
)
T. For example, AIP
1
T
=
{
(
34,1
)
,
(
17,2
)
} also contains integer pairs associated with F
1. If we know that an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
), we also can determine the value of f
1 by searching the forth column generated by F
1
(
mod
⁡
(
1,34
)
) in Sub-T1 for (
0,32
), and we find a unique f
1
=
100 with f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
). So the unique integer f
1
∈
F
1 is f
1
=
100 such that f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
).


### 3.3.2. Simultaneous Diophantine Equation

Now, we consider a simultaneous Diophantine equation problem as follows; given integerss
1 and s
2 and positive integer sequences u
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
), find x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P defined in (9) such that
(11)
s
1
=
〈
u
,
x
〉
,
s
2
=
〈
v
,
x
〉
.
It is pointed out that if max
⁡
u
≤
2
d
u
n and max
⁡
v
≤
2
d
v
n, for some constants d
u and d
v subject to d
u
+
d
v
<
lo
g
2
192, (
s
1
,
s
2
) will have exponentially many preimages in 𝕊
E
=
ℤ
192
n satisfying (11); namely,
(12)
P
d
≥
|
𝕊
E
|
(
191
max
⁡
u
)
(
191
max
⁡
v
)
≥
19
2
n
19
1
2
2
d
u
+
d
v
,
which is 𝒪
(
2
lo
g
2
192
-
d
u
-
d
v
). What we mean is that if we require x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
E and d
u
+
d
v
<
lo
g
2
192, (11) will be a many-to-one function. In the subsequent contents, we will define a condition such that (11) will have at most one solution in 𝕊
P (to guarantee the unique decipherability for ciphertexts) and propose an algorithm to solve (11). Besides, some transformations will be introduced in the construction of the proposed PKC to derive a compact knapsack problem equipped with noninjectivity, a trapdoor, and one-wayness natures.


### 3.3.3. An Easy Problem and the Algorithm Solving It

For some specialu and v, we can efficiently determine f
n in (11) as stated in the following lemma.Lemma 17.
Assuming that (11) has solutions in 𝕊
P, g
c
d
n
u
=
g
c
d
n
v
=
1, and (
g
c
d
n
-
1
u
,
g
c
d
n
-
1
v
)
∈
A
I
P
〈
n
〉
12
∪
A
I
P
〈
n
〉
12
T, then f
n
∈
F
n can be efficiently and uniquely determined.Proof.
We first note thatgc
d
n
-
1
u
∣
u
i and gc
d
n
-
1
v
∣
v
i, for i
=
1
,
…
,
n
-
1, so the two equations in (11) modulo gc
d
n
-
1
u and gc
d
n
-
1
v, respectively, give s
1
=
u
n
f
n
(
mod
⁡
gc
d
n
-
1
u
) and s
2
=
v
n
f
n
(
mod
⁡
gc
d
n
-
1
v
). Observing that gc
d
n
u
=
gcd
(
gc
d
n
-
1
u
,
u
n
)
=
1, we can invert u
n and similarly v
n:
(13)
(
f
n
1
,
f
n
2
)
=
f
n
(
mod
⁡
(
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
)
=
(
u
n
-
1
s
1
(
mod
⁡
gc
d
n
-
1
u
)
,
v
n
-
1
s
2
(
mod
⁡
gc
d
n
-
1
v
)
)
.
If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12, we determine the unique corresponding value f
n according to Remark 14. If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
T, we use the method given in Remark 16 to determine the unique f
n.The above lemma says that for some specialu and v, we can determine the solution f
n
,
…
,
f
1 to (11) one by one as if we peel off an onion, so the nameOnion Algorithm comes.Theorem 18.
Assuming that (11) has solutions in 𝕊
P:
(14)
g
c
d
n
u
=
g
c
d
n
v
=
1
,
and that, for i
=
2
,
…
,
n,
(15)
(
g
c
d
i
-
1
u
g
c
d
i
u
,
g
c
d
i
-
1
v
g
c
d
i
v
)
∈
A
I
P
〈
i
〉
12
∪
A
I
P
〈
i
〉
12
T
,
the solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11) can be efficiently and uniquely determined.Proof.
From Lemma17, f
n can be efficiently and uniquely determined.
Fori
=
n
-
1
,
…
,
2, assuming that f
i
+
1
,
…
,
f
n have been uniquely determined, we know that
(16)
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
=
∑
j
=
1
i
‍
u
j
f
j
.
We note that gc
d
i
u
∣
u
j for 1
≤
j
≤
i, so gc
d
i
u divides the right side and hence the left side of (16). We set
(17)
s
i
1
=
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
gc
d
i
u
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
.
A similar analysis also applies to the second equation of (11), so we set s
i
2
=
(
s
2
-
∑
j
=
i
+
1
n
‍
v
j
f
j
)
/
gc
d
i
v to obtain
(18)
s
i
1
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
,
s
i
2
=
∑
j
=
1
i
‍
v
j
gc
d
i
v
f
j
.
If we view (18) as a new simultaneous Diophantine equation problem with integer sequences (
u
1
/
gc
d
i
u
,
…
,
u
i
/
gc
d
i
u
) and (
v
1
/
gc
d
i
v
,
…
,
v
i
/
gc
d
i
v
), what follows shows that the new problem satisfies the conditions in Lemma 17.
Firstly, (11) has solutions, and f
i
+
1
,
…
,
f
n have been uniquely determined, so (18) must have solutions.
Secondly, recalling the meaning ofgc
d
i
u, we claim that these entries divided by their gcd must be relatively prime:
(19)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
gc
d
i
u
)
=
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
gc
d
i
v
)
=
1
.
Thirdly,(20)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
-
1
gc
d
i
u
)
=
gc
d
i
-
1
u
gc
d
i
u
,
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
-
1
gc
d
i
v
)
=
gc
d
i
-
1
v
gc
d
i
v
.
From (15) and the previous two proven things, we know that (18) indeed satisfies the conditions in Lemma 17. So we can efficiently determine a unique f
i
∈
F
i.
Finally, oncef
2
,
…
,
f
n have been uniquely determined, it is a trivial thing to determine a unique f
1 just by computing
(21)
f
1
=
s
1
-
∑
i
=
2
n
‍
u
i
f
i
u
1
or
s
2
-
∑
i
=
2
n
‍
v
i
f
i
v
1
.
Both values on the right side of the above equation must be not only identical but also in F
1 because (11) has solutions in 𝕊
P and f
2
,
…
,
f
n have been uniquely determined.Given the problem (11), satisfying the conditions presented in Theorem 18, theOnion Algorithm for solving (11) is summarized as shown in Algorithm 1.Algorithm 1:
Onion Algorithm.
(1) Compute(
f
n
1
,
f
n
2
) according to (13).
(2)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12  then
(3)  Search for(
f
n
1
,
f
n
2
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
)
=
(
f
n
1
,
f
n
2
). Store f
n.
(4)end if
(5)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12
T  then
(6)  Search for(
f
n
2
,
f
n
1
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
)
=
(
f
n
2
,
f
n
1
). Store f
n.
(7)end if
(8)for  i
=
n
-
1
,
…
,
2  do
(9) Compute (18) and
(
f
i
1
,
f
i
2
)
=
(
s
i
1
(
u
i
gcd
i
u
)
-
1
(
mod
⁡
gcd
i
-
1
u
gcd
i
u
)
,
s
i
2
(
v
i
gcd
i
v
)
-
1
(
mod
⁡
gcd
i
-
1
v
gcd
i
v
)
)
. (*)
(10)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12  then
(11)Search the column in Sub-T
〈
i
〉
12  generated
byF
i modulo (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
for(
f
i
1
,
f
i
2
) such that (
f
i
1
,
f
i
2
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
). Store
f
i.
(12)
end if
(13)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12
T  then
(14)Search the column in Sub-T
〈
i
〉
12 generated
byF
i modulo (
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
for(
f
i
2
,
f
i
1
) such that (
f
i
2
,
f
i
1
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
). Store
f
i.
(15)
end if
(16)end for
(17) Compute and storef
1
=
(
s
1
-
∑
i
=
2
n
‍
u
i
f
i
)
/
u
1.
(18)return  x
=
(
f
1
,
…
,
f
n
).Now we use a toy example to illustrate what we discuss in this subsection about theOnion Algorithm.Example 19.
Assume that the following equations have solutions in𝕊
P; find the solution x
=
(
f
1
,
f
2
,
f
3
) to 11
f
1  +  9
f
2  +  13
f
3
=
2926, 93
f
1  +  62
f
2  +  89
f
3
=
20783. We can verify that (
gc
d
3
u
,
gc
d
3
v
)
=
(
1,1
), (
gc
d
2
u
,
gc
d
2
v
)
=
(
1,31
), (
gc
d
1
u
,
gc
d
1
v
)
=
(
11,93
), and (
gc
d
2
u
/
gc
d
3
u
,
gc
d
2
v
/
gc
d
3
v
)
=
(
1,31
)
∈
AI
P
3
,
(
gc
d
1
u
/
gc
d
2
u
,
gc
d
1
v
/
gc
d
2
v
)
=
(
11,3
)
∈
AI
P
2
T, so (14) and (15) are satisfied. Hence, we use theOnion Algorithm to compute (
f
31
,
f
32
)
=
(
2926
×
1
3
-
1
(
mod
⁡
1
)
,
20783
×
8
9
-
1
(
mod
⁡
31
)
)
=
(
0,20
). We look up  Sub-T3 and find that f
3
=
82
(
mod
⁡
(
1,31
)
)
=
(
0,20
). So f
3
=
82. We compute s
21
=
(
2926
-
13
×
82
)
/
1
=
1860, s
22
=
(
20783
-
89
×
82
)
/
31
=
435. Then we compute (
f
21
,
f
22
)
=
(
1860
×
9
-
1
(
mod
⁡
11
)
,
435
×
(
62
/
31
)
-
1
(
mod
⁡
93
/
31
)
)
=
(
5,0
). We search Sub-T2 for (
0,5
) and find that f
2
=
159
(
mod
⁡
(
3,11
)
)
=
(
0,5
). So we determine f
2
=
159. Finally, we get f
1
=
(
2926
-
9
×
159
-
13
×
82
)
/
11
=
39. Thus, a unique x
=
(
39,159,82
) is determined.


## 3.3.1. Indistinguishability and Associated Integer Pairs

Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2 and f
i
∈
F
i, we define f
i
(
mod
⁡
(
a
,
b
)
)
=
(
f
i
(
mod
⁡
a
)
,
f
i
(
mod
⁡
b
)
) and the set F
i
(
mod
⁡
(
a
,
b
)
)
=
{
f
i
(
mod
⁡
(
a
,
b
)
)
∣
f
i
∈
F
i
}. In fact, we can look F
i
(
mod
⁡
(
a
,
b
)
) as a transformation on F
i. If the two cardinalities are identical, |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, the transformation forms a bijection.Definition 12.
Given an integer pair(
a
,
b
)
∈
(
ℤ
+
)
2, if |
F
i
(
mod
⁡
(
a
,
b
)
)
|
=
|
F
i
|, we call F
i to be distinguishable modulo (
a
,
b
), or (
a
,
b
) is an associated integer pair with F
i.Example 13.
Decide whetherF
61 is distinguishable modulo (
1,34
) and (
2,19
) or not, respectively. We note that F
61
=
F
1 contains the integers listed in the third column of  Sub-T1. Calculations show that |
F
61
|
=
|
F
61
(
mod
⁡
(
1,34
)
)
|
=
16. The 16 values in F
61
(
mod
⁡
(
1,34
)
) are listed in the forth column of Sub-T1. So, F
61 is distinguishable modulo (
1,34
). However, |
F
61
|
=
16
≠
|
F
61
(
mod
⁡
(
2,19
)
)
|
=
14 in that 4 and 42 modulo (
2,19
) produce a same integer pair (
0,4
), and 24 and 138 modulo (
2,19
) produce a same integer pair (
0,5
). So F
61 is not distinguishable modulo (
2,19
).Remark 14.
WhenF
i is distinguishable modulo (
a
,
b
), there is a bijection between the integers in F
i and the integer pairs in F
i
(
mod
⁡
(
a
,
b
)
). For example, the third and the forth columns of Sub-T1 listed the integers in F
1 and the integer pairs in F
1
(
mod
⁡
(
1,34
)
). For example, if we know an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
), we search the forth column generated by F
1
(
mod
⁡
(
1,34
)
) for (
0,32
) in Sub- T1 and find that (
0,32
) lies in the same line with 100, so f
1
=
100.Remark 15.
From Remark10, we have that, for congruent indices j’s modulo 12, we get a same set F
j
(
mod
⁡
(
a
,
b
)
). For each i
=
〈
j
〉
12
(
mod
⁡
12
), we give two integer pairs (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
) associated with F
i, and the corresponding integer pairs modulo (
a
i
1
,
b
i
1
) and (
a
i
2
,
b
i
2
), respectively, in the forth and fifth column of Sub-T〈
j
〉
12. We denote the set consisting of the two integer pairs (
a
j
1
,
b
j
1
) and (
a
j
2
,
b
j
2
) as AIP〈
j
〉
12. For example, AIP〈
73
〉
12=AIP1
=
{
(
1,34
)
,
(
2,17
)
}. In Table 2, we list all the 12 sets of AIP〈
j
〉
12.Table 2
Associated integer pairs withF
i.
Set
Associated integer pairs
AIP1
{
(
1,34
)
,
(
2,17
)
}
AIP2
{
(
1,33
)
,
(
3,11
)
}
AIP3
{
(
1,31
)
,
(
1,37
)
}
AIP4
{
(
1,46
)
,
(
2,23
)
}
AIP5
{
(
1,29
)
,
(
1,47
)
}
AIP6
{
(
1,39
)
,
(
3,13
)
}
AIP7
{
(
1,34
)
,
(
2,17
)
}
AIP8
{
(
1,33
)
,
(
3,11
)
}
AIP9
{
(
1,31
)
,
(
1,37
)
}
AIP10
{
(
1,46
)
,
(
2,23
)
}
AIP11
{
(
1,29
)
,
(
1,47
)
}
AIP0
{
(
1,39
)
,
(
3,13
)
}Table 3
Suggested security parameters.
Security level
Moderate
Higher
Highest
n
60
90
120
Public key size
21282
47025
82796
Information rate
0.49
0.50
0.51
Costs for BFA I
2
240
2
360
2
480
Costs for BFA II
2
125.9
2
186.5
2
246.9
P
d
1
2
86.9
2
146.1
2
205.7
P
d
2
2
587.8
2
899.4
2
1211.6
P
d
3
2
111.4
2
183
2
255.1Remark 16.
Note thatF
i is distinguishable modulo (
a
,
b
) if and only if F
i is distinguishable modulo (
b
,
a
)
=
(
a
,
b
)
T. For example, AIP
1
T
=
{
(
34,1
)
,
(
17,2
)
} also contains integer pairs associated with F
1. If we know that an integer f
1
∈
F
1 satisfies f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
), we also can determine the value of f
1 by searching the forth column generated by F
1
(
mod
⁡
(
1,34
)
) in Sub-T1 for (
0,32
), and we find a unique f
1
=
100 with f
1
(
mod
⁡
(
1,34
)
)
=
(
0,32
). So the unique integer f
1
∈
F
1 is f
1
=
100 such that f
1
(
mod
⁡
(
34,1
)
)
=
(
32,0
).


## 3.3.2. Simultaneous Diophantine Equation

Now, we consider a simultaneous Diophantine equation problem as follows; given integerss
1 and s
2 and positive integer sequences u
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
), find x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P defined in (9) such that
(11)
s
1
=
〈
u
,
x
〉
,
s
2
=
〈
v
,
x
〉
.
It is pointed out that if max
⁡
u
≤
2
d
u
n and max
⁡
v
≤
2
d
v
n, for some constants d
u and d
v subject to d
u
+
d
v
<
lo
g
2
192, (
s
1
,
s
2
) will have exponentially many preimages in 𝕊
E
=
ℤ
192
n satisfying (11); namely,
(12)
P
d
≥
|
𝕊
E
|
(
191
max
⁡
u
)
(
191
max
⁡
v
)
≥
19
2
n
19
1
2
2
d
u
+
d
v
,
which is 𝒪
(
2
lo
g
2
192
-
d
u
-
d
v
). What we mean is that if we require x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
E and d
u
+
d
v
<
lo
g
2
192, (11) will be a many-to-one function. In the subsequent contents, we will define a condition such that (11) will have at most one solution in 𝕊
P (to guarantee the unique decipherability for ciphertexts) and propose an algorithm to solve (11). Besides, some transformations will be introduced in the construction of the proposed PKC to derive a compact knapsack problem equipped with noninjectivity, a trapdoor, and one-wayness natures.


## 3.3.3. An Easy Problem and the Algorithm Solving It

For some specialu and v, we can efficiently determine f
n in (11) as stated in the following lemma.Lemma 17.
Assuming that (11) has solutions in 𝕊
P, g
c
d
n
u
=
g
c
d
n
v
=
1, and (
g
c
d
n
-
1
u
,
g
c
d
n
-
1
v
)
∈
A
I
P
〈
n
〉
12
∪
A
I
P
〈
n
〉
12
T, then f
n
∈
F
n can be efficiently and uniquely determined.Proof.
We first note thatgc
d
n
-
1
u
∣
u
i and gc
d
n
-
1
v
∣
v
i, for i
=
1
,
…
,
n
-
1, so the two equations in (11) modulo gc
d
n
-
1
u and gc
d
n
-
1
v, respectively, give s
1
=
u
n
f
n
(
mod
⁡
gc
d
n
-
1
u
) and s
2
=
v
n
f
n
(
mod
⁡
gc
d
n
-
1
v
). Observing that gc
d
n
u
=
gcd
(
gc
d
n
-
1
u
,
u
n
)
=
1, we can invert u
n and similarly v
n:
(13)
(
f
n
1
,
f
n
2
)
=
f
n
(
mod
⁡
(
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
)
=
(
u
n
-
1
s
1
(
mod
⁡
gc
d
n
-
1
u
)
,
v
n
-
1
s
2
(
mod
⁡
gc
d
n
-
1
v
)
)
.
If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12, we determine the unique corresponding value f
n according to Remark 14. If (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
T, we use the method given in Remark 16 to determine the unique f
n.The above lemma says that for some specialu and v, we can determine the solution f
n
,
…
,
f
1 to (11) one by one as if we peel off an onion, so the nameOnion Algorithm comes.Theorem 18.
Assuming that (11) has solutions in 𝕊
P:
(14)
g
c
d
n
u
=
g
c
d
n
v
=
1
,
and that, for i
=
2
,
…
,
n,
(15)
(
g
c
d
i
-
1
u
g
c
d
i
u
,
g
c
d
i
-
1
v
g
c
d
i
v
)
∈
A
I
P
〈
i
〉
12
∪
A
I
P
〈
i
〉
12
T
,
the solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11) can be efficiently and uniquely determined.Proof.
From Lemma17, f
n can be efficiently and uniquely determined.
Fori
=
n
-
1
,
…
,
2, assuming that f
i
+
1
,
…
,
f
n have been uniquely determined, we know that
(16)
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
=
∑
j
=
1
i
‍
u
j
f
j
.
We note that gc
d
i
u
∣
u
j for 1
≤
j
≤
i, so gc
d
i
u divides the right side and hence the left side of (16). We set
(17)
s
i
1
=
s
1
-
∑
j
=
i
+
1
n
‍
u
j
f
j
gc
d
i
u
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
.
A similar analysis also applies to the second equation of (11), so we set s
i
2
=
(
s
2
-
∑
j
=
i
+
1
n
‍
v
j
f
j
)
/
gc
d
i
v to obtain
(18)
s
i
1
=
∑
j
=
1
i
‍
u
j
gc
d
i
u
f
j
,
s
i
2
=
∑
j
=
1
i
‍
v
j
gc
d
i
v
f
j
.
If we view (18) as a new simultaneous Diophantine equation problem with integer sequences (
u
1
/
gc
d
i
u
,
…
,
u
i
/
gc
d
i
u
) and (
v
1
/
gc
d
i
v
,
…
,
v
i
/
gc
d
i
v
), what follows shows that the new problem satisfies the conditions in Lemma 17.
Firstly, (11) has solutions, and f
i
+
1
,
…
,
f
n have been uniquely determined, so (18) must have solutions.
Secondly, recalling the meaning ofgc
d
i
u, we claim that these entries divided by their gcd must be relatively prime:
(19)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
gc
d
i
u
)
=
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
gc
d
i
v
)
=
1
.
Thirdly,(20)
gcd
(
u
1
gc
d
i
u
,
…
,
u
i
-
1
gc
d
i
u
)
=
gc
d
i
-
1
u
gc
d
i
u
,
gcd
(
v
1
gc
d
i
v
,
…
,
v
i
-
1
gc
d
i
v
)
=
gc
d
i
-
1
v
gc
d
i
v
.
From (15) and the previous two proven things, we know that (18) indeed satisfies the conditions in Lemma 17. So we can efficiently determine a unique f
i
∈
F
i.
Finally, oncef
2
,
…
,
f
n have been uniquely determined, it is a trivial thing to determine a unique f
1 just by computing
(21)
f
1
=
s
1
-
∑
i
=
2
n
‍
u
i
f
i
u
1
or
s
2
-
∑
i
=
2
n
‍
v
i
f
i
v
1
.
Both values on the right side of the above equation must be not only identical but also in F
1 because (11) has solutions in 𝕊
P and f
2
,
…
,
f
n have been uniquely determined.Given the problem (11), satisfying the conditions presented in Theorem 18, theOnion Algorithm for solving (11) is summarized as shown in Algorithm 1.Algorithm 1:
Onion Algorithm.
(1) Compute(
f
n
1
,
f
n
2
) according to (13).
(2)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12  then
(3)  Search for(
f
n
1
,
f
n
2
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
u
,
gcd
n
-
1
v
)
)
=
(
f
n
1
,
f
n
2
). Store f
n.
(4)end if
(5)if  (
gcd
n
-
1
u
,
gcd
n
-
1
v
)
∈
AIP
〈
n
〉
12
T  then
(6)  Search for(
f
n
2
,
f
n
1
) in Sub-T
〈
n
〉
12 generated by
F
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
) to get f
n
∈
F
n such that
f
n
(
mod
⁡
(
gcd
n
-
1
v
,
gcd
n
-
1
u
)
)
=
(
f
n
2
,
f
n
1
). Store f
n.
(7)end if
(8)for  i
=
n
-
1
,
…
,
2  do
(9) Compute (18) and
(
f
i
1
,
f
i
2
)
=
(
s
i
1
(
u
i
gcd
i
u
)
-
1
(
mod
⁡
gcd
i
-
1
u
gcd
i
u
)
,
s
i
2
(
v
i
gcd
i
v
)
-
1
(
mod
⁡
gcd
i
-
1
v
gcd
i
v
)
)
. (*)
(10)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12  then
(11)Search the column in Sub-T
〈
i
〉
12  generated
byF
i modulo (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
for(
f
i
1
,
f
i
2
) such that (
f
i
1
,
f
i
2
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
). Store
f
i.
(12)
end if
(13)
if  (
gcd
i
-
1
u
/
gcd
i
u
,
gcd
i
-
1
v
/
gcd
i
v
)
∈
AIP
〈
i
〉
12
T  then
(14)Search the column in Sub-T
〈
i
〉
12 generated
byF
i modulo (
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
for(
f
i
2
,
f
i
1
) such that (
f
i
2
,
f
i
1
)
=
f
i
(
mod
⁡
(
gcd
i
-
1
v
/
gcd
i
v
,
gcd
i
-
1
u
/
gcd
i
u
)
). Store
f
i.
(15)
end if
(16)end for
(17) Compute and storef
1
=
(
s
1
-
∑
i
=
2
n
‍
u
i
f
i
)
/
u
1.
(18)return  x
=
(
f
1
,
…
,
f
n
).Now we use a toy example to illustrate what we discuss in this subsection about theOnion Algorithm.Example 19.
Assume that the following equations have solutions in𝕊
P; find the solution x
=
(
f
1
,
f
2
,
f
3
) to 11
f
1  +  9
f
2  +  13
f
3
=
2926, 93
f
1  +  62
f
2  +  89
f
3
=
20783. We can verify that (
gc
d
3
u
,
gc
d
3
v
)
=
(
1,1
), (
gc
d
2
u
,
gc
d
2
v
)
=
(
1,31
), (
gc
d
1
u
,
gc
d
1
v
)
=
(
11,93
), and (
gc
d
2
u
/
gc
d
3
u
,
gc
d
2
v
/
gc
d
3
v
)
=
(
1,31
)
∈
AI
P
3
,
(
gc
d
1
u
/
gc
d
2
u
,
gc
d
1
v
/
gc
d
2
v
)
=
(
11,3
)
∈
AI
P
2
T, so (14) and (15) are satisfied. Hence, we use theOnion Algorithm to compute (
f
31
,
f
32
)
=
(
2926
×
1
3
-
1
(
mod
⁡
1
)
,
20783
×
8
9
-
1
(
mod
⁡
31
)
)
=
(
0,20
). We look up  Sub-T3 and find that f
3
=
82
(
mod
⁡
(
1,31
)
)
=
(
0,20
). So f
3
=
82. We compute s
21
=
(
2926
-
13
×
82
)
/
1
=
1860, s
22
=
(
20783
-
89
×
82
)
/
31
=
435. Then we compute (
f
21
,
f
22
)
=
(
1860
×
9
-
1
(
mod
⁡
11
)
,
435
×
(
62
/
31
)
-
1
(
mod
⁡
93
/
31
)
)
=
(
5,0
). We search Sub-T2 for (
0,5
) and find that f
2
=
159
(
mod
⁡
(
3,11
)
)
=
(
0,5
). So we determine f
2
=
159. Finally, we get f
1
=
(
2926
-
9
×
159
-
13
×
82
)
/
11
=
39. Thus, a unique x
=
(
39,159,82
) is determined.


## 3.4.  The Proposed Probabilistic Public Key Encryption

In this subsection, we use the results obtained in previous subsections to derive a probabilistic public key encryption.


### 3.4.1. Key Generation

Randomly choose two sequencesu
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
)
∈
(
ℤ
+
)
n, satisfying conditions (14) and (15) given in Theorem 18, and a two-dimensional invertible square matrix with positive integer entries upper bounded by a constant,
(22)
Δ
=
(
δ
11
δ
12
δ
21
δ
22
)
,
δ
i
j
=
𝒪
(
1
)
,
1
≤
i
,
j
≤
2
.
Compute
(23)
(
g
h
)
=
(
g
1
⋯
g
n
h
1
⋯
h
n
)
=
Δ
(
u
v
)
.
Randomly choose two primes p
≠
q such that
(24)
p
>
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
>
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.
Let N
=
p
q. Compute the vector b
=
(
b
1
,
…
,
b
n
) using the Chinese remainder theorem,
(25)
b
i
≡
g
i
(
mod
⁡
p
)
,
b
i
≡
h
i
(
mod
⁡
q
)
.
Randomly choose an integer w
∈
ℤ
N
* and compute
(26)
a
i
=
w
b
i
(
mod
⁡
N
)
,
i
=
1
,
…
,
n
.
The public key is a
=
(
a
1
,
…
,
a
n
). The secret key consists of p, q, and w
-
1
(
mod
⁡
N
), Δ
-
1. When decrypting a ciphertext, the decrypter also needs to store the values of gc
d
i
u, gc
d
i
v, i
=
1
,
…
,
n, and Table 1.


### 3.4.2. Encryption

To encrypt a messagem
=
(
m
1
,
…
,
m
n
)
∈
𝕄
=
ℤ
8
n, the encrypter randomly chooses an auxiliary key r
=
(
r
1
,
…
,
r
n
)
∈
{
0,1
}
n and computes the plaintext x
=
(
f
1
,
…
,
f
n
)
=
F
(
m
,
r
) and the ciphertext using the public key a,
(27)
c
=
〈
a
,
x
〉
.


### 3.4.3. Decryption

To decipher a ciphertextc, the decrypter firstly computes c
N
=
〈
w
-
1
c
〉
N
=
w
-
1
c
(
mod
⁡
N
), and then c
p
=
〈
c
N
〉
p, c
q
=
〈
c
N
〉
q. Secondly, the decrypter computes
(28)
(
s
1
s
2
)
=
Δ
-
1
(
c
p
c
q
)
.
Thirdly, the decrypter uses theOnion Algorithm to determine a unique solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11). Finally, the decrypter decodes x into the corresponding message m by using the method illustrated in Remark 11.


### 3.4.4.  Why Decryption Works

To illustrate why the decryption works, we observe thatc
N
=
〈
b
,
x
〉
(
mod
⁡
N
) from (26), so c
p
=
〈
g
,
x
〉
(
mod
⁡
p
) and c
q
=
〈
h
,
x
〉
(
mod
⁡
q
) according to (25). From (23), we know that g
i
=
δ
11
u
i
+
δ
12
v
i
>
0, so 0
≤
c
p
<
p from (24). Now we conclude that c
p
=
〈
g
,
x
〉 and similarly c
q
=
〈
h
,
x
〉. Hence, we have
(29)
(
s
1
s
2
)
=
Δ
-
1
(
g
h
)
(
f
1
⋮
f
n
)
=
(
u
v
)
(
f
1
⋮
f
n
)
,
from which (11) is derived. It is easy to verify that (11) satisfies the conditions listed in Theorem 18, and hence can be efficiently solved withOnion Algorithm to give a unique solution x
∈
𝕊
P. Then x is decoded into the original message m.


### 3.4.5. On Generatingu and v

Now, we give an algorithm to generate then-dimensional positive integer sequences u and v satisfying conditions (14) and (15) in Theorem 18.Theorem 20.
The generatedu and v satisfy (14) and (15).Proof.
We note that, fori
=
1
,
…
,
n,
(30)
gc
d
i
u
=
gcd
(
u
1
,
…
,
u
i
)
=
gcd
(
ζ
1
∏
j
=
1
n
‍
α
j
,
…
,
ζ
i
∏
j
=
i
n
‍
α
j
)
=
gcd
(
∏
j
=
1
n
‍
α
j
,
…
,
∏
j
=
i
n
‍
α
j
)
=
∏
j
=
i
n
‍
α
j
.
Similarly, gc
d
i
v
=
gcd
(
v
1
,
…
,
v
i
)
=
∏
j
=
i
n
‍
β
j. We immediately have gc
d
n
u
=
α
n
=
gc
d
n
v
=
β
n
=
1. Thus, (14) is satisfied. For i
=
2
,
…
,
n, we have
(31)
(
gc
d
i
-
1
u
gc
d
i
u
,
gc
d
i
-
1
v
gc
d
i
v
)
=
(
∏
j
=
i
-
1
n
‍
α
j
∏
j
=
i
n
‍
α
j
,
∏
j
=
i
-
1
n
‍
β
j
∏
j
=
i
n
‍
β
j
)
=
(
α
i
-
1
,
β
i
-
1
)
∈
AI
P
〈
i
〉
12
∪
AI
P
〈
i
〉
12
T
,
so (15) is satisfied, as desired.Now we use an example to illustrate Algorithm2.Algorithm 2:Generating u and v.
(1) Fori
=
1
,
…
,
n
-
1, randomly choose (
α
i
,
β
i
)
∈
AIP
〈
i
+
1
〉
12
∪
AIP
〈
i
+
1
〉
12
T with repetition permitted.
(2) Randomly choose2
(
n
-
1
) numbers ζ
2
,
…
,
ζ
n and
η
2
,
…
,
η
n and set ζ
1
=
η
1
=
α
n
=
β
n
=
1 such that
gcd
(
ζ
i
,
α
j
)
=
gcd
(
η
i
,
β
j
)
=
1 for 1
≤
i
,
j
≤
n, and
gcd
(
ζ
i
,
ζ
i
+
1
)
=
gcd
(
η
i
,
η
i
+
1
)
=
1 for i
=
1
,
…
,
n
-
1.
(3)for  i
=
1
,
…
,
n  do
(4)u
i
=
ζ
i
∏
j
=
i
n
‍
α
j,  v
i
=
η
i
∏
j
=
i
n
‍
β
j.   (★)
(5)end for
(6)return  u
=
(
u
1
,
…
,
u
n
), v
=
(
v
1
,
…
,
v
n
).Example 21.
We randomly choose(
α
1
,
β
1
)
=
(
11,3
)
∈
AI
P
2
∪
AI
P
2
T, (
α
2
,
β
2
)
=
(
1,31
)
∈
AI
P
3
∪
AI
P
3
T and ζ
2
=
9, ζ
3
=
13, η
2
=
2, η
3
=
89, and set ζ
1
=
η
1
=
α
3
=
β
3
=
1, so we can compute u
1
=
ζ
1
α
1
α
2
α
3
=
11, u
2
=
ζ
2
α
2
α
3
=
9, u
3
=
ζ
3
α
3
=
13, and v
1
=
η
1
β
1
β
2
β
3
=
93, v
2
=
η
2
β
2
β
3
=
62, v
3
=
η
3
β
3
=
89, which are the coefficients in Example 19.


### 3.4.6.  Remarks and Suggested Security Parameters

The suggested parametersn are listed in Table 3.We provide some remarks on the proposed PKC as follows.Remark 22.
We can choose a 2-dimensional square matrixΔ with determinant equal to ±
1 because the inverse Δ
-
1 can be easily represented when |
Δ
|
=
±
1.Remark 23.
We should choosep and q slightly greater than ∑
i
=
1
n
‍
g
i
max
⁡
F
i and ∑
i
=
1
n
‍
h
i
max
⁡
F
i, respectively. See (24). So for convenience of discussions, we always assume that
(32)
p
≈
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
≈
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.Remark 24.
In Algorithm2, we suggest choosing ζ
i and η
i with some special lengths in order that the generated u
i’s (v
i’s, resp.) share an almost same binary length; that is,
(33)
|
ζ
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
-
|
∏
j
=
i
n
‍
α
j
|
2
,
|
η
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
-
|
∏
j
=
i
n
‍
β
j
|
2
,
So, for i
=
1
,
…
,
n
-
1, we have
(34)
|
u
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
=
|
u
1
|
2
,
|
v
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
=
|
v
1
|
2
.
For convenience of discussions, we also assume that u
1 and v
1 have an almost same binary length, so from (34), we have
(35)
|
u
i
|
2
≈
|
u
1
|
2
≈
|
v
i
|
2
≈
|
v
1
|
2
.


## 3.4.1. Key Generation

Randomly choose two sequencesu
=
(
u
1
,
…
,
u
n
) and v
=
(
v
1
,
…
,
v
n
)
∈
(
ℤ
+
)
n, satisfying conditions (14) and (15) given in Theorem 18, and a two-dimensional invertible square matrix with positive integer entries upper bounded by a constant,
(22)
Δ
=
(
δ
11
δ
12
δ
21
δ
22
)
,
δ
i
j
=
𝒪
(
1
)
,
1
≤
i
,
j
≤
2
.
Compute
(23)
(
g
h
)
=
(
g
1
⋯
g
n
h
1
⋯
h
n
)
=
Δ
(
u
v
)
.
Randomly choose two primes p
≠
q such that
(24)
p
>
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
>
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.
Let N
=
p
q. Compute the vector b
=
(
b
1
,
…
,
b
n
) using the Chinese remainder theorem,
(25)
b
i
≡
g
i
(
mod
⁡
p
)
,
b
i
≡
h
i
(
mod
⁡
q
)
.
Randomly choose an integer w
∈
ℤ
N
* and compute
(26)
a
i
=
w
b
i
(
mod
⁡
N
)
,
i
=
1
,
…
,
n
.
The public key is a
=
(
a
1
,
…
,
a
n
). The secret key consists of p, q, and w
-
1
(
mod
⁡
N
), Δ
-
1. When decrypting a ciphertext, the decrypter also needs to store the values of gc
d
i
u, gc
d
i
v, i
=
1
,
…
,
n, and Table 1.


## 3.4.2. Encryption

To encrypt a messagem
=
(
m
1
,
…
,
m
n
)
∈
𝕄
=
ℤ
8
n, the encrypter randomly chooses an auxiliary key r
=
(
r
1
,
…
,
r
n
)
∈
{
0,1
}
n and computes the plaintext x
=
(
f
1
,
…
,
f
n
)
=
F
(
m
,
r
) and the ciphertext using the public key a,
(27)
c
=
〈
a
,
x
〉
.


## 3.4.3. Decryption

To decipher a ciphertextc, the decrypter firstly computes c
N
=
〈
w
-
1
c
〉
N
=
w
-
1
c
(
mod
⁡
N
), and then c
p
=
〈
c
N
〉
p, c
q
=
〈
c
N
〉
q. Secondly, the decrypter computes
(28)
(
s
1
s
2
)
=
Δ
-
1
(
c
p
c
q
)
.
Thirdly, the decrypter uses theOnion Algorithm to determine a unique solution x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P to (11). Finally, the decrypter decodes x into the corresponding message m by using the method illustrated in Remark 11.


## 3.4.4.  Why Decryption Works

To illustrate why the decryption works, we observe thatc
N
=
〈
b
,
x
〉
(
mod
⁡
N
) from (26), so c
p
=
〈
g
,
x
〉
(
mod
⁡
p
) and c
q
=
〈
h
,
x
〉
(
mod
⁡
q
) according to (25). From (23), we know that g
i
=
δ
11
u
i
+
δ
12
v
i
>
0, so 0
≤
c
p
<
p from (24). Now we conclude that c
p
=
〈
g
,
x
〉 and similarly c
q
=
〈
h
,
x
〉. Hence, we have
(29)
(
s
1
s
2
)
=
Δ
-
1
(
g
h
)
(
f
1
⋮
f
n
)
=
(
u
v
)
(
f
1
⋮
f
n
)
,
from which (11) is derived. It is easy to verify that (11) satisfies the conditions listed in Theorem 18, and hence can be efficiently solved withOnion Algorithm to give a unique solution x
∈
𝕊
P. Then x is decoded into the original message m.


## 3.4.5. On Generatingu and v

Now, we give an algorithm to generate then-dimensional positive integer sequences u and v satisfying conditions (14) and (15) in Theorem 18.Theorem 20.
The generatedu and v satisfy (14) and (15).Proof.
We note that, fori
=
1
,
…
,
n,
(30)
gc
d
i
u
=
gcd
(
u
1
,
…
,
u
i
)
=
gcd
(
ζ
1
∏
j
=
1
n
‍
α
j
,
…
,
ζ
i
∏
j
=
i
n
‍
α
j
)
=
gcd
(
∏
j
=
1
n
‍
α
j
,
…
,
∏
j
=
i
n
‍
α
j
)
=
∏
j
=
i
n
‍
α
j
.
Similarly, gc
d
i
v
=
gcd
(
v
1
,
…
,
v
i
)
=
∏
j
=
i
n
‍
β
j. We immediately have gc
d
n
u
=
α
n
=
gc
d
n
v
=
β
n
=
1. Thus, (14) is satisfied. For i
=
2
,
…
,
n, we have
(31)
(
gc
d
i
-
1
u
gc
d
i
u
,
gc
d
i
-
1
v
gc
d
i
v
)
=
(
∏
j
=
i
-
1
n
‍
α
j
∏
j
=
i
n
‍
α
j
,
∏
j
=
i
-
1
n
‍
β
j
∏
j
=
i
n
‍
β
j
)
=
(
α
i
-
1
,
β
i
-
1
)
∈
AI
P
〈
i
〉
12
∪
AI
P
〈
i
〉
12
T
,
so (15) is satisfied, as desired.Now we use an example to illustrate Algorithm2.Algorithm 2:Generating u and v.
(1) Fori
=
1
,
…
,
n
-
1, randomly choose (
α
i
,
β
i
)
∈
AIP
〈
i
+
1
〉
12
∪
AIP
〈
i
+
1
〉
12
T with repetition permitted.
(2) Randomly choose2
(
n
-
1
) numbers ζ
2
,
…
,
ζ
n and
η
2
,
…
,
η
n and set ζ
1
=
η
1
=
α
n
=
β
n
=
1 such that
gcd
(
ζ
i
,
α
j
)
=
gcd
(
η
i
,
β
j
)
=
1 for 1
≤
i
,
j
≤
n, and
gcd
(
ζ
i
,
ζ
i
+
1
)
=
gcd
(
η
i
,
η
i
+
1
)
=
1 for i
=
1
,
…
,
n
-
1.
(3)for  i
=
1
,
…
,
n  do
(4)u
i
=
ζ
i
∏
j
=
i
n
‍
α
j,  v
i
=
η
i
∏
j
=
i
n
‍
β
j.   (★)
(5)end for
(6)return  u
=
(
u
1
,
…
,
u
n
), v
=
(
v
1
,
…
,
v
n
).Example 21.
We randomly choose(
α
1
,
β
1
)
=
(
11,3
)
∈
AI
P
2
∪
AI
P
2
T, (
α
2
,
β
2
)
=
(
1,31
)
∈
AI
P
3
∪
AI
P
3
T and ζ
2
=
9, ζ
3
=
13, η
2
=
2, η
3
=
89, and set ζ
1
=
η
1
=
α
3
=
β
3
=
1, so we can compute u
1
=
ζ
1
α
1
α
2
α
3
=
11, u
2
=
ζ
2
α
2
α
3
=
9, u
3
=
ζ
3
α
3
=
13, and v
1
=
η
1
β
1
β
2
β
3
=
93, v
2
=
η
2
β
2
β
3
=
62, v
3
=
η
3
β
3
=
89, which are the coefficients in Example 19.


## 3.4.6.  Remarks and Suggested Security Parameters

The suggested parametersn are listed in Table 3.We provide some remarks on the proposed PKC as follows.Remark 22.
We can choose a 2-dimensional square matrixΔ with determinant equal to ±
1 because the inverse Δ
-
1 can be easily represented when |
Δ
|
=
±
1.Remark 23.
We should choosep and q slightly greater than ∑
i
=
1
n
‍
g
i
max
⁡
F
i and ∑
i
=
1
n
‍
h
i
max
⁡
F
i, respectively. See (24). So for convenience of discussions, we always assume that
(32)
p
≈
∑
i
=
1
n
‍
g
i
max
⁡
F
i
,
q
≈
∑
i
=
1
n
‍
h
i
max
⁡
F
i
.Remark 24.
In Algorithm2, we suggest choosing ζ
i and η
i with some special lengths in order that the generated u
i’s (v
i’s, resp.) share an almost same binary length; that is,
(33)
|
ζ
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
-
|
∏
j
=
i
n
‍
α
j
|
2
,
|
η
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
-
|
∏
j
=
i
n
‍
β
j
|
2
,
So, for i
=
1
,
…
,
n
-
1, we have
(34)
|
u
i
|
2
≈
|
∏
j
=
1
n
‍
α
j
|
2
=
|
u
1
|
2
,
|
v
i
|
2
≈
|
∏
j
=
1
n
‍
β
j
|
2
=
|
v
1
|
2
.
For convenience of discussions, we also assume that u
1 and v
1 have an almost same binary length, so from (34), we have
(35)
|
u
i
|
2
≈
|
u
1
|
2
≈
|
v
i
|
2
≈
|
v
1
|
2
.


## 4. Performance

This section analyzes the performance related issues, such as the computational complexity of the encryption and decryption algorithms, the public key size and the information rate.


### 4.1. Estimation of Public Key Size

We first point out two facts. Firstly, when generatingu and v by using Algorithm 2, for i
=
1
,
…
,
n
-
1, we randomly choose (
α
i
,
β
i
)
∈
AI
P
〈
i
+
1
〉
12
∪
AI
P
〈
i
+
1
〉
12
T in the first step. We also set α
n
=
β
n
=
1. So from Table 2, we see that α
i
β
i
≤
47, for i
=
1
,
…
,
n
-
1. Secondly, max
⁡
F
i
≤
191.From (23), we rewrite g
i and h
i as g
i
=
δ
11
u
i
+
δ
12
v
i and h
i
=
δ
21
u
i
+
δ
22
v
i with δ
i
j
=
𝒪
(
1
), and from (35), we have |
g
i
|
2
≈
|
h
i
|
2
≈
|
u
i
|
2
≈
|
v
i
|
2
≈
|
u
1
|
2
≈
|
v
1
|
2.We recall that the public key consists ofn integers a
=
(
a
1
,
…
,
a
n
), and the length of each of them is upper bounded by that of N
=
p
q, so from (32) we have
(36)
|
N
|
2
≈
|
p
|
2
+
|
q
|
2
≤
|
191
∑
i
=
1
n
‍
g
i
|
2
+
|
191
∑
i
=
1
n
‍
h
i
|
2
≈
|
191
n
g
i
|
2
+
|
191
n
h
i
|
2
≈
|
19
1
2
n
2
u
1
v
1
|
2
=
|
19
1
2
n
2
∏
i
=
1
n
-
1
‍
α
i
β
i
|
2
≤
|
19
1
2
n
2
4
7
n
-
1
|
2
≈
(
n
-
1
)
lo
g
2
47
+
2
lo
g
2
n
+
2
lo
g
2
191
.
So the public key size is estimated via
(37)
n
|
N
|
2
≤
n
(
n
-
1
)
lo
g
2
47
+
2
n
lo
g
2
n
+
2
n
lo
g
2
191
,
which is upper bounded by 𝒪
(
n
2
).


### 4.2.  Computational Complexity

We analyze the computational costs for encrypting a message and decrypting a ciphertext. Givenm and r, we only need 𝒪
(
n
) bit operations to compute x. To encrypt x, the encrypter only needs to perform n multiplications with the multipliers a
i bounded by 𝒪
(
n
) and f
i
≤
191, and n
-
1 additions. So 𝒪
(
n
2
) bit operations suffice to do the computations in (27). The computational complexity for the encryption algorithm is given as 𝒪
(
n
2
).The decrypter first performs a modular multiplicationc
N
=
〈
w
-
1
c
〉
N, and two modular reductions c
p
=
〈
c
N
〉
p, c
q
=
〈
c
N
〉
q, which cost 𝒪
(
n
2
) bit operations in total. To solve (11) for each f
i and hence m
i, the decrypter computes (
*
) to determine (
f
i
1
,
f
i
2
) with the moduli gc
d
i
-
1
u
/
gc
d
i
u, gc
d
i
-
1
v
/
gc
d
i
v
≤
47. So it will take 𝒪
(
1
) bit operations to compute each (
f
i
1
,
f
i
2
). The look-up operation on Sub-T〈
i
〉
12 for f
i and m
i only costs 𝒪
(
1
) bit operations. So the decrypter only needs 𝒪
(
n
) bit operations to use theOnion Algorithm to solve (11) for x and m. The computational complexity of the decryption algorithm is also 𝒪
(
n
2
).


### 4.3.  Information Rate

The information rateρ of a cryptosystem is defined as the ratio of the binary length of the message to that of the cipher-text. In the proposed cryptosystem, the information rate is
(38)
ρ
=
3
n
lo
g
2
max
⁡
ℂ
.
We need to evaluate the binary length of max
⁡
ℂ. Note that
(39)
max
⁡
ℂ
=
∑
i
=
1
n
‍
a
i
max
⁡
F
i
<
191
∑
i
=
1
n
‍
a
i
<
191
n
N
.
If we rewrite (36) as
(40)
N
≤
19
1
2
n
2
4
7
n
-
1
,
we obtain
(41)
max
⁡
ℂ
≤
191
n
N
<
19
1
3
n
3
4
7
n
-
1
.
So the information rate is evaluated by
(42)
ρ
≈
3
n
lo
g
2
(
19
1
3
n
3
4
7
n
-
1
)
,
which is asymptotically 3
/
lo
g
2
47
≈
0.54.The public key sizes and information rates for the suggested security parameters are listed in Table3, from which we see that the public key size is about dozens of a 1024-RSA modulus. The public key size is acceptable.


## 4.1. Estimation of Public Key Size

We first point out two facts. Firstly, when generatingu and v by using Algorithm 2, for i
=
1
,
…
,
n
-
1, we randomly choose (
α
i
,
β
i
)
∈
AI
P
〈
i
+
1
〉
12
∪
AI
P
〈
i
+
1
〉
12
T in the first step. We also set α
n
=
β
n
=
1. So from Table 2, we see that α
i
β
i
≤
47, for i
=
1
,
…
,
n
-
1. Secondly, max
⁡
F
i
≤
191.From (23), we rewrite g
i and h
i as g
i
=
δ
11
u
i
+
δ
12
v
i and h
i
=
δ
21
u
i
+
δ
22
v
i with δ
i
j
=
𝒪
(
1
), and from (35), we have |
g
i
|
2
≈
|
h
i
|
2
≈
|
u
i
|
2
≈
|
v
i
|
2
≈
|
u
1
|
2
≈
|
v
1
|
2.We recall that the public key consists ofn integers a
=
(
a
1
,
…
,
a
n
), and the length of each of them is upper bounded by that of N
=
p
q, so from (32) we have
(36)
|
N
|
2
≈
|
p
|
2
+
|
q
|
2
≤
|
191
∑
i
=
1
n
‍
g
i
|
2
+
|
191
∑
i
=
1
n
‍
h
i
|
2
≈
|
191
n
g
i
|
2
+
|
191
n
h
i
|
2
≈
|
19
1
2
n
2
u
1
v
1
|
2
=
|
19
1
2
n
2
∏
i
=
1
n
-
1
‍
α
i
β
i
|
2
≤
|
19
1
2
n
2
4
7
n
-
1
|
2
≈
(
n
-
1
)
lo
g
2
47
+
2
lo
g
2
n
+
2
lo
g
2
191
.
So the public key size is estimated via
(37)
n
|
N
|
2
≤
n
(
n
-
1
)
lo
g
2
47
+
2
n
lo
g
2
n
+
2
n
lo
g
2
191
,
which is upper bounded by 𝒪
(
n
2
).


## 4.2.  Computational Complexity

We analyze the computational costs for encrypting a message and decrypting a ciphertext. Givenm and r, we only need 𝒪
(
n
) bit operations to compute x. To encrypt x, the encrypter only needs to perform n multiplications with the multipliers a
i bounded by 𝒪
(
n
) and f
i
≤
191, and n
-
1 additions. So 𝒪
(
n
2
) bit operations suffice to do the computations in (27). The computational complexity for the encryption algorithm is given as 𝒪
(
n
2
).The decrypter first performs a modular multiplicationc
N
=
〈
w
-
1
c
〉
N, and two modular reductions c
p
=
〈
c
N
〉
p, c
q
=
〈
c
N
〉
q, which cost 𝒪
(
n
2
) bit operations in total. To solve (11) for each f
i and hence m
i, the decrypter computes (
*
) to determine (
f
i
1
,
f
i
2
) with the moduli gc
d
i
-
1
u
/
gc
d
i
u, gc
d
i
-
1
v
/
gc
d
i
v
≤
47. So it will take 𝒪
(
1
) bit operations to compute each (
f
i
1
,
f
i
2
). The look-up operation on Sub-T〈
i
〉
12 for f
i and m
i only costs 𝒪
(
1
) bit operations. So the decrypter only needs 𝒪
(
n
) bit operations to use theOnion Algorithm to solve (11) for x and m. The computational complexity of the decryption algorithm is also 𝒪
(
n
2
).


## 4.3.  Information Rate

The information rateρ of a cryptosystem is defined as the ratio of the binary length of the message to that of the cipher-text. In the proposed cryptosystem, the information rate is
(38)
ρ
=
3
n
lo
g
2
max
⁡
ℂ
.
We need to evaluate the binary length of max
⁡
ℂ. Note that
(39)
max
⁡
ℂ
=
∑
i
=
1
n
‍
a
i
max
⁡
F
i
<
191
∑
i
=
1
n
‍
a
i
<
191
n
N
.
If we rewrite (36) as
(40)
N
≤
19
1
2
n
2
4
7
n
-
1
,
we obtain
(41)
max
⁡
ℂ
≤
191
n
N
<
19
1
3
n
3
4
7
n
-
1
.
So the information rate is evaluated by
(42)
ρ
≈
3
n
lo
g
2
(
19
1
3
n
3
4
7
n
-
1
)
,
which is asymptotically 3
/
lo
g
2
47
≈
0.54.The public key sizes and information rates for the suggested security parameters are listed in Table3, from which we see that the public key size is about dozens of a 1024-RSA modulus. The public key size is acceptable.


## 5. Security Analysis

The adversary has two methods to attack the proposed cryptosystem: solve the cracking problem [26], that is, breaking the one-wayness of the underlying encryption function without knowing the trapdoor, and solve the trapdoor problem, that is, reversing the basic mathematical construction of the trapdoor in a PKC. Efficient algorithms for the latter also help to efficiently solve the former. In this section, we first analyze the hardness of the cracking problem by investigating the underlying PSTOFs under some attack models, and then examine the intractability for key-recovery attacks.


### 5.1. Brute Force Attack

#### 5.1.1. Brute Force Attack I

One straightforward way to attack the system is to solve (27) for x by exhausting all the ∑
i
=
1
n
‍
a
i
f
i with x
∈
𝕊
P. But note that |
F
i
|
=
16, so the brute force attack will take on the order of 𝒪
(
1
6
n
) steps. The computational costs under brute force attack I (BFA I for short) given in Table 3 are measured in bit operations with respect to the suggested parameters.


#### 5.1.2. Brute Force Attack II

A better method is to compute and sort each of the sets(43)
S
1
=
{
∑
i
=
1
n
/
2
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
S
2
=
{
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
and then scan S
1 and S
2, looking for a common element. If a common element s
=
∑
i
=
1
n
/
2
‍
a
i
f
i
=
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i is found, then c
=
∑
i
=
1
n
‍
a
i
f
i. The entire procedure takes 𝒪
(
n
1
6
n
/
2
) steps [27]. See Table 3 for the computational costs under brute force attack II (BFA II for short) with respect to the suggested parameters.


### 5.2. Linearization Attack

In this subsection, we assume that the adversary aims at recovering the corresponding plaintext (and hence the message) by reversing the underlying encryption function without learning the trapdoor information. When a concrete attack model is concerned, we firstly formalize and then prove the underlying PSTOF.


#### 5.2.1. Linearization Attack I

Encryption function (27) of the proposed PKC is a linear function mapping an element in 𝕊
P into an integer in the ciphertext space ℂ. Now we define
(44)
T
1
:
𝕊
E
=
ℤ
192
n
⟼
ℂ
=
T
1
(
𝕊
E
)
,
T
1
(
x
)
=
〈
a
,
x
〉
=
c
,
x
∈
𝕊
E
.Theorem 25.
If the compact knapsackC
K
P
192
(
a
,
c
) is intractable, T
1 is a PSTOF.Proof.
It is easy to verify that the five conditions except the second one in Definition2 are satisfied; (45) below guarantees the noninjectivity of function T
1. So T
1 is indeed a PSTOF underlying the proposed PKC under the compact knapsack intractability assumption.The distinction between the two functions (27) and (44) is that the preimage sets are different. Given a ciphertext c, c will have a unique preimage in 𝕊
P, namely, the corresponding plaintext, while c will have many preimages in the equivalent plaintext space 𝕊
E.We have pointed out in Remark9 that the message encoding function F can simulate the process of randomly choosing an element from 𝕊
E
=
ℤ
192
n. That is to say, if one can obtain a preimage of c with respect to T
1, the preimage is a randomly output preimage from all the preimages in T
1
-
1
(
c
)
=
{
x
∈
𝕊
E
∣
T
(
x
)
=
c
} and not necessarily the plaintext x
∈
𝕊
P.Now, we explain why we say we can further weaken the underlying cryptographic hardness assumption. If we assume that the compact knapsack problemCK
P
192
(
a
,
c
) is easy; that is, T
1 is not one-way, the proposed cryptosystem seems still secure. Under the assumption, there exists an oracle 𝒜 for the compact knapsack problem CK
P
192
(
a
,
c
). We note that each time the adversary can obtain a (at most polynomially many) preimage of c by accessing the oracle 𝒜. However, we will show that c has exponentially many (denoted as 2
λ
1
(
n
)) preimages, over which the plaintext x
∈
𝕊
P seems uniformly distributed. So we can heuristically argue that the adversary only obtains polynomially many p
(
n
) preimages by performing polynomially many p
(
n
) accesses to the oracle 𝒜, and hence those p
(
n
) preimages contain the target plaintext x
∈
𝕊
P with a negligible probability p
(
n
)
/
2
λ
1
(
n
). Thus, we can conceive T
1 as a preimage selective trapdoor (not one-way) function assuming that the underlying compact knapsack problem CK
P
192
(
a
,
c
) is easy. In fact, under the assumption, the security of the proposed PKC is based on the assumption that it is computationally infeasible to recover a solution to a highly noninjective compact knapsack problem CK
P
192
(
a
,
c
) with a predesignated special structure (i.e., the structure of 𝕊
P).To illustrate, we need to show that a ciphertext has exponentially many preimages with respect toT
1. We use the preimage density given in Definition 4 to roughly evaluate the number of preimages for a ciphertext. To begin with, we need to estimate the cardinalities for the image set (ciphertext space ℂ) and the preimage set (i.e., the equivalent space 𝕊
E
=
ℤ
192
n). It is obvious that |
𝕊
E
|
=
19
2
n. We note (41) and |
ℂ
|
≤
max
⁡
ℂ
+
1
≈
max
⁡
ℂ, so we have |
ℂ
|
≤
19
1
3
n
3
4
7
n
-
1 and hence the preimage density is
(45)
P
d
1
=
𝕊
E
|
ℂ
|
≥
19
2
n
19
1
3
n
3
4
7
n
-
1
=
2
λ
1
(
n
)
=
2
𝒪
(
n
)
,
where λ
1
(
n
)
=
n
lo
g
2
192
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191. See Table 3 for the manipulations of P
d
1 for the suggested security parameters.


#### 5.2.2. Linearization Attack II

Now, we consider an attack transforming (27) into a standard 0-1 knapsack problem. The adversary can combine all of these 16 values in F
i denoted as F
i
=
{
f
i
(
1
)
,
…
,
f
i
(
16
)
} with each entry a
i in a to derive a new integer sequence w
=
(
w
1
(
1
)
,
…
,
w
1
(
16
)
,
…
,
w
n
(
1
)
,
…
,
w
n
(
16
)
) such that w
i
(
j
)
=
a
i
f
i
(
j
) with i
=
1
,
…
,
n, j
=
1
,
…
,
16. Under the linearization attack model, we define the following function:
(46)
T
2
:
𝕊
E
2
=
{
0,1
}
16
n
⟼
ℂ
2
=
T
2
(
𝕊
E
2
)
,
T
2
(
y
)
=
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
y
i
(
j
)
=
c
,
where y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
∈
𝕊
E
2. We set
(47)
𝕊
P
2
=
{
y
∈
{
0,1
}
16
n
∣
∑
j
=
1
16
‍
y
i
(
j
)
=
1,1
≤
i
≤
n
}
.Theorem 26.
If the knapsack problemK
P
(
w
,
c
) is intractable, T
2 is a PSTOF.Proof.
To verify(
3
) and (
4
) in Definition 2, we consider a mapping τ
:
𝕊
P
↦
𝕊
P
2 as follows. Given an arbitrary x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P, we must have that for i
=
1
,
…
,
n, there should exist a unique f
i
(
j
)
∈
F
i such that f
i
=
f
i
(
j
) with 1
≤
j
≤
16. Now we define y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
=
τ
(
x
) with y
i
(
j
)
=
1 when f
i
=
f
i
(
j
) and y
i
(
j
)
=
0 otherwise. So we must have for 1
≤
i
≤
n, ∑
j
=
1
16
‍
y
i
(
j
)
=
1, and ∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
f
i. So y
∈
𝕊
P
2. Furthermore, any y
∈
𝕊
P
2 must have a preimage x
=
τ
-
1
(
y
) with f
i
=
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
). We further note that |
𝕊
P
|
=
|
𝕊
P
2
|
=
1
6
n and can argue that τ is a bijection from 𝕊
P to 𝕊
P
2. By observing
(48)
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
W
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
f
i
=
〈
a
,
x
〉
,
we know that x
∈
𝕊
P is a solution to (27) if and only if y
=
τ
(
x
) is a solution to (46). So (
3
) and (
4
) in Definition 2 are satisfied.
To show the noninjectivity of (46), we first note that the image set is ℂ
2
=
T
2
(
𝕊
E
2
) and that
(49)
max
⁡
ℂ
2
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
<
191
×
16
∑
i
=
1
n
‍
a
i
<
16
×
191
n
N
≤
16
×
19
1
3
n
3
4
7
n
-
1
.
The last symbol  ≤  in (49) is due to (40). Hence, we have |
ℂ
2
|
<
16
×
19
1
3
n
3
4
7
n
-
1
+
1. So we compute the preimage density via
(50)
P
d
2
=
𝕊
E
2
|
ℂ
2
|
≥
2
16
n
16
×
19
1
3
n
3
4
7
n
-
1
=
2
λ
2
(
n
)
=
2
𝒪
(
n
)
,
where λ
2
(
n
)
=
16
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
4. See Table 3 for the manipulations of P
d
2 for the suggested security parameters. Thus, T
2 is indeed a PSTOF.The computational infeasibility for the linearization attack is supported by either of the following arguments.Remark 27 (noninjectivity-based security argument).
If we assume that the adversary can solve the knapsack problemKP
(
w
,
c
), then T
2 is a preimage selective trapdoor function. A given ciphertext c will have exponentially many 2
λ
2
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages including the target solution in 𝕊
E
2 with a negligible probability p
(
n
)
/
2
λ
2
(
n
).Remark 28 (density-based security argument).
It is known that knapsack problems achieving a density smaller than 0.9408 are solvable with an overwhelming probability by accessing an oracle for the shortest vector problem over lattices [23, 24]. We show that the underlying knapsack problem KP
(
w
,
c
) (46) obtain a sufficiently large density. Note that
(51)
d
2
=
16
n
lo
g
2
max
⁡
w
≥
16
n
lo
g
2
(
max
⁡
a
max
⁡
F
i
)
≥
16
n
lo
g
2
(
191
N
)
.
Observing (40), we have that d
2 approaches 16
/
lo
g
2
47
≈
2.88 when n approaches infinity.Remark 29 (dimension-based security argument).
In real life practice, we use known efficient lattice reduction algorithms to simulate a shortest vector oracle in low-dimensional lattice. However, when the dimension is sufficiently large, say larger than 500, known lattice reduction algorithms fail to output a relatively short lattice vector. Under the suggested parameters, knapsack problemKP
(
w
,
c
) (46) achieves sufficiently large dimensions 960, 1440, 1920, respectively.


#### 5.2.3. Linearization Attack III

Now we consider another linear attack III, which also transforms the problem (27) into a knapsack problem. We note that 0
≤
f
i
≤
191, so 8 bits are needed to represent each f
i. For i
=
1
,
…
,
n, we define d
i
(
j
)
=
2
j
-
1
a
i with j
=
1
,
…
,
8 and obtain an 8
n-dimensional integer sequence d
=
(
d
1
(
1
)
,
…
,
d
1
(
8
)
,
…
,
d
n
(
1
)
,
…
,
d
n
(
8
)
). Now we provide the following function:
(52)
T
3
:
𝕊
E
3
=
{
0,1
}
8
n
⟼
ℂ
3
=
T
3
(
𝕊
E
3
)
,
T
3
(
z
)
=
〈
d
,
z
〉
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
z
i
(
j
)
=
c
,
where z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
∈
𝕊
E
3. We set
(53)
𝕊
P
3
=
{
z
∈
{
0,1
}
8
n
∣
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
∈
F
i
,
1
≤
i
≤
n
}
.Theorem 30.
If the knapsack problemK
P
(
d
,
c
) is intractable, T
3 is a PSTOF.Proof.
It is easy to verify that(
1
) and (
5
) in Definition 2 are satisfied. In fact, any element z
∈
𝕊
P
3 stands for a binary representation of an element x
∈
𝕊
P, and in turn, the binary representation of any element x
∈
𝕊
P falls into the set 𝕊
P
3. So if we define a mapping τ from 𝕊
P
3 to 𝕊
P, τ
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
=
(
∑
j
=
1
8
‍
2
j
-
1
z
1
(
j
)
,
…
,
∑
j
=
1
8
‍
2
j
-
1
z
n
(
j
)
), τ is a bijection. Furthermore, we note that
(54)
〈
d
,
z
〉
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
=
〈
a
,
x
〉
.
So z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
) is a solution to (52) if and only if τ
(
z
)
=
x
∈
𝕊
P is a solution to (27). So conditions (
3
) and (
4
) in Definition 2 are satisfied. To show the noninjectivity of T
3, we first evaluate the cardinalities of 𝕊
E
3 and ℂ
3. It is obvious that |
𝕊
E
3
|
=
2
8
n. To estimate |
ℂ
3
|, we first note that
(55)
max
⁡
ℂ
3
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
=
255
∑
i
=
1
n
‍
a
i
<
255
×
n
N
≤
255
×
19
1
2
n
3
4
7
n
-
1
.
So the preimage density of T
3 can be estimated via
(56)
P
d
3
=
𝕊
E
3
|
ℂ
3
|
≥
2
8
n
255
×
19
1
2
n
3
4
7
n
-
1
=
2
λ
3
(
n
)
=
2
𝒪
(
n
)
,
where λ
3
(
n
)
=
8
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
lo
g
2
255. See Table 3 for the values of P
d
3 under the suggested security parameters. Thus, condition (
2
) in Definition 2 is satisfied, so T
3 is indeed a PSTOF.Remark 31 (noninjectivity-based security argument).
If one conquers the knapsack problemKP
(
d
,
c
), then T
3 is a pre-image selective trapdoor function. A ciphertext will have exponentially many 2
λ
3
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages which include the solution in 𝕊
E
3 with a negligible probability p
(
n
)
/
2
λ
3
(
n
).Remark 32 (density and dimension based arguments).
The density to (52) is estimated via
(57)
d
3
=
8
n
lo
g
2
max
⁡
d
≥
8
n
lo
g
2
(
2
7
max
⁡
a
)
≥
8
n
lo
g
2
(
2
7
N
)
,
which is 8
/
lo
g
2
47
≈
1.44
>
0.9408 when n approaches infinity. The knapsack problem KP
(
d
,
c
) (52) has sufficiently large dimensions 480, 540, and 960 for the suggested parameters.


### 5.3.  Key-Recovery Attacks

When we discuss the cracking problem, we only study the computational infeasibilities for the adversary to solve (27) without considering the structure of the public integer sequence a. To claim the security of the proposed PKC, we need to examine whether the trapdoor is easy to discover or not. So we need to examine the security of the proposed PKC against known attacks.The public integer sequencea distinguishes with a randomly chosen positive integer sequence in two respects, that is, the special structures defined in (14) and (15) and the size conditions given in (24). We discuss the effects of these conditions on the security.


#### 5.3.1. GCD Attack

The GCD attack in [4] was used to successfully attack the knapsack-based probabilistic public key encryption [28]. The attack illustrates that if the entries of b
=
(
b
1
,
…
,
b
n
) assume a linear combinatorial relation with small integer combinatorial coefficients, we can recover the secret modulus N by computing the greatest common divisor for a set of numbers. This point will be explored later on, or the readers can refer to [4] for more details. We first note that if the modulus N
=
p
q is known, under the suggested parameters, n
=
60, 90, and 120, the binary length of N is upper bounded by 355, 523, 690, respectively. See (36). It is not intractable to factor the moduli by using the fastest factorization algorithm [29]. Hence, one can factor N into its prime products. Once p and q have been obtained, the adversary can do the modular reductions, a
i
p
=
a
i
(
mod
⁡
p
) and a
i
q
=
a
i
(
mod
⁡
p
). If we denote the modular reductions of w
-
1 modulo p and q as w
p
-
1 and w
q
-
1, from (25) and (26), we know g
i
=
a
i
p
w
p
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
p
) and h
i
=
a
i
q
w
q
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
q
) and then exhaust the matrix Δ to reverse the process of (23) as
(58)
(
u
v
)
=
Δ
-
1
(
g
h
)
=
(
δ
22
-
δ
12
-
δ
21
δ
11
)
(
g
h
)
,
where for convenience, we just set |
Δ
|
=
1. So we have
(59)
u
i
=
δ
22
〈
a
i
p
w
p
-
1
〉
p
-
δ
12
〈
a
i
q
w
q
-
1
〉
q
,
v
i
=
δ
11
〈
a
i
q
w
q
-
1
〉
q
-
δ
21
〈
a
i
p
w
p
-
1
〉
p
.
We note that gc
d
n
-
1
u
∣
u
i, gc
d
n
-
1
v
∣
v
i for i
=
1
,
…
,
n
-
1, a
i
p and a
i
q are publicly computable once p and q have been obtained, and (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
∪
AI
P
〈
n
〉
12
T and δ
i
j can be efficiently exhausted (and hence we can assume that they are all known). So, for i
=
1
,
…
,
n
-
1, we have
(60)
δ
22
a
i
p
x
0
-
δ
22
x
2
i
p
-
δ
12
a
i
q
x
1
-
δ
12
x
2
i
+
1
q
-
k
i
gc
d
n
-
1
u
=
0
,
δ
11
a
i
q
x
1
-
δ
11
x
2
i
+
1
q
-
δ
21
a
i
p
x
0
-
δ
21
x
2
i
p
-
l
i
gc
d
n
-
1
v
=
0
with integer unknowns 0
<
x
0
=
w
p
-
1
<
p, 0
<
x
1
=
w
q
-
1
<
q, x
2
i (x
2
i
+
1, resp.) being the incomplete quotient of a
i
p
x
0 (a
i
q
x
1, resp.) divided by p (q, resp.), and k
i and l
i are the quotients of u
i and v
i divided by gc
d
n
-
1
u and gc
d
n
-
1
v, respectively. So we have 0
≤
x
2
i
<
a
i
p, 0
≤
x
2
i
+
1
<
a
i
q, 0
<
k
i
<
p
/
gc
d
n
-
1
u, and 0
<
l
i
<
q
/
gc
d
n
-
1
v. We can use an efficient heuristic algorithm for solving a system of linear Diophantine equations with lower and upper bounds on the variables given in [30] (see also Section 3 of [4] for a simplified description) to determine these unknowns, and eventually the full secret keys. So we caution that in implementation, we must keep the modulus N secret. However, we will show that the GCD attack is useless to derive modulus N.The condition for the GCD attack to succeed in finding modulusN is that we can construct some linear relations using the entries of the public sequence b. To illustrate, we recall (26) and argue that there must exist integers s
i such that b
i
w
-
s
i
N
=
a
i. We assume that the entries of b share some linear combinatorial relations with small coefficients, say t
1
b
1
-
t
2
b
2
=
0, t
3
b
3
-
t
4
b
4
=
0, where by saying small coefficients we mean we can efficiently do exhaustive search for these t
i’s. So we conclude that N
∣
t
1
a
1
-
t
2
a
2
=
N
(
s
1
t
1
-
s
2
t
2
) and N
∣
t
3
a
3
-
t
4
a
4 and hence can expect N
=
gcd
(
t
1
a
1
-
t
2
a
2
,
t
3
a
3
-
t
4
a
4
). We must admit that the entries of u (and v) do share a linear combinatorial relation; for example, from (★) we derive ζ
2
u
1
-
α
1
u
2
=
0. However, we should bear in mind that b is fully scrambled by (23) and (25) especially through the confusion role of the Chinese remainder theorem in (25). So it is unlikely for the adversary to derive modulus N by launching a GCD-like attack on the proposal.


#### 5.3.2. Simultaneous Diophantine Approximation Attack

After Shamir broke the basic Merkle-Hellman knapsack cryptosystem [31, 32], cryptanalysts began to investigate the security of the multiply iterated Merkle-Hellman cryptosystem. Lagarias observed that the size conditions and the modular transformation in the multiply iterated Merkle-Hellman cryptosystem help him construct a simultaneous Diophantine approximation problem [7]. Lagarias showed that he can successfully launch a key-recovery attack on the doubly iterated Merkle-Hellman cryptosystem through his simultaneous Diophantine approximation approach.Many knapsack-type cryptosystems use size conditions to disguise an easy knapsack problem. In such a cryptosystem, the designer randomly generates an easy knapsack problem,y
=
∑
i
=
1
n
‍
a
i
x
i
,
x
i
∈
[
0
,
2
b
-
1
], and chooses a modulus m and a multiplier w, gcd
(
m
,
w
)
=
1. He uses the size condition m
>
(
2
b
-
1
)
∑
i
=
1
n
‍
a
i to disguise the easy knapsack sequence a
=
(
a
1
,
…
,
a
n
) as a seemingly hard knapsack sequence b
=
(
b
1
,
…
,
b
n
) by a modular multiplication, b
i
=
〈
w
a
i
〉
m. The size condition and the public sequence can be utilized to derive a simultaneous Diophantine approximation problem, namely, the problem to find a set of rational numbers sharing a common and relatively small denominator to simultaneously approximate a given set of real numbers. By launching the simultaneous Diophantine approximation attack, the adversary can obtain some useful information about (
w
,
m
). See [6, 7] for more details about the relation between the simultaneous Diophantine approximation problem and knapsack public key cryptanalytics.The trapdoor of the proposed system is disguised using the Chinese remainder theorem, which involves no size conditions. Hence, the adversary cannot expect finding some information about the trapdoor by launching a simultaneous Diophantine approximation attack. However, the reader may doubt that the size condition has been used in (24). We should observe that if the adversary wants to launch a simultaneous Diophantine approximation attack, he must peel off the outmost shuffle in (25) and (26). This seems intractable in that the adversary does not know the primes p and q.


#### 5.3.3. Orthogonal Lattice Attack

To examine the security, we must consider the orthogonal lattice attacks introduced by Nguyen and Stern [8, 9], which were used to successfully though heuristically recover the secret keys of two PKCs [33, 34]. We first illustrate why the orthogonal lattice attack can be used to reconstruct the secret key of the PKC in [34], and then show why our proposal is immune from the orthogonal lattice attack.In the PKC [34], the security parameter s
=
1024 is suggested, a modulus N
=
p
q with p and q being primes of lengths, respectively, |
p
|
2
=
3
s
/
4 and |
q
|
2
=
s
/
4 is chosen, and the secret sequence g
=
(
g
1
,
…
,
g
n
) (typically n
=
180) with each entry g
i
<
p
1
/
l (typically l
=
17) is generated so that the public sequence a
=
(
a
1
,
…
,
a
n
) can be computed via a modular multiplication a
i
=
w
g
i
(
mod
⁡
N
) for a randomly chosen w
∈
ℤ
N
*. The core for the orthogonal lattice attack to recover the secret key of [34] is to choose 0
<
m
≤
n entries a
m
=
(
a
1
,
…
,
a
m
) from a and then obtain sufficiently many small and linearly independent solutions x
m
=
(
x
1
,
…
,
x
m
) to 〈
a
m
,
x
m
〉
=
0. Given a solution x
m, we must have 〈
a
m
,
x
m
〉
=
〈
w
g
m
,
x
m
〉
=
w
〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), where g
m
=
(
g
1
,
…
,
g
m
). So 〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), which means that x
m is orthogonal to g
m, or 〈
g
m
,
x
m
〉
=
k
p with k
≠
0. In the second case, from Cauchy-Schwarz inequality, we have
(61)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
m
p
1
/
l
≈
N
12
/
17
m
,
when concrete parameters are concerned, which implies that either x
m is orthogonal to g
m or the norm of x
m is quite large. From the observations, the authors of [9] conjectured that among the reduced basis (
b
1
,
…
,
b
m
-
2
,
b
m
-
1
) of the (
m
-
1
)-dimensional lattice consisting of the integer solutions to 〈
a
m
,
x
m
〉
=
0, the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 are orthogonal to g
m, namely, Assumption 4 of [9]. By noting that g
m belongs to the two-dimensional orthogonal lattice ℒ
⊥ consisting of all m-dimensional integer vectors orthogonal to the lattice vectors in ℒ
(
b
1
,
…
,
b
m
-
2
) and that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value, they provide another assumption conjecturing that g
m is a shortest vector in ℒ
⊥, namely, Assumption 5 of [9]. So given a
m, we can expect to find the reduced basis b
1
,
…
,
b
m
-
2 and the shortest vector g
m by using lattice reduction algorithms.In the proposed cryptosystem, we generatep according to (24), so we can assume that p
>
191
n
g
i. Equation (61) turns out to be
(62)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
p
/
(
191
n
)
m
=
191
n
m
.
Under the suggested parameters n
=
60, 90, 120, 191
n is at most 15 bits long, so the assumption will be too strong to be satisfied that the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 have norms less than 191
n
/
m and hence are orthogonal to g
m. Furthermore, in [34], we can argue that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value; however, we just obtain ∥
g
m
∥
<
m
p
/
(
191
n
) in the proposed cryptosystem and hence cannot assume that g
m is a shortest vector in ℒ
⊥.To summarize, we can conjecture that the requirement ofg
i
l
<
p in [34] makes both to find m
-
2 linearly independent short vectors b
1
,
…
,
b
m
-
2 and to accept the shortest vector in ℒ
⊥ as the target vector g
m possible, while in the proposed cryptosystem p
>
191
n
g
i is only somewhat larger than those g
i, from which we cannot formalize Assumptions 4 and 5 provided in [9]. Hence, the proposed cryptosystem is invulnerable to the orthogonal lattice attack.Remark 33.
Now we explain why we introduce the matrixΔ when generating the public keys. If Δ is the two-dimensional identity matrix I
2, g
=
u, we can distil a relatively large common divisor t
=
gc
d
m
g
=
gc
d
m
u
=
∏
i
=
m
n
‍
α
i (see (★)) from the preceding m entries of g. Thus, if we define g
m
′
=
(
g
1
′
,
…
,
g
m
′
) with g
i
′
=
g
i
/
t being sharply reduced, then we can recover g
m
′ by the orthogonal lattice attack and eventually g
m by firstly exhausting the value of t
=
∏
i
=
m
n
‍
α
i and then combining g
i
′ and t to derive g
i
=
t
g
i
′. However, after the transformation of (23), we cannot expect to extract a large greatest common divisor for the entries of g
m. We suggest choosing Δ with determinant being δ
11
δ
22
-
δ
21
δ
12
=
±
1 in Remark 22, in which case we can make sure that gcd
(
δ
11
,
δ
12
)
=
gcd
(
δ
21
,
δ
22
)
=
1. If the two gcd’s are greater than 1, say δ
=
gcd
(
δ
11
,
δ
12
)
>
1, then δ
∣
g
i
=
δ
11
u
i
+
δ
12
v
i and hence t
=
gc
d
m
g
≥
δ, which may compromise the security.


## 5.1. Brute Force Attack

### 5.1.1. Brute Force Attack I

One straightforward way to attack the system is to solve (27) for x by exhausting all the ∑
i
=
1
n
‍
a
i
f
i with x
∈
𝕊
P. But note that |
F
i
|
=
16, so the brute force attack will take on the order of 𝒪
(
1
6
n
) steps. The computational costs under brute force attack I (BFA I for short) given in Table 3 are measured in bit operations with respect to the suggested parameters.


### 5.1.2. Brute Force Attack II

A better method is to compute and sort each of the sets(43)
S
1
=
{
∑
i
=
1
n
/
2
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
S
2
=
{
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
and then scan S
1 and S
2, looking for a common element. If a common element s
=
∑
i
=
1
n
/
2
‍
a
i
f
i
=
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i is found, then c
=
∑
i
=
1
n
‍
a
i
f
i. The entire procedure takes 𝒪
(
n
1
6
n
/
2
) steps [27]. See Table 3 for the computational costs under brute force attack II (BFA II for short) with respect to the suggested parameters.


## 5.1.1. Brute Force Attack I

One straightforward way to attack the system is to solve (27) for x by exhausting all the ∑
i
=
1
n
‍
a
i
f
i with x
∈
𝕊
P. But note that |
F
i
|
=
16, so the brute force attack will take on the order of 𝒪
(
1
6
n
) steps. The computational costs under brute force attack I (BFA I for short) given in Table 3 are measured in bit operations with respect to the suggested parameters.


## 5.1.2. Brute Force Attack II

A better method is to compute and sort each of the sets(43)
S
1
=
{
∑
i
=
1
n
/
2
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
S
2
=
{
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i
∣
f
i
∈
F
i
}
,
and then scan S
1 and S
2, looking for a common element. If a common element s
=
∑
i
=
1
n
/
2
‍
a
i
f
i
=
c
-
∑
i
=
n
/
2
+
1
n
‍
a
i
f
i is found, then c
=
∑
i
=
1
n
‍
a
i
f
i. The entire procedure takes 𝒪
(
n
1
6
n
/
2
) steps [27]. See Table 3 for the computational costs under brute force attack II (BFA II for short) with respect to the suggested parameters.


## 5.2. Linearization Attack

In this subsection, we assume that the adversary aims at recovering the corresponding plaintext (and hence the message) by reversing the underlying encryption function without learning the trapdoor information. When a concrete attack model is concerned, we firstly formalize and then prove the underlying PSTOF.


### 5.2.1. Linearization Attack I

Encryption function (27) of the proposed PKC is a linear function mapping an element in 𝕊
P into an integer in the ciphertext space ℂ. Now we define
(44)
T
1
:
𝕊
E
=
ℤ
192
n
⟼
ℂ
=
T
1
(
𝕊
E
)
,
T
1
(
x
)
=
〈
a
,
x
〉
=
c
,
x
∈
𝕊
E
.Theorem 25.
If the compact knapsackC
K
P
192
(
a
,
c
) is intractable, T
1 is a PSTOF.Proof.
It is easy to verify that the five conditions except the second one in Definition2 are satisfied; (45) below guarantees the noninjectivity of function T
1. So T
1 is indeed a PSTOF underlying the proposed PKC under the compact knapsack intractability assumption.The distinction between the two functions (27) and (44) is that the preimage sets are different. Given a ciphertext c, c will have a unique preimage in 𝕊
P, namely, the corresponding plaintext, while c will have many preimages in the equivalent plaintext space 𝕊
E.We have pointed out in Remark9 that the message encoding function F can simulate the process of randomly choosing an element from 𝕊
E
=
ℤ
192
n. That is to say, if one can obtain a preimage of c with respect to T
1, the preimage is a randomly output preimage from all the preimages in T
1
-
1
(
c
)
=
{
x
∈
𝕊
E
∣
T
(
x
)
=
c
} and not necessarily the plaintext x
∈
𝕊
P.Now, we explain why we say we can further weaken the underlying cryptographic hardness assumption. If we assume that the compact knapsack problemCK
P
192
(
a
,
c
) is easy; that is, T
1 is not one-way, the proposed cryptosystem seems still secure. Under the assumption, there exists an oracle 𝒜 for the compact knapsack problem CK
P
192
(
a
,
c
). We note that each time the adversary can obtain a (at most polynomially many) preimage of c by accessing the oracle 𝒜. However, we will show that c has exponentially many (denoted as 2
λ
1
(
n
)) preimages, over which the plaintext x
∈
𝕊
P seems uniformly distributed. So we can heuristically argue that the adversary only obtains polynomially many p
(
n
) preimages by performing polynomially many p
(
n
) accesses to the oracle 𝒜, and hence those p
(
n
) preimages contain the target plaintext x
∈
𝕊
P with a negligible probability p
(
n
)
/
2
λ
1
(
n
). Thus, we can conceive T
1 as a preimage selective trapdoor (not one-way) function assuming that the underlying compact knapsack problem CK
P
192
(
a
,
c
) is easy. In fact, under the assumption, the security of the proposed PKC is based on the assumption that it is computationally infeasible to recover a solution to a highly noninjective compact knapsack problem CK
P
192
(
a
,
c
) with a predesignated special structure (i.e., the structure of 𝕊
P).To illustrate, we need to show that a ciphertext has exponentially many preimages with respect toT
1. We use the preimage density given in Definition 4 to roughly evaluate the number of preimages for a ciphertext. To begin with, we need to estimate the cardinalities for the image set (ciphertext space ℂ) and the preimage set (i.e., the equivalent space 𝕊
E
=
ℤ
192
n). It is obvious that |
𝕊
E
|
=
19
2
n. We note (41) and |
ℂ
|
≤
max
⁡
ℂ
+
1
≈
max
⁡
ℂ, so we have |
ℂ
|
≤
19
1
3
n
3
4
7
n
-
1 and hence the preimage density is
(45)
P
d
1
=
𝕊
E
|
ℂ
|
≥
19
2
n
19
1
3
n
3
4
7
n
-
1
=
2
λ
1
(
n
)
=
2
𝒪
(
n
)
,
where λ
1
(
n
)
=
n
lo
g
2
192
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191. See Table 3 for the manipulations of P
d
1 for the suggested security parameters.


### 5.2.2. Linearization Attack II

Now, we consider an attack transforming (27) into a standard 0-1 knapsack problem. The adversary can combine all of these 16 values in F
i denoted as F
i
=
{
f
i
(
1
)
,
…
,
f
i
(
16
)
} with each entry a
i in a to derive a new integer sequence w
=
(
w
1
(
1
)
,
…
,
w
1
(
16
)
,
…
,
w
n
(
1
)
,
…
,
w
n
(
16
)
) such that w
i
(
j
)
=
a
i
f
i
(
j
) with i
=
1
,
…
,
n, j
=
1
,
…
,
16. Under the linearization attack model, we define the following function:
(46)
T
2
:
𝕊
E
2
=
{
0,1
}
16
n
⟼
ℂ
2
=
T
2
(
𝕊
E
2
)
,
T
2
(
y
)
=
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
y
i
(
j
)
=
c
,
where y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
∈
𝕊
E
2. We set
(47)
𝕊
P
2
=
{
y
∈
{
0,1
}
16
n
∣
∑
j
=
1
16
‍
y
i
(
j
)
=
1,1
≤
i
≤
n
}
.Theorem 26.
If the knapsack problemK
P
(
w
,
c
) is intractable, T
2 is a PSTOF.Proof.
To verify(
3
) and (
4
) in Definition 2, we consider a mapping τ
:
𝕊
P
↦
𝕊
P
2 as follows. Given an arbitrary x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P, we must have that for i
=
1
,
…
,
n, there should exist a unique f
i
(
j
)
∈
F
i such that f
i
=
f
i
(
j
) with 1
≤
j
≤
16. Now we define y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
=
τ
(
x
) with y
i
(
j
)
=
1 when f
i
=
f
i
(
j
) and y
i
(
j
)
=
0 otherwise. So we must have for 1
≤
i
≤
n, ∑
j
=
1
16
‍
y
i
(
j
)
=
1, and ∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
f
i. So y
∈
𝕊
P
2. Furthermore, any y
∈
𝕊
P
2 must have a preimage x
=
τ
-
1
(
y
) with f
i
=
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
). We further note that |
𝕊
P
|
=
|
𝕊
P
2
|
=
1
6
n and can argue that τ is a bijection from 𝕊
P to 𝕊
P
2. By observing
(48)
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
W
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
f
i
=
〈
a
,
x
〉
,
we know that x
∈
𝕊
P is a solution to (27) if and only if y
=
τ
(
x
) is a solution to (46). So (
3
) and (
4
) in Definition 2 are satisfied.
To show the noninjectivity of (46), we first note that the image set is ℂ
2
=
T
2
(
𝕊
E
2
) and that
(49)
max
⁡
ℂ
2
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
<
191
×
16
∑
i
=
1
n
‍
a
i
<
16
×
191
n
N
≤
16
×
19
1
3
n
3
4
7
n
-
1
.
The last symbol  ≤  in (49) is due to (40). Hence, we have |
ℂ
2
|
<
16
×
19
1
3
n
3
4
7
n
-
1
+
1. So we compute the preimage density via
(50)
P
d
2
=
𝕊
E
2
|
ℂ
2
|
≥
2
16
n
16
×
19
1
3
n
3
4
7
n
-
1
=
2
λ
2
(
n
)
=
2
𝒪
(
n
)
,
where λ
2
(
n
)
=
16
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
4. See Table 3 for the manipulations of P
d
2 for the suggested security parameters. Thus, T
2 is indeed a PSTOF.The computational infeasibility for the linearization attack is supported by either of the following arguments.Remark 27 (noninjectivity-based security argument).
If we assume that the adversary can solve the knapsack problemKP
(
w
,
c
), then T
2 is a preimage selective trapdoor function. A given ciphertext c will have exponentially many 2
λ
2
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages including the target solution in 𝕊
E
2 with a negligible probability p
(
n
)
/
2
λ
2
(
n
).Remark 28 (density-based security argument).
It is known that knapsack problems achieving a density smaller than 0.9408 are solvable with an overwhelming probability by accessing an oracle for the shortest vector problem over lattices [23, 24]. We show that the underlying knapsack problem KP
(
w
,
c
) (46) obtain a sufficiently large density. Note that
(51)
d
2
=
16
n
lo
g
2
max
⁡
w
≥
16
n
lo
g
2
(
max
⁡
a
max
⁡
F
i
)
≥
16
n
lo
g
2
(
191
N
)
.
Observing (40), we have that d
2 approaches 16
/
lo
g
2
47
≈
2.88 when n approaches infinity.Remark 29 (dimension-based security argument).
In real life practice, we use known efficient lattice reduction algorithms to simulate a shortest vector oracle in low-dimensional lattice. However, when the dimension is sufficiently large, say larger than 500, known lattice reduction algorithms fail to output a relatively short lattice vector. Under the suggested parameters, knapsack problemKP
(
w
,
c
) (46) achieves sufficiently large dimensions 960, 1440, 1920, respectively.


### 5.2.3. Linearization Attack III

Now we consider another linear attack III, which also transforms the problem (27) into a knapsack problem. We note that 0
≤
f
i
≤
191, so 8 bits are needed to represent each f
i. For i
=
1
,
…
,
n, we define d
i
(
j
)
=
2
j
-
1
a
i with j
=
1
,
…
,
8 and obtain an 8
n-dimensional integer sequence d
=
(
d
1
(
1
)
,
…
,
d
1
(
8
)
,
…
,
d
n
(
1
)
,
…
,
d
n
(
8
)
). Now we provide the following function:
(52)
T
3
:
𝕊
E
3
=
{
0,1
}
8
n
⟼
ℂ
3
=
T
3
(
𝕊
E
3
)
,
T
3
(
z
)
=
〈
d
,
z
〉
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
z
i
(
j
)
=
c
,
where z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
∈
𝕊
E
3. We set
(53)
𝕊
P
3
=
{
z
∈
{
0,1
}
8
n
∣
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
∈
F
i
,
1
≤
i
≤
n
}
.Theorem 30.
If the knapsack problemK
P
(
d
,
c
) is intractable, T
3 is a PSTOF.Proof.
It is easy to verify that(
1
) and (
5
) in Definition 2 are satisfied. In fact, any element z
∈
𝕊
P
3 stands for a binary representation of an element x
∈
𝕊
P, and in turn, the binary representation of any element x
∈
𝕊
P falls into the set 𝕊
P
3. So if we define a mapping τ from 𝕊
P
3 to 𝕊
P, τ
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
=
(
∑
j
=
1
8
‍
2
j
-
1
z
1
(
j
)
,
…
,
∑
j
=
1
8
‍
2
j
-
1
z
n
(
j
)
), τ is a bijection. Furthermore, we note that
(54)
〈
d
,
z
〉
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
=
〈
a
,
x
〉
.
So z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
) is a solution to (52) if and only if τ
(
z
)
=
x
∈
𝕊
P is a solution to (27). So conditions (
3
) and (
4
) in Definition 2 are satisfied. To show the noninjectivity of T
3, we first evaluate the cardinalities of 𝕊
E
3 and ℂ
3. It is obvious that |
𝕊
E
3
|
=
2
8
n. To estimate |
ℂ
3
|, we first note that
(55)
max
⁡
ℂ
3
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
=
255
∑
i
=
1
n
‍
a
i
<
255
×
n
N
≤
255
×
19
1
2
n
3
4
7
n
-
1
.
So the preimage density of T
3 can be estimated via
(56)
P
d
3
=
𝕊
E
3
|
ℂ
3
|
≥
2
8
n
255
×
19
1
2
n
3
4
7
n
-
1
=
2
λ
3
(
n
)
=
2
𝒪
(
n
)
,
where λ
3
(
n
)
=
8
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
lo
g
2
255. See Table 3 for the values of P
d
3 under the suggested security parameters. Thus, condition (
2
) in Definition 2 is satisfied, so T
3 is indeed a PSTOF.Remark 31 (noninjectivity-based security argument).
If one conquers the knapsack problemKP
(
d
,
c
), then T
3 is a pre-image selective trapdoor function. A ciphertext will have exponentially many 2
λ
3
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages which include the solution in 𝕊
E
3 with a negligible probability p
(
n
)
/
2
λ
3
(
n
).Remark 32 (density and dimension based arguments).
The density to (52) is estimated via
(57)
d
3
=
8
n
lo
g
2
max
⁡
d
≥
8
n
lo
g
2
(
2
7
max
⁡
a
)
≥
8
n
lo
g
2
(
2
7
N
)
,
which is 8
/
lo
g
2
47
≈
1.44
>
0.9408 when n approaches infinity. The knapsack problem KP
(
d
,
c
) (52) has sufficiently large dimensions 480, 540, and 960 for the suggested parameters.


## 5.2.1. Linearization Attack I

Encryption function (27) of the proposed PKC is a linear function mapping an element in 𝕊
P into an integer in the ciphertext space ℂ. Now we define
(44)
T
1
:
𝕊
E
=
ℤ
192
n
⟼
ℂ
=
T
1
(
𝕊
E
)
,
T
1
(
x
)
=
〈
a
,
x
〉
=
c
,
x
∈
𝕊
E
.Theorem 25.
If the compact knapsackC
K
P
192
(
a
,
c
) is intractable, T
1 is a PSTOF.Proof.
It is easy to verify that the five conditions except the second one in Definition2 are satisfied; (45) below guarantees the noninjectivity of function T
1. So T
1 is indeed a PSTOF underlying the proposed PKC under the compact knapsack intractability assumption.The distinction between the two functions (27) and (44) is that the preimage sets are different. Given a ciphertext c, c will have a unique preimage in 𝕊
P, namely, the corresponding plaintext, while c will have many preimages in the equivalent plaintext space 𝕊
E.We have pointed out in Remark9 that the message encoding function F can simulate the process of randomly choosing an element from 𝕊
E
=
ℤ
192
n. That is to say, if one can obtain a preimage of c with respect to T
1, the preimage is a randomly output preimage from all the preimages in T
1
-
1
(
c
)
=
{
x
∈
𝕊
E
∣
T
(
x
)
=
c
} and not necessarily the plaintext x
∈
𝕊
P.Now, we explain why we say we can further weaken the underlying cryptographic hardness assumption. If we assume that the compact knapsack problemCK
P
192
(
a
,
c
) is easy; that is, T
1 is not one-way, the proposed cryptosystem seems still secure. Under the assumption, there exists an oracle 𝒜 for the compact knapsack problem CK
P
192
(
a
,
c
). We note that each time the adversary can obtain a (at most polynomially many) preimage of c by accessing the oracle 𝒜. However, we will show that c has exponentially many (denoted as 2
λ
1
(
n
)) preimages, over which the plaintext x
∈
𝕊
P seems uniformly distributed. So we can heuristically argue that the adversary only obtains polynomially many p
(
n
) preimages by performing polynomially many p
(
n
) accesses to the oracle 𝒜, and hence those p
(
n
) preimages contain the target plaintext x
∈
𝕊
P with a negligible probability p
(
n
)
/
2
λ
1
(
n
). Thus, we can conceive T
1 as a preimage selective trapdoor (not one-way) function assuming that the underlying compact knapsack problem CK
P
192
(
a
,
c
) is easy. In fact, under the assumption, the security of the proposed PKC is based on the assumption that it is computationally infeasible to recover a solution to a highly noninjective compact knapsack problem CK
P
192
(
a
,
c
) with a predesignated special structure (i.e., the structure of 𝕊
P).To illustrate, we need to show that a ciphertext has exponentially many preimages with respect toT
1. We use the preimage density given in Definition 4 to roughly evaluate the number of preimages for a ciphertext. To begin with, we need to estimate the cardinalities for the image set (ciphertext space ℂ) and the preimage set (i.e., the equivalent space 𝕊
E
=
ℤ
192
n). It is obvious that |
𝕊
E
|
=
19
2
n. We note (41) and |
ℂ
|
≤
max
⁡
ℂ
+
1
≈
max
⁡
ℂ, so we have |
ℂ
|
≤
19
1
3
n
3
4
7
n
-
1 and hence the preimage density is
(45)
P
d
1
=
𝕊
E
|
ℂ
|
≥
19
2
n
19
1
3
n
3
4
7
n
-
1
=
2
λ
1
(
n
)
=
2
𝒪
(
n
)
,
where λ
1
(
n
)
=
n
lo
g
2
192
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191. See Table 3 for the manipulations of P
d
1 for the suggested security parameters.


## 5.2.2. Linearization Attack II

Now, we consider an attack transforming (27) into a standard 0-1 knapsack problem. The adversary can combine all of these 16 values in F
i denoted as F
i
=
{
f
i
(
1
)
,
…
,
f
i
(
16
)
} with each entry a
i in a to derive a new integer sequence w
=
(
w
1
(
1
)
,
…
,
w
1
(
16
)
,
…
,
w
n
(
1
)
,
…
,
w
n
(
16
)
) such that w
i
(
j
)
=
a
i
f
i
(
j
) with i
=
1
,
…
,
n, j
=
1
,
…
,
16. Under the linearization attack model, we define the following function:
(46)
T
2
:
𝕊
E
2
=
{
0,1
}
16
n
⟼
ℂ
2
=
T
2
(
𝕊
E
2
)
,
T
2
(
y
)
=
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
y
i
(
j
)
=
c
,
where y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
∈
𝕊
E
2. We set
(47)
𝕊
P
2
=
{
y
∈
{
0,1
}
16
n
∣
∑
j
=
1
16
‍
y
i
(
j
)
=
1,1
≤
i
≤
n
}
.Theorem 26.
If the knapsack problemK
P
(
w
,
c
) is intractable, T
2 is a PSTOF.Proof.
To verify(
3
) and (
4
) in Definition 2, we consider a mapping τ
:
𝕊
P
↦
𝕊
P
2 as follows. Given an arbitrary x
=
(
f
1
,
…
,
f
n
)
∈
𝕊
P, we must have that for i
=
1
,
…
,
n, there should exist a unique f
i
(
j
)
∈
F
i such that f
i
=
f
i
(
j
) with 1
≤
j
≤
16. Now we define y
=
(
y
1
(
1
)
,
…
,
y
1
(
16
)
,
…
,
y
n
(
1
)
,
…
,
y
n
(
16
)
)
=
τ
(
x
) with y
i
(
j
)
=
1 when f
i
=
f
i
(
j
) and y
i
(
j
)
=
0 otherwise. So we must have for 1
≤
i
≤
n, ∑
j
=
1
16
‍
y
i
(
j
)
=
1, and ∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
f
i. So y
∈
𝕊
P
2. Furthermore, any y
∈
𝕊
P
2 must have a preimage x
=
τ
-
1
(
y
) with f
i
=
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
). We further note that |
𝕊
P
|
=
|
𝕊
P
2
|
=
1
6
n and can argue that τ is a bijection from 𝕊
P to 𝕊
P
2. By observing
(48)
〈
w
,
y
〉
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
W
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
y
i
(
j
)
=
∑
i
=
1
n
‍
a
i
f
i
=
〈
a
,
x
〉
,
we know that x
∈
𝕊
P is a solution to (27) if and only if y
=
τ
(
x
) is a solution to (46). So (
3
) and (
4
) in Definition 2 are satisfied.
To show the noninjectivity of (46), we first note that the image set is ℂ
2
=
T
2
(
𝕊
E
2
) and that
(49)
max
⁡
ℂ
2
=
∑
i
=
1
n
‍
∑
j
=
1
16
‍
w
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
16
‍
f
i
(
j
)
<
191
×
16
∑
i
=
1
n
‍
a
i
<
16
×
191
n
N
≤
16
×
19
1
3
n
3
4
7
n
-
1
.
The last symbol  ≤  in (49) is due to (40). Hence, we have |
ℂ
2
|
<
16
×
19
1
3
n
3
4
7
n
-
1
+
1. So we compute the preimage density via
(50)
P
d
2
=
𝕊
E
2
|
ℂ
2
|
≥
2
16
n
16
×
19
1
3
n
3
4
7
n
-
1
=
2
λ
2
(
n
)
=
2
𝒪
(
n
)
,
where λ
2
(
n
)
=
16
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
4. See Table 3 for the manipulations of P
d
2 for the suggested security parameters. Thus, T
2 is indeed a PSTOF.The computational infeasibility for the linearization attack is supported by either of the following arguments.Remark 27 (noninjectivity-based security argument).
If we assume that the adversary can solve the knapsack problemKP
(
w
,
c
), then T
2 is a preimage selective trapdoor function. A given ciphertext c will have exponentially many 2
λ
2
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages including the target solution in 𝕊
E
2 with a negligible probability p
(
n
)
/
2
λ
2
(
n
).Remark 28 (density-based security argument).
It is known that knapsack problems achieving a density smaller than 0.9408 are solvable with an overwhelming probability by accessing an oracle for the shortest vector problem over lattices [23, 24]. We show that the underlying knapsack problem KP
(
w
,
c
) (46) obtain a sufficiently large density. Note that
(51)
d
2
=
16
n
lo
g
2
max
⁡
w
≥
16
n
lo
g
2
(
max
⁡
a
max
⁡
F
i
)
≥
16
n
lo
g
2
(
191
N
)
.
Observing (40), we have that d
2 approaches 16
/
lo
g
2
47
≈
2.88 when n approaches infinity.Remark 29 (dimension-based security argument).
In real life practice, we use known efficient lattice reduction algorithms to simulate a shortest vector oracle in low-dimensional lattice. However, when the dimension is sufficiently large, say larger than 500, known lattice reduction algorithms fail to output a relatively short lattice vector. Under the suggested parameters, knapsack problemKP
(
w
,
c
) (46) achieves sufficiently large dimensions 960, 1440, 1920, respectively.


## 5.2.3. Linearization Attack III

Now we consider another linear attack III, which also transforms the problem (27) into a knapsack problem. We note that 0
≤
f
i
≤
191, so 8 bits are needed to represent each f
i. For i
=
1
,
…
,
n, we define d
i
(
j
)
=
2
j
-
1
a
i with j
=
1
,
…
,
8 and obtain an 8
n-dimensional integer sequence d
=
(
d
1
(
1
)
,
…
,
d
1
(
8
)
,
…
,
d
n
(
1
)
,
…
,
d
n
(
8
)
). Now we provide the following function:
(52)
T
3
:
𝕊
E
3
=
{
0,1
}
8
n
⟼
ℂ
3
=
T
3
(
𝕊
E
3
)
,
T
3
(
z
)
=
〈
d
,
z
〉
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
z
i
(
j
)
=
c
,
where z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
∈
𝕊
E
3. We set
(53)
𝕊
P
3
=
{
z
∈
{
0,1
}
8
n
∣
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
∈
F
i
,
1
≤
i
≤
n
}
.Theorem 30.
If the knapsack problemK
P
(
d
,
c
) is intractable, T
3 is a PSTOF.Proof.
It is easy to verify that(
1
) and (
5
) in Definition 2 are satisfied. In fact, any element z
∈
𝕊
P
3 stands for a binary representation of an element x
∈
𝕊
P, and in turn, the binary representation of any element x
∈
𝕊
P falls into the set 𝕊
P
3. So if we define a mapping τ from 𝕊
P
3 to 𝕊
P, τ
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
)
=
(
∑
j
=
1
8
‍
2
j
-
1
z
1
(
j
)
,
…
,
∑
j
=
1
8
‍
2
j
-
1
z
n
(
j
)
), τ is a bijection. Furthermore, we note that
(54)
〈
d
,
z
〉
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
z
i
(
j
)
=
〈
a
,
x
〉
.
So z
=
(
z
1
(
1
)
,
…
,
z
1
(
8
)
,
…
,
z
n
(
1
)
,
…
,
z
n
(
8
)
) is a solution to (52) if and only if τ
(
z
)
=
x
∈
𝕊
P is a solution to (27). So conditions (
3
) and (
4
) in Definition 2 are satisfied. To show the noninjectivity of T
3, we first evaluate the cardinalities of 𝕊
E
3 and ℂ
3. It is obvious that |
𝕊
E
3
|
=
2
8
n. To estimate |
ℂ
3
|, we first note that
(55)
max
⁡
ℂ
3
=
∑
i
=
1
n
‍
∑
j
=
1
8
‍
d
i
(
j
)
=
∑
i
=
1
n
‍
a
i
∑
j
=
1
8
‍
2
j
-
1
=
255
∑
i
=
1
n
‍
a
i
<
255
×
n
N
≤
255
×
19
1
2
n
3
4
7
n
-
1
.
So the preimage density of T
3 can be estimated via
(56)
P
d
3
=
𝕊
E
3
|
ℂ
3
|
≥
2
8
n
255
×
19
1
2
n
3
4
7
n
-
1
=
2
λ
3
(
n
)
=
2
𝒪
(
n
)
,
where λ
3
(
n
)
=
8
n
-
(
n
-
1
)
lo
g
2
47
-
3
lo
g
2
n
-
3
lo
g
2
191
-
lo
g
2
255. See Table 3 for the values of P
d
3 under the suggested security parameters. Thus, condition (
2
) in Definition 2 is satisfied, so T
3 is indeed a PSTOF.Remark 31 (noninjectivity-based security argument).
If one conquers the knapsack problemKP
(
d
,
c
), then T
3 is a pre-image selective trapdoor function. A ciphertext will have exponentially many 2
λ
3
(
n
) binary solutions. So a polynomial-time adversary only obtains polynomially many p
(
n
) preimages which include the solution in 𝕊
E
3 with a negligible probability p
(
n
)
/
2
λ
3
(
n
).Remark 32 (density and dimension based arguments).
The density to (52) is estimated via
(57)
d
3
=
8
n
lo
g
2
max
⁡
d
≥
8
n
lo
g
2
(
2
7
max
⁡
a
)
≥
8
n
lo
g
2
(
2
7
N
)
,
which is 8
/
lo
g
2
47
≈
1.44
>
0.9408 when n approaches infinity. The knapsack problem KP
(
d
,
c
) (52) has sufficiently large dimensions 480, 540, and 960 for the suggested parameters.


## 5.3.  Key-Recovery Attacks

When we discuss the cracking problem, we only study the computational infeasibilities for the adversary to solve (27) without considering the structure of the public integer sequence a. To claim the security of the proposed PKC, we need to examine whether the trapdoor is easy to discover or not. So we need to examine the security of the proposed PKC against known attacks.The public integer sequencea distinguishes with a randomly chosen positive integer sequence in two respects, that is, the special structures defined in (14) and (15) and the size conditions given in (24). We discuss the effects of these conditions on the security.


### 5.3.1. GCD Attack

The GCD attack in [4] was used to successfully attack the knapsack-based probabilistic public key encryption [28]. The attack illustrates that if the entries of b
=
(
b
1
,
…
,
b
n
) assume a linear combinatorial relation with small integer combinatorial coefficients, we can recover the secret modulus N by computing the greatest common divisor for a set of numbers. This point will be explored later on, or the readers can refer to [4] for more details. We first note that if the modulus N
=
p
q is known, under the suggested parameters, n
=
60, 90, and 120, the binary length of N is upper bounded by 355, 523, 690, respectively. See (36). It is not intractable to factor the moduli by using the fastest factorization algorithm [29]. Hence, one can factor N into its prime products. Once p and q have been obtained, the adversary can do the modular reductions, a
i
p
=
a
i
(
mod
⁡
p
) and a
i
q
=
a
i
(
mod
⁡
p
). If we denote the modular reductions of w
-
1 modulo p and q as w
p
-
1 and w
q
-
1, from (25) and (26), we know g
i
=
a
i
p
w
p
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
p
) and h
i
=
a
i
q
w
q
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
q
) and then exhaust the matrix Δ to reverse the process of (23) as
(58)
(
u
v
)
=
Δ
-
1
(
g
h
)
=
(
δ
22
-
δ
12
-
δ
21
δ
11
)
(
g
h
)
,
where for convenience, we just set |
Δ
|
=
1. So we have
(59)
u
i
=
δ
22
〈
a
i
p
w
p
-
1
〉
p
-
δ
12
〈
a
i
q
w
q
-
1
〉
q
,
v
i
=
δ
11
〈
a
i
q
w
q
-
1
〉
q
-
δ
21
〈
a
i
p
w
p
-
1
〉
p
.
We note that gc
d
n
-
1
u
∣
u
i, gc
d
n
-
1
v
∣
v
i for i
=
1
,
…
,
n
-
1, a
i
p and a
i
q are publicly computable once p and q have been obtained, and (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
∪
AI
P
〈
n
〉
12
T and δ
i
j can be efficiently exhausted (and hence we can assume that they are all known). So, for i
=
1
,
…
,
n
-
1, we have
(60)
δ
22
a
i
p
x
0
-
δ
22
x
2
i
p
-
δ
12
a
i
q
x
1
-
δ
12
x
2
i
+
1
q
-
k
i
gc
d
n
-
1
u
=
0
,
δ
11
a
i
q
x
1
-
δ
11
x
2
i
+
1
q
-
δ
21
a
i
p
x
0
-
δ
21
x
2
i
p
-
l
i
gc
d
n
-
1
v
=
0
with integer unknowns 0
<
x
0
=
w
p
-
1
<
p, 0
<
x
1
=
w
q
-
1
<
q, x
2
i (x
2
i
+
1, resp.) being the incomplete quotient of a
i
p
x
0 (a
i
q
x
1, resp.) divided by p (q, resp.), and k
i and l
i are the quotients of u
i and v
i divided by gc
d
n
-
1
u and gc
d
n
-
1
v, respectively. So we have 0
≤
x
2
i
<
a
i
p, 0
≤
x
2
i
+
1
<
a
i
q, 0
<
k
i
<
p
/
gc
d
n
-
1
u, and 0
<
l
i
<
q
/
gc
d
n
-
1
v. We can use an efficient heuristic algorithm for solving a system of linear Diophantine equations with lower and upper bounds on the variables given in [30] (see also Section 3 of [4] for a simplified description) to determine these unknowns, and eventually the full secret keys. So we caution that in implementation, we must keep the modulus N secret. However, we will show that the GCD attack is useless to derive modulus N.The condition for the GCD attack to succeed in finding modulusN is that we can construct some linear relations using the entries of the public sequence b. To illustrate, we recall (26) and argue that there must exist integers s
i such that b
i
w
-
s
i
N
=
a
i. We assume that the entries of b share some linear combinatorial relations with small coefficients, say t
1
b
1
-
t
2
b
2
=
0, t
3
b
3
-
t
4
b
4
=
0, where by saying small coefficients we mean we can efficiently do exhaustive search for these t
i’s. So we conclude that N
∣
t
1
a
1
-
t
2
a
2
=
N
(
s
1
t
1
-
s
2
t
2
) and N
∣
t
3
a
3
-
t
4
a
4 and hence can expect N
=
gcd
(
t
1
a
1
-
t
2
a
2
,
t
3
a
3
-
t
4
a
4
). We must admit that the entries of u (and v) do share a linear combinatorial relation; for example, from (★) we derive ζ
2
u
1
-
α
1
u
2
=
0. However, we should bear in mind that b is fully scrambled by (23) and (25) especially through the confusion role of the Chinese remainder theorem in (25). So it is unlikely for the adversary to derive modulus N by launching a GCD-like attack on the proposal.


### 5.3.2. Simultaneous Diophantine Approximation Attack

After Shamir broke the basic Merkle-Hellman knapsack cryptosystem [31, 32], cryptanalysts began to investigate the security of the multiply iterated Merkle-Hellman cryptosystem. Lagarias observed that the size conditions and the modular transformation in the multiply iterated Merkle-Hellman cryptosystem help him construct a simultaneous Diophantine approximation problem [7]. Lagarias showed that he can successfully launch a key-recovery attack on the doubly iterated Merkle-Hellman cryptosystem through his simultaneous Diophantine approximation approach.Many knapsack-type cryptosystems use size conditions to disguise an easy knapsack problem. In such a cryptosystem, the designer randomly generates an easy knapsack problem,y
=
∑
i
=
1
n
‍
a
i
x
i
,
x
i
∈
[
0
,
2
b
-
1
], and chooses a modulus m and a multiplier w, gcd
(
m
,
w
)
=
1. He uses the size condition m
>
(
2
b
-
1
)
∑
i
=
1
n
‍
a
i to disguise the easy knapsack sequence a
=
(
a
1
,
…
,
a
n
) as a seemingly hard knapsack sequence b
=
(
b
1
,
…
,
b
n
) by a modular multiplication, b
i
=
〈
w
a
i
〉
m. The size condition and the public sequence can be utilized to derive a simultaneous Diophantine approximation problem, namely, the problem to find a set of rational numbers sharing a common and relatively small denominator to simultaneously approximate a given set of real numbers. By launching the simultaneous Diophantine approximation attack, the adversary can obtain some useful information about (
w
,
m
). See [6, 7] for more details about the relation between the simultaneous Diophantine approximation problem and knapsack public key cryptanalytics.The trapdoor of the proposed system is disguised using the Chinese remainder theorem, which involves no size conditions. Hence, the adversary cannot expect finding some information about the trapdoor by launching a simultaneous Diophantine approximation attack. However, the reader may doubt that the size condition has been used in (24). We should observe that if the adversary wants to launch a simultaneous Diophantine approximation attack, he must peel off the outmost shuffle in (25) and (26). This seems intractable in that the adversary does not know the primes p and q.


### 5.3.3. Orthogonal Lattice Attack

To examine the security, we must consider the orthogonal lattice attacks introduced by Nguyen and Stern [8, 9], which were used to successfully though heuristically recover the secret keys of two PKCs [33, 34]. We first illustrate why the orthogonal lattice attack can be used to reconstruct the secret key of the PKC in [34], and then show why our proposal is immune from the orthogonal lattice attack.In the PKC [34], the security parameter s
=
1024 is suggested, a modulus N
=
p
q with p and q being primes of lengths, respectively, |
p
|
2
=
3
s
/
4 and |
q
|
2
=
s
/
4 is chosen, and the secret sequence g
=
(
g
1
,
…
,
g
n
) (typically n
=
180) with each entry g
i
<
p
1
/
l (typically l
=
17) is generated so that the public sequence a
=
(
a
1
,
…
,
a
n
) can be computed via a modular multiplication a
i
=
w
g
i
(
mod
⁡
N
) for a randomly chosen w
∈
ℤ
N
*. The core for the orthogonal lattice attack to recover the secret key of [34] is to choose 0
<
m
≤
n entries a
m
=
(
a
1
,
…
,
a
m
) from a and then obtain sufficiently many small and linearly independent solutions x
m
=
(
x
1
,
…
,
x
m
) to 〈
a
m
,
x
m
〉
=
0. Given a solution x
m, we must have 〈
a
m
,
x
m
〉
=
〈
w
g
m
,
x
m
〉
=
w
〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), where g
m
=
(
g
1
,
…
,
g
m
). So 〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), which means that x
m is orthogonal to g
m, or 〈
g
m
,
x
m
〉
=
k
p with k
≠
0. In the second case, from Cauchy-Schwarz inequality, we have
(61)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
m
p
1
/
l
≈
N
12
/
17
m
,
when concrete parameters are concerned, which implies that either x
m is orthogonal to g
m or the norm of x
m is quite large. From the observations, the authors of [9] conjectured that among the reduced basis (
b
1
,
…
,
b
m
-
2
,
b
m
-
1
) of the (
m
-
1
)-dimensional lattice consisting of the integer solutions to 〈
a
m
,
x
m
〉
=
0, the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 are orthogonal to g
m, namely, Assumption 4 of [9]. By noting that g
m belongs to the two-dimensional orthogonal lattice ℒ
⊥ consisting of all m-dimensional integer vectors orthogonal to the lattice vectors in ℒ
(
b
1
,
…
,
b
m
-
2
) and that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value, they provide another assumption conjecturing that g
m is a shortest vector in ℒ
⊥, namely, Assumption 5 of [9]. So given a
m, we can expect to find the reduced basis b
1
,
…
,
b
m
-
2 and the shortest vector g
m by using lattice reduction algorithms.In the proposed cryptosystem, we generatep according to (24), so we can assume that p
>
191
n
g
i. Equation (61) turns out to be
(62)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
p
/
(
191
n
)
m
=
191
n
m
.
Under the suggested parameters n
=
60, 90, 120, 191
n is at most 15 bits long, so the assumption will be too strong to be satisfied that the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 have norms less than 191
n
/
m and hence are orthogonal to g
m. Furthermore, in [34], we can argue that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value; however, we just obtain ∥
g
m
∥
<
m
p
/
(
191
n
) in the proposed cryptosystem and hence cannot assume that g
m is a shortest vector in ℒ
⊥.To summarize, we can conjecture that the requirement ofg
i
l
<
p in [34] makes both to find m
-
2 linearly independent short vectors b
1
,
…
,
b
m
-
2 and to accept the shortest vector in ℒ
⊥ as the target vector g
m possible, while in the proposed cryptosystem p
>
191
n
g
i is only somewhat larger than those g
i, from which we cannot formalize Assumptions 4 and 5 provided in [9]. Hence, the proposed cryptosystem is invulnerable to the orthogonal lattice attack.Remark 33.
Now we explain why we introduce the matrixΔ when generating the public keys. If Δ is the two-dimensional identity matrix I
2, g
=
u, we can distil a relatively large common divisor t
=
gc
d
m
g
=
gc
d
m
u
=
∏
i
=
m
n
‍
α
i (see (★)) from the preceding m entries of g. Thus, if we define g
m
′
=
(
g
1
′
,
…
,
g
m
′
) with g
i
′
=
g
i
/
t being sharply reduced, then we can recover g
m
′ by the orthogonal lattice attack and eventually g
m by firstly exhausting the value of t
=
∏
i
=
m
n
‍
α
i and then combining g
i
′ and t to derive g
i
=
t
g
i
′. However, after the transformation of (23), we cannot expect to extract a large greatest common divisor for the entries of g
m. We suggest choosing Δ with determinant being δ
11
δ
22
-
δ
21
δ
12
=
±
1 in Remark 22, in which case we can make sure that gcd
(
δ
11
,
δ
12
)
=
gcd
(
δ
21
,
δ
22
)
=
1. If the two gcd’s are greater than 1, say δ
=
gcd
(
δ
11
,
δ
12
)
>
1, then δ
∣
g
i
=
δ
11
u
i
+
δ
12
v
i and hence t
=
gc
d
m
g
≥
δ, which may compromise the security.


## 5.3.1. GCD Attack

The GCD attack in [4] was used to successfully attack the knapsack-based probabilistic public key encryption [28]. The attack illustrates that if the entries of b
=
(
b
1
,
…
,
b
n
) assume a linear combinatorial relation with small integer combinatorial coefficients, we can recover the secret modulus N by computing the greatest common divisor for a set of numbers. This point will be explored later on, or the readers can refer to [4] for more details. We first note that if the modulus N
=
p
q is known, under the suggested parameters, n
=
60, 90, and 120, the binary length of N is upper bounded by 355, 523, 690, respectively. See (36). It is not intractable to factor the moduli by using the fastest factorization algorithm [29]. Hence, one can factor N into its prime products. Once p and q have been obtained, the adversary can do the modular reductions, a
i
p
=
a
i
(
mod
⁡
p
) and a
i
q
=
a
i
(
mod
⁡
p
). If we denote the modular reductions of w
-
1 modulo p and q as w
p
-
1 and w
q
-
1, from (25) and (26), we know g
i
=
a
i
p
w
p
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
p
) and h
i
=
a
i
q
w
q
-
1
=
a
i
w
-
1
=
b
i
(
mod
⁡
q
) and then exhaust the matrix Δ to reverse the process of (23) as
(58)
(
u
v
)
=
Δ
-
1
(
g
h
)
=
(
δ
22
-
δ
12
-
δ
21
δ
11
)
(
g
h
)
,
where for convenience, we just set |
Δ
|
=
1. So we have
(59)
u
i
=
δ
22
〈
a
i
p
w
p
-
1
〉
p
-
δ
12
〈
a
i
q
w
q
-
1
〉
q
,
v
i
=
δ
11
〈
a
i
q
w
q
-
1
〉
q
-
δ
21
〈
a
i
p
w
p
-
1
〉
p
.
We note that gc
d
n
-
1
u
∣
u
i, gc
d
n
-
1
v
∣
v
i for i
=
1
,
…
,
n
-
1, a
i
p and a
i
q are publicly computable once p and q have been obtained, and (
gc
d
n
-
1
u
,
gc
d
n
-
1
v
)
∈
AI
P
〈
n
〉
12
∪
AI
P
〈
n
〉
12
T and δ
i
j can be efficiently exhausted (and hence we can assume that they are all known). So, for i
=
1
,
…
,
n
-
1, we have
(60)
δ
22
a
i
p
x
0
-
δ
22
x
2
i
p
-
δ
12
a
i
q
x
1
-
δ
12
x
2
i
+
1
q
-
k
i
gc
d
n
-
1
u
=
0
,
δ
11
a
i
q
x
1
-
δ
11
x
2
i
+
1
q
-
δ
21
a
i
p
x
0
-
δ
21
x
2
i
p
-
l
i
gc
d
n
-
1
v
=
0
with integer unknowns 0
<
x
0
=
w
p
-
1
<
p, 0
<
x
1
=
w
q
-
1
<
q, x
2
i (x
2
i
+
1, resp.) being the incomplete quotient of a
i
p
x
0 (a
i
q
x
1, resp.) divided by p (q, resp.), and k
i and l
i are the quotients of u
i and v
i divided by gc
d
n
-
1
u and gc
d
n
-
1
v, respectively. So we have 0
≤
x
2
i
<
a
i
p, 0
≤
x
2
i
+
1
<
a
i
q, 0
<
k
i
<
p
/
gc
d
n
-
1
u, and 0
<
l
i
<
q
/
gc
d
n
-
1
v. We can use an efficient heuristic algorithm for solving a system of linear Diophantine equations with lower and upper bounds on the variables given in [30] (see also Section 3 of [4] for a simplified description) to determine these unknowns, and eventually the full secret keys. So we caution that in implementation, we must keep the modulus N secret. However, we will show that the GCD attack is useless to derive modulus N.The condition for the GCD attack to succeed in finding modulusN is that we can construct some linear relations using the entries of the public sequence b. To illustrate, we recall (26) and argue that there must exist integers s
i such that b
i
w
-
s
i
N
=
a
i. We assume that the entries of b share some linear combinatorial relations with small coefficients, say t
1
b
1
-
t
2
b
2
=
0, t
3
b
3
-
t
4
b
4
=
0, where by saying small coefficients we mean we can efficiently do exhaustive search for these t
i’s. So we conclude that N
∣
t
1
a
1
-
t
2
a
2
=
N
(
s
1
t
1
-
s
2
t
2
) and N
∣
t
3
a
3
-
t
4
a
4 and hence can expect N
=
gcd
(
t
1
a
1
-
t
2
a
2
,
t
3
a
3
-
t
4
a
4
). We must admit that the entries of u (and v) do share a linear combinatorial relation; for example, from (★) we derive ζ
2
u
1
-
α
1
u
2
=
0. However, we should bear in mind that b is fully scrambled by (23) and (25) especially through the confusion role of the Chinese remainder theorem in (25). So it is unlikely for the adversary to derive modulus N by launching a GCD-like attack on the proposal.


## 5.3.2. Simultaneous Diophantine Approximation Attack

After Shamir broke the basic Merkle-Hellman knapsack cryptosystem [31, 32], cryptanalysts began to investigate the security of the multiply iterated Merkle-Hellman cryptosystem. Lagarias observed that the size conditions and the modular transformation in the multiply iterated Merkle-Hellman cryptosystem help him construct a simultaneous Diophantine approximation problem [7]. Lagarias showed that he can successfully launch a key-recovery attack on the doubly iterated Merkle-Hellman cryptosystem through his simultaneous Diophantine approximation approach.Many knapsack-type cryptosystems use size conditions to disguise an easy knapsack problem. In such a cryptosystem, the designer randomly generates an easy knapsack problem,y
=
∑
i
=
1
n
‍
a
i
x
i
,
x
i
∈
[
0
,
2
b
-
1
], and chooses a modulus m and a multiplier w, gcd
(
m
,
w
)
=
1. He uses the size condition m
>
(
2
b
-
1
)
∑
i
=
1
n
‍
a
i to disguise the easy knapsack sequence a
=
(
a
1
,
…
,
a
n
) as a seemingly hard knapsack sequence b
=
(
b
1
,
…
,
b
n
) by a modular multiplication, b
i
=
〈
w
a
i
〉
m. The size condition and the public sequence can be utilized to derive a simultaneous Diophantine approximation problem, namely, the problem to find a set of rational numbers sharing a common and relatively small denominator to simultaneously approximate a given set of real numbers. By launching the simultaneous Diophantine approximation attack, the adversary can obtain some useful information about (
w
,
m
). See [6, 7] for more details about the relation between the simultaneous Diophantine approximation problem and knapsack public key cryptanalytics.The trapdoor of the proposed system is disguised using the Chinese remainder theorem, which involves no size conditions. Hence, the adversary cannot expect finding some information about the trapdoor by launching a simultaneous Diophantine approximation attack. However, the reader may doubt that the size condition has been used in (24). We should observe that if the adversary wants to launch a simultaneous Diophantine approximation attack, he must peel off the outmost shuffle in (25) and (26). This seems intractable in that the adversary does not know the primes p and q.


## 5.3.3. Orthogonal Lattice Attack

To examine the security, we must consider the orthogonal lattice attacks introduced by Nguyen and Stern [8, 9], which were used to successfully though heuristically recover the secret keys of two PKCs [33, 34]. We first illustrate why the orthogonal lattice attack can be used to reconstruct the secret key of the PKC in [34], and then show why our proposal is immune from the orthogonal lattice attack.In the PKC [34], the security parameter s
=
1024 is suggested, a modulus N
=
p
q with p and q being primes of lengths, respectively, |
p
|
2
=
3
s
/
4 and |
q
|
2
=
s
/
4 is chosen, and the secret sequence g
=
(
g
1
,
…
,
g
n
) (typically n
=
180) with each entry g
i
<
p
1
/
l (typically l
=
17) is generated so that the public sequence a
=
(
a
1
,
…
,
a
n
) can be computed via a modular multiplication a
i
=
w
g
i
(
mod
⁡
N
) for a randomly chosen w
∈
ℤ
N
*. The core for the orthogonal lattice attack to recover the secret key of [34] is to choose 0
<
m
≤
n entries a
m
=
(
a
1
,
…
,
a
m
) from a and then obtain sufficiently many small and linearly independent solutions x
m
=
(
x
1
,
…
,
x
m
) to 〈
a
m
,
x
m
〉
=
0. Given a solution x
m, we must have 〈
a
m
,
x
m
〉
=
〈
w
g
m
,
x
m
〉
=
w
〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), where g
m
=
(
g
1
,
…
,
g
m
). So 〈
g
m
,
x
m
〉
=
0
(
mod
⁡
p
), which means that x
m is orthogonal to g
m, or 〈
g
m
,
x
m
〉
=
k
p with k
≠
0. In the second case, from Cauchy-Schwarz inequality, we have
(61)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
m
p
1
/
l
≈
N
12
/
17
m
,
when concrete parameters are concerned, which implies that either x
m is orthogonal to g
m or the norm of x
m is quite large. From the observations, the authors of [9] conjectured that among the reduced basis (
b
1
,
…
,
b
m
-
2
,
b
m
-
1
) of the (
m
-
1
)-dimensional lattice consisting of the integer solutions to 〈
a
m
,
x
m
〉
=
0, the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 are orthogonal to g
m, namely, Assumption 4 of [9]. By noting that g
m belongs to the two-dimensional orthogonal lattice ℒ
⊥ consisting of all m-dimensional integer vectors orthogonal to the lattice vectors in ℒ
(
b
1
,
…
,
b
m
-
2
) and that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value, they provide another assumption conjecturing that g
m is a shortest vector in ℒ
⊥, namely, Assumption 5 of [9]. So given a
m, we can expect to find the reduced basis b
1
,
…
,
b
m
-
2 and the shortest vector g
m by using lattice reduction algorithms.In the proposed cryptosystem, we generatep according to (24), so we can assume that p
>
191
n
g
i. Equation (61) turns out to be
(62)
∥
x
m
∥
≥
|
〈
g
m
,
x
m
〉
|
∥
g
m
∥
≥
p
p
/
(
191
n
)
m
=
191
n
m
.
Under the suggested parameters n
=
60, 90, 120, 191
n is at most 15 bits long, so the assumption will be too strong to be satisfied that the first m
-
2 basis vectors b
1
,
…
,
b
m
-
2 have norms less than 191
n
/
m and hence are orthogonal to g
m. Furthermore, in [34], we can argue that ∥
g
m
∥
<
m
p
1
/
l
=
m
p
1
/
17 is a very small value; however, we just obtain ∥
g
m
∥
<
m
p
/
(
191
n
) in the proposed cryptosystem and hence cannot assume that g
m is a shortest vector in ℒ
⊥.To summarize, we can conjecture that the requirement ofg
i
l
<
p in [34] makes both to find m
-
2 linearly independent short vectors b
1
,
…
,
b
m
-
2 and to accept the shortest vector in ℒ
⊥ as the target vector g
m possible, while in the proposed cryptosystem p
>
191
n
g
i is only somewhat larger than those g
i, from which we cannot formalize Assumptions 4 and 5 provided in [9]. Hence, the proposed cryptosystem is invulnerable to the orthogonal lattice attack.Remark 33.
Now we explain why we introduce the matrixΔ when generating the public keys. If Δ is the two-dimensional identity matrix I
2, g
=
u, we can distil a relatively large common divisor t
=
gc
d
m
g
=
gc
d
m
u
=
∏
i
=
m
n
‍
α
i (see (★)) from the preceding m entries of g. Thus, if we define g
m
′
=
(
g
1
′
,
…
,
g
m
′
) with g
i
′
=
g
i
/
t being sharply reduced, then we can recover g
m
′ by the orthogonal lattice attack and eventually g
m by firstly exhausting the value of t
=
∏
i
=
m
n
‍
α
i and then combining g
i
′ and t to derive g
i
=
t
g
i
′. However, after the transformation of (23), we cannot expect to extract a large greatest common divisor for the entries of g
m. We suggest choosing Δ with determinant being δ
11
δ
22
-
δ
21
δ
12
=
±
1 in Remark 22, in which case we can make sure that gcd
(
δ
11
,
δ
12
)
=
gcd
(
δ
21
,
δ
22
)
=
1. If the two gcd’s are greater than 1, say δ
=
gcd
(
δ
11
,
δ
12
)
>
1, then δ
∣
g
i
=
δ
11
u
i
+
δ
12
v
i and hence t
=
gc
d
m
g
≥
δ, which may compromise the security.


## 6. Conclusions

In this paper, we defined a public key cryptographic scenario PSTOF and used the knapsack problem to exemplify how to further weaken the cryptographic assumptions used in public key cryptography. Extensive security scrutiny is made on the proposed probabilistic encryption scheme; however, some security drawbacks may still exist in the proposal. If some cryptanalysts announced that the proposed cryptosystem is breakable, we would not be surprised in that some cleverer and efficient cryptanalytic method may be developed. But we are confident that the proposal can be broken only by successfully launching a key-recovery attack. We think that if someone invents a PSTOF with a hard-to-discover trapdoor by fully exploring the noninjectivity property of the underlying one-way function, it can be used to provide a higher level of security. We hope that some more elegant methods can be developed in the cryptographic literature to provide more practical and secure realizations of the concept of PSTOF. Some more cryptanalytic discussions are needed to obtain all-sided and in-depth security analysis of the proposal, which belongs to our future work.



---

*Source: 475678-2014-04-27.xml*