Open AccessArticle

Practical NTRU Signcryption in the Standard Model

Jianhua Yan

¹,

Xiuhua Lu

²,

Muzi Li

^3,*,

Licheng Wang

⁴,

Jingxian Zhou

⁵ and

Wenbin Yao

⁶

School of Information and Electric Engineering, Ludong University, Yantai 264025, China

School of Cyber Science and Engineering, Qufu Normal University, Qufu 273165, China

Archive Library, Ludong University, Yantai 264025, China

⁴

School of Cyberspace Security, Beijing Institute of Technology, Beijing 100081, China

⁵

Institute of Science and Technology Innovation, Civil Aviation University of China, Tianjin 300300, China

⁶

School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China

Author to whom correspondence should be addressed.

Entropy 2023, 25(12), 1651; https://doi.org/10.3390/e25121651

Submission received: 18 October 2023 / Revised: 3 December 2023 / Accepted: 6 December 2023 / Published: 13 December 2023

(This article belongs to the Section Information Theory, Probability and Statistics)

Download Versions Notes

Abstract

Based on the NTRU trapdoor used in NIST’s Falcon, a signcryption scheme following the sign-then-encrypt paradigm is constructed. The existing partitioning technique based on Waters hash over the lattice can not complete the security reduction in the standard model for the signature part due to the “partiality” of the pre-image generated with the NTRU trapdoor. To address this, a variant of Waters hash over small integers is proposed and, the probability of the successful reduction is analyzed. The resulting signcryption achieves existential unforgeability under the adaptive chosen-message attacks. By utilizing the uniqueness of the secret and the noise in an NTRU instance, the tag used in encryption is eliminated. Furthermore, a method to construct tamper-sensitive lattice public key encryption is proposed. This approach implants the ciphertext-sensitive information into the lattice public key encryption and binds it to the encrypted information. The malleability to the public key ciphertext triggers the change of the message–signature pair so that the IND-CCA2 security of the entire ciphertext can be guaranteed by the signature for the message. Thanks to the rational design and the efficiency of the NTRU trapdoor, the computational overhead of the proposed scheme is reduced significantly compared to the existing lattice-based signcryption scheme, reaching orders of magnitude improvement in efficiency. The experiment shows that the proposed scheme is efficient.

Keywords:

lattice; NTRU signcryption; IND-CCA2; partitioning technique; quantum-resistant

1. Introduction

Network interaction in complex scenarios provides better services and more convenience for people to live, work, and study. The information security issues in complex scenarios have also become a thorny issue for network workers. In general, a common requirement for information security in complex scenarios is to ensure the comprehensive security of information: confidentiality, integrity, authentication, and non-repudiation. The signcryption due to Zheng [1] can simultaneously guarantee the above-integrated security at a low cost. Designing a secure signcryption scheme has become a research hotspot. Cryptographers have conducted a lot of in-depth research on signcryption based on the number theory and have achieved a series of good results. However, the rapid development of quantum computing [2] has posed a serious threat to the security foundation of traditional cryptography based on number theory. Lattice-based cryptography is becoming the backbone of quantum-resistant cryptography, due to its advantages in efficiency, flexibility, and security in the average case. It has become a common concern to construct a signcryption scheme based on the lattice.

1.1. Related Works

To resist quantum attacks, Li et al. proposed the first lattice-based signcryption [3]. After that, the lattice signcryption is developed in three directions: different security models, advanced primitives, and specific applications. Regarding the applications, the signcryption applied to the management of health records has been studied in depth [4,5]. In terms of advanced signcryption primitives, the identity-based signcryption scheme [6], attribute-based signcryption scheme [7] (to support non-interactive fine-grained access control), and multi-recipient scheme [8] were constructed. For the security model, the schemes under the random oracle [9,10,11,12,13], in which [11] is the most efficient due to drawing lessons from the signcryption on Schnorr signature from [14] and the compression technique [15,16], and some schemes under the standard model were constructed.

In 2013, Yan et al. constructed a secure lattice signcryption scheme [17] under the standard model (YWW+13 [17] for short) based on the MP trapdoor [18]. This scheme follows the sign-then-encrypt (StE) paradigm, and the security of the ciphertext must be shifted to a reliance on the unforgeability of the signature with the help of the message authentication code (MAC). In fact, the MAC itself has the ability to improve IND-CCA1 security to IND-CCA2 security. Since the tag used for encryption is generated with the signature value, the lattice-based chameleon hash function is required in the process to vanish the trapdoor for completing the security reduction, which increases the computational overhead and the size of the public key. In 2018, Sato et al. made great progress in proposing a secure signcryption scheme [19] (SS18 [19] for short) under the standard model also based on the MP trapdoor. The lattice-based public key encryption (PKE) is actually an instance of learning with errors (LWE),

c^{'}

{[A ∥ u]}^{t} s + e

, plus the encoding of the message

[0 ∥ μ] ⌊ q / 2 ⌋

. The malleability of the ciphertext lies in the homomorphic computational property of the LWE instance and that of the message. That is, it will affect the decryption, adding

{[A ∥ u]}^{t} s^{'}

to the LWE instance, appending a small error

e^{'}

to the LWE instance or superimposing additional information to the message. To eliminate the malleability of the ciphertext, the LWE instance is signed along with the original message in SS18 [19]. Meanwhile, the homomorphic malleability to the plaintext code will of course break the signatures. In this sense, the scheme belongs to the encrypt-then-sign (EtS) paradigm instead of the StE paradigm, as they claim. In 2019, Yang et al. constructed a signcryption scheme [20] (YCL+19 [20] for short) under the standard model based on ring learning with errors (RLWE) [21]. YCL+19 uses the key exchange [22,23] rather than the public key encryption to generate the key for the symmetric encryption, which reduces the size of the public key encryption. The hint information of the lattice-based key exchange is naturally immune to tampering due to its sensitivity to key recovery. However, it incurs a security risk to expose another part of the key exchange. Liu et al. proposed an NTRU-based signcryption [24] (LTTM19 [24] for short) by adopting NTRU-based key encapsulation [25] and an NTRU-based signature [26]. However, the unsigncryption queries can not be implemented in the security reduction under the standard model, so the scheme is not IND-CCA2 secure as they claimed. In the sign-then-encrypt (StE) paradigm, the signature seems more natural than that in encrypt-then-sign (EtS) paradigm since it is signed only for the message. Moreover, the construction of signcryption under the StE paradigm is more concerned with cryptographers [27,28]. It is also a problem of great importance to design a secure lattice-based signcryption scheme following the StE paradigm.

To address the quantum threat to cryptography based on number theory, in 2017, the National Institute of Standards and Technology (NIST) began collecting the post-quantum public key cryptography algorithms through an open, competitive process. The post-quantum cryptographic (PQC) algorithm should meet the following five requirements: secure under the existing computing conditions and quantum computers, fast operation, reasonable communication overhead, can be used as a direct replacement for the existing algorithms and protocols, and broad application scenarios. After many rounds of rigorous screening, NIST announced the screening results of the third round of post-quantum cryptographic algorithm standardization in July 2022. In the four post-quantum algorithms, there are two lattice-based signature algorithms, CRYSTALS-Dilithium [29] and Falcon [30], and they are more efficient than the hash-based signature. In fact, in May 2022, the scientists from Google published the latest research results [31] in the journal “Nature” to illustrate the importance of post-quantum cryptography (PQC) and appeal to transition to PQC. Thus, it is a natural question: Can an efficient signcryption scheme following the StE paradigm be designed based on the NIST standard, which is secure in the standard model and does not require MAC transferring?

1.2. Proposed Design

To resist quantum attacks, we construct a signcryption scheme based on NTRU, referred to as SC-NTRU. Our contribution can be summarized in two main points. First, we introduce an approach to improve the security of the encryption segment using the signature segment for the messages in the signcryption. The signature security can be appropriately decreased compared with that in the EtS paradigm. Second, we construct a new abort-resistant hash to adapt to the approximate pre-image scenario, and utilize it to build an NTRU signature secure in the standard model. The reasonable design and efficient trapdoor of SC-NTRU lead to a significant reduction in computational overhead, surpassing existing lattice-based signcryption methods by several orders of magnitude.

We have developed a method to achieve IND-CCA2 security in signcryption by combining three techniques. Firstly, we leverage the uniqueness of the secret and noise used in lattice-based encryption to transform tag-based encryption into general encryption. Secondly, we embed sensitive information related to the ciphertext itself into the ciphertext, binding it to the information to be encrypted using public key encryption (PKE). As the entire encryption is a hybrid encryption, the plaintext hidden in PKE serves as a key for symmetric encryption. Any modification to the ciphertext will consequently modify the key of the symmetric encryption due to their interdependence. Thirdly, we exploit the one-to-one property of symmetric encryption, such that a modified public key ciphertext will produce a modified message–signature pair. Subsequently, the unforgeability of the signature can be utilized to check the malleability and enhance the IND-CCA2 security of the complete ciphertext. It is important to note that the signature here does not need to achieve strong unforgeability while the strong unforgeability for a signature is necessary in the general construction of the IND-CCA2 secure encryption scheme. Since the message–signature pair here is encrypted and concealed from potential adversaries, any attempt to forge a signature would result in a new signature. In summary, the requirement for the signature to enhance encryption to IND-CCA2 security is diminished. Even a strong forgery of the signature supplies no help to unsigncrypting.

A common approach to constructing a secure lattice signature scheme in the standard model is through a partitioning technique based on Waters hash [32]. In [33], this hash function takes the form

H (ν_{0}, ν_{1}, \dots, ν_{ℵ}) = \sum_{i = 0}^{ℵ} {(- 1)}^{ν_{i}} p_{i}

, with

p_{i} \in Z_{q}

for

i = 0, 1, \dots, ℵ

; it is also referred to as an abort-resistant hash function. The probability of the hash not aborting is demonstrated using the concept of the hyperplane in [34]. However, we find that this hash proposed in [34] can not help us complete the security reduction for the signature component involved in the signcrytion. The pre-image generated by the NTRU trapdoor exhibits a certain level of “partiality”. The entire NTRU trapdoor does not fall into the category of approximate trapdoors, such as that constructed by Chen [35] based on [18], and the pre-image generated by NTRU trapdoor can be exact in its entirety. However, the checkout polynomial only operates on a subset of the pre-image, which is reflected in its form

s_{1} + s_{2} * h_{f} = 0

(refer to Algorithm 2). In other words, the pre-image corresponding to the checkout polynomial is merely an approximate pre-image, as there exists a small error vector

x^{'} = y - h_{f} x

. The range of the existing abort-resistant hash is

Z_{q}

. When the hash value operates on the checkout polynomial, the product of the hash value and the short error vector

x^{'}

results in a vector close to the uniform distribution over

Z_{q}^{n}

. Consequently, this product vector makes it impossible to simulate the signature in security reduction. To address this issue, we modify the hash range to a space with a small value. However, this modification leads to a significant increase in the abort probability, which hinders secure reduction. To overcome this issue, we introduce a new random variable that cyclically selects random numbers when the abort condition is met. This helps to avoid premature abandonment. Subsequently, we need to evaluate the probability of successfully completing reduction when an adversary forges a signature. However, this evaluation is not trivial since the hyperplane model for the abort-resistant hash defined over a ring (

Z_{q}

) is inadequate for the hash over small integers.

2. Preliminaries

In this paper, the notations are as follows.

Z

: the set of integers;

Z^{+}

: the set of positive integers;

R

: the ring

R

= Z [x] / (1 + x^{n})

; for a prime q,

R_{q}

= R / q

; the bold lowercase letter: polynomial or the vector composed of the coefficients of the polynomial; the bold uppercase letter: matrix;

\tilde{B}

: Gram–Schmidt orthogonalization of the matrix

B

;

∥ x ∥

: the two-norm of a vector named

x

;

∥ X ∥

: the maximum of the column vectors,

∥ X ∥ = m a x_{i} {∥ X_{i} ∥}

2.1. NTRU Lattice and Hard Problem

Definition 1 (NTRU Lattice).

Let

R

= Z [x] / (1 + x^{n})

for some power-of-two integer n. Let

h = g * f^{- 1} mod q

for

f, g \in R

and

q \in Z^{+}

. The corresponding NTRU lattice to

h, f

is defined as

\begin{matrix} \begin{matrix} Λ_{h, q} = {(u, v) \in R^{2} | u + v * h = 0 mod q} . \end{matrix} \end{matrix}

Λ_{h, q}

is a full-rank lattice over

Z^{2 n}

linearly spanned by the row vectors of

A_{h, q} = (\begin{matrix} - A_{N} (h) & I_{n} \\ q I_{n} & O_{n} \end{matrix})

, where

A_{N} (h)

denotes the anti-circulant matrix generated by the vector

h

Definition 2

(Decisional Small Polynomial Ratio: DSPR [36]). Let

R

= Z [x] / (1 + x^{n})

R_{q} = R / q

. For

g, f \in R

with small coefficients and

f

invertible over

R_{q}

, the distinguishing problem between the distribution of

h = g f^{- 1} mod q

and that of

h^{'} \overset{$}{\leftarrow} R_{q}

is defined as the decisional small polynomial ratio problem.

The hardness of the search version of DSPR has been studied in [37].

Definition 3 (Search Learning with Errors in a Ring of Integers).

Let Ψ be a family of distributions over

K_{R}

and

2 < q \in Z

. The RLWE problem RLWE

_{q, Ψ}

is to find

s \in R_{q}^{\lor}

by allowing access to arbitrarily many samples from

A_{s, Ψ}

for

ψ \in Ψ

Proposition 1

(Hardness of RLWE [21]). Let K denote an arbitrary number field with degree n. Let

Z ∋ q = q (n) \geq 2

and arbitrary

α = α (n) \in (0, 1)

satisfying

α q \geq ω (\sqrt{\log n})

. A probabilistic polynomial time quantum reduction can be constructed from K-

{DGS}_{γ}

O_{K}

{LWE}_{q, Ψ_{\leq α}}

, where

γ = η_{ϵ} (I) \cdot ω (\sqrt{\log n}) / α

2.2. Trapdoor Generation and Pre-Image Sample Algorithm

Proposition 2 (NTRU Key Generation).

Inputting dimension n and modulus q, there is an efficient keyGen algorithm to output public key

h

and the trapdoor

B = (\begin{matrix} A_{N} (g) & - A_{N} (f) \\ A_{N} (g^{'}) & - A_{N} (f^{'}) \end{matrix})

, such that

h

is computationally indistinguishable from the uniform distribution over

R

∥ \tilde{B} ∥ \leq 1.17 \sqrt{q}

, and

g, f \leftarrow D_{Z^{n}, η}

for

η \leq 1.17 \sqrt{q / (2 n)}

Proposition 3

(Pre-Image Sampling [38]). Let

ϵ = 2^{- λ} / (2 n)

for arbitrary

n, λ \in Z^{+}

, Δ denote statistical distance. For any basis

B \in Z^{n \times n}

Λ_{A, q}

and arbitrary syndrome vector

u \in Z^{n}

, there is a pre-image sampling algorithm

GS

x = GS (B, η, u)

, such that

A x = u mod q

and

Δ (D_{Λ (B, η, u)}, x) \leq 2^{- λ}

, when

η \geq ∥ \tilde{B} ∥ \cdot ζ_{ϵ}^{'} (Z)

and

ζ_{ϵ}^{'} (Z) \approx \frac{1}{π} \sqrt{\frac{1}{2} l n (2 + \frac{2}{ϵ})}

. ϵ can be relaxed to

2^{- λ / 2} / (4 \sqrt{2} n)

, and

ζ_{ϵ}^{'} (Z) \approx \frac{1}{\sqrt{2} π} \sqrt{ln 2^{(λ + 7) / 2} n}

Proposition 4 (Discrete Gaussian Distribution).

Let Λ be an m-dimension lattice. Let real s be the Gauss parameter and

c \in R^{m}

be the center. The discrete Gauss distribution has the following good properties.

1.: (Lemma 4.4 of [39]) For any positive real k, $P r [| x | > k s; x \overset{$}{\leftarrow} D_{Z, s}] \leq 2 e^{- k^{2} / 2}$ .
2.: (Lemma 4.4 of [39]) When $s > 3 / \sqrt{2 π}$ , $D_{Z, s}^{m} (x) < 2^{- m}$ for all vector $x \in Z^{m}$ .
3.: (Lemma 4.4 of [39]) For any positive real k, $P r [∥ x ∥ > k s \sqrt{m}; x \overset{$}{\leftarrow} D_{Z, s}^{m}] \leq k^{m} e^{(1 - k^{2}) m / 2}$ .
4.: (Lemma 4.3 of [39]) Let $t \in R^{+}, v \in R^{m}$ . Then $P r [〈 z, v 〉 > t] \leq 2 e^{- t^{2} / (2 s^{2} {∥ v ∥}^{2})}$ .
5.: (Lemma 4.4 of [40]) $\underset{x \sim D_{Λ, s, c}}{P r} [∥ x - c ∥ \geq s \sqrt{m}] \leq \frac{1 - ϵ}{1 + ϵ} 2^{- m}$ .
6.: (Lemma 5.2 and Corollary 5.4 of [41]) Let $n, m$ be integers, s real and q prime. When $s \geq ω (\sqrt{\log m})$ , $s \geq η_{ϵ} (Λ^{⊥} (A))$ for $ϵ \in (0, 1 / 2)$ . When $m \geq 2 n \log q, s \geq ω (\sqrt{\log m})$ , with $1 - 2 q^{- n}$ probability, the syndrome $y = A x$ is statistically close to uniform over $Z_{q}^{n}$ for all $A \in Z_{q}^{n \times m}$ , $x \overset{$}{\leftarrow} D_{Z, s}^{m}$ .
7.: (Lemma 2.4 of [42] or lemma 4.4 [40]).

$ρ_{s} (Λ + c) \in [\frac{1 - ϵ}{1 + ϵ}, 1] \cdot ρ_{s} (Λ) .$

3. Signcryption: Syntax and Security Models

In this section, the syntax and security models of signcryption are presented.

3.1. Syntax of Signcryption

A signcryption scheme is composed of the following four algorithms:

Setup $(λ)$ : This algorithm takes a security parameter $λ$ as input, then returns the public parameter $P P$ .
KeyGen $(λ, PP)$ : Input the security parameter $λ$ and the public parameter $P P$ , and output the public key and private key pairs $(P K, S K)$ for users.
SignCrypt $(μ, P K_{s}, S K_{s}, P K_{r})$ : Take a message $μ$ , the sender’s public key $P K_{s}$ and private key $S K_{s}$ , and the recipient’s public key $P K_{r}$ , generate a ciphertext c.
UnSignCrypt $(c, P K_{s}, S K_{r})$ : Inputting a ciphertext c, the sender’s public key $P K_{s}$ and the recipient’s private key $S K_{r}$ , this algorithm unsigncrypts the ciphertext and verifies the signature. If the signature can pass the verification, it returns the message $μ$ , otherwise it returns ⊥.

3.2. Security Models of Signcryption

To clarify the confidence of the signcryption, an IND-CCA2 game is introduced (Table 1).

Initial: The challenger $C$ runs the setup and key generation algorithms to generate public parameters $P P$ , the receiver’s keys $(P k_{r}, S K_{r})$ , and the sender’s keys $(P k_{s}, S K_{s})$ , followed by giving $(P P, P k_{r}, P k_{s}, S K_{s})$ to an adversary $A$ .
Phase 1: The adversary $A$ implements the unsigncryption queries in an adaptive manner bounded by polynomial times. If c is a valid ciphertext, $C$ replies with the corresponding plaintext $μ$ , otherwise it returns ⊥.
Challenge: $A$ selects two plaintexts $μ_{0}, μ_{1}$ with equal length and gives them to $C$ . $C$ tosses a fair coin $b \in {0, 1}$ and generates a challenge ciphertext $c^{*} =$ signcrypt $(P K_{s}, S K_{s},$ $P K_{r}, μ_{b})$ followed by giving $c^{*}$ to $A$ .
Phase 2: $A$ continues to perform unsigncryption queries as in Phase 1, except for not permitting to query unsigncryption on $c^{*}$ .
Guess: $A$ gives $b^{*}$ as the guess on b tossed by $C$ .

Then, the advantage of

A

to win Game IND-CCA2 is defined as

A d v (A) = | Pr [b = b^{'}] - \frac{1}{2} |

Definition 4 (Confidentiality of Signcryption).

A signcryption scheme is said to be indistinguishable against inner choose ciphertext attacks (IND-CCA2) if there exists no probabilistic polynomial time inner adversary who can win Game IND-CCA2 with a non-negligible advantage.

To capture the unforgeability of the signcryption, an EUF-CMA game is introduced (Table 2).

Initial: The challenger $C$ runs the setup and key generation algorithms to generate public parameters, the keys for the receiver and sender are as in the IND-CCA2 Game. Subsequently, $C$ gives $(P P, P k_{s}, P k_{r}, S K_{r})$ to $A$ .
Signcrypt: $A$ chooses messages $μ$ and implements polynomially-bounded signcryption queries by an adaptive approach. $C$ replies with the corresponding ciphertexts c.
Forge: $A$ outputs $c^{*}$ , which contains a new signature for some $μ$ that has not been previously queried.

Then, the advantage of

A

to win Game EUF-CMA is defined as

A d v (A) = Pr [(μ, σ)

Unsigncrypt

(c^{*}) and N]

, where

N

denotes the fact that

σ

is a valid signature for

μ

not discoved by the unsigncryption queries.

Definition 5 (Existential Unforgeability of Signcryption).

A signcryption scheme is said to be existentially unforgeable against inner chosen message attacks (EUF-CMA) if no probabilistic polynomial time forgery can win Game UF-CMA with a non-negligible advantage.

4. Signcryption Based on NTRU

In this section, a signcryption scheme based on NTRU is proposed, followed by its correctness and parameter settings.

4.1. Construction

The symmetric encryption ENC involved in the proposed scheme is IND-OT secure and one-to-one. That is, for a plaintext

μ

and symmetric key k, there is only one ciphertext c satisfying DEC

_{k} (c) = μ

Setup $(1^{λ})$ : On inputting a security parameter $1^{λ}$ , generate the public parameters and hash functions.
- Choose hash functions: $H_{0} : {0, 1}^{*} \to {0, 1}^{ℵ}$ , $H_{1} : R_{q} \to R_{q}$ , $H_{2} : R_{q} \times R_{q} \to {0, 1, 2, 3}^{n}$ .
- $y, u \overset{$}{\leftarrow} R_{q}$ .
- $z_{i} \overset{$}{\leftarrow} R_{q}$ for $i = 0, 1, \dots, ℵ$ .
- publish public parameters $(y, u, {z_{i}}_{i = 1}^{ℵ})$ .
KeyGen $(1^{ℓ})$ : User i generates it own public key and private key.
- $(B, h) \leftarrow KeyGen (n, q)$ to satisfy $B (\begin{matrix} i \\ h \end{matrix}) = 0$ where $B = (\begin{matrix} A (g) & - A (f) \\ A (G) & - A (F) \end{matrix}) \in Z^{2 n \times 2 n}$ , The coefficient vector of $i$ is ${(1, 0, 0, \dots, 0)}^{t}$ .
- $b, d \overset{$}{\leftarrow} R_{q}$ .
- Publish $(b, d, h)$ as public key and keep $B$ as private key. Namely, the sender’s (resp. receiver’s) public and private key are $((b_{s}, d_{s}, h_{s}), B_{s})$ (resp. $((b_{r}, d_{r}, h_{r}), B_{r})$ ).
SignCrypt $(μ, h_{r}, B_{s}, {z_{i}}_{i = 0}^{ℵ})$ .
- $k \overset{$}{\leftarrow} {0, 1, 2, 3}^{n}$ .
- $ν$ : $= H_{0} (μ, b_{r}, k)$ .
- $z$ : $= z_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} z_{i}$ .
- $x_{1} \leftarrow D_{Z^{n}, η_{1}}$ .
- $t$ : $= y - z x_{1}$ .
- $(x_{0}^{'}, x_{0})$ : $= (t, 0) - SamplePre (B_{s}, η_{1}, (t, 0))$ .
- $x$ : $= {(x_{0}, x_{1})}^{t}$ .
- $r \overset{$}{\leftarrow} {- 1, 0, 1}^{n}$ , $e_{0}, e_{2} \overset{$}{\leftarrow} {- ϱ, \dots, ϱ}^{n}$ , $e_{1} \overset{$}{\leftarrow} {([- ϱ \sqrt{n}, ϱ \sqrt{n}] \cap Z)}^{n}$ .
- $c_{0}$ : $= r h_{r} + e_{0}$ .
- $c_{1}$ : $= r (b_{r} + H_{1} (c_{0}) d_{r}) + e_{1}$ .
- $c_{2}^{'}$ : $= ⌊ (r u + e_{2}) / 2^{ℓ} ⌋$ .
- $c_{2}$ : $= c_{2}^{'} + ⌊ ((H_{2} (c_{1}, c_{2}^{'}) \oplus k) ⌊ q / 8 ⌋) / 2^{ℓ} ⌋$ .
- $c_{3}$ : $= {Enc}_{H_{3} (k)} (x, μ)$ .
- output $(c_{0}, c_{1}, c_{2}, c_{3})$ .
UnSignCrypt $(c_{0}, c_{1}, c_{2}, c_{3}, B_{r}, h_{s}, {z_{i}}_{i = 0}^{ℵ})$ .
- $s_{1} \leftarrow D_{Z^{n}, η_{2}}$ .
- $t$ : $= u - s_{1} (b_{r} + H_{1} (c_{0}) d_{r})$ .
- $(s_{0}^{'}, s_{0}) = (t, 0) - SamplePre (B_{r}, η_{2}, (t, 0))$ .
- $w$ : $= c_{2} * 2^{ℓ} - s_{1} c_{1} - s_{0} c_{0}$ .
- $\tilde{k} : = ⌊ \frac{w}{⌊ q / 8 ⌋} ⌉$ .
- $c_{2}^{'} = c_{2} - ⌊ \tilde{k} ⌊ q / 8 ⌋ / 2^{ℓ} ⌋$ .
- $k = \tilde{k} \oplus H_{2} (c_{1}, c_{2}^{'})$ .
- $(x, μ)$ : $= {Dec}_{H_{3} (k)} (c_{3})$ .
- $ν$ : $= H_{0} (μ, b_{r}, k)$ .
- $z$ : $= z_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} z_{i}$ .
- If $∥ (h_{s}, z) x - y ∥ \leq \frac{1}{2 π^{3}} ℵ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}$ return $μ$ , otherwise return ⊥.

4.2. Correctness

In the proposed scheme, we draw lessons from [43] to use the ciphertext generated in the previous step (i.e.,

c_{0}

) as the tag to produce the subsequent ciphertext. On the one hand, it can transform a tag encryption to a normal encryption. On the other hand, when

c_{0}

is determined, the rest of the ciphertexts are relatively determined except for the influence of errors and the value to be encrypted, which is important for the security reduction (reference to Theorem 1). We give the unique witness for NTRU as follows.

Lemma 1 (Unique Witness).

Let

ϱ = 20 \log n, q = \frac{5}{π^{3}} ϱ ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

for all but a negligible fraction of

h \in R

and any syndrome

c \in R

be the number of the pair

(r, e) \in {- 1, 0, 1}^{n} \times {- ϱ, \dots, ϱ}^{n}

to satisfy that

c = r h + e

is no more than one.

Proof.

For each

c \in R

, suppose that there exist two different

(r, e) \neq (r^{'}, e^{'}) \in {- 1, 0, 1}^{n} \times {- 1, 0, 1}^{n}

satisfying

r + h e = r^{'} + h e^{'} = c

. Then,

(r - r^{'}) h = e^{'} - e \in {- 2 ϱ, \dots, 2 ϱ}^{n}

. To complete this lemma, it only needs to argue that

∥ \tilde{r} {h ∥}_{\infty} > 4 ϱ + 1

with overwhelming probability, for

\tilde{r} \in {- 2, \dots, 2}^{n}

. Let £ denote the n-dimension open

ℓ_{\infty}

cube with the radius of each dimension being

4 ϱ + 1

(edge length

8 ϱ + 2

). Then, for any fix

\tilde{r} \in {- 2, \dots, 2}^{n}

, the probability that

\tilde{r} h

falls into some cubic £ is

{(8 ϱ + 2)}^{n} / q^{n}

. According to the union bound, for all

\tilde{r} \in {- 2, \dots, 2}^{n}

, the probability of

\tilde{r} h

falling into some £ is no more than

5^{n} {(\frac{8 ϱ + 2}{q})}^{n} = {(\frac{40 ϱ + 10}{q})}^{n} < {(\frac{41 ϱ}{\frac{5}{π^{3}} ϱ ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}})}^{n} = {(\frac{41 π^{3}}{5 ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}})}^{n},

5^{n} {(\frac{8 ϱ + 2}{q})}^{n} = {(\frac{40 ϱ + 10}{q})}^{n} < {(\frac{41 ϱ}{\frac{6 \sqrt{2}}{π^{3}} ϱ ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}})}^{n} = {(\frac{41 π^{3}}{6 \sqrt{2} ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}})}^{n},

which is negligible. That is, for all but a negligible fraction of

h

∥ \tilde{r} {h ∥}_{\infty} > 4 ϱ + 1

. □

By the way, in the scheme, the converted ciphertext with each dimensional error less than

\frac{4}{\sqrt{2} π^{2}} ϱ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

, the unique witness also holds. The corresponding probability is

{(\frac{8}{\sqrt{2} π^{2}} ϱ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} / q)}^{n} 5^{n} \approx {(5 / 36)}^{n}

, which is negligible.

In order to guarantee the correctness and security of the proposed scheme, the following requirements should be satisfied.

The RLWE should be hard $α q \geq ω (\sqrt{\log n})$ (Proposition 1).
The pre-image sample algorithm works well, $η \geq ∥ \tilde{B} ∥ \cdot ζ_{ϵ}^{'} (Z)$ for $ζ_{ϵ}^{'} (Z) \approx \frac{1}{π}$ $\sqrt{\frac{1}{2} l n (2 + \frac{2}{ϵ})}$ and $ϵ = 2^{- λ / 2} / (4 \sqrt{2} n)$ [38], where $B$ is the corresponding basis of a lattice (Proposition 3).
In the security reduction, a simulated trapdoor (Algorithm 1) can be used for sampling (Proposition 3).
The correctness of the unsigncryption requires that both the error in the public key encryption and the error in the signature are small enough to guarantee security.

Therefore, the Gaussian parameter and the modulus can be set as follows.

η_{2}

: Gaussian parameter for decryption;

η_{1}

: Gaussian parameter for signature. The correctness of the proposed scheme is implied in Lemmas 11 and 16.

\begin{matrix} \begin{matrix} η_{1} = \frac{1}{2 π^{3}} ℵ n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}, η_{2} = \frac{1}{\sqrt{2} π^{2}} n {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}, ϱ = 10 {(\log n)}^{3 / 4}, \\ q = \frac{6 \sqrt{2}}{π^{3}} ϱ ℵ n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}, η_{3} = \frac{1}{\sqrt{2} π^{2}} \sqrt{n} ln (2^{(7 + λ) / 2} n) \end{matrix} \end{matrix}

(1)

5. Security and Performance

The confidentiality and unforgeability of SC-NTRU are demonstrated in Section 5.1. The efficiency of the SC-NTRU is evaluated by analyzing the numbers of different kinds of computations in Section 5.2. An experiment for SC-NTRU is presented in Section 5.3.

5.1. Security

The IND-CCA2 security of the proposed scheme is based on a variant of the search RLWE implied in [38]. We formalize it as follows.

Definition 6 (Variant of Search RLWE).

Let

ϱ, t

be small integers,

s \in R_{q}

with

{∥ s ∥}_{\infty} \leq ϱ

. Let ℓ denote a positive integer, and Ψ be a family of distributions over

K_{R}

. For

i \in [ℓ + 1]

e_{i} \leftarrow Ψ

a_{i} \leftarrow R_{q}

. The search RLWE is to find

k \in {[2^{t - 1}]}^{n}

from

c_{i} = a_{i} s + e_{i}

for

i \in [ℓ]

and

c_{ℓ + 1} = a_{ℓ + 1} s + e_{ℓ + 1} + k ⌊ q / 2^{t} ⌋

Remark 1.

The variant is as hard as the standard search LWE. Suppose there exists an adversary

A

who can find the correct

k

. Then,

A

can compute

c_{ℓ + 1}^{'} = a_{ℓ + 1} s + e_{ℓ + 1}

due to

k ⌊ q / 2^{t} ⌋

hidden by

c_{ℓ + 1}^{'}

. That is,

A

has the ability to compute

c_{ℓ + 1}^{'}

from

{c_{i}}_{i = 1}^{ℓ}

. One method is that

A

learns

r

from

{c_{i}}_{i = 1}^{ℓ}

, then

A

uses the same

r

to get

k

from

c_{ℓ + 1}

. This means that the variant of the search RLWE can be reduced to the standard search RLWE in polynomial time. The other method is that

A

can find the mapping from

{a_{i}}_{i = 1}^{ℓ}

a_{ℓ + 1}

. The mapping must have the form as

a_{ℓ + 1} = \sum_{i = 1}^{ℓ} x_{i} a_{i} + y

, where

x_{i}, y

are sampled from

R_{q}

with small coefficients. Otherwise,

a_{ℓ + 1} = \sum_{i = 1}^{ℓ} x_{i} a_{i}^{κ_{i}} + y

1 \neq κ_{i} \in Z

. When the mapping is applied to

{c_{i}}_{i = 1}^{ℓ}

, the error will increase almost to the uniform distribution, which leads to failing to obtain

k

from

c_{ℓ + 1}

. In fact, it is also a search RLWE problem to find the mapping

a_{ℓ + 1} = \sum_{i = 1}^{ℓ} x_{i} a_{i}^{κ_{i}} + y

Theorem 1 (IND-CCA2).

Under the parameter settings as in Equation (1), the proposed signcryption scheme is IND-CCA2 secure against inner adversaries in the standard model, as long as the RLWE

_{n, m, q}

problem and DSPR problem are computationally intractable.

Proof.

The theorem can be proven by a series of games G

_{0}

, G

_{1}

, ⋯, G

_{13}

. In each game, the adversary

A

’s probability of success is

P r [A_{i}]

for

i \in {0, 1, \dots, 13}

. G

_{0}

is the real IND-CCA2 security game. In G

_{0} \dots

_{10}

, the challenge ciphertexts are all hybrid encryption ciphertexts. It is proven that the successive games satisfy the indistinguishability or the game transitions based on failure events to

A

. Thus, the difference between attacking in G

_{0}

and attacking in G

_{10}

is guaranteed to be negligible. Due to the security of the symmetric encryption involved, the ciphertext of the symmetric encryption

c_{3}

does not reveal any information about the plaintext and the corresponding signature.

Only using symmetric encryption, a direct attack on the message–signature pair is no less difficult than an attack on the symmetric key. According to the unforgeability of the signature and the security of the symmetric encryption, it is proven that it is impossible to manipulate

c_{3}

to obtain a valid ciphertext to help the attack. Therefore, ignoring the ciphertext

c_{3}

in the challenge ciphertext of G

_{11}

, the transformation does not increase the hardness of the adversary’s attack. Following that, it is shown that the game transitions based on failure events are satisfied from game G

_{11}

to G

_{13}

. In G

_{13}

, the challenge ciphertext is an RLWE instance, and the probability that the adversary succeeds to obtain the information encrypted by the public key is negligible. Thus, the

A

’s success probability to attack in G

_{0}

is also negligible. This means that the proposed scheme is IND-CCA2 secure. The games are as follows.

G $_{0}$ : The game G $_{0}$ is the original IND-CCA2 game, namely, $h_{r} \leftarrow KeyGen, b_{r}, d_{r} \leftarrow Z_{q}^{n}$ .
–
Setup: Choose hash functions: $H_{0} : {0, 1}^{*} \to {0, 1}^{ℵ}$ , $H_{1} : R_{q} \to R_{q}$ , $H_{2} : R_{q} \times R_{q} \to {0, 1, 2, 3}^{*}$ , and public parameters $y, u \overset{$}{\leftarrow} R_{q}$ .
–
KeyGen: Generate the public and private keys: $(B_{s}, h_{s}) \leftarrow KeyGen (n, q)$ , $(B_{r}, h_{r})$ $\leftarrow KeyGen (n, q)$ , $b_{s}, d_{s} \overset{$}{\leftarrow} R_{q}, z_{i} \overset{$}{\leftarrow} R_{q}$ for $i = 0, 1, \dots, ℵ$ . Publish $(b_{s}, d_{s}, h_{s}, h_{r})$ as the public key and keep $B_{s}$ and $B_{r}$ as private keys.
–
Phase I: Upon receiving an unsigncryption query from $A$ , $C$ uses the private key $B_{r}$ to unsigncrypt as in the proposed scheme. If the signature satisfies the constraint $∥ (h_{s}, z) x - y ∥ \leq \frac{1}{2 π^{3}} ℵ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}$ , $C$ returns the message $μ$ , otherwise it returns ⊥.
–
Challenge: After a polynomial round of interaction with $C$ , $A$ gives a satisfied signal to $C$ . $C$ randomly chooses a message $μ$ and generates the challenge ciphertext $c^{*} = (c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3}^{*})$ according to the steps of sincryption in the proposed scheme, then gives $c^{*}$ to $A$ .
–
Phase II: If the ciphertext for unsigncryption from $A$ is $c^{*}$ , $C$ replies with ⊥ directly. Otherwise, $C$ unsigncrypts the querying ciphertext as in Phase I.
G $_{1}$ : In the game G $_{1}$ , only the producing method of $b_{r}$ is changed. Let $b_{r} = h_{r} p + e$ where $p \leftarrow {- 1, 0, 1}^{n}, e \leftarrow {- ϱ, \dots, ϱ}^{n}$ . Since $C$ has the normal private key, the unsigncryption approach is the same as in G $_{0}$ .
G $_{2}$ : Before publishing the public keys, $C$ generates a challenge ciphertext $c^{*} = (c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3}^{*})$ normally, namely $c_{0}^{*} = r h_{r} + e_{0}$ , $c_{1}^{*} = r (b_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1}$ , $c_{2}^{'}$ : $= ⌊ (r u + e_{2}) / 2^{ℓ} ⌋$ , $c_{2}^{*}$ : $= c_{2}^{'} + ⌊ ((H_{2} (c_{1}^{*}, c_{2}^{'}) \oplus k) ⌊ q / 8 ⌋) / 2^{ℓ} ⌋$ , $c_{3}^{*}$ : $= {Enc}_{H_{3} (k)} (x, μ)$ for $r \overset{$}{\leftarrow} {- 1, 0, 1}^{n}, e_{0}, e_{2} \overset{$}{\leftarrow} {- ϱ, \dots, ϱ}^{n}, e_{1} \overset{$}{\leftarrow} {([- ϱ \sqrt{n}, ϱ \sqrt{n}] ⋂ Z)}^{n}$ .
G $_{3}$ : In the game G $_{3}$ , $C$ continues changing $b_{r}$ as $b_{r} = h_{r} p + e - H_{0} (c_{0}^{*}) d_{r}$ where the method to generate $p, e$ is identical to that in G $_{2}$ .
G $_{4}$ : The game G $_{4}$ is the same as G $_{3}$ , except for the approach to produce $d_{r}$ . $C$ generates $d_{r}$ by KeyGen algorithm, $d_{r} \leftarrow KeyGen$ , instead of $d_{r} \overset{$}{\leftarrow} R_{q}$ .
G $_{5}$ : $C$ answers with ⊥ to the unsigncryption queries with the kind of ciphertext $(c_{0}^{*}, c_{1}, c_{2}, c_{3})$ in phase I. The others remain the same as in the game G $_{5}$ .
G $_{6}$ : In this game, in phase I, $C$ answers all the unsigncryption queries normally, but $C$ replies with ⊥ to the queries with ciphertext $(c_{0}, c_{1}, c_{2})$ satisfying $c_{0} \neq c_{0}^{*}$ but $H_{1} (c_{0}) = H_{1} (c_{0}^{*})$ .
G $_{7}$ : In phase II, $C$ answers with ⊥ to unsigncryption queries with the kind of ciphertext $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3})$ meeting $c_{3} \neq c_{3}^{*}$ . Except for the cases above, $C$ responds to the unsigncryption queries as in G $_{6}$ .
G $_{8}$ : In phase II, $C$ responds with ⊥ to the unsigncryption queries with the form $(c_{0}^{*}, c_{1}, c_{2}, c_{3})$ , satisfying $(c_{1}, c_{2}) \neq (c_{1}^{*}, c_{2}^{*})$ . Replying to the other unsigncryption queries keeps the same as in G $_{7}$ .
G $_{9}$ : In this game, $C$ produces $h_{r} \leftarrow Z_{q}^{n}$ instead of $h_{r} \leftarrow KeyGen$ . Moreover, $C$ will use $d_{r}$ to answer the unsigncryption queries. The others are identical to the game G $_{8}$ .
G $_{10}$ : In this game, $C$ produces the challenge ciphertext by collaborating with a signer, which for convenience will be called signature oracle $O_{s i g n}$ . First, $C$ generates $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}')$ normally as in G $_{9}$ , followed by giving $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}')$ to $O_{s i g n}$ . Then, $O_{s i g n}$ randomly chooses a message $μ$ and $k \overset{$}{\leftarrow} {0, 1, 2, 3}^{n}$ , and produces a signature $(x, k)$ for $μ$ . Next, $O_{s i g n}$ generates $c_{3}^{*} = {Enc}_{k} (μ, x)$ and gives it to $C$ . Lastly, $C$ gives $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3}^{*})$ to $A$ as the challenge ciphertext and waits to get $(μ, k, x)$ from $A$ .
G $_{11}$ : $C$ changes the challenge ciphertext a little. $C$ does not give $k$ to $O_{s i g n}$ and does not need to get $c_{3}$ from $O_{s i g n}$ . $C$ just gives the ciphertext $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*})$ generated by itself to $A$ as the challenge ciphertext. If $A$ is able to obtain the plaintext $k$ in $c_{2}^{*}$ with non-negligible probability, $C$ admits that $A$ wins the game with the same probability.
G $_{12}$ : This game is identical with the game G $_{11}$ except that the challenge ciphertext $c_{1}^{*}$ is computed as $c_{1}^{*} = c_{0}^{*} p + e_{1}$ where $e_{1} \overset{$}{\leftarrow} {([- ϱ \sqrt{n}, ϱ \sqrt{n}] ⋂ Z)}^{n}$ .
G $_{13}$ : $C$ queries the variant RLWE oracle to fetch an instance $((\begin{matrix} a_{1} \\ a_{2} \end{matrix}), (\begin{matrix} z_{1} \\ z_{2} \end{matrix}))$ Then, $C$ publishes the public keys as $h_{r} = a_{1}, u = a_{2}$ . $C$ and sets the challenge ciphertext as follows $c_{0}^{*} = z_{1}, c_{2}^{*} = z_{2}$ . The construction method for $c_{1}^{*}$ remains identical with that in G $_{12}$ , that is $c_{1}^{*} = c_{0}^{*} p + e_{1}$ .

□

Lemma 2.

The games G

_{1}

and G

_{0}

are computationally indistinguishable when

ϱ = 20 \log n

Proof.

This lemma can be proven by hybrids. First,

C

chooses

h^{'} \overset{$}{\leftarrow} R_{q}

and calculates

b_{r}^{'} = h^{'} p + e

where

p \overset{$}{\leftarrow} {- 1, 0, 1}^{n}, e \overset{$}{\leftarrow} {- ϱ, \dots, ϱ}^{n}

. The infinity norm of the error

e

is set at

20 \log n

, which satisfies the constraint for errors in RLWE, i.e., the Gaussian parameter

α q \geq ω (\sqrt{\log n})

(see Proposition 1). According to the intractability of RLWE,

b_{r}^{'}

and

b_{r} \overset{$}{\leftarrow} R_{q}

are computationally indistinguishable. Next,

C

continues modifying

b_{r}^{'}

b_{r}^{'} = h_{r} p + e

. Since

h_{r}

and

h^{'}

are statistically indistinguishable according to the uniform property of the algorithm KeyGen, the new

b_{r}^{'}

is computationally indistinguishable with

b_{r} \overset{$}{\leftarrow} R_{q}

. Given all this, the games G

_{1}

and G

_{0}

are computationally indistinguishable. □

Lemma 3.

The games G

_{2}

and G

_{1}

are identical from the view of

A

Proof.

Since the computation procedure for

(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3}^{*})

is completely hidden from

A

. In the view of

A

, it makes no difference whether or not some challenge ciphertext has been generated before the public key is published. That is, the difference between G

_{2}

and G

_{1}

is only the difference in concept. Consequently, the lemma holds. □

Lemma 4.

The game G

_{3}

is statistically indistinguishable with the game G

_{2}

Proof.

The only difference between the games G

_{3}

and G

_{2}

b_{r}

. In G

_{3}

C

calculates

b_{r} = h_{r} p + e - H_{0} (c_{0}^{*}) d_{r}

, while in G

_{2}

b_{r} = h_{r} p + e

. Since

c_{0}^{*}

is fixed and

d_{r}

submits to the uniform distribution. Therefore, the

b_{r}

is statistically indistinguishable with the

b_{r}

in the game G

_{2}

. □

Due to the uniform property of the public keys generated by the KeyGen algorithm, we have the following lemma.

Lemma 5.

The game G

_{4}

is statistically indistinguishable with the game G

_{3}

It is difficult to directly prove the statistical indistinguishability between the games G

_{5}

and G

_{4}

. However, the game sequences can be continued by the game transitions based on failure events.

Lemma 6.

Let E

_{5}

denote the event that

A

makes the unsigncryption queries with the ciphertexts

(c_{0}, c_{1}, c_{2}, c_{3})

meeting

c_{0} = c_{0}^{*}

in phase I. From the point of view of

A

, the games G

_{5}

and G

_{4}

are totally the same, when E

_{5}

does not occur. Furthermore,

P r [A_{5} | \neg E_{5}] = P r [A_{4} | \neg E_{5}]

, and

P r [E_{5}]

is negligible.

Proof.

First, in the game G

_{5}

C

may reply to all the unsigncryption queries normally except for the queried ciphertexts

(c_{0}, c_{1}, c_{2}, c_{3})

with

c_{0} = c_{0}^{*}

. Therefore, the behavior of

C

is identical in games G

_{5}

and G

_{4}

, when E

_{5}

does not happen. That is,

A

learns exactly the same knowledge form

C

, when not considering the event E

_{5}

Second, in the games G

_{5}

and G

_{4}

c_{0}^{*}

is hidden from

A

in phase I. Whether

c_{0}^{*}

is obtained by evaluating

r h_{r} + e_{0}

or by guessing, the probability that

A

computes a ciphertext with the form

(c_{0}^{*}, c_{1}, c_{2}, c_{3})

q^{- n}

. That is to say, the probability that

C

can not correctly answer the valid unsigncryption queries is no more than

q^{- n}

, which is negligible. The difference is that

C

deliberately answers the query E

_{5}

with ⊥ in G

_{5}

instead of unsigncrypting normally as in G

_{4}

. In summary, the reduction for the attack capability learned in G

_{5}

compared to that in G

_{4}

is negligible. □

Lemma 7.

Let E

_{6}

denote the events that

A

makes the unsigncryption queries with the ciphertexts

(c_{0}, c_{1}, c_{2}, c_{3})

meeting

c_{0} \neq c_{0}^{*}

but

H_{1} (c_{0}) = H_{1} (c_{0}^{*})

in phase I. The games G

_{6}

and G

_{5}

are identical in the adversary

A

’s view, when E

_{6}

does not happen,

P r [A_{6} | \neg E_{6}] = P r [A_{5} | \neg E_{6}]

. Moreover,

P r [E_{6}]

is negligible.

Proof.

First, in G

_{6}

, the approach of

C

to answer the unsigncryption queries is totally identical when the queried ciphertexts

(c_{0}, c_{1}, c_{2}, c_{3})

satisfy

c_{0} \neq c_{0}^{*}

and

H_{1} (c_{0}) = H_{1} (c_{0}^{*})

. Therefore, the knowledge learned from G

_{6}

and G

_{5}

is the same, when not considering the event E

_{6}

Second, for a known

c_{0}^{*}

A

finds a

c_{0}

satisfying

c_{0} \neq c_{0}^{*}

but

H_{0} (c_{0}) = H_{0} (c_{0}^{*})

, which means

A

discovers a hash collision. We set the hash function to satisfy the security intensity of the proposed signcryption system, namely, the probability that hash collision occurs is no more than a negligible probability

2^{- λ}

. In fact,

c_{0}^{*}

is hidden in phase I, then the probability that

A

just computes a ciphertext with

c_{0} \neq c_{0}^{*}

and

H_{0} (c_{0}) = H_{0} (c_{0}^{*})

is also no more than the above probability

2^{- λ}

. Thus, even though the attack power of

A

obtained in G

_{6}

is less than that in G

_{5}

, the difference is negligible. □

Lemma 8.

Let E

_{7}

denote the events that

A

set the unsigncryption queries with the type of ciphertext

(c_{0}^{*}, c_{1}^{*}, c_{2}^{*}, c_{3})

meeting

c_{3} \neq c_{3}^{*}

in phase II. In the adversary

A

’s view, the games G

_{7}

and G

_{6}

are identical, when E

_{7}

does not happen. Namely,

P r [A_{7} | \neg E_{7}] = P r [A_{6} | \neg E_{7}]

. Furthermore,

P r [E_{7}]

is negligible.

Proof.

The ciphertext elements

(c_{0}, c_{1}, c_{2})

constitute the ciphertext of the public key encryption. Once the elements are determined, the plaintext

k

involved in the public key encryption is determined and unique. That is, the key used for the symmetric encryption is fixed. According to the one-to-one property of the symmetric encryption ENC, modifying

c_{3}

will yield a distinct message–signature pair

(x^{'}, μ^{'}) = {Dec}_{k} (c_{3})

(relative to

(x, μ)

). The probability of the new message–signature pair successfully passing the signature verification is negligible. We prove this conclusion through a classification discussion. It can be divided into two cases.

Case 1: $A$ generates the ciphertext $c_{3}$ by its signature for some message $μ$ . As an inner adversary, $A$ has the ability to yield signatures by itself. However, the procedure to generate $c_{3}$ requires $k^{*}$ . The probability of obtaining $k^{*}$ from $(c_{0}^{*}, c_{1}^{*}, c_{2}^{*})$ is negligible due to the security of the public key encryption part. Please refer to Lemma 15 for more details.
Case 2: $A$ generates the ciphertext $c_{3}$ randomly. According to the one-to-one property of the symmetric encryption, a random message–signature pair $(μ, x)$ is unsigncrypted from $c_{3}$ . Since $A$ does not possess knowledge of $μ$ , it cannot generate a valid signature for it despite having the private key for signature generation. Consequently, the probability $(μ, k, x)$ passing signature verification is negligible.

□

Lemma 9.

Let E

_{8}

denote the event that in phase II,

A

makes the unsigncryption queries with the form of the ciphertext as

(c_{0}^{*}, c_{1}, c_{2}, c_{3})

and

(c_{1}, c_{2}) \neq (c_{1}^{*}, c_{2}^{*})

. In the adversary

A

’s view, the games G

_{8}

and G

_{7}

are identical, when

E_{8}

does not occur. Namely,

P r [A_{8} | \neg E_{8}] = P r [A_{7} | \neg E_{8}]

. Moreover,

P r [E_{8}]

is negligible.

Proof.

This lemma can be argued by a classification discussion. Let

k, k^{*}

be the keys concealed in

c_{2}

c_{2}^{*}

, respectively.

Case 1: $k^{*}$ remains unchanged, i.e., $k = k^{*}$ . To guarantee the validity of the ciphertext, the information hidden by $c_{2}$ should be $⌊ (H (c_{1}, c_{2}^{'}) \oplus k^{*}) ⌊ q / 8 ⌋ / 2^{ℓ} ⌋$ . To fulfill this requirement, there are only two possible subcases.
–
$A$ generates $c_{2}$ through encryption. On one hand, $A$ does not know the $k^{*}$ concealed in $c_{2}^{*}$ . On the other hand, $A$ chooses a $r$ distinct from the secret $r$ used in the $c_{0}^{*}$ , which will lead to an invalid public key ciphertext. Thus, the probability of this subcase occurring is negligible.
–
$A$ produces $c_{2}$ by falsifying $c_{2}^{*}$ . For this, $A$ should have the ability to compute $c_{2} - c_{2}^{*} + ⌊ ((H (c_{1}, c_{2}^{'}) \oplus k^{*}) - (H (c_{1}^{*}, c_{2}^{*}') \oplus k^{*})) ⌊ q / 8 ⌋ / 2^{ℓ} ⌋$ . The probability of this event is negligible since $c_{2}^{*}'$ and $k$ involved in $c_{2}^{*}$ are hidden from $A$ .
Case 2: $k \neq k^{*}$ and $c_{3}$ remains unchanged. In this case, due to the one-to-one property of the symmetric encryption, the message–signature pair $(μ, k, x)$ extracted from $c_{3}$ is completely random. As a result, the probability of $(μ, k, x)$ passing signature verification is negligible.
Case 3: $k \neq k^{*}$ and $c_{3} \neq c_{3}^{*}$ . The case can be divided into two subcases.
–
In the procedure to generate $c_{3}$ , the plaintext $μ$ corresponding to it is not known to $A$ . Consequently, the probability $(c_{1}^{*}, c_{2}, c_{3})$ being a valid ciphertext is negligible. The argument is the same as that of case 2 in the proof of Lemma 8.
–
The ciphertext $c_{3}$ is generated based on a valid message–signature pair produced by $A$ . It can be further divided into two subcases. (1) $c_{2}$ is obtained though encrypting by $A$ . The argument to this subcase is identical to subcase 1 of case 1 in this Lemma 9. Due to the uniqueness of LWE (see Lemma 1), $r$ has already been determined by $c_{0}^{*}$ . The probability of $A$ choosing $r$ used in $c_{0}^{*}$ is negligible. The the distinct $r$ yields an invalid ciphertext. (2) $c_{2}$ is falsified from $c_{2}^{*}$ by $A$ . This is similar to the demonstration in subcase 2 of case 1 of Lemma 9. $A$ needs to compute $c_{2} - c_{2}^{*} + ⌊ ((H (c_{1}, c_{2}^{'}) \oplus k) - (H (c_{1}^{*}, c_{2}^{*}') \oplus k^{*})) ⌊ q / 8 ⌋ / 2^{ℓ} ⌋$ without knowing $k^{*}$ , and the probability of this event is negligible.

□

Algorithm 1 SimExtractE

(h_{r}, b_{r}, d_{r}, τ, τ^{*}, u)

Require:

: public keys $h_{r}, b_{r}, d_{r} \in R_{q}$ , in which $d_{r} \leftarrow KeyGen$ , $b_{r} = h_{r} p + e$ for $p, e \leftarrow {- ϱ, \dots, ϱ}^{n}$ ;
: a pair of un-equivalent tags $τ, τ^{*} \leftarrow {- ϱ, \dots, ϱ}^{n}$ ;
: a syndrome $u \in R_{q}$ .

Ensure:
A private key

(x_{1}, x_{2})

1:: $x_{0}^{'} \leftarrow {- 1, 0, 1}^{n}$
2:: $x^{'} = (u - h_{r} x_{0}^{'}) / (τ - τ^{*})$
3:: $(x_{1}^{'}, x_{1}) = (x^{'}, 0) - SamplePre (B_{d}, η_{2}, (x^{'}, 0))$ ( $η_{2} = \frac{1}{\sqrt{2} π^{2}} n {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}$ )
4:: $x_{0} = x_{0}^{'} - p x_{1}$
5:: output $(x_{0}, x_{1})$ as the private key.

Lemma 10.

Under the parameter settings as in Equation (1), the

(x_{0}, x_{1})

generated in Algorithm 1 is a valid private key. That is,

∥ u - [h_{r} ∥ b_{r} + τ d_{r}] (x_{0}, x_{1}) ∥ \leq \frac{3}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

and

∥ (x_{0}, x_{1}) ∥ \leq \frac{1}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

. It ensures that this private key can be used correctly in unsigncryption.

Proof.

First, we argue that the multiplication of

[h_{r} ∥ b_{r} + τ d_{r}]

and

(x_{0}, x_{1})

is close enough to

u

\begin{matrix} \begin{matrix} [h_{r} ∥ b_{r} + τ d_{r}] (x_{0}, x_{1}) & = h_{r} x_{0} + (h_{r} p + e - τ^{*} d_{r} + τ d_{r}) x_{1} \\ = h_{r} (x_{0} + p x_{1}) + e x_{1} + (τ - τ^{*}) d_{r} x_{1} \\ = h_{r} x_{0}^{'} + e x_{1} + (τ - τ^{*}) (x^{'} - x_{1}^{'}) \\ = h_{r} x_{0}^{'} + e x_{1} + (u - h_{r} x_{0}^{'}) - (τ - τ^{*}) x_{1}^{'} \\ = u + e x_{1} - (τ - τ^{*}) x_{1}^{'} \end{matrix} \end{matrix}

(2)

\begin{matrix} \begin{matrix} ∥ u - [h_{r} ∥ b_{r} + τ d_{r}] (x_{0}, x_{1}) ∥ = & ∥ (τ - τ^{*}) x_{1}^{'} - e x_{1} ∥ \leq ∥ e x_{1} ∥ + ∥ (τ - τ^{*}) x_{1}^{'} ∥ \\ \leq & {∥ e ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} + ∥ Ø - Ø^{*} ∥_{\infty} ∥ x_{1}^{'} ∥ \sqrt{n} \sqrt{n} \\ = & ϱ η_{2} \sqrt{n} n + 2 η_{2} \sqrt{n} n \leq (ϱ + 2) \frac{1}{\sqrt{2} π^{2}} n {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n^{3 / 2} \\ = & \frac{1}{\sqrt{2} π^{2}} (ϱ + 2) n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} . \end{matrix} \end{matrix}

(3)

Second, we demonstrate that

(x_{0}, x_{1})

is short.

\begin{matrix} \begin{matrix} ∥ (x_{0}, x_{1}) ∥ = & \sqrt{∥ x_{0} ∥^{2} + {∥ x_{1} ∥}^{2}} \leq \sqrt{∥ x_{0}^{'} ∥^{2} + ∥ p x_{1} ∥^{2} + {∥ x_{1} ∥}^{2}} \\ \approx & ∥ p x_{1} {∥ \leq ∥ p ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \approx ϱ η_{2} \sqrt{n} n \\ \leq & \frac{1}{\sqrt{2} π^{2}} n ϱ {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n^{3 / 2} \\ = & \frac{1}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} \end{matrix} \end{matrix}

(4)

Here,

x_{0}

takes up most of the length of the whole vector

[x_{0}, x_{1}]

. That is,

\begin{matrix} \begin{matrix} ∥ x_{0} ∥ \leq \frac{1}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}, ∥ x_{1} ∥ \leq \frac{1}{\sqrt{2} π^{2}} n^{3 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} . \end{matrix} \end{matrix}

(5)

From the above, the private key and the error are of the same magnitude, differing only by a constant factor. In fact, we can use Lemma 3 of [43] to reduce the length of the private key and the error by the factor

\sqrt{n}

, so that the modulus q can also be reduced by

\sqrt{n}

. □

Lemma 11.

In the adversary

A

’s view, the games G

_{9}

and G

_{8}

are totally identical. Furthermore,

P r [F_{9}] = P r [F_{8}]

Proof.

First, the public keys in the games G

_{9}

and G

_{8}

are identical. Second,

C

does not reply to the unsigncryption queries for the ciphertexts with

c_{0} \neq c_{0}^{*}

in the games G

_{9}

and G

_{8}

. Third, we argue that

C

can correctly unsigncrypt with the private key produced in Algorithm 1, when

c_{0} \neq c_{0}^{*}

. Let

\tilde{c_{2}} = r u + e_{2} + (H_{2} (c_{1}, c_{2}^{'}) \oplus k) ⌊ q / 8 ⌋

\begin{matrix} \begin{matrix} 2^{ℓ} c_{2} - [c_{0} ∥ c_{1}] (x_{0}, x_{1}) & = 2^{ℓ} c_{2} - \tilde{c_{2}} + \tilde{c_{2}} - [c_{0} ∥ c_{1}] (x_{0}, x_{1}) \\ = 1 - 2^{ℓ} + r u + e_{2} + k ⌊ q / 8 ⌋ - [(r h_{r} + e_{0}) ∥ (r (b_{r} + H_{1} (c_{0}) d_{r}) + e_{1})] (x_{0}, x_{1}) \\ \approx k ⌊ q / 8 ⌋ + r [u - [h_{r} ∥ (b_{r} + H_{1} (c_{0}) d_{r})] (x_{0}, x_{1})] + e_{2} - e_{0} x_{0} - e_{1} x_{1} \end{matrix} \end{matrix}

(6)

Let

e^{'} = u - [h_{r} ∥ (b_{r} + H_{1} (c_{0}) d_{r})] (x_{0}, x_{1})

. According to Lemma 10,

∥ e^{'} ∥ \leq \frac{1}{\sqrt{2} π^{2}} (ϱ^{2} + 3 ϱ) n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

. Then,

\begin{matrix} \begin{matrix} ∥ r [u - [h_{r} ∥ (b_{r} + H_{1} (c_{0}) d_{r})] (x_{0}, x_{1})] + e_{2} - e_{0} x_{0} - e_{1} x_{1} ∥_{\infty} = {∥ r e^{'} + e_{2} - e_{0} x_{0} - e_{1} x_{1} ∥}_{\infty} \\ \leq & ∥ r e^{'} ∥_{\infty} + ∥ e_{2} ∥_{\infty} + ∥ e_{0} x_{0} ∥_{\infty} + ∥ e_{1} x_{1} ∥_{\infty} \leq {∥ r ∥}_{\infty} ∥ e^{'} ∥ \sqrt{n} + ∥ e_{2} ∥_{\infty} + ∥ e_{0} ∥_{\infty} ∥ x_{0} ∥ \sqrt{n} + ∥ e_{1} ∥_{\infty} ∥ x_{1} ∥ \sqrt{n} \\ \leq & ∥ e^{'} ∥ \sqrt{n} + ∥ e_{2} ∥_{\infty} + ∥ e_{0} ∥_{\infty} ∥ x_{0}^{'} ∥ \sqrt{n} + ∥ e_{0} ∥_{\infty} {∥ p ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \sqrt{n} + ∥ e_{1} ∥_{\infty} ∥ x_{1} ∥ \sqrt{n} \\ \leq & \frac{3}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} \sqrt{n} + ϱ + ϱ \sqrt{n} \sqrt{n} + ϱ^{2} \frac{1}{\sqrt{2} π^{2}} n {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n^{1 / 2} n^{3 / 2} \\ + ϱ \sqrt{n} \frac{1}{\sqrt{2} π^{2}} n ln {(2^{(7 + λ) / 2} n)}^{3 / 2} n^{1 / 2} n^{1 / 2} \\ \approx & \frac{1}{\sqrt{2} π^{2}} (ϱ^{2} + 3 ϱ) n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} \end{matrix} \end{matrix}

(7)

Since

\frac{1}{\sqrt{2} π^{2}} (ϱ^{2} + 3 ϱ) n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} < \frac{1}{9} q

, the simulated private key can be used to correctly decrypt the public-key ciphertext. In summary, the games G

_{9}

and G

_{8}

are identical in

A

’s view. Therefore,

A

has the same ability to attack the proposed schemes in G

_{9}

and G

_{8}

. □

Lemma 12.

In the adversary

A

’s view, the games G

_{10}

and G

_{9}

are identical. It is reasonable that

C

needs

A

to return

(μ, k, x)

. Moreover,

P r [F_{10}] = P r [F_{9}]

Proof.

In the games G

_{10}

and G

_{9}

, the difference is that

μ

is chosen by

O_{s i g n}

, and the signature

(k, x)

and the ciphertext

c_{3}^{*}

are also generated by

O_{s i g n}

in G

_{10}

, while they are all generated by

C

in G

_{9}

. However, the public keys and private keys for the signature are identical, and the procedure for generating

(μ, k, x)

is executed strictly according to the signcryption algorithm. Therefore, the distribution of the challenge ciphertexts and the signatures involved in them are also identical in both games. In a word, the difference between the two games is only conceptual, and

A

’s view in the games G

_{10}

and G

_{9}

are completely the same. Therefore, what

A

can learn in the two games is identical.

Next, we demonstrate by contradiction that it is reasonable to require

A

to return

(μ, k, x)

in G

_{10}

. Suppose that

A

does not know the information of

k

, but it can recover

(μ, x)

. That is,

A

computes the correct

μ

without knowing

(c_{0}^{*}, c_{1}^{*}, c_{2}^{*})

. Due to

(μ, x) = D E C_{K} (c_{3})

A

obtaining

(μ, x)

from

c_{3}

without

k

is contradictory to the security of the symmetric encryption. That is,

A

knows

k

with the same probability to recover

(μ, x)

. Therefore, it is equivalent to computing

(μ, x)

and computing

(μ, k, x)

from the challenge ciphertext. Thus,

C

requiring

A

to return

(μ, k, x)

does not increase the hardness to attack the scheme. □

Lemma 13.

The modification to the game is rational, and the hardness of winning the game G

_{11}

is the same as that of winning G

_{10}

, in

A

’s view. Furthermore,

P r [F_{11}] = P r [F_{10}]

Proof.

First, as proven in Lemma 12, if

A

can guess the

k

encrypted in

c_{2}

, then it can compute the corresponding message and signature when given

c_{3}

. From this perspective, the crux of cracking the proposed scheme lies in obtaining

k

Second,

c_{3}

does not provide any assistance in obtaining

k

. Firstly, it is impossible to directly obtain

k

from

c_{3}

. Since the symmetric encryption used in this scheme is IND-OT secure and one-to-one,

c_{3}

does not leak any information of

H_{3} (k)

A

. Therefore,

c_{3}

does not disclose any information of

k

. Secondly, as proven in Lemma 8, the probability of obtaining assistance in computing

k

by changing

c_{3}

is negligible.

Third, in the absence of

c_{3}

, it will not increase the probability of obtaining

k

by falsifying

(c_{0}^{*}, c_{1}^{*}, c_{2}^{*})

. Although the message and signature (

μ, x

) concealed in

c_{3}

can help to verify the correctness of

k

, the information of

k

can not also be changed without

c_{3}

. As proven in Lemma 7, the probability that

A

gets assistance to obtain

k

by changing

c_{0}^{*}

is negligible. The probability of

A

receiving assistance to obtain

k

by changing

(c_{1}^{*}, c_{2}^{*})

is also negligible, as proven in Lemma 9.

In conclusion, the hardness of winning the games G

_{11}

and G

_{10}

is identical whether

c_{3}

is known or not. □

Lemma 14.

A

’s view, the games G

_{12}

and G

_{11}

are statistically indistinguishable. Furthermore,

P r [F_{12} | \neg E_{12}] = P r [F_{11} | \neg E_{11}]

and

P r [E_{12}] = P r [E_{11}]

is negligible.

Proof.

In the game G

_{11}

c_{1}^{*} = r (b_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1} = r (h_{r} p + e - H_{1} (c_{0}^{*}) d_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1} = r h_{r} p + r e + e_{1} = c_{0}^{*} p - e_{0} p + r e + e_{1}

\begin{matrix} \begin{matrix} c_{1}^{*} & = r (b_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1} = r (h_{r} p + e - H_{1} (c_{0}^{*}) d_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1} \\ = r h_{r} p + r e + e_{1} = c_{0}^{*} p - e_{0} p + r e + e_{1} \end{matrix} \end{matrix}

Let

\tilde{c_{1}^{*}}

denote the ciphertext

c_{1}^{*}

in the game G

_{12}

. Then,

\tilde{c_{1}^{*}} = c_{0}^{*} p + e_{1} = c_{1}^{*} + e_{0} p - r e

, where

c_{1}^{*}

is the corresponding ciphertext in G

_{11}

. We need to argue that

(c_{0}^{*}, \tilde{c_{1}^{*}}, c_{2}^{*})

is also a valid ciphertext. That is,

(c_{0}^{*}, \tilde{c_{1}^{*}}, c_{2}^{*})

can be decrypted correctly with the valid private key. Suppose that

(s_{0}, s_{1})

is a valid private key for the ciphertext, i.e.,

(s_{0}, s_{1})

is short enough. It might be good to set the key

(s_{0}, s_{1})

to an equal element size to that of the simulated key. The simulated key can decrypt well, although in the two kinds of known keys, the element size of the simulated key is a little larger than that of the real key. That is,

∥ s_{0} ∥ \leq \frac{1}{\sqrt{2} π^{2}} ϱ n^{5 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

∥ s_{1} ∥ \leq \frac{1}{\sqrt{2} π^{2}} ϱ n^{3 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

\begin{matrix} \begin{matrix} ∥ c_{2}^{*} - (c_{0}^{*} ∥ \tilde{c_{1}^{*}}) (s_{0} ∥ s_{1}) ∥_{\infty} = & ∥ c_{2}^{*} - (c_{0}^{*} ∥ c_{1}^{*}) (s_{0} ∥ s_{1}) - (\tilde{c_{1}^{*}} - c_{1}^{*}) s_{1} ∥_{\infty} \\ \leq & ∥ c_{2}^{*} - (c_{0}^{*} ∥ c_{1}^{*}) (s_{0} ∥ s_{1}) ∥_{\infty} + {∥ (\tilde{c_{1}^{*}} - c_{1}^{*}) s_{1} ∥}_{\infty} . \end{matrix} \end{matrix}

(8)

\begin{matrix} \begin{matrix} ∥ c_{2}^{*} - (c_{0}^{*} ∥ \tilde{c_{1}^{*}}) (s_{0} ∥ s_{1}) ∥_{\infty} & = ∥ c_{2}^{*} - (c_{0}^{*} ∥ c_{1}^{*}) (s_{0} ∥ s_{1}) - (\tilde{c_{1}^{*}} - c_{1}^{*}) s_{1} ∥_{\infty} \\ \leq ∥ c_{2}^{*} - (c_{0}^{*} ∥ c_{1}^{*}) (s_{0} ∥ s_{1}) ∥_{\infty} + {∥ (\tilde{c_{1}^{*}} - c_{1}^{*}) s_{1} ∥}_{\infty} \end{matrix} \end{matrix}

(9)

∥ c_{2}^{*} - (c_{0}^{*} ∥ c_{1}^{*}) (s_{0} ∥ s_{1}) ∥_{\infty} \leq \frac{1}{\sqrt{2} π^{2}} (ϱ^{2} + 3 ϱ) n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

\begin{matrix} \begin{matrix} ∥ (\tilde{c_{1}^{*}} - c_{1}^{*}) s_{1} ∥_{\infty} & = ∥ (e_{0} p - r e) s_{1} ∥_{\infty} \leq ∥ e_{0} p s_{1} ∥_{\infty} + ∥ r e s_{1} ∥_{\infty} \leq ∥ e_{0} ∥_{\infty} ∥ p s_{1} ∥ \sqrt{n} + {∥ r ∥}_{\infty} {∥ e s_{1} ∥}_{\infty} \\ \leq {ϱ ∥ p ∥}_{\infty} ∥ s_{1} ∥ n^{3 / 2} + {∥ e ∥}_{\infty} ∥ s_{1} ∥ n^{3 / 2} \leq (ϱ^{2} + ϱ) \frac{1}{\sqrt{2} π^{2}} n {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} \sqrt{n} n^{3 / 2} \\ \leq \frac{1}{\sqrt{2} π^{2}} (ϱ^{2} + ϱ) {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n^{3} \end{matrix} \end{matrix}

(10)

Therefore,

∥ c_{2}^{*} - (c_{0}^{*} ∥ \tilde{c_{1}^{*}}) (s_{0} ∥ s_{1}) ∥_{\infty} \leq \frac{1}{\sqrt{2} π^{2}} (2 ϱ^{2} + 4 ϱ) {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n^{3} < ⌊ q / 16 ⌋

. Thus, the challenge ciphertext is also a valid one. That is, if

A

can obtain the correct

k

from

(c_{0}^{*}, c_{1}^{*}, c_{2}^{*})

, then it can also obtain the same

k

from

(c_{0}^{*}, \tilde{c_{1}^{*}}, c_{2}^{*})

. □

Lemma 15.

A

’s view, the games G

_{13}

and G

_{12}

are computationally indistinguishable. Furthermore,

P r [F_{13} | \neg E_{13}] = P r [F_{12} | \neg E_{12}]

, and

P r [E_{13}] = P r [E_{12}]

is negligible.

Proof.

Reduction from LWE. When the LWE oracle is

O = O_{s}

, namely the pseudorandom case, the challenge ciphertext has the same distribution as in the game G

_{12}

. First, the public keys used directly to encrypt the challenge ciphertext are

(h_{r}, b_{r} + H_{1} (c_{0}^{*}) d_{r}, u) = (a_{1}, a_{1} p + e - H_{1} (c_{0}^{*}) d_{r} + H_{1} (c_{0}^{*}) d_{r}, a_{2}) = (a_{1}, a_{1} p + e, a_{2})

. Second, the challenge ciphertext is

c_{0}^{*} = z_{0} = r a_{1} + e_{0}

for some

r, e_{0} \leftarrow {- 1, 0, 1}^{n}

, according to the definition of LWE. Due to

z_{2} = r a_{2} + e_{2}

c_{2}^{*} = z_{2} + k ⌊ q / 2 ⌋ = r a_{2} + e_{2} + k ⌊ q / 2 ⌋

. The

c_{1}^{*}

is as follows.

c_{1}^{*} = c_{0}^{*} p + \tilde{e} = (r a_{1} + e_{0}) p + (r e - e_{0} p + e_{1}) = r (a_{1} r + e) + e_{1} = r (b_{r} + H_{1} (c_{0}^{*}) d_{r}) + e_{1} .

Obviously, the challenge ciphertext

c^{*}

is exactly the challenge ciphertext in game G

_{12}

. In this case,

A

’s advantage to distinguish the two games is zero.

When the LWE oracle is the real random case

O = O_{$}

, the challenge ciphertext is uniformly distributed. In the challenge ciphertext,

c_{0}^{*} = z_{0}

obeys the uniform distribution. Due to

z_{1} \overset{$}{\leftarrow} Z_{q}^{n}

c_{2}^{*} = z_{1} + k ⌊ q / 2 ⌋

is distributed uniformly. On the other hand, the generation method for

c_{1}^{*}

stays the same as in game G

_{12}

c_{1}^{*} = (z_{1} p + e_{1}) - e_{0} p + r e

(z_{1} p + e_{1})

is computationally indistinguishable from the uniform distribution over

Z_{q}^{n}

, and

- e_{0} p + r e

is restricted to a small range. Therefore,

c_{1}^{*}

is computationally indistinguishable from the uniform distribution over

Z_{q}^{n}

. That is to say, in terms of distinguishing the games G

_{12}

and G

_{11}

c_{1}^{*}

is no more effective than

(c_{0}^{*}, c_{2}^{*})

C

uses the guess from

A

as the answer for the LWE oracle. Therefore, the advantage of

A

in distinguishing the two games is an adversary’s advantage in attacking RLWE, which is negligible. □

In Theorem 2, the unforgeability of SC-NTRU will be proven by the interaction between the challenger

C

and an adversary

A

. To complete Theorem 2, some necessary conclusions are demonstrated in Lemmas 16 to 18.

Lemma 16.

In the query phase, the simulated signature generated by the simulated trapdoor in Algorithm 2 is indistinguishable from the real signature, and it can pass the signature verification.

Proof.

To argue that the signature generated by the simulated trapdoor in Algorithm 2 and that by the real trapdoor are identical, it is sufficient to demonstrate that the simulated trapdoor is short and has the same structure property as that of the real trapdoor. For the size property, we argue that the simulated trapdoor is short enough that it can use the same Gaussian parameter to sample as that used in the sample with the real trapdoor. For the structure property, we show that the size of the deviation and the length of the simulated trapdoor are the same, which is also the inherent character of the real trapdoor.

In Algorithm 2, for the case of

r = 0

\begin{matrix} \begin{matrix} [h_{s} ∥ f] (x_{0}, x_{1}) & = [h_{s} ∥ h_{s} p + e + p h_{f}] (x_{0}^{'} - p x_{1}, x_{1}) = h_{s} (x_{0}^{'} - p x_{1}) + (h_{s} p + e + p h_{f}) x_{1} \\ = p (h_{s} x_{0}^{'} / p + h_{f} x_{1}) + e x_{1} = e x_{1} - p x_{1}^{'} \\ ∥ e x_{1} - p x_{1}^{'} ∥ & \leq p ∥ x_{1}^{'} ∥ + ∥ e x_{1} ∥ \leq p ∥ x_{1}^{'} {∥ + ∥ e ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \leq p η_{3}^{'} \sqrt{n} + ϱ (ℵ + 1) η_{3}^{'} \sqrt{n} \sqrt{n} \sqrt{n} \\ = η_{3}^{'} \sqrt{n} (p + ϱ (ℵ + 1) n) = η_{3}^{'} \sqrt{n} (ℵ + 1) (ξ + ϱ n) \approx ϱ (ℵ + 1) \frac{1}{\sqrt{2} π^{2}} \sqrt{n} ln (2^{(7 + λ) / 2} n) n^{3 / 2} \\ = \frac{1}{\sqrt{2} π^{2}} ϱ (ℵ + 1) n^{2} ln (2^{(7 + λ) / 2} n) \\ ∥ (x_{0}, x_{1}) ∥ & = ∥ (x_{0}^{'} - p x_{1}, x_{1}) ∥ = \sqrt{∥ x_{0}^{'} - p x_{1} ∥^{2} + {∥ x_{1} ∥}^{2}} \leq \sqrt{∥ x_{0}^{'} ∥^{2} + ∥ p x_{1} ∥^{2} + {∥ x_{1} ∥}^{2}} \\ \approx ∥ p x_{1} {∥ \leq ∥ p ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \leq (ℵ + 1) η_{3} n^{3 / 2} = \frac{1}{\sqrt{2} π^{2}} (ℵ + 1) n^{2} ln (2^{(7 + λ) / 2} n) \end{matrix} \end{matrix}

(11)

In the case of

r = 1

\begin{matrix} \begin{matrix} [h_{s} ∥ f] (x_{0}, x_{1}) & = [h_{s} ∥ h_{s} p + e + p h_{f}] (- p x_{1}, x_{1}) = h_{s} (- p x_{1}) + (h_{s} p + e + p h_{f}) x_{1} \\ = p (x_{1}^{'} + h_{f} x_{1}) + e x_{1} - p x_{1}^{'} = e x_{1} - p x_{1}^{'} \\ ∥ e x_{1} - p x_{1}^{'} ∥ & \leq p ∥ x_{1}^{'} ∥ + ∥ e x_{1} ∥ \leq p ∥ x_{1}^{'} {∥ + ∥ e ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \leq p η_{0} \sqrt{n} + ϱ (ℵ + 1) η_{0} \sqrt{n} n \\ = η_{0} \sqrt{n} ((ℵ + 1) ξ + ϱ (ℵ + 1) n) \approx \frac{1}{\sqrt{2} π} ϱ (ℵ + 1) n^{3 / 2} \sqrt{ln (2^{(7 + λ) / 2} n)} \\ ∥ (x_{0}, x_{1}) ∥ & = ∥ (- p x_{1}, x_{1}) ∥ \leq \sqrt{∥ p x_{1} ∥^{2} + {∥ x_{1} ∥}^{2}} \approx {∥ p ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} = (ℵ + 1) η_{0} \sqrt{n} n \\ \approx \frac{1}{\sqrt{2} π} (ℵ + 1) n^{3 / 2} \sqrt{ln (2^{(7 + λ) / 2} n)} \end{matrix} \end{matrix}

(12)

When using the simulated trapdoor to sign, the Gaussian parameter to sample is

\frac{1}{\sqrt{2} π^{2}} (ℵ + 1) n^{2} ln (2^{(7 + λ) / 2} n) \frac{1}{\sqrt{2} π} \sqrt{ln (2^{(7 + λ) / 2} n)} = \frac{1}{2 π^{3}} (ℵ + 1) n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

For simplicity, it can be set as

\frac{1}{2 π^{3}} (ℵ + 1) n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

. The Gaussian parameter for the real trapdoor to sign is also this value, according to Equation (1). It is easy to see that the size and structure property of the simulated trapdoor are the same as those of the real trapdoor, respectively. □

Lemma 17.

Under the parameter settings in Equation (1), the vector

x_{0} + p x_{1}

constructed by

C

in the forgery phase of Theorem 2 derives a valid solution for the search RLWE instance

(h_{s}, y)

Proof.

Since the

x

output by

A

is a valid forgery,

x

obeys

D_{Z^{n}, 0, η}

with

η = \frac{1}{2 π^{3}} (ℵ + 1) n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

and

∥ y - (h_{s}, f) {x ∥}_{\infty} \leq \frac{1}{2 π^{3}} (ℵ + 1) ς n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

for some constant

ς > 1

. Then, it has

\begin{matrix} \begin{matrix} ∥ y - h_{s} (x_{0} + p x_{1}) ∥_{\infty} = ∥ y - [h_{s} | | h_{s} p] (x_{0}, x_{1}) ∥_{\infty} = ∥ y - [h_{s} | | h_{s} p + e {] (x_{0}, x_{1}) + e x_{1} ∥}_{\infty} \\ \leq & ∥ y - [h_{s} | | h_{s} p + e] (x_{0}, x_{1}) ∥_{\infty} + ∥ e x_{1} ∥_{\infty} \leq \frac{1}{2 π^{3}} (ℵ + 1) ς n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} + {∥ e ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \\ \leq & \frac{1}{2 π^{3}} (ℵ + 1) ς n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} + ϱ \frac{1}{2 π^{3}} {(ℵ + 1)}^{2} n^{2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} n \\ \approx & \frac{1}{2 π^{3}} ϱ {(ℵ + 1)}^{2} n^{3} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} \end{matrix} \end{matrix}

(13)

Similarly,

∥ y - h_{s} (x_{0} + p x_{1}) ∥ \leq \frac{1}{2 π^{3}} ϱ {(ℵ + 1)}^{2} n^{7 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}

Furthermore, the size of the vector

x_{0} + p x_{1}

may be evaluated in the same approach.

\begin{matrix} \begin{matrix} ∥ x_{0} + p x_{1} ∥ \leq & ∥ x_{0} ∥ + ∥ p x_{1} ∥ \leq ∥ x_{0} {∥ + ∥ p ∥}_{\infty} ∥ x_{1} ∥ \sqrt{n} \sqrt{n} \\ \leq & \frac{1}{2 π^{3}} {(ℵ + 1)}^{2} n^{7 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2} . \end{matrix} \end{matrix}

(14)

Therefore,

y - h_{s} (x_{0} + p x_{1})

and

x_{0} + p x_{1}

is short enough, and they form a solution for the RLWE instance

(h_{s}, y)

under the parameter settings in Equation (1). □

Lemma 18.

For the query times

0 < Q < \sqrt{\frac{2}{3} π ℵ ξ (ξ + 1)}

, the upper bound ξ of

p_{i}

for i from 1 to ℵ. Both the signature queries and forgery in the simulation can be completed without aborts, with probability

\begin{matrix} \begin{matrix} \frac{\sqrt{3}}{π \sqrt{2 ℵ ξ (ξ + 1)}} (1 - \frac{\sqrt{3} Q}{π \sqrt{2 ℵ ξ (ξ + 1)}}) \leq P r [c o m p l e t e] \leq \frac{\sqrt{3}}{π \sqrt{2 ℵ ξ (ξ + 1)}}, \end{matrix} \end{matrix}

(15)

no matter what strategy

A

takes. In particular, when

Q < \frac{\sqrt{3} π^{4} q}{20 n^{2} ℵ^{1 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}}

, the sucessful probability satisfies

\frac{\sqrt{3}}{π \sqrt{20 ℵ ξ (ξ + 1)}} < P r [c o m p l e t e] < \frac{\sqrt{3}}{π \sqrt{2 ℵ ξ (ξ + 1)}}

Proof.

First, we evaluate the probability

P r [1 + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i} = 0 | ν_{i} \overset{$}{\leftarrow} {0, 1}, p_{i} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}]

since

{(- 1)}^{ν_{i}} p_{i}

submits the uniform distribution over

{- ξ, - ξ + 1, \dots, ξ}

P r [{(- 1)}^{ν_{i}} p_{i}

t | ν_{i} \overset{$}{\leftarrow} {0, 1}, p_{i} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}

t \in {- ξ, - ξ + 1, \dots, ξ}]

1 / (2 ξ + 1)

. The mean and variance are

E [{(- 1)}^{ν_{i}} p_{i}] = 0,

D [{(- 1)}^{ν_{i}} p_{i}] = \frac{1}{2 ξ + 1} \sum_{i = - ξ}^{ξ} i^{2} = \frac{1}{3} ξ (ξ + 1)

, respectively. Then,

E [\frac{1}{ℵ} \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}] = 0

D [\frac{1}{ℵ} \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}] = \frac{1}{3 ℵ} ξ (ξ + 1)

. When ℵ becomes big enough,

\frac{1}{ℵ} \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}

obeys the Gaussian distribution

ψ_{0, \sqrt{\frac{1}{3 ℵ} ξ (ξ + 1)}}

, according to the Central Limit Theorem. Then,

\begin{matrix} \begin{matrix} P r [1 + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i} = 0 | ν_{i} \overset{$}{\leftarrow} {0, 1}, p_{i} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}] \\ = & P r [\frac{1}{ℵ} \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i} = - \frac{1}{ℵ} | ν_{i} \overset{$}{\leftarrow} {0, 1}, p_{i} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}] \\ = & \frac{1}{\sqrt{2 π} \sqrt{\frac{ℵ}{3} ξ (ξ + 1)}} e^{- 1 / (\frac{2}{3} ℵ^{3} ξ (ξ + 1))} \approx \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}} \end{matrix} \end{matrix}

(16)

This probability is non-negligible.

Next, we evaluate the probability that the simulation normally completes the signature queries and forgery with the affine subspaces method, as in [34]. Since

f_{i} = h_{s} p_{i} + e_{i} + p_{i}^{'} h_{f}

p_{i}, e_{i} \overset{$}{\leftarrow} {- 1, 0, 1}^{n}

p_{i}^{'} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}

from

i = 0

to ℵ except

p_{0}^{'} = 1

. At the beginning of the game, the values of

p_{i}^{'}

s are completely hidden from

A

by the LWE instances

h_{s} p_{i} + e_{i}

. Even though

A

knows the calculation form of

f_{i}

, some information is leaked due to signature queries.

A

can not infer enough information by Bayesian updating to observably increase the probability of forging. For

ν^{*}

, the event

1 + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}^{*}} p_{i}^{'} = 0

corresponds a hyperplane

V^{*}

with

| V^{*} | = \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}} | V |

, where

| V |

denotes the size of the total space determined by

(p_{1}, p_{2}, \dots p_{ℵ})

. Let

V_{j}

denote a hyperplane that can lead to an abort in the jth signature query. Then,

| V^{*} ∖ V_{j} | = | V^{*} - V^{*} \cap V_{j} | = \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}} (1 - \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}}) | V |

. The lower bound can be computed by the union bound,

\begin{matrix} \begin{matrix} P r [c o m p l e t e] = P r [(p_{1}, p_{2} \dots, p_{ℵ}) \in (V^{*} ∖ \cup_{j = 1}^{Q} V_{j})] \geq \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}} (1 - \frac{\sqrt{3} Q}{\sqrt{2 π ℵ ξ (ξ + 1)}}) \end{matrix} \end{matrix}

(17)

The upper bound can be evaluated trivially,

P r [c o m p l e t e] \leq \frac{\sqrt{3}}{\sqrt{2 π ℵ ξ (ξ + 1)}}

Specifically, when

Q < \frac{9 \sqrt{2 π ℵ ξ (ξ + 1)}}{10 \sqrt{3}} < \frac{9 \sqrt{2 π ℵ ϱ n (ϱ n + 1)}}{10 \sqrt{3}} \approx \frac{9 ϱ n \sqrt{2 π ℵ}}{10 \sqrt{3}} \approx \frac{\sqrt{3} π^{7 / 2} q}{20 n^{2} ℵ^{1 / 2} {(ln (2^{(7 + λ) / 2} n))}^{3 / 2}},

\frac{\sqrt{3} Q}{\sqrt{2 π ℵ ξ (ξ + 1)}} < \frac{9}{10}

\frac{\sqrt{3}}{10 \sqrt{2 π ℵ ξ (ξ + 1)}} < P r [c o m p l e t e] < \frac{\sqrt{3}}{π \sqrt{2 ℵ ξ (ξ + 1)}}

. □

Theorem 2.

If there exists an adversary

A

who can forge an existential signature for SC-NTRU with probability ϵ by carrying out adaptive chosen-message queries, then a probabilistic algorithm

C

can be constructed to solve the search LWE

_{n, m, q}

problem with parameter settings in Equation (1) in almost the same time with probability

\frac{\sqrt{3} ϵ}{π \sqrt{2 ℵ ξ (ξ + 1)}} (1 - \frac{\sqrt{3} Q}{π \sqrt{2 ℵ ξ (ξ + 1)}})

Proof.

Setup. The challenger

C

queries the RLWE oracle to fetch a random RLWE

(q, n, m, β)

instance

(h_{s}, y)

. Then,

C

generates the simulation environment for

A

as follows.

$C$ generates a public and private key pair by running the KeyGen algorithm $(B_{f}, h_{f}) \leftarrow KeyGen (n, q)$ .
$C$ samples $p_{i}, e_{i} \overset{$}{\leftarrow} {- 1, 0, 1}^{n}$ , $p_{i}^{'} \overset{$}{\leftarrow} {- ξ, - ξ + 1, \dots, ξ}$ from $i = 1$ to ℵ but sets $p_{i}^{'} = 1$ , then computes $f_{i} = h_{s} p_{i} + e_{i} + p_{i}^{'} h_{f}$ for i from 1 to ℵ.

C

returns

(h_{f}, {f_{i}}_{i = 0}^{ℵ})

A

Queries.

A

submits a randomly chosen message

μ \in {0, 1}^{*}

C

to query.

C

replies to the query by generating the corresponding signature as follows.

$k \overset{$}{\leftarrow} {0, 1}^{λ}$ .
$ν$ : $= H_{0} (μ, b_{r}, k)$ .
$p^{'} = p_{0}^{'} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}^{'}$ . If $p^{'} = 0$ , go to step 1.
$p = p_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}$ .
$f$ : $= f_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} f_{i}$ .
$e$ : $= e_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} e_{i}$ .
Generate a basis $B : =$ SimExtractS $(h_{s}, p, e, p^{'}, h_{f}, B_{f})$ for $(h_{s}, f)$ (see Algorithm 2).
$(x^{'}, x)$ : $= (y, 0) - SamplePre (B, η, (y, 0))$ .
return $x$ as the signature.

Forgery.

C

receives a forgery

x

signature on a new message

μ

, then constructs the solution for ISIS as follows.

Compute $p^{'} = p_{0}^{'} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}^{'}$ . If $p^{'} \neq 0$ , abort.
$p = p_{0} + \sum_{i = 1}^{ℵ} {(- 1)}^{ν_{i}} p_{i}$ .
Divide $x$ as $(x_{0}, x_{1}) \in Z_{q}^{n} \times Z_{q}^{n}$ .
Return $(x_{0} + p x_{1}, y - h_{s} (x_{0} + p x_{1}))$ as the solution for $(h_{s}, y)$ .

Firstly, according to Lemma 16, the simulated signatures generated during the query phase are valid and indistinguishable from the real signatures. That is,

C

creates a simulated environment, indistinguishable from reality for adversaries. This will lead

A

to complete the reduction game.

Secondly, according to Lemma 17, the coefficient vector of

y - h_{s} (x_{0} + p x_{1})

is short enough under the parameter settings in Equation (1). Therefore, the polynomials generated in step 4 of the forgery phase form a solution for the RLWE instance

(h_{s}, y)

Finally, according to Lemma 18, the simulation can successfully complete both signature queries and forgery without aborting, with non-negligible probability.

In summary,

C

can obtain a solution for an RLWE instance with non-negligible probability, if

A

has the ability to forge a valid signature for the SC-NTRU scheme. □

Algorithm 2 SimExtractS

(h_{s}, p, e, p, h_{f}, B_{f}

)

Require:

: public keys $h_{s}, h_{f} \in R_{q}$ and syndrome $u \in R_{q}$ , in which $h_{f} \leftarrow K e y G e n$ , $b_{r} = h_{r} p + e$ for $p, e \leftarrow {- 1, 0, 1}^{n}$ ;
: a pair of un-equivalent tags $τ, τ^{*}$ ;
: a syndrome $u \in R_{q}$ ;
: a basis $B_{f}$ for $h_{f}$ .

Ensure:
A private key

(x_{1}, x_{2})

1:: $f = h_{s} p + e + p h_{f}$
2:: $Γ = {}$
3:: repeat
4:: $r \overset{$}{\leftarrow} {0, 1}$
5:: if $r = 0$ then
6:: $x_{0}^{'} \leftarrow D_{Z^{n}, η_{0}, 0}$ (where $η_{0} = \frac{1}{π} \sqrt{\frac{1}{2} ln (2^{(7 + λ) / 2} n)}$ )
7:: $y^{'} = (- h_{s} x_{0}^{'}) / p$
8:: $(x_{1}^{'}, x_{1})$ : $= (y^{'}, 0) - SamplePre (B_{f}, η_{3}, (y^{'}, 0))$ where $η_{3} = \frac{1.17}{π} \sqrt{\frac{1}{2} ln (2^{(7 + λ) / 2} n) q}$
9:: $x_{0} = x_{0}^{'} - p x_{1}$
10:: else
11:: $(x_{1}^{'}, x_{1})$ : $= (g_{f_{i}}, t_{f_{i}})$ where $(g_{f_{i}}, t_{f_{i}})$ is a basis vector of $Λ_{f, q}$
12:: $x_{0} = - p x_{1}$
13:: end if
14:: $b = (x_{0}, x_{1})$
15:: if $b$ is linearly independent with the vectors in $Γ$ then
16:: $Γ = Γ \cap b$
17:: end if
18:: until $| Γ | = 2 n$
19:: covert $2 n$ linearly independent vectors in $Γ$ to a basis $B$ of $(h_{s} ∥ f)$ with the algorithm in Lemma $7.1$ of [44].

5.2. Performance

In the existing lattice-based signcryption schemes, some building blocks are often used, such as the algorithm SampleD of [18], Inver of [18], SamplePre of [41], inverting matrix and solving system of linear equations, etc. To facilitate the performance comparison, we summarize some basic conclusions about the computational cost for these building blocks. In order to clearly state these conclusions, we introduce some notations for the basic mathematical operations. Let

\times_{Z}

\times_{Z_{q}}

\times_{R}

denote the multiplication operation over

Z

Z_{q}

R

, respectively. Let

+_{Z}

+_{Z_{q}}

+_{R}

denote the addition operation over

Z

Z_{q}

R

, respectively.

The computational overhead of matrix inversion and solving systems of linear equations can be evaluated by regular computation.

Proposition 5.

The computational cost to invert an n-dimensional matrix over

Z_{q}

is about

\frac{2}{3} n (n^{2} + 3 n - 1)

multiplications over

Z_{q}

Proposition 6.

The computational cost of solving

n \times m

-dimension nonhomogeneous linear equations over

Z_{q}

is about

\frac{1}{2} n (n + 1) (m + 1) + \frac{1}{6} (n - 2) (n - 1) (n + 3)

multiplications and additions over

Z_{q}

, and

2 n O (\log q)

inversion over

Z_{q}

. Here, the equation substitution is

m n - \frac{1}{2} n (n - 1)

multiplications and

m n + \frac{1}{2} n (n + 1)

additions over

Z_{q}

and

O (\log q)

inversion over

Z_{q}

Micciancio and Peikert presented a pre-image sample algorithm named SampleD

^{O}

, specifically designed for the MP trapdoor [18]. For more details, please refer to [18]. The computational overhead of the algorithm can be broken down into the following steps:

Step 1: Generating $(2 n \log q)$ -dimension DGS.
Step 2: Performing $(n^{2} \log^{2} q + n^{2} \log q)$ $\times_{Z}$ and $+_{Z}$ , as well as $(n^{2} \log q)$ $\times_{Z_{q}}$ and $+_{Z_{q}}$ .
Step 3: Conducting $(n^{2})$ $\times_{Z}$ and $+_{Z}$ , $(n^{2})$ $\times_{Z_{q}}$ and $+_{Z_{q}}$ , and utilizing $n \log q$ -dimension DGS.
Step 4: Involving $(n^{2} \log^{2} q)$ $\times_{Z}$ and $+_{Z}$ .

Therefore, the overall computational overhead of SampleD

^{O}

is summarized as follows.

Proposition 7.

The computational cost of Algorithm SampleD

^{O}

of [18] is about

3 n \log q

discrete Gaussian samples (DGS),

2 n^{2} \log^{2} q + n^{2} \log q + n \log q

multiplications and additions over

Z

n^{2} \log q + n^{2}

multiplications and additions over

Z_{q}

. The overhead to compute the Gaussian parameter is

3 n^{3} \log^{3} q

, which can be precomputed.

Except for SampleD, the computational cost of signcryption of [17] is about

5 n \log q

DGS,

8 n^{2} \log q

multiplications over

Z_{q}

(λ + 8) n^{2} \log q + n \log q - n

additions over

Z_{q}

n^{2} \log^{2} q + n \log q

multiplications over

Z

n^{2} \log^{2} q - n \log q

additions over

Z

In [18], an inversion algorithm called

I n v e r

is presented for the MP trapdoor. The computational overhead of the steps is described as follows.

Step 1: Involves $(n^{2} \log^{2} q)$ $\times_{Z}$ and $+_{Z}$ .
Step 2: Includes $(n \log q)$ $\times_{Z}$ and $+_{Z}$ , as well as $(n \log q)$ $\times_{Z_{q}}$ and $+_{Z_{q}}$ .
Step 3: Requires $(2 n^{2} \log q + n^{2})$ $\times_{Z_{q}}$ and $+_{Z}$ .

Therefore, the total computational overhead of Algorithm

I n v e r

is as follows.

Proposition 8.

The computational cost of Algorithm Inver of [18] is about

n^{2} \log^{2} q + 2 n^{2} \log q + n^{2} + n \log q

multiplications and

n^{2} \log^{2} q + 2 n^{2} \log q + n^{2} - 2 n

additions over

Z_{q}

2 n \log q

multiplications and additions over

Z

. In the process, the cost of the inversion oracle is

2 n \log q

multiplications and additions over

Z

In addition to solving system of linear equations, Algorithm SamplePre also involves executing the randomized nearest-plane algorithm. The computational cost of its steps is as follows.

step a: Involves $(2 m)$ $\times_{R}$ and $(2 m - 2)$ $+_{R}$ .
step b: Requires 1 DGS.
step c: Needs m $\times_{Z}$ and $(2 m)$ $+_{Z}$ .

The procedure is carried out m times. Consequently, the total computational cost of SamplePre without solving equations is calculated as follows.

Proposition 9.

Except for solving equations, the computational cost of Algorithm SamplePre of [41] is about 2

m^{2}

multiplications and additions over

R

m^{2}

multiplications and 2

m^{2}

additions over

Z

and m DGS.

The operations involved in Algorithm Gaussian_Sampler of [38] are almost identical to those in Algorithm SamplePre except for the solving equations part. However, the dimension of the basis used in Gaussian_Sampler is

2 n \times 2 n

. Consequently, its computational overhead includes

(8 n^{2})

\times_{R}

and

+_{R}

(4 n^{2})

\times_{Z}

and

(8 n^{2})

+_{Z}

, and

2 n

DGS. However, the circulant property of the basis matrix allows for the use of fast Fourier orthogonalization, which can speed up the procedure significantly [45]. According to [45], when adopting fast Fourier orthogonalization, the complexity of the Gaussian_Sampler is given as follows.

Proposition 10.

The computational cost of Algorithm Gaussian_Sampler of [38] is about

2 n

DGS,

4 Θ (n \log n)

multiplications and additions over

R

4 Θ (n \log n)

multiplications and additions over

Z

In Table 3, the sizes of public parameters, public key, private key, ciphertext, and security are compared. The sizes of the public parameters and the public key of SC-NTRU are approximately in the order of magnitude of

1 / (n \log q)

of those of YWW+13 [17], SS18 [19], and YCL+19 [20]. The private key size of SC-NTRU is roughly in the order of magnitude of

2 / (n \log^{2} q)

of those of YWW+13 [17] and SS18 [19], and

4 / (n \log^{2} q)

of that of YCL+19 [20]. Except for the plaintext length, the ciphertext size of SC-NTRU is about at the order of magnitude of

1 / \log q

of those of YWW+13 [17], SS18 [19], and YCL+19 [20]. Regarding security, the proposed scheme achieves IND-CCA2 security against adaptively chosen ciphertext attacks, similar to the other schemes in the table. However, when facing adaptively chosen message attacks, the proposed scheme is EUF-CMA secure instead of SUF-CMA security, as in YWW+13 [17] and SS18 [19]. Our intention is to demonstrate that a EUF-CMA secure signature component is sufficient to guarantee the IND-CCA2 security of the signcryption ciphertext.

In Table 4, the computational overhead of YWW+13 [17], SS18 [19], YCL+19 [20], and SC-NTRU is compared. First, the cost of the key generation is compared. In the key generation phase of YWW+13 [17] and SS18 [19], the computation of

(\frac{2}{3} n^{3} + 2 n^{2}) \times_{Z_{q}}

is required to invert the matrix

H

. As it is the repeating computation in signcryption, it is reasonable to count its overhead into the key generation instead of signcryption. The numbers of

\times_{Z_{q}}

and

+_{Z_{q}}

of SC-NTRU are in the order of magnitude of

1 / n

of those of YWW+13 [17] and SS18 [19], and at a lower order of magnitude of YCL+19 [20]. The number of DGS of SC-NTRU is about

2 / (n \log^{2} q)

of those of YWW+13 [17] and SS18 [19]. In SC-NTRU, the samples from

U (Z_{q})

are not needed; however, the numbers of samples reach

n^{2} \log q

in YWW+13 [17] and SS18 [19].

Next, the overhead of the signcryption is compared. The

\times_{Z_{q}}

and

+_{Z_{q}}

operations in SC-NTRU are in the order of magnitude of

1 / n

of YWW+13 [17] and SS18 [19], respectively. The numbers of

\times_{Z}

and

+_{Z}

of SC-NTRU are in the order of magnitude of

1 / (n \log q)

of those of YWW+13 [17] and SS18 [19], and at a lower order of magnitude of YCL+19 [20]. The number of DGS of SC-NTRU is no more than

1 / (4 \log q)

of those of YWW+13 [17] and SS18 [19], and at a lower order of magnitude of YCL+19 [20]. Compared with YWW+13 [17] and SS18 [19], SC-NTRU requires

(4 θ (n \log n))

additional

\times_{R}

and

+_{R}

, and they are about

4 / (n \log^{3} q)

of YCL+19 [20]. In summary, although the schemes of YWW+13 [17] and SS18 [19] are built on the ordinary lattice, their signcryption performance significantly outperforms that of YCL+19 [20], due to not requiring the expensive basis extension. However, their signcryption cost is several orders of magnitude higher than that of SC-NTRU.

Finally, the cost of unsigncryption is compared. The numbers of

\times_{Z_{q}}

and

+_{Z_{q}}

operations of SC-NTRU are in the order of magnitude of

1 / n

and

1 / (n \log q + ℓ)

of those of YWW+13 [17] and SS18 [19], respectively. The numbers of

\times_{Z}

and

+_{Z}

operations of SC-NTRU are in the order of magnitude of

1 / (n \log q)

and

1 / (n \log q ℓ)

of those of YWW+13 [17] and SS18 [19], respectively. Compared with YWW+13 [17], SC-NTRU needs

3 n

additional DGS; however, it is only

1 / (k ℓ)

of that of SS18 [19]. The numbers of DGS,

\times_{Z_{q}}

and

+_{Z_{q}}

\times_{Z}

and

+_{Z}

\times_{R}

and

+_{R}

of SC-NTRU are in the order of magnitude of

3 / (2 \log q)

1 / \log q

4 / \log q

, and

4 / \log q

of those of YCL+19 [20]. In summary, since YCL+19 [20] adopts the ideal lattice, the performance of the unsigncryption greatly outperforms YWW+13 [17] and SS18 [19]; however, its overheads are

\log q / 4

2 \log q / 3

of those of SC-NTRU.

To sum up, due to the efficiency of the NTRU trapdoor and reasonable construction, the proposed scheme achieves orders of magnitude of improvement in computation cost over the existing signcryption schemes.

5.3. Experiment

To assess the actual performance of SC-NTRU, we conducted experiments using the C programming language. The experimental environment is set up on a Ubuntu platform with 4 GB of memory. The dimension of the NTRU lattice has a significant impact on security. Therefore, we choose three sets of typical parameters: n = 256, 512, and 1024, corresponding to low, medium, and high levels of security, respectively. We run the experiment 1000 times and calculate the average time. The experimental data are presented in Table 5. According to the data in the table, the running time of key generation, signcrypt, and unsigncrypt exhibit running times on the order of milliseconds. Notably, the running time of signcrypt (and unsigncrypt) ranges between 1.3 and 6.2 (1.1 and 5.5), demonstrating the efficiency of SC-NTRU.

6. Conclusions

In this paper, a signcryption scheme following the StE paradigm is proposed based on the intractability of the NTRU lattice and RLWE, which serves as the security foundation of Falcon in NIST PQC. First, it is shown how to embed some sensitive information into a general lattice-based public key encryption (PKE) and bind it with the message being encrypted by PKE. The malleability to the ciphertext ultimately leads to the modification in the message–signature pair. Consequently, the signature for the message can also be utilized to verify and guarantee the IND-CCA2 security of the ciphertext. Thus, the need for the MAC to transfer from the public key to the signature is eliminated.

Secondly, a new abort-resistant hash is proposed to match the “partiality” of the pre-image in relation to the checkout polynomial, so that an NTRU signature secure in the standard model can be built with it. The computational overhead analysis demonstrates a significant improvement in the efficiency of SC-NTRU, surpassing existing lattice-based signcryption methods by orders of magnitude. The experiment shows that SC-NTRU is very efficient.

Author Contributions

Methodology, J.Y., X.L., M.L. and L.W.; Validation, J.Y., X.L., J.Z. and W.Y.; Formal analysis, J.Y., L.W. and W.Y.; Investigation, M.L., J.Z. and W.Y.; Writing—original draft, J.Y. and X.L.; Writing—review & editing, M.L.; Supervision, L.W. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by the National Defense Basic Scientific Research program of China (Grant No. JCKY2020602B008), the Study Abroad Foundation Visiting Program (No. 201908370041), the Natural Science Foundation of Shandong Province (No. ZR2017MF035), and the National Natural Science Foundation of China (NSFC) (No. 61972050).

Data Availability Statement

Data is contained within the article.

Conflicts of Interest

The authors declare no conflict of interest.

References

Zheng, Y. Digital Signcryption or How to Achieve Cost(Signature & Encryption) «Cost(Signature) + Cost(Encryption)». In Proceedings of the Advances in Cryptology—CRYPTO’97, 17th Annual International Cryptology Conference, Santa Barbara, CA, USA, 17–21 August 1997; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 1997; Volume 1294, pp. 165–179. [Google Scholar] [CrossRef]
Shor, P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 1997, 26, 1484–1509. [Google Scholar] [CrossRef]
Li, F.; Bin Muhaya, F.T.; Khan, M.K.; Takagi, T. Lattice-Based Signcryption; John Wiley & Sons, Ltd.: Hoboken, NJ, USA, 2012. [Google Scholar] [CrossRef]
Rao Sreenivasa, Y. A secure and efficient Ciphertext-Policy Attribute-Based Signcryption for Personal Health Records sharing in cloud computing. Future Gener. Comput. Syst. FGCS 2017, 52, 95–108. [Google Scholar]
Deng, F.; Wang, Y.; Li, P.; Hu, X.; Geng, J.; Qin, Z. Ciphertext-Policy Attribute-Based Signcryption with Verifiable Outsourced Designcryption for Sharing Personal Health Records. IEEE Access 2018, 6, 39473–39486. [Google Scholar] [CrossRef]
Yan, J.; Wang, L.; Dong, M.; Yang, Y.; Yao, W. Identity-based signcryption from lattices. Secur. Commun. Netw. 2015, 8, 3751–3770. [Google Scholar] [CrossRef]
Yan, J.; Wang, L.; Li, M.; Ahmad, H.; Yue, J.; Yao, W. Attribute-Based Signcryption from Lattices in the Standard Model. IEEE Access 2019, 7, 56039–56050. [Google Scholar] [CrossRef]
Zhang, X.; Xu, C.; Xue, J. Efficient multi-receiver identity-based signcryption from lattice assumption. Int. J. Electron. Secur. Digit. Forensics 2018, 10, 20. [Google Scholar] [CrossRef]
Wang, F.; Hu, Y.; Wang, C. Post-quantum secure hybrid signcryption from lattice assumption. Appl. Math. Inf. Sci. 2012, 6, 23–28. [Google Scholar]
Lu, X.; Wen, Q.; Wang, L.; Du, J. A Lattice-based Signcryption Scheme without Trapdoors. J. Electron. Inf. 2016, 38, 2287. [Google Scholar] [CrossRef]
Gérard, F.; Merckx, K. SETLA: Signature and Encryption from Lattices; Springer: Cham, Switzerland, 2018. [Google Scholar]
Liu, Z.; Han, Y.L.; Yang, X.Y. A Signcryption Scheme Based Learning with Errors over Rings without Trapdoor. In Proceedings of the National Conference of Theoretical Computer Science, Lanzhou, China, 2–4 August 2019. [Google Scholar]
Liu, Z.; Han, Y.; Yang, X.; Yang, S. Provable security signcryption scheme based on RLWE without trapdoor. J. Commun. 2020, 41, 12. [Google Scholar]
Savu, L. Signcryption scheme based on schnorr digital signature. arXiv 2012, arXiv:1202.1663. [Google Scholar] [CrossRef]
Bai, S.; Galbraith, S.D. An improved compression technique for signatures based on learning with errors. IACR Cryptol. EPrint Arch. 2013, 2013, 838. [Google Scholar]
Güneysu, T.; Lyubashevsky, V.; Pöppelmann, T. Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. In Proceedings of the CHES; Lecture Notes in Computer Science; Prouff, E., Schaumont, P., Eds.; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7428, pp. 530–547. [Google Scholar]
Yan, J.; Wang, L.; Wang, L.; Yang, Y.; Yao, W. Efficient Lattice-Based Signcryption in Standard Model. Math. Probl. Eng. 2013, 2013, 702539. [Google Scholar] [CrossRef]
Micciancio, D.; Peikert, C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In Proceedings of the Advances in Cryptology—EUROCRYPT 2012; Lecture Notes in Computer Science; Pointcheval, D., Johansson, T., Eds.; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7237, pp. 700–718. [Google Scholar] [CrossRef]
Sato, S.; Shikata, J. Lattice-Based Signcryption without Random Oracles; Springer: Cham, Switzerland, 2018. [Google Scholar]
Yang, X.; Cao, H.; Li, W.; Xuan, H. Improved Lattice-Based Signcryption in the Standard Model. IEEE Access 2019, 7, 155552–155562. [Google Scholar] [CrossRef]
Lyubashevsky, V.; Peikert, C.; Regev, O. On Ideal Lattices and Learning with Errors over Rings. In Proceedings of the EUROCRYPT; Lecture Notes in Computer Science; Gilbert, H., Ed.; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6110, pp. 1–23. [Google Scholar]
Peikert, C. Lattice Cryptography for the Internet. In Proceedings of the PQCrypto; Mosca, M., Ed.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2014; Volume 8772, pp. 197–219. [Google Scholar]
Zhang, J.; Zhang, Z.; Ding, J.; Snook, M. Authenticated Key Exchange from Ideal Lattices. IACR Cryptol. EPrint Arch. 2014, 2014, 589. [Google Scholar]
Liu, Z.Y.; Tso, R.; Tseng, Y.F.; Mambo, M. Signcryption from NTRU Lattices without Random Oracles. In Proceedings of the 2019 14th Asia Joint Conference on Information Security (AsiaJCIS), Kobe, Japan, 1–2 August 2019. [Google Scholar]
del Pino, R.; Lyubashevsky, V.; Pointcheval, D. The Whole is Less Than the Sum of Its Parts: Constructing More Efficient Lattice-Based AKEs. In Proceedings of the Security and Cryptography for Networks—10th International Conference, SCN 2016, Amalfi, Italy, 31 August–2 September 2016; Lecture Notes in Computer Science. Zikas, V., Prisco, R.D., Eds.; Springer: Berlin/Heidelberg, Germany, 2016; Volume 9841, pp. 273–291. [Google Scholar]
Zhang, Y.; Hu, Y.; Xie, J.; Jiang, M. Efficient ring signature schemes over NTRU Lattices. Secur. Commun. Netw. 2016, 9, 5252–5261. [Google Scholar] [CrossRef]
An, J.H.; Dodis, Y.; Rabin, T. On the Security of Joint Signature and Encryption. In Proceedings of the Advances in Cryptology—EUROCRYPT 2002; Knudsen, L.R., Ed.; Springer: Berlin/Heidelberg, Germany, 2002; pp. 83–107. [Google Scholar]
Matsuda, T.; Matsuura, K.; Schuldt, J.C.N. Efficient Constructions of Signcryption Schemes and Signcryption Composability. In Proceedings of the International Conference on Cryptology in India, New Delhi, India, 13–16 December 2009. [Google Scholar]
Ducas, L.; Kiltz, E.; Lepoint, T.; Lyubashevsky, V.; Stehlé, D. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018, 2018, 238–268. [Google Scholar] [CrossRef]
Fouque, P.A.; Hoffstein, J.; Kirchner, P.; Lyubashevsky, V.; Zhang, Z. Falcon: Fast-Fourier Lattice-Based Compact Signatures over NTRU. Submiss. NIST’s Post-Quantum Cryptogr. Stand. Process 2018, 36, 1–75. [Google Scholar]
Joseph, D.; Misoczki, R.; Manzano, M.; Tricot, J.; Pinuaga, F.D.; Lacombe, O.; Leichenauer, S.; Hidary, J.; Venables, P.; Hansen, R. Transitioning organizations to post-quantum cryptography. Nature 2022, 605, 237–243. [Google Scholar] [CrossRef]
Waters, B. Efficient Identity-Based Encryption without Random Oracles. In Proceedings of the Advances in Cryptology—EUROCRYPT 2005; Lecture Notes in Computer Science; Cramer, R., Ed.; Springer: Berlin/Heidelberg, Germany, 2005; Volume 3494, pp. 114–127. [Google Scholar] [CrossRef]
Agrawal, S.; Boneh, D.; Boyen, X. Efficient Lattice (H)IBE in the Standard Model. In Advances in Cryptology—EUROCRYPT 2010; Lecture Notes in Computer Science; Gilbert, H., Ed.; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6110, pp. 553–572. [Google Scholar] [CrossRef]
Boyen, X. Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More. In Public Key Cryptography—PKC 2010; Lecture Notes in Computer Science; Nguyen, P., Pointcheval, D., Eds.; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6056, pp. 499–517. [Google Scholar] [CrossRef]
Chen, Y.; Genise, N.; Mukherjee, P. Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures. In Proceedings of the Advances in Cryptology—ASIACRYPT 2019—25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8–12 December 2019; Proceedings, Part III; Lecture Notes in Computer Science; Galbraith, S.D., Moriai, S., Eds.; Springer: Berlin/Heidelberg, Germany, 2019; Volume 11923, pp. 3–32. [Google Scholar]
López-Alt, A.; Tromer, E.; Vaikuntanathan, V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19–22 May 2012; Karloff, H.J., Pitassi, T., Eds.; ACM: New York, NY, USA, 2012; pp. 1219–1234. [Google Scholar]
Hoffstein, J.; Pipher, J.; Silverman, J.H. NTRU: A Ring-Based Public Key Cryptosystem. In Proceedings of the ANTS: 3rd International Algorithmic Number Theory Symposium (ANTS), Portland, OR, USA, 21–25 June 1998. [Google Scholar]
Ducas, L.; Lyubashevsky, V.; Prest, T. Efficient Identity-Based Encryption over NTRU Lattices. IACR Cryptol. EPrint Arch. 2014, 2014, 794. [Google Scholar]
Lyubashevsky, V. Lattice Signatures without Trapdoors. In Advances in Cryptology—EUROCRYPT 2012; Lecture Notes in Computer Science; Pointcheval, D., Johansson, T., Eds.; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7237, pp. 738–755. [Google Scholar] [CrossRef]
Micciancio, D.; Regev, O. Worst-case to average-case reductions based on Gaussian measure. SIAM J. Comput. 2007, 37, 267–302. [Google Scholar] [CrossRef]
Gentry, C.; Peikert, C.; Vaikuntanathan, V. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC ’08, New York, NY, USA, 17–20 May 2008; pp. 197–206. [Google Scholar] [CrossRef]
Peikert, C. An Efficient and Parallel Gaussian Sampler for Lattices. In Advances in Cryptology—CRYPTO 2010; Lecture Notes in Computer Science; Rabin, T., Ed.; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6223, pp. 80–97. [Google Scholar] [CrossRef]
Zhang, J.; Yu, Y.; Fan, S.; Zhang, Z. Improved lattice-based CCA2-secure PKE in the standard model. Sci. China Inf. Sci. 2020, 63, 182101. [Google Scholar] [CrossRef]
Micciancio, D.; Goldwasser, S. Complexity of Lattice Problems: A Cryptographic Perspective; Springer: Berlin/Heidelberg, Germany, 2002; Volume 671. [Google Scholar]
Ducas, L.; Prest, T. Fast Fourier Orthogonalization. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, New York, NY, USA, 20–22 July 2016; pp. 191–198. [Google Scholar] [CrossRef]

Table 1. Game IND-CCA2 between

C

and

A

Table 1. Game IND-CCA2 between

C

and

A

	$C$	Communication	$A$
Intial.	${(p k_{s}, s k_{s}), (p k_{r}, s k_{r})} \leftarrow KeyGen (1^{k})$	$\overset{p k_{s}, p k_{r}, s k_{s}}{\to}$
Phase 1.		$\leftarrow_{for Unsigncrypt}^{c}$	choose c
	$μ = UnSigncrypt (c, p k_{r}, p k_{s}, s k_{r})$	$\to_{as reply}^{μ}$
	…	…	…
Challenge		$\leftarrow_{for challenge}^{μ_{0}, μ_{1}}$	choose $μ_{0}, μ_{1}$ with equal length
Challenge	Toss a coin b, $c^{*} = Signcrypt (μ_{b}, p k_{r}, p k_{s}, s k_{s})$	$\to_{as reply}^{c^{*}}$
Phase 2.	repeat Phase 1, except reply ⊥ to the query for $c^{*}$	repeat	repeat
Guess		$\leftarrow_{as reply}^{b^{'}}$	guess $b^{'}$

Table 2. Game EUF-CMA between

C

and

A

Table 2. Game EUF-CMA between

C

and

A

	$C$	Communication	$A$
Initial.	${(p k_{s}, s k_{s}), (p k_{r}, s k_{r})} \leftarrow KeyGen (1^{k})$	$\overset{p k_{s}, p k_{r}, s k_{r}}{\to}$
Queries		$\leftarrow_{for Signcrypt}^{μ}$	choose $μ$
	$c = SC (μ, p k_{r}, p k_{s}, s k_{s})$	$\to_{as reply}^{c}$
	…	…	…
Forgery		$\leftarrow_{as reply}^{c^{*}}$	generate $c^{*}$

Table 3. Comparison of the key size, public parameter size, and security of the related schemes.

Scheme	YWW+13 [17]	SS18 [19]	YCL+19 [20]	Ours
public parameter	$(λ + 3) n^{2} \log^{2} q$ $+ n ℓ \log q$	$(λ + 3) n^{2} \log^{2} q$ $+ n ℓ \log q$	$(2 k^{'} + ℓ + 5)$ $n^{2} \log^{2} q$	$(ℵ + 1) n \log q$ ¹
public key	$3 n^{2} \log^{2} q$ $+ n ℓ \log q$	$3 n^{2} \log^{2} q$ $+ n ℓ \log q$	$n^{2} \log^{2} q$	$3 n \log q$
private key	$24 n^{2} \log^{2} q \log σ$ ²	$24 n^{2} \log^{2} q \log σ$	$12 n^{2} \log^{2} q \log σ$	$48 n \log σ$
ciphertext	$2 n \log^{2} q + \| μ \|$ $+ 48 n \log q \log σ_{1}$ ³	$2 n \log^{2} q + \| μ \|$ $+ 12 (7 n + ℓ) \log q$ $\cdot \log σ_{2}$	$4 n \log^{2} q + \| μ \|$ $+ 36 n \log q \log σ_{3}$ $+ n + ℓ$	$3 n \log q + \| μ \|$ $+ 24 n \log σ_{4}$
security	IND-CCA2, SUF-CMA	IND-CCA2, SUF-CMA	IND-CCA2, EUF-CMA	IND-CCA2, EUF-CMA
based on NIST	No	No	No	Yes

λ

ℓ

ℵ

are all with the security parameter, so they are roughly the same. ² Every element of the private key is stored in 12log

σ

, when its Gaussian parameter is

σ

. ³

| μ |

denotes the length of the message.

Table 4. Comparison of the computation overhead of the related signcryption schemes.

	Computation Type	YWW+13 [17]	SS18 [19]	YCL+19 [20]	Ours
Setup	$\leftarrow U (Z_{q})$	$(λ + 3) n^{2} \log q$ $+ n ℓ$	$(λ + 3) n^{2} \log q$ $+ n ℓ + n$	$(ℓ + 5) n \log q$	$(ℵ + 5) n$
KeyGen	$\leftarrow U (Z_{q})$	$n^{2} \log q$	$n^{2} \log q$	$σ n ((m - 2 σ - r)$ $/ ⌈ \log q ⌉ + r + 2)$	0
	DGS	$n^{2} \log^{2} q$	$n^{2} \log^{2} q$	0	$2 n$
	$\times_{Z_{q}}$	$n^{3} \log^{2} q$ $+ \frac{2}{3} n^{3} + 2 n^{2}$	$n^{3} \log^{2} q$ $+ \frac{2}{3} n^{3} + 2 n^{2}$	$(m - 2 σ - r)$ $(r + σ)$	$7 O (n^{2} \log n)$ $+ 8 O (n \log n)$
	$+_{Z_{q}}$	$n^{3} \log^{2} q$ $+ \frac{2}{3} n^{3} + 2 n^{2}$	$n^{3} \log^{2} q$ $+ \frac{2}{3} n^{3} + 2 n^{2}$	$(m - 2 σ - r)$ $(r + σ)$	$7 O (n^{2} \log n)$ $+ 8 O (n \log n)$
	$\times_{Z}$	0	0	0	$4 n$
	$+_{Z}$	0	0	0	$4 n$
Signcrypt	DGS	$8 n \log q$	$9 n \log q + ℓ$	$n^{2} \log^{2} q$ $+ 6 n \log q + n$	$2 n$
	$\times_{Z_{q}}$	$10 n^{2} \log q$ $+ 2 n \log q$ $+ n^{2} + n ℓ$	$10 n^{2} \log q$ $+ n \log q$ $+ n^{2} + n ℓ$	$n \log q (3 \log q + 8)$ $\cdot O (n \log n) +$ $(2 \log q - 1) n^{2} \log q$	$5 O (n \log n)$
	$+_{Z_{q}}$	$(λ + 10) n^{2} \log q$ $+ n^{2} + n ℓ - 2 n$	$(λ + 11) n^{2} \log q$ $+ n^{2} + n ℓ - 5 n$ $+ 4 n \log q + ℓ$	$n \log q (3 \log q + 8)$ $\cdot O (n \log n) + n ℓ +$ $(2 \log q - 1) n^{2} \log q$	$5 O (n \log n)$ $+ (ℵ + 3) n$
	$\times_{Z}$	$2 n^{2} \log^{2} q$ $+ n^{2} \log q$ $+ 3 n \log q + n^{2}$	$2 n^{2} \log^{2} q$ $+ n^{2} \log q$ $+ 3 n \log q + ℓ$	$(n \log^{3} q + 2 \log^{2} q)$ $\cdot O (n \log n)$	$4 θ (n \log n)$
	$+_{Z}$	$2 n^{2} \log^{2} q$ $+ n^{2} \log q$ $+ 2 n \log q + n^{2}$	$2 n^{2} \log^{2} q$ $+ n^{2} \log q$ $+ n \log q$	$(n \log^{3} q + 2 \log^{2} q)$ $\cdot O (n \log n) + n \log q ℓ$	$4 θ (n \log n)$
	$\times_{R}$	0	0	$(n \log^{3} q + 2 \log^{2} q)$ $\cdot O (n \log n)$	$4 θ (n \log n)$
	$+_{R}$	0	0	$(n \log^{3} q + 2 \log^{2} q)$ $\cdot O (n \log n)$	$4 θ (n \log n)$
UnSigncrypt	DGS	0	$3 n k ℓ$	$2 n \log q$	$3 n$
	$\times_{Z_{q}}$	$8 n^{2} \log q$ $+ n ℓ$	$n^{2} \log^{2} q$ $+ n^{2} \log q (ℓ + 11)$ $+ n^{2} (ℓ + 1)$ $+ 2 n \log q ℓ$	$(8 \log q + 1) O (n \log n)$ $+ O (n \log q \log (n \log q))$	$4 O (n \log n)$ $+ O (2 n \log 2 n)$
	$+_{Z_{q}}$	$8 n^{2} \log q$ $+ λ n \log q$ $+ n ℓ - n$	$n^{2} \log^{2} q + n^{2}$ $\log q (λ + ℓ + 11)$ $+ n^{2} (ℓ + 1)$ $+ 2 n \log q (2 ℓ + 1)$	$(8 \log q + 1) O (n \log n)$ $+ O (n \log q \log (n \log q))$ $+ 6 n \log q$	$4 O (n \log n)$ $+ O (2 n \log 2 n)$ $+ ℵ n$
	$\times_{Z}$	$2 n^{2} \log^{2} q$ $+ 8 n \log q$ $+ 2 \log q$	$2 n^{2} \log^{2} q ℓ$ $+ n^{2} \log q ℓ$ $+ 2 n \log q ℓ$ $+ 5 n \log q + 2 ℓ$	$\log q O (n \log n)$ $+ 2 n \log q$	$4 θ (n \log n)$ $+ 5 n$
	$+_{Z}$	$2 n^{2} \log^{2} q$ $+ 6 n \log q$ $+ 2 \log q$	$2 n^{2} \log^{2} q ℓ$ $+ n^{2} \log q ℓ$ $+ 2 n \log q ℓ$ $+ 5 n \log q + 2 ℓ$	$\log q O (n \log n)$ $+ 2 n \log q$	$4 θ (n \log n)$ $+ 3 n$
	$\times_{R}$	0	0	$\log q O (n \log n)$ $+ 2 n \log q$	$4 θ (n \log n)$
	$+_{R}$	0	0	$\log q O (n \log n)$ $+ 2 n \log q$	$4 θ (n \log n)$

Table 5. Actual performance of SC-NTRU under different parameters.

n	q	Keygen (ms)	SC (μs)	USC (μs)
256	52,145,447,681	16.45	1342.48	1198.03
512	425,478,982,619	36.17	2904.77	2585.58
1024	3,470,791,299,527	95.81	6134.78	5436.07

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Yan, J.; Lu, X.; Li, M.; Wang, L.; Zhou, J.; Yao, W. Practical NTRU Signcryption in the Standard Model. Entropy 2023, 25, 1651. https://doi.org/10.3390/e25121651

AMA Style

Yan J, Lu X, Li M, Wang L, Zhou J, Yao W. Practical NTRU Signcryption in the Standard Model. Entropy. 2023; 25(12):1651. https://doi.org/10.3390/e25121651

Chicago/Turabian Style

Yan, Jianhua, Xiuhua Lu, Muzi Li, Licheng Wang, Jingxian Zhou, and Wenbin Yao. 2023. "Practical NTRU Signcryption in the Standard Model" Entropy 25, no. 12: 1651. https://doi.org/10.3390/e25121651

APA Style

Yan, J., Lu, X., Li, M., Wang, L., Zhou, J., & Yao, W. (2023). Practical NTRU Signcryption in the Standard Model. Entropy, 25(12), 1651. https://doi.org/10.3390/e25121651

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Practical NTRU Signcryption in the Standard Model

Abstract

1. Introduction

1.1. Related Works

1.2. Proposed Design

2. Preliminaries

2.1. NTRU Lattice and Hard Problem

2.2. Trapdoor Generation and Pre-Image Sample Algorithm

3. Signcryption: Syntax and Security Models

3.1. Syntax of Signcryption

3.2. Security Models of Signcryption

4. Signcryption Based on NTRU

4.1. Construction

4.2. Correctness

5. Security and Performance

5.1. Security

5.2. Performance

5.3. Experiment

6. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI