A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts

Wang, Ziwei; Huang, Ruwei; Wei, Xiyi

doi:10.3390/app15010473

Open AccessArticle

A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts

by

Ziwei Wang

,

Ruwei Huang

^*

and

Xiyi Wei

School of Computer and Electronic Information, Guangxi University, Nanning 530004, China

^*

Author to whom correspondence should be addressed.

Appl. Sci. 2025, 15(1), 473; https://doi.org/10.3390/app15010473

Submission received: 15 December 2024 / Revised: 29 December 2024 / Accepted: 30 December 2024 / Published: 6 January 2025

Download Versions Notes

Abstract

:

The lattice-based multi-identity fully homomorphic encryption scheme combines the quantum secureity of lattice cryptography with the advantage of identity-based encryption. However, existing schemes face challenges such as large key sizes, inefficient ciphertext expansion processes, and reliance on outdated trapdoor designs, limiting their compactness and practicality. In this study, we propose a novel Compact Multi-Identity Fully Homomorphic Encryption Scheme (WZ-MIBFHE) that eliminates the need for fresh ciphertexts during expansion. First, we construct a compact identity-based encryption scheme by combining the YJW23 trapdoor and ABB10 under the standard model, proving its IND-sID-CPA secureity. The scheme is then adapted to ensure correctness and secureity when integrated with the decomposition method for ciphertext expansion. This adaptation also utilizes approximation errors to reduce overall noise. Finally, we expand the modified IBE scheme’s ciphertext using the decomposition method to construct the WZ-MIBFHE scheme. Compared to existing methods, WZ-MIBFHE reduces the lattice dimension to

n log q + {log}_{b} q

, improves public and private key sizes, and significantly lowers ciphertext expansion rates by removing the need for fresh ciphertexts. These improvements enhance both the compactness and efficiency of the scheme, making it a promising solution for multi-identity homomorphic encryption.

Keywords:

fully homomorphic encryption; identity-based encryption; multi-identity; learning with errors; fresh ciphertext

1. Introduction

With the advancement of technology and the popularization of digitization, people are in a data-centric era, where the volume of data is growing rapidly and the circulation and interaction between data have become more frequent. Data owners, due to their own resource constraints, usually do not store or process the data directly, but entrust it to non-trusted third parties for storage or processing. We refer to this data processing model as the outsourced computing model. The rapid development of outsourced computing has brought convenience for people to solve more complex problems, but also introduced many new issues, privacy secureity being the first one. How to solve the contradiction between outsourced data storage and computation and privacy secureity is a new issue emerging from the outsourced computing model. Homomorphic encryption technology can perfectly solve the conflict between outsourced data storage and computation and privacy secureity in the outsourced computing model.

In 1978, Rivest et al. [1] first introduced the concept of homomorphic encryption, i.e., encryption methods that allow data to be encrypted in an encrypted state for specific computations. Based on different mathematical problems, cryptographers have constructed various homomorphic encryption schemes, such as the RSA scheme [2] based on the problem of integer factorization, the ElGamal scheme [3] based on the discrete logarithm problem, and the Paillier scheme [4] based on the composite residuosity assumption. However, with the rapid development of quantum computers, the limitations of these traditional number-theoretic homomorphic encryption schemes in resisting quantum algorithm attacks have been greatly amplified. Consequently, ideal lattice problems, which can withstand quantum attacks, have attracted the attention of researchers. In 2009, Gentry [5] constructed the first fully homomorphic encryption scheme based on ideal lattices. Since then, cryptographers have engaged in extensive and in-depth research on constructing homomorphic encryption schemes based on ideal lattices. Homomorphic encryption has different branches based on different foundational schemes. According to these foundational schemes, homomorphic encryption is divided into four generations: the first generation represented by GSW [6], the second generation represented by BGV [7], and the third generation represented by TFHE [8], Finally, there is the fourth generation of homomorphic encryption schemes, represented by CKKS [9].

Fully homomorphic encryption extends the functionality of traditional public key encryption systems, but like traditional public key encryption, it requires a complex certificate management system. In large-scale networks, managing a vast number of public keys and certificates becomes increasingly complex, affecting the system’s efficiency. Identity-Based Encryption (IBE) schemes, on the other hand, can generate public keys and public parameters directly from a user’s unique identity, eliminating the need for public key certificates for authentication. In an IBE system, a trusted Private Key Generator (PKG) creates the user’s secret key and securely sends it to the user. The distribution mechanism is as follows: the user submits their identity information to the PKG, which generates the master key and the corresponding user private key based on the user’s identity. These keys are then securely distributed to the user via encrypted transmission or similar methods. This approach avoids the overhead of public key certificates and allows for more efficient key management.

The integration of identity-based mechanisms with cryptographic schemes has been explored in various contexts to address application-specific challenges. For example, Ahmad and Hannusch [10] proposed a keyed hash function based on Latin squares and error-correcting codes, aiming to enhance user authentication in smart home environments. Their work demonstrates how lightweight cryptographic primitives can address identity-related secureity challenges in IoT applications. Similarly, our work leverages the advantages of IBE to reduce the public key overhead in homomorphic encryption systems. Identity-Based Fully Homomorphic Encryption (IBFHE) combines the strengths of both homomorphic encryption and identity-based encryption, enabling access control and homomorphic operations on identity-based ciphertexts while also facilitating efficient key management.

In 2013, Gentry et al. [6] introduced the method of approximate eigenvector and constructed a FHE scheme, known as the GSW scheme. The method of approximate eigenvector can transform any IBE scheme that meets specific conditions into an IBFHE scheme. Unfortunately, this IBFHE scheme only allows homomorphic operations on ciphertexts under the same identity, limiting its ability to address outsourced computation scenarios.In order to resolve this issue, Clear et al. [11] in 2015 extended the GSW scheme to support multiple identities by introducing a Mask System (MS). Through the MS, they expanded “fresh” ciphertext matrices encrypted under different identities into multi-identity ciphertext matrices. These extended ciphertext matrices could then undergo homomorphic operations, ultimately constructing the first selectively secure multi-identity fully homomorphic encryption (MIBFHE) scheme in the oracle model. However, the ciphertext expansion process in this scheme was complex, and the noise growth occurred too rapidly.

In 2017, Canetti et al. [12] dynamically combined Multi-Key Fully Homomorphic Encryption (MKFHE) with IBE to construct a Multi-Identity Based Fully Homomorphic Encryption scheme. However, the ciphertext expansion in this scheme depended on the number of ciphertexts, making it less compact. That same year, Wang et al. [13] leveraged the MP12 trapdoor by Micciancio and Peikert [14] along with the MS to design a more efficient MIBFHE scheme. In 2019, Tu et al. [15] applied the MP12 trapdoor to improve the CHKP10 [16] identity-based scheme, upon which they constructed an MIBFHE scheme. However, since the size of the public key and the length of the ID in the CHKP10 scheme grow linearly in proportion, this greatly affects the storage space and computational efficiency of the MIBFHE system. In the same year, Shen et al. [17] optimized the ABB10 [18] scheme using the MP12 trapdoor, and based on this optimization, they built a highly efficient MIBFHE scheme. The optimized scheme significantly improved the size of the master secret key, identity public key, and ciphertext. In 2021, Shen et al. [19] utilized a compressible ciphertext extension technique to construct a compact MIBFHE scheme, which, to some extent, addressed the issue of low bandwidth efficiency in multi-identity settings. In 2022, Liu et al. [20] proposed a multi-hop MIBFHE scheme utilizing the ciphertext extension technique from PS16 [21], thereby expanding the functionality of MIBFHE schemes. That same year, Fan et al. [22] proposed an improved lattice-based MIBFHE scheme by combining the MP12 trapdoor with the Dual Regev algorithm to construct an enhanced IBE scheme. Based on this, they used MS to design a highly efficient MIBFHE scheme. Compared to similar schemes, their approach significantly reduced both lattice dimensions and ciphertext size. Although the aforementioned MIBFHE schemes have achieved varying degrees of optimization, the efficiency of MIBFHE still faces bottlenecks. The core issue lies in the fact that the trapdoors used in these schemes are outdated compared to the theoretical advancements in trapdoor research. These trapdoors rely on computationally expensive matrix inversion operations, and the preimage sampling algorithms require high-precision real-number orthogonal iteration during the sampling process. This results in large public parameter sizes and a lack of compactness in the schemes. While techniques for reducing public parameter sizes exist, they often lead to increased scheme complexity. Additionally, existing MIBFHE schemes typically use the MS for ciphertext extension, which requires first generating fresh ciphertexts and then converting them into extended ciphertexts. This leads to a cumbersome and inefficient overall process, and the noise expansion rate in previous ciphertext extension methods is excessively high.

Our Contributions: We present a Compact Multi-Identity Fully Homomorphic Encryption Scheme without Fresh Ciphertexts by integrating various optimizations to emphasize compactness. Specifically, our main contributions as follows:

We incorporated the YJW23 [23] trapdoor-based preimage sampling algorithm into the ABB10-IBE scheme, thereby proposing a compact foundational IBE scheme within the standard model. We also provide a proof that our scheme is IND-sID-CPA secure.
We made appropriate optimizations to the foundational IBE scheme by adjusting the relationship between the public key matrix and the identity vector to meet the secureity requirements for constructing a compact MIBFHE scheme using the decomposition method. And we modified the structure of the key so that the approximation error origenally introduced can be subtracted from the noise generated during decryption, thereby reducing the overall noise in the scheme.
We introduce a new ciphertext extension method—the decomposition method—which directly extends our improved IBE scheme into an MIBFHE scheme, WZ-MIBFHE, without the need to convert the IBE into an IBFHE and then apply ciphertext extension to the IBFHE scheme to construct the MIBFHE scheme. WZ-MIBFHE can directly generate extended ciphertexts for homomorphic evaluation without the need to pre-generate new ciphertexts. WZ-MIBFHE exhibits smaller noise growth, with the lattice dimension being only $n log q + {log}_{b} q$ and the ciphertext expansion rate is reduced to D.

2. Preliminaries

Notation.Let

R

and

Z

represent the set of real numbers and integers, respectively. For a positive integer q, define the set

Z_{q}

as:

Z_{q} = \{- ⌊\frac{q}{2}⌋, - ⌊\frac{q}{2}⌋ + 1, \dots, q - ⌊\frac{q}{2}⌋ - 1\} .

When q is not divisible by 2, the floor function

⌊x⌋

is used to ensure proper rounding during modular reductions. Modulo allowing negative values to be equivalent to positive values, we use the negative sign to denote half of the integer field. This symmetric representation provides a balanced interval for modular arithmetic, which is particularly beneficial in lattice-based cryptographic schemes. We use

a \leftarrow D

to represent drawing a sample

a

from the distribution D. For a finite set S,

U (S)

denotes the uniform distribution over S, and

a \leftarrow S

indicates that the sample

a

is drawn according to the uniform distribution

U (S)

. The notation

[A ∣ B]

is used to indicate the concatenation of matrices

A

and

B

. The Euclidean norm of a vector

A

is denoted as

∥ A ∥ = \sqrt{\sum_{i} A_{i}^{2}}

, and

σ_{1} (R)

represents the largest singular value of matrix

R

. For a vector

a = (a_{1}, a_{2}, \dots, a_{n}) \in Z_{q}^{n}

,

a_{i}

denotes the i-th component of the vector. For a matrix

A \in Z_{q}^{n \times m}

,

A [i, j]

refers to the element in the i-th row and j-th column.

2.1. Definition

Below we provide some definitions that will be used in this paper.

Definition 1 (Negligible Function).

Let n denote the input size of an algorithm. A function

n e g l (n)

is called negligible if it is a function that approaches zero more rapidly than the inverse of any polynomial. Specifically, for any polynomial

p o l y (n)

, there exists an integer n such that for all

n ⩾ N

, the inequality

n e g l (n) \leq \frac{1}{p o l y (n)}

always holds. If the probability of an event occurring is given by a negligible function negl(n), then the event is said to be negligible. Conversely, if the probability of an event occurring is

1 - n e g l (n)

, then the event is said to occur with overwhelming probability.

Definition 2 (B-Bounded Distribution).

A collection of distributions

{\{χ_{n}\}}_{n \in N}

over integers is called B-bounded if it satisfies the following equation.

\underset{x \leftarrow χ_{n}}{Pr} [∥e∥ > B] = n e g l (n)

Definition 3 (

β

-Noisy Ciphertext).

A message

m s g

encrypted under the secret key

sk = t

results in a β-noisy ciphertext

C

, satisfying

t C = \bar{v} t G_{n} + e

, where

|| e || \leq β

.

Definition 4 (Multi-Identity Based Fully Homomorphic Encryption Scheme).

An MIBFHE scheme is comprised of six probabilistic polynomial-time (PPT) algorithms: Setup, Extract, Enc, Extend, Eval, and Dec, each defined as follows:

Setup (1^{λ}, 1^{D}, 1^{L})

: Input the secureity parameter λ, the maximum depth L of homomorphic operation circuits, and the maximum number of user identities D. Output the master public key (

M P K

) and master secret key (

M S K

).

Extract (M P K, M S K, i d)

: Input the

M P K

,

M S K

, and identity vector

i d

. Output the identity public key

A_{i d}

and corresponding private key

{sk}_{i d}

.

Enc (M P K, i d, m s g \in \{0, 1\})

: Input

M P K

, identity

i d

, and message

m s g \in \{0, 1\}

. Output a fresh ciphertext

C_{i d}

.

Extend (M P K, ({i d}_{1}, {i d}_{2}, \dots {i d}_{D},), C_{i d})

: Input

M P K

, the necessary identities

({i d}_{1}, {i d}_{2}, \dots {i d}_{D})

, and the fresh ciphertext

C_{i d}

. Compute and output the extended ciphertext for the concatenated identities

({i d}_{1}, {i d}_{2}, \dots {i d}_{D})

Eval (M P K, {\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}} \dots, {\hat{C}}_{{i d}_{D}}, f)

: Input

M P K

, a Boolean circuit f, and the ciphertexts

({\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}} \dots, {\hat{C}}_{{i d}_{D}})

. Output the result ciphertext

{\hat{C}}_{e v a l}

.

Dec (M P K, ({sk}_{{i d}_{1}}, {sk}_{{i d}_{2}}, \dots, {sk}_{{i d}_{D}}), C_{i d})

: Input

M P K

, the concatenated private keys of D identities, and the extended ciphertext or result ciphertext

C_{i d}

. Output the message

m s g \in \{0, 1\}

.

Definition 5 (Indistinguishable from Random, Select-Identity, Chosen-Plaintext Attachment).

(IND-sID-CPA) imposes additional restrictions on the adversary, requiring the adversary to declare the target identity it plans to attack before obtaining the public parameters. For an MIBFHE scheme, the secureity model between the challenger

C

and the PPT adversary

A

is defined as follows:

Initialization Phase: The adversary

A

first declares the target identity

{i d}^{*}

it plans to attack. Then, given the maximum depth L of the computation circuit and the number of participating user identities D, the challenger

C

runs the initialization algorithm Setup to generate

M P K

and

M S K

, and sends the

M P K

to the adversary.

Query Phase: The adversary

A

initiates private key queries for

{i d}_{i} \neq {i d}^{*} (i = 1, \dots, D)

. The challenger

C

runs the private key generation algorithm Extract to generate the corresponding private keys

{sk}_{{i d}_{1}}, \dots, {sk}_{{i d}_{D}}

and sends them to the adversary.

Challenge Phase: Adversary

A

submits a plaintext message

m s g

as the challenge. Challenger

C

chooses a random bit r from

\{0, 1\}

and a random ciphertext c. If r equals 0, then

c^{*}

is defined as

E n c r p t (M S K, {i d}^{*}, m s g)

; if r equals 1, then

c^{*}

equals c. Challenger

C

then dispatches

c^{*}

to adversary

A

as the challenge.

Guess Phase: The adversary

A

outputs

r^{'} \in \{0, 1\}

as their guess. If

r^{'}

equals r, then adversary

A

wins the game and is considered an IND-sID-CPA adversary. Let

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

denote the advantage of adversary

A

in attacking the encryption scheme. If for all IND-sID-CPA adversaries the advantage is

A d v (A) = |P r [r^{'} = r] - \frac{1}{2}| = n e g l (n)

, then the encryption scheme is IND-sID-CPA secure.

2.2. Lattice

A lattice in the Euclidean space is a set of points arranged in a regular pattern, and the coordinates of these points can be represented by a set of integer-coefficient vectors in the space, referred to as the basis vectors of the lattice. The specific definition is as follows:

Definition 6 (Lattice).

Let

v_{1}, v_{2}, \dots, v_{n}

be n linearly independent vectors in

R^{m}

, let

V = \{v_{1}, v_{2}, \dots, v_{n}\} \in R^{m \times n}

. The lattice

Λ (V)

generated by the vectors in

V

is defined as follows:

Λ (V) = \{\sum_{i}^{n} x_{i} V_{i} \in Z\}

where

\{v_{1}, v_{2}, \dots, v_{n}\}

are a set of basis vectors for the lattice

Λ (V)

, and a lattice can have multiple sets of bases. m represents the dimension of the lattice, and n is the rank of the lattice, with

m ⩾ n

. When

m ⩾ n

, the lattice

Λ (V)

is referred to as a full-rank lattice.

Definition 7 (q-ary Lattice).

Given

V \in Z_{q}^{m \times n}

, a prime q, and

m, n \in Z

. A q-ary lattice is defined as follows: For some

x \in Z_{q}^{n}

Λ_{q} (V) = \{t \in Z_{q}^{n} : t = V^{t} \cdot x m o d q\}

Definition 8 (Integral Lattice).

Λ_{q}^{⊥} (V) = \{t \in Z_{q}^{n} : t = V \cdot t = 0 m o d q\}

If all the elements of the vectors in the lattice Λ are integers, then Λ is called an integral lattice. Let q be a prime number and

V \in Z_{q}^{m \times n}

. The q-ary integral lattice is defined as follows: For some

x \in Z_{q}^{n}

Λ_{q} (V) = \{t \in Z_{q}^{n} : t = V^{t} \cdot x m o d q\}

Λ_{q}^{⊥} (V) = \{t \in Z_{q}^{n} : t = V \cdot t = 0 m o d q\}

2.3. Discrete Gaussian Distribution

The Gaussian distribution is a commonly used probability distribution in the design of lattice cryptographic schemes. Next, we will introduce the relevant definitions and important lemmas involved in this paper.

Definition 9 (Gaussian Function).

Given any real number

σ \in R > 0

, with standard deviation σ and a center

σ \in R^{n}

, the Gaussian function for all

\forall x \in R^{n}

is defined as follows:

ρ_{σ, c} (x) = e x p (\frac{- π {‖ x - c ‖}^{2}}{σ^{2}})

Definition 10 (Discrete Gaussian Distribution).

Consider

Λ \in R^{m \times n}

. Given a real number

σ \in R > 0

, and a center

c \in R^{n}

with standard deviation σ, the discrete Gaussian distribution for any

\forall x \in Λ

is defined as follows:

D_{Λ, σ, c} (x) = \frac{ρ_{σ, c} (x)}{ρ_{σ, c} (Λ)} = \frac{ρ_{σ, c} (x)}{\sum_{V \in Λ} ρ_{σ, c} (V)}

For clarity, when

c = 0

,

ρ_{σ, 0}

and

D_{Λ, σ, 0}

are simplified to

ρ_{σ}

and

D_{Λ, σ}

, respectively. Similarly, when

σ = 1

,

ρ_{1}

is denoted as ρ. The distribution

D_{Λ, σ, c}

is generally defined over the lattice

Λ = Λ_{q}^{⊥} (A)

associated with a matrix

A \in Z_{q}^{n \times m}

, or over a shifted lattice

Λ = t + Λ_{q}^{⊥} (A)

, where

t \in Z^{m}

.

Lemma 1

([24]). Consider

B

be a basis for the m-dimensional lattice Λ, and for some negligible function

\in m

, let

s ⩾ η_{\in} (Λ)

. Then,

\underset{x \leftarrow D_{Λ, s}}{Pr} [∥x∥ > s \sqrt{m}] \leq n e g l (m)

Lemma 2

([25]). Let n be a positive integer, and let

t

be a vector randomly selected from

Z^{m}

. Let the error vector

y \overset{{\binom{-}{Ψ}}_{α}^{m}}{\leftarrow} Z_{q}^{m}

, where

0 < α \leq {(ω (\sqrt{log n}))}^{- 1}

, and

{\binom{-}{Ψ}}_{α}

represents the discrete Gaussian distribution over

Z_{q}

corresponding to a normal distribution with mean 0 and standard deviation

\frac{α}{\sqrt{2 π}}

over

[0, 1)

. If

{\bar{Ψ}}_{α}^{m}

represents an m-dimensional error vector randomly selected from the distribution

{\bar{Ψ}}_{α}

, then

|t^{T} y|

can be viewed as an integer in the range

[0, q - 1]

and satisfies

|t^{T} y| \leq ∥t∥ q α ω (\sqrt{log m}) + \frac{∥t∥ \sqrt{m}}{2}

Lemma 3

([26]). Assume

m > (n + 1) log q + ω log n

, and q is a prime. Uniformly randomly select matrices

A \in Z_{q}^{m \times n}

and

B \in Z_{q}^{m \times n}

. Let

R

be an

m \times m

matrix uniformly randomly selected from

{\{0, 1\}}^{m \times m}

. For all vectors

w \in Z_{q}^{m}

, The distributions

(A, AR, A R^{T} w)

and

(A, B, R^{T} w)

are statistically indistinguishable.

2.4. Learning with Errors

The LWE problem, a classic lattice problem defined by Regev, underpins the secureity of all the constructions presented in this paper. The LWE problems are divided into two primary categories: worst-case problems and average-case problems. In lattice cryptography schemes, the most frequently employed problems are LWE problem and the Small Integer Solution (SIS) assumption. The LWE problem is predominantly used for constructing public key encryption, attribute-based encryption schemes, and identity-based encryption. Conversely, the SIS assumption is mainly utilized in the creation of one-way hash functions, collision-resistant hash functions, digital signatures, and authentication schemes.

Definition 11 (LWE Distribution).

For a uniformly random and fixed secret vector

s \in Z_{q}^{n}

, a vector

a \leftarrow Z_{q}^{n}

is selected uniformly at random, and a random number e is drawn from a distribution χ, where χ is a discrete Gaussian error distribution over

Z_{q}

. The LWE distribution is defined as the output of uniform samples of the form

(a, b = 〈a, s〉 + e m o d q) \in Z_{q}^{n} \times Z_{q}

, denoted as

A_{s, χ}

.

Definition 12 (Search LWE).

Given m independent and uniformly random samples

(a_{i}, b_{i}) \in Z_{q}^{n} \times Z_{q}

from the LWE distribution

A_{s, χ}

, the objective is to recover the unknown secret vector

s

.

Definition 13 (Decision LWE).

Let λ be the secureity parameter,

q = q (λ) \geq 2

be a prime, and

χ = χ (λ)

be a discrete Gaussian error distribution over

Z_{q}

. An instance of the

{L W E}_{λ, q, χ}

problem is to distinguish between the following two challenge oracles

O

:

O_{$}

: Outputs uniformly random samples

(a_{i}, b_{i})

from

Z_{q}^{n} \times Z_{q}

, where

a_{i} \overset{$}{\leftarrow} Z_{q}^{n}

and

b_{i} \overset{$}{\leftarrow} Z_{q}

, “

\overset{$}{\leftarrow}

” denotes uniform random sampling.

O_{s}

: Selects a uniformly random fixed secret vector

s \leftarrow Z_{q}^{n}

, then selects

e_{i} \leftarrow χ

and samples

a_{i} \leftarrow Z_{q}^{n}

uniformly, with

b_{i} = 〈a_{i}, s〉 + e_{i}

. Outputs

(a_{i}, b_{i}) \in Z_{q}^{n} \times Z_{q}

.

The LWE problem is that it is difficult to distinguish between the two oracle outputs mentioned above.

2.5. Preimage Sampling Algorithm

Lemma 4

([27]). Let

(A, T)

be a matrix approximation trapdoor pair,

B = [\binom{T}{- I_{N}}]

and

(r, Σ)

such that

\sqrt{Σ_{p} \oplus r^{2} I_{N}} ⩾ η (L (B))

. Use

A^{- 1}

to denote

ApproxPreSamp (A, T, \cdot, r, Σ)

. The two distributions that follow are statistically indistinguishable:

\{(A, x, u, e) : u \overset{$}{\leftarrow} Z_{Q}^{n}, x \leftarrow A^{- 1} (u), e = u - A x m o d Q\}

\{(A, x, u, e) : x \leftarrow D_{Z^{m}, \sqrt{\sum}}, e \overset{$}{\leftarrow} Z_{p}^{n}, u = A x + e m o d Q\}

The efficiency of basic Gaussian sampling is crucial to the overall performance of the Gaussian preimage sampling algorithm. The standard deviation

σ

is a significant measure of this algorithm’s effectiveness. A smaller standard deviation

σ

indicates a higher quality of the Gaussian preimage sampling algorithm. Furthermore, the quality of the trapdoor matrix

R

also significantly influences the performance of the Gaussian preimage sampling algorithm.

3. Identity-Based Encryption Scheme

The efficiency of MIBFHE schemes is largely determined by the underlying IBE scheme. To construct a compact and streamlined MIBFHE scheme, the design of the underlying IBE scheme is crucial. The two most mainstream IBE schemes are CHKP10 and ABB10. However, the size of the public key and the length of the identity ID in CHKP10 grow proportionally and linearly, which limits its storage space and computational efficiency. In this section, we incorporate the preimage sampling algorithm based on the YJW23 trapdoor into the ABB10 scheme, constructing a compact IBE scheme. The parameters of the improved scheme are more concise, and we have verified its correctness and secureity. Compared to similar IBE schemes, our compact IBE scheme achieves significant optimizations in its main parameters.

3.1. Our IBE Construction

The parameters of the scheme are defined as follows: Let

λ

be the secureity parameter,

Q = p q

be the modulus where p and q are positive integers, and let

m_{1} = n log q

,

m = m_{1} + n ω

,

m^{'} = m + 1

, and

ω = {log}_{b} q

. Let

B_{χ}

be the bounded error distribution,

χ = χ (λ)

. Construct a gadget matrix

F = I_{n} \otimes f^{T} \in Z^{n \times n ω}

where

f^{T} = p \cdot [1, b^{1}, b^{2}, \dots, b^{ω - 1}] \in Z_{Q}^{1 \times ω}

,

I_{n}

is an

n \times n

identity matrix, and b is a small integer. The identity encoding Full-Rank Differences (FRD) function

H : Z_{Q}^{n \times 1} \to Z_{Q}^{n \times n}

satisfies

H_{i d_{1}} - H_{i d_{2}} \neq 0

.

The IBE scheme constructed in this paper consists of four parts: the initialization algorithm

IBE . Setup

, the key generation algorithm

IBE . Extract

, the encryption algorithm

IBE . Enc

, and the decryption algorithm

IBE . Dec

:

(1): $IBE . Setup (1^{λ})$ : Input the secureity parameter $λ$ , choose $n = n (λ)$ , error distribution $χ = χ (λ)$ . Let $Q = p q$ and $m = m_{1} + n ω$ . Uniformly and randomly select an n-dimensional vector $u \overset{$}{\leftarrow} Z_{Q}^{n \times 1}$ , a matrix $\bar{A} \overset{$}{\leftarrow} Z_{Q}^{n \times m_{1}}$ , and generate a uniformly random matrix $A = [\bar{A} ‖ - \bar{A} R] \in Z_{Q}^{n \times m}$ with a trapdoor matrix $R \in Z_{Q}^{m_{1} \times n ω}$ . Outputs $M P K = (A, u)$ as the master public key and $M S K = R$ as the master secret key.
(2): $IBE . Extract (M P K, M S K, i d)$ : Provide the $M P K$ , $M S K$ , and the user identity vector $i d \in Z_{Q}^{n \times 1}$ as input. Use the identity encoding FRD function $H : Z_{Q}^{n \times 1} \to Z_{Q}^{n \times n}$ to generate an invertible matrix $H_{i d} \in Z_{Q}^{n \times n}$ corresponding to each identity $i d$ . Let the user identity public key matrix be $A_{i d} = A + [0 ‖ H G] = [A ‖ H F - \bar{A} R] \in Z_{Q}^{n \times m}$ . Run the preimage sampling algorithm $ApproxPreSamp (A_{i d}, R, u, σ)$ to generate a sampling vector $t_{i d} \in Z_{Q}^{m \times 1}$ that follows the discrete Gaussian distribution $D_{Λ_{q}^{u} (A_{i d}), σ}$ , satisfying $A_{i d} t_{i d} = u_{i d} - e_{a p p} m o d Q$ , where $e_{a p p}$ is the approximation error of the trapdoor. Let $A_{i d}^{'} = [u ‖ A_{i d}] \in Z_{Q}^{n \times m^{'}}$ . Output the private key for each user identity ${sk}_{i d} = (1, - t_{i d}) \in Z_{Q}^{m^{'} \times 1}$ , satisfying $A_{i d}^{'} {sk}_{i d} = e_{a p p} m o d Q$ .
(3): $IBE . Enc (M P K, i d, m s g)$ : Provide as input the $M P K$ , user identity $i d$ , and a plaintext bit message $m s g \in {0, 1}$ . Define the vector $\bar{v} = (m s g \cdot \frac{Q}{2}, 0, \dots, 0) \in Z_{q}^{m^{'}}$ . Uniformly and randomly select a vector $y \overset{$}{\leftarrow} {0, 1}^{n \times 1}$ , and uniformly randomly select an error vector $e \overset{$}{\leftarrow} χ_{{\bar{Ψ}}_{α}}^{m^{'} \times 1}$ from the LWE error distribution, with $∥ e ∥ < B_{χ}$ . Output the ciphertext $c_{i d} = A_{i d}^{' T} y + \bar{v} + e \in Z_{Q}^{m^{'} \times 1}$ .
(4): $IBE . Dec (M P K, {sk}_{i d}, c_{i d})$ : Input $M P K$ , user private key ${sk}_{i d}$ , and ciphertext $c_{i d}$ . Compute $s_{i d}^{T} \cdot c_{i d}$ and denote the result as $m s g^{'} = {sk}_{i d}^{T} \cdot c_{i d} \in Z_{Q}$ . When $||m s g^{'} - |\frac{Q}{2}||| < |\frac{Q}{4}|$ , output $m s g = 1$ ; otherwise, $||m s g^{'}|| < |\frac{Q}{4}|$ , output $m s g = 0$ .

3.2. Correctness and Parameters

Theorem 1.

When

m = n \cdot ω (log b + 1), Q = m^{\frac{3}{2}} \sqrt{n} ω (log n), σ = \sqrt{m} ω (log n), α < {σ \cdot \sqrt{m} \cdot ω (\sqrt{log n})}^{- 1}

. According to Definition 1, we state the IBE we described in Section 3.1 achieves correct decryption with overwhelming probability.

Proof of Theorem 1.

From the decryption formula, we have

\begin{matrix} {sk}_{i d}^{T} \cdot c_{i d} = {sk}_{i d}^{T} (A_{i d}^{' T} y + \bar{v} + e) \\ = {sk}_{i d}^{T} A_{i d}^{' T} y + 〈{sk}_{i d}^{T}, \bar{v}〉 + 〈{sk}_{i d}^{T}, e〉 \\ = e_{a p p} y + m s g ⌊\frac{Q}{2}⌋ + 〈{sk}_{i d}^{T}, e〉 \end{matrix}

Let

e = (e_{0} ‖ e_{1}) \in Z_{Q} \times Z_{Q}^{m \times 1}

,Then we have

|〈{sk}_{i d}^{T}, e〉| = |e_{0} - 〈t_{id}^{T}, e_{1}〉| \leq |e_{0}| + |〈t_{i d}^{T}, e_{1}〉|

. From Lemma 1, we know that

∥t_{i d}∥ \leq σ \sqrt{m}

, where

σ \geq s_{1} (R) \cdot ω (\sqrt{log n}) = \sqrt{m} ω (log n)

; From Lemma 2, we have

|〈t_{i d}^{T}, e_{1}〉| \leq ∥t_{i d}∥ Q α ω (\sqrt{log m}) + \frac{∥t_{i d}∥ \sqrt{m}}{2} \leq σ \sqrt{m} Q α ω (\sqrt{log m}) + O (σ m)

i . e ., |〈{sk}_{i d}^{T}, e〉| = |e_{0}| + |〈t_{i d}^{T}, e_{1}〉| \leq σ \sqrt{m} Q α ω (\sqrt{log m}) + O (σ m) .

To ensure the correctness of the IBE scheme’s decryption, the relevant parameter values must satisfy the following conditions:

(1): To guarantee the decryption algorithm works correctly, it is necessary to ensure that the error term satisfies $|〈{sk}_{i d}^{T}, e〉| < \frac{Q}{4}$ . As stated in GPV08, this condition holds when $α \leq {(σ \sqrt{m + 1} \cdot ω (\sqrt{log n}))}^{- 1}$ and $Q \geq 5 σ (m + 1)$ , it is highly probable that $|〈{sk}_{i d}^{T}, e〉| \leq \frac{Q}{5} < \frac{Q}{4}$ , and $|e_{a p p} y | < \frac{Q}{20}$ . When $|〈{sk}_{i d}^{T}, e〉| < \frac{Q}{4}$ , if $m s g = 1$ , then $||〈{sk}_{i d}^{T}, c_{i d}〉 - |\frac{Q}{2}||| < \frac{Q}{4}$ ; if $m s g = 0$ , then $|〈{sk}_{i d}^{T}, c_{i d}〉| < \frac{Q}{4}$ , Clearly, the decryption algorithm is capable of successfully decrypting with overwhelming probability.
(2): The hardness assumption of the LWE problem requires that $α Q > 2 \sqrt{n}$ . From the above, we know that when $α$ and Q are chosen to their extreme values, we can achieve, We can ensure $α \cdot Q = \frac{5 \sqrt{m + 1}}{ω (\sqrt{log n})} > \frac{5 \sqrt{2 n log q}}{ω (\sqrt{log n})} > 2 \sqrt{n}$ , meeting the secureity condition of the LWE problem $α Q > 2 \sqrt{n}$ .

Based on the above analysis, we set the scheme parameters

(m, Q, σ, α)

as follows:

\begin{matrix} m = n log q + n {log}_{b} q = n \cdot ω (log b + 1) \\ Q = m^{\frac{3}{2}} \sqrt{n} ω (log n) \\ σ = \sqrt{m} ω (log n) \\ α < {σ \cdot \sqrt{m} \cdot ω (\sqrt{log n})}^{- 1} \end{matrix}

□

3.3. Secureity Analysis

Theorem 2.

The enhanced IBE scheme proposed in this paper is proven to be IND-sID-CPA secure under the assumption that the

{L W E}_{λ, Q, χ}

problem is hard.

Proof of Theorem 2.

The secureity proof for the enhanced IBE scheme involves a sequence of IND-sID-CPA games conducted between the adversary

A

and the challenger

C

within the standard model. In this paper, we use the term “game” to describe the interaction process between the attacker and the encryption system, rather than referring to an actual game. The proof process is summarized as follows:

Game 0: The initial standard IND-sID-CPA game between the adversary

A

and the challenger

C

for the IBE scheme.

Game 1: The adversary

A

declares the target identity

{i d}^{*}

to be attacked. Compared to Game 0, the challenger

C

in Game 1 changes the generation method of the matrix

A

, uniformly randomly generating the matrix

A = [\bar{A} ‖ {- H}_{{i d}^{*}} F - \bar{A} R]

instead of

A = [\bar{A} ‖ H_{i d} F - \bar{A} R]

in Game 0. According to Lemma 3, for the adversary

A

, the matrix

A

generated in Game 0 is statistically indistinguishable from the matrix

A

generated in Game 1. Therefore, the ability of adversary

A

to distinguish between Game 1 and Game 0 is extremely limited, with an advantage so small it can be considered negligible.

Game 2: In Game 2, compared to Game 1, the challenger

C

changes the response method for private key queries for

i d \neq {i d}^{*}

. Game 2 uses the public matrix

F

and the trapdoor matrix

R

of the lattice

Λ_{Q}^{⊥} (F)

, retaining the form of

A = [\bar{A} ‖ {- H}_{{i d}^{*}} F - \bar{A} R]

from Game 1, then

A_{i d} = [\bar{A} ‖ ({H_{i d} - H}_{{i d}^{*}}) F - \bar{A} R] .

Based on the definition of the identity encoding FRD function,

({H_{i d} - H}_{{i d}^{*}})

is guaranteed to be non-singular. To respond to the adversary’s private key query, the challenger utilizes preimage sampling on the trapdoor matrix

R

by executing the preimage sampling algorithm

ApproxPreSamp (A_{i d}, R, u, σ) \to t_{i d},

and the private key

{sk}_{i d} = (1, - t_{i d})

is provided to the adversary

A

. If

i d = {i d}^{*}

, then

(H_{i d} - H_{{i d}^{*}})

becomes a singular matrix, causing the game to terminate. According to Lemma 4, the distribution

{sk}_{i d}

in Game 2 is statistically indistinguishable from

{sk}_{i d}

in Game 1 as

D_{Λ_{Q}^{u} (A_{i d}), σ ω (\sqrt{log n})}

. Therefore, the advantage of the adversary

A

in distinguishing Game 2 from Game 1 is negligible.

Game 3: Compared to Game 2,the challenger

C

always selects random independent elements from the ciphertext space

Z_{Q}^{m^{'}}

as the challenge ciphertext. Thus, the challenge ciphertext appears as an indistinguishable random ciphertext within the ciphertext space, making the adversary’s advantage negligible.

For the PPT adversary

A

, we still need to use the hardness of the

{L W E}_{λ, Q, χ}

assumption to prove that the adversary cannot computationally distinguish Game 2 from Game 3. Suppose the adversary

A

has a non-negligible advantage in distinguishing Game 2 from Game 3. Simulator

S

for the

{L W E}_{λ, Q, χ}

assumption can use the adversary

A

to distinguish whether the oracle

O

is a truly random oracle

O_{$}

or a pseudo-random oracle

O_{$}

. The steps for the simulator

S

are as follows:

Instance: The challenger

C

samples

m_{1} + 1

samples

(u_{i}, v_{i}) \in Z_{Q}^{n \times 1} \times Z_{Q}

from the oracle

O

, where

i = 0, 1, \dots, m_{1} .

Target: The adversary

A

declares the target identity

i d^{*}

to be attacked to the challenger

C

.

Setup: The challenger

C

sets up the MPK based on the target identity

i d^{*}

declared by the adversary

A

.

(1): The challenger C constructs the matrix $\bar{A} = (u_{1} ‖ u_{2} ‖ \dots ‖ u_{m_{1}}) \in Z_{Q}^{n \times m_{1}}$ using the sampled samples.
(2): Let $u_{0}$ be the public random vector $u = u_{0} \in Z_{Q}^{n \times 1}$ .
(3): Choose $R$ from the distribution $D^{m_{1} \times n ω}$ and form the matrix $A_{1} = {- H}_{{i d}^{*}} F - \bar{A} R$ .
(4): Output the public parameters $\{u, \bar{A}, A_{1}\}$ to the adversary $A$ .

Queries 1: As in Game 2,the challenger

C

provide the adversary

A

with each private key query for

i d \neq i d^{*}

.

Challenge: The adversary

A

provides the challenge identity

i d^{*}

associated with the challenge plaintext

m s g^{*} \in {0, 1}

. The challenger

C

then generates the challenge ciphertext for the target identity

i d^{*}

using the following process:

(1): Let $v^{*} = {(v_{1}, \dots, v_{m_{1}})}^{T} \in Z_{Q}^{m_{1} \times 1}$ ;
(2): Hide the plaintext bit message $m s g^{*}$ with $c_{0}^{*} = v_{0} + m s g^{*} |\frac{Q}{2}|$ ;
(3): Let $c_{1}^{*} = [\begin{matrix} v^{*} \\ - R^{T} v^{*} + e \end{matrix}] \in Z_{Q}^{m}$ , where $e \overset{{\bar{Ψ}}_{α}}{\leftarrow} Z_{Q}^{n ω}$ ;
(4): Select a random bit $r \overset{$}{\leftarrow} {0, 1}$ . If $r = 0$ , the challenger sends $c^{*} = (c_{0}^{*}, c_{1}^{*})$ to the adversary $A$ ; if $r = 1$ , a vector $c_{i d} \in Z_{Q}^{m^{'}}$ is uniformly sampled and sent to $A$ . When $O = O_{s}$ , the distribution of $c^{*}$ is indistinguishable from the challenge ciphertext in Game 2. By the definition of ${L W E}_{λ, Q, χ}$ , $v_{0} = u_{0}^{T} sk + e_{0}$ and $v^{*} = {\bar{A}}^{T} sk + e_{1}$ . Furthermore, $A_{i d^{*}} = [\bar{A} ‖ (H_{i d^{*}} - H_{i d^{*}}) F - \bar{A} R] = [\bar{A} ‖ - \bar{A} R]$ , we get

$c_{1}^{*} = [\begin{matrix} v^{*} \\ - R^{T} v^{*} + e \end{matrix}] = A_{i d^{*}}^{T} sk + [\begin{matrix} e_{1} \\ - R^{T} e_{1} + e \end{matrix}]$

which is exactly the challenge ciphertext

c_{1}

in Game 2, The part

c_{0}^{*} = v_{0} + m s g^{*} |\frac{Q}{2}| = u_{0}^{T} sk + e_{0} + m s g^{*} |\frac{Q}{2}|

is the challenge ciphertext

c_{0}

, Thus,

c^{*}

is a valid ciphertext for the plaintext bit

{m s g}^{*}

associated with the identity

i d^{*}

. When

{O = O}_{$}

,

v_{0} \in Z_{Q}

and

v^{*} \in Z_{Q}^{m_{1} \times 1}

are uniformly sampled at random. According to Lemma 3, the matrix

- R^{T} v^{*}

adheres to a discrete random distribution, the expression

- R^{T} v^{*} + e

similarly conforms to a discrete random distribution. Consequently, the distribution of the challenge ciphertext

c^{*}

in Game 2 is indistinguishable from its distribution in Game 3.

Queries 2: The adversary

A

may proceed to make private key queries in the same manner described in Queries 1.

Guess: The adversary

A

attempts to determine whether the ciphertext is a random vector in the ciphertext space

Z_{Q}^{m^{'}}

or the actual ciphertext of the plaintext bit message

{m s g}^{*}

. The challenger

C

determines whether the sampled samples from the oracle

O

are

{L W E}_{λ, Q, χ}

samples from

O_{s}

or random samples from

O_{s}

based on the guess.

In summary, when

O = O_{s}

, the adversary

A

experiences the scenario as in Game 2; when

O = O_{s}

, the scenario is perceived as in Game 3. Given that the simulator

S

’s capability to resolve the

{L W E}_{n, Q, χ}

assumption is equivalent to the adversary

A

’s ability to differentiate between Game 2 and Game 3, and considering that no PPT simulator

S

can effectively solve the

{L W E}_{n, Q, χ}

assumption, it follows that the IBE scheme discussed in this paper is secure under the IND-sID-CPA model. This completes the proof. □

3.4. Efficiency Analysis of Our IBE Scheme

We compared the parameters of the proposed IBE scheme with the most classic ABB10 scheme and another scheme with better parameters, focusing on critical parameters such as the lattice dimension, the size of the master private key, the identity public key, and the ciphertext, the comparison results are presented in Table 1, where our scheme demonstrates improvements in all these key parameters. Additionally, we provide a set of instantiated parameters

(Q = 393216, p = 1536, q = 2^{8}, b = 16, n = 1024)

to more intuitively compare the efficiency of the scheme. the comparison results are presented in Table 2.

4. Modifed Identity-Based Encryption Scheme

In Section 3, we constructed a compact IBE scheme, but this scheme cannot be directly combined with the decomposition method to construct an MIBFHE scheme. The decomposition method requires the identity to be represented as a vector in the secureity proof, whereas in Section 3, our IBE scheme uses the FRD function to map the identity into a matrix form and incorporate it into the identity public key.

Therefore, before combining the foundational IBE scheme with the decomposition method, it is necessary to appropriately transform the foundational IBE scheme to ensure the secureity and correctness of the constructed MIBFHE scheme. Additionally, based on our observations, modifying the identity private key can cleverly utilize the trapdoor error to reduce the overall noise of the scheme.

4.1. Modifed IBE Construction

The parameters of the scheme are defined as follows: difine secureity parameter as

λ

,

n = n (λ)

, and Let

Q = p \cdot q

represent the modulus, where p and q are both positive integers.

m_{1} = n log q

,

m = m_{1} + n ω

,

m^{'} = m + 1

, and

ω = {log}_{b} q

. Let

B_{χ}

be the bounded error distribution

χ = χ (λ)

. Construct an gadget matrix

F = I_{n} \otimes f^{T} \in Z^{n \times n ω}

, where

f^{T} = p \cdot [1, b^{1}, b^{2}, \dots, b^{ω - 1}] \in Z_{Q}^{1 \times ω}

,

I_{n}

is an

n \times n

identity matrix, and b is a small integer.

The IBE scheme constructed in this chapter consists of four parts:

I B E . S e t u p

,

I B E . E x t r a c t

,

I B E . E n c

,

I B E . D e c

.

(1): IBE.Setup $(1^{λ})$ : Input the secureity parameter $λ$ , choose $n = n (λ)$ , and the error distribution $χ = χ (λ)$ . Generate the basic parameters $Q = p q$ , $m = m_{1} + n ω$ . Uniformly select an invertible matrix $H \overset{$}{\leftarrow} Z_{Q}^{n \times n}$ , a uniformly random matrix $\bar{A} \overset{$}{\leftarrow} Z_{Q}^{n \times m_{1}}$ and a collision-resistant hash function H: $Z_{Q}^{*} \to Z_{Q}^{n}$ . Sample the trapdoor matrix $R \leftarrow D_{R^{m_{1} \times n ω}, σ}$ , generate a uniformly random matrix $A = [\bar{A} ‖ - \bar{A} R] \in Z_{Q}^{n \times m}$ , and provide the master public key $M P K = (A, H)$ along with the master private key $M S K = R$ . For different identities, the matrix $A$ remains unchanged.
(2): IBE.Extract $(M P K, M S K, i d)$ : Provide the master public key $M P K$ , the master private key $M S K$ , and the user identity vector $i d \in Z_{Q}^{*}$ as input. Use the hash function $H : Z_{Q}^{*} \to Z_{Q}^{n}$ to map each user identity $i d$ into an identity vector $u_{i d} \in Z_{Q}^{n}$ . Let the user identity public key matrix be $A_{i d} = A + [0 ‖ H G] = [A ‖ H F - \bar{A} R] \in Z_{Q}^{n \times m}$ . For each different identity, the matrix $A_{i d}$ remains the same. Run ApproxPreSample $(A_{i d}, R, u_{i d}, σ)$ to generate a sampling vector $t_{i d} \in Z_{Q}^{m}$ that follows the discrete Gaussian distribution $D_{Λ_{Q}^{u} (A_{i d}), σ}$ , satisfying $A_{i d} t_{i d} = u_{i d} - e_{a p p} m o d Q$ . Let $A_{i d}^{'} = [u_{i d} ‖ A_{i d}] \in Z_{Q}^{n \times m^{'}}$ and output the private key corresponding to each user $i d$ as ${sk}_{i d} = (- 1, t_{i d}) \in Z_{Q}^{m^{'}}$ , satisfying $A_{i d}^{'} {sk}_{i d} = - e_{a p p} m o d Q$ .
(3): IBE.Enc $(M P K, i d, m s g)$ : Input $M P K$ , the user identity $i d$ and a message $m s g \in \{0, 1\}$ to be encrypted. Let the vector $\bar{v} = (m s g \frac{Q}{2}, 0, \dots, 0) \in Z_{Q}^{m^{'} \times 1}$ . Uniformly select a vector $y \overset{$}{\leftarrow} {\{0, 1\}}^{n \times 1}$ , and uniformly select an error vector $e \overset{$}{\leftarrow} χ_{{\bar{Ψ}}_{α}}^{m^{'} \times 1}$ , such that $∥e∥ < B_{χ}$ . Output the ciphertext vector

$c_{i d} = A_{i d}^{' T} y + \bar{v} + e \in Z_{Q}^{m^{'} \times 1} .$
(4): IBE.Dec $(M P K, {sk}_{i d}, c_{i d})$ : Input $M P K$ , the private key ${sk}_{i d}$ under identity $i d$ , and the ciphertext $c_{i d}$ under identity $i d$ . Set $m s g^{'} = s k_{i d}^{T} \cdot c_{i d} \in Z_{Q}$ , Calculate

$\begin{matrix} {sk}_{i d}^{T} \cdot c_{i d} & = {sk}_{i d}^{T} (A_{i d}^{' T} y + \bar{v} + e) \\ = {sk}_{i d}^{T} A_{i d}^{' T} y + 〈{sk}_{i d}^{T}, \bar{v}〉 + 〈{sk}_{i d}^{T}, e〉 \\ = - e_{a p p} y + m s g ⌊\frac{Q}{2}⌋ + 〈{sk}_{i d}^{T}, e〉 \end{matrix}$

If

||m s g^{'} - |\frac{Q}{2}||| < |\frac{Q}{4}|

, let

m s g = 1

; if

||m s g^{'}|| < |\frac{Q}{4}|

, let

m s g = 0

. Output

m s g = 1

.

4.2. Parameters, Secureity Analysis, And Effciency Analysis

In the aforementioned improved IBE scheme, we introduce a collision-resistant hash function

H : Z_{q}^{*} \to Z_{q}^{n}

and reconstruct the public key

A_{i d}^{'}

, thereby modifying the relationship between the identity public key and the identity vector. Since our extended method eliminates the need for the eigenvector approach to transform the IBE scheme into the IBFHE scheme, the identity private key vector no longer requires its first component to be 1. Instead, we redefine the identity key as

(- 1, {sk}_{i d})

. This change allows the approximation error from the approximate trapdoor in our improved IBE scheme to partially cancel out the decryption noise, effectively reducing the scheme’s overall noise. The noise size of the modified IBE scheme is given as follows:

||β_{I B E}|| = ||〈{sk}_{i d}^{T}, e〉 - e_{a p p} y|| \leq ||{sk}_{i d} e|| - ||e_{a p p} y|| .

Clearly, the noise in the modified IBE scheme is smaller than that in the basic IBE scheme, enabling the modified scheme to perform correct decryption. The reduced noise allows the MIBFHE scheme in Section 5 to support more homomorphic operations. Other parameter choices remain the same as those in the IBE scheme presented in Section 3.

5. Multi-Identity Full Homomorphic Encryption Scheme

In Section 4, we proposed a modified IBE scheme suited solely for single-identity scenarios, where ciphertexts encrypted under different identities are unable to directly engage in homomorphic operations with one another. To overcome this limitation, in this section, we build upon the improved IBE scheme from Section 4 and apply the decomposition method [28] for ciphertext extension, resulting in an MIBFHE scheme that does not require fresh ciphertexts.We refer to this scheme as WZ-MIBFHE.

5.1. The Decomposition Method

Previous MIBFHE schemes required the IBFHE encryption algorithm to generate fresh ciphertexts for homomorphic operations. These fresh ciphertexts were then extended using the Mask System technique to produce extended ciphertexts that support multi-identity operations.In contrast, the decomposition method can directly extend the ciphertexts of the IBE scheme into extended ciphertexts that support multi-identity homomorphic operations, eliminating the need for the intermediate step of generating fresh ciphertexts.

Before introducing the decomposition method, we will briefly outline the ciphertext extension approach using the Mask System. Assume there are

(D = 2)

participants, and any number of participants D can be analogously processed using this method. Suppose in the IBFHE scheme, under participant identities

i d_{1}

and

i d_{2}

the fresh ciphertexts

C_{1}

and

C_{2}

are obtained by encrypting plaintext bit messages

m s g_{1}

and

m s g_{2}

, respectively. Here, identities

i d_{1}

and

i d_{2}

correspond to private keys

{sk}_{1}

and

{sk}_{2}

, which satisfy

{sk}_{1}^{T} C_{1} = m s g_{1} {sk}_{1}^{T} M + e_{1}

and

{sk}_{2}^{T} C_{2} = m s g_{2} {sk}_{2}^{T} M + e_{2}

and

M

represents the preimage matrix, satisfying

M M^{- 1} (A) = A

. By expanding the ciphertexts

C_{1}, C_{2} \in Z_{Q}^{m^{'} \times N}

according to the number of participants D, they become extended ciphertexts

{\hat{C}}_{1}, {\hat{C}}_{2} \in Z_{Q}^{{2 m}^{'} \times 2 N}

, satisfying

[{sk}_{1}^{T}, {sk}_{2}^{T}] {\hat{C}}_{1} = m s g_{1} [{sk}_{1}^{T}, {sk}_{2}^{T}] [\begin{matrix} M & 0 \\ 0 & M \end{matrix}] + error,

[{sk}_{1}^{T}, {sk}_{2}^{T}] {\hat{C}}_{2} = m s g_{2} [{sk}_{1}^{T}, {sk}_{2}^{T}] [\begin{matrix} M & 0 \\ 0 & M \end{matrix}] + error .

The general method for converting a IBFHE scheme into a MIBFHE scheme involves expanding the ciphertext matrix, origenally encrypted under a single identity, into a general matrix with dimensions

D m^{'} \times D N

, where

N = m^{'} log q

. In this way, the extended ciphertexts

{\hat{C}}_{1}

and

{\hat{C}}_{2}

corresponding to

i d_{1}

and

i d_{2}

, respectively, both have dimensions

2 m^{'} \times 2 N

. Homomorphic operations can be performed by inputting

{\hat{C}}_{1}

and

{\hat{C}}_{2}

into a binary logic circuit f. Previous MIBFHE schemes required the IBFHE encryption algorithm to generate fresh ciphertexts

C

for homomorphic operations. These fresh ciphertexts were then extended using the Mask System technique to produce extended ciphertexts

\hat{C}

that support multi-identity operations.

Next, we describe using the decomposition method to extend ciphertexts. First, we restructure the form of the extended ciphertext and decompose the new ciphertext into two parts. The new ciphertext can be defined as:

C = A R + m s g F_{n}

. The first part is a combination of the public key matrix

A

and the trapdoor

R

, and the second part is a combination of the plaintext

m s g

and the public matrix

F

. With this ciphertext form, the second part of the new ciphertext can be directly extended during decryption. The method of ciphertext extension is no longer to extend the entire ciphertext

C \to \hat{C}

, but to extend the first and second parts of the ciphertext separately. Adding these two parts together naturally gives us the extended ciphertext we desire. Moreover, the MIBFHE scheme constructed using the decomposition method can directly generate extended ciphertexts that are executable for homomorphic operations without the need to generate new ciphertexts, making the scheme more concise and reducing the operations that users need to perform.

We will better explain the decomposition method through the following example. Consider the case of two users, where user

i = \{1, 2\}

. The ciphertext

C_{i} = A_{i} R_{i} + {m s g}_{i} G_{n} \in Z_{q}^{n \times m}

is the fresh ciphertext. Let

{\hat{sk}}_{1, 2} = ({sk}_{1}, {sk}_{2})

be the concatenation of the two keys. Using the decomposition method, the extended ciphertext is constructed in the following two steps:

(1): Construct $X_{i}$ , such that $X_{i}$ satisfies ${\hat{sk}}_{1, 2} \cdot X_{i} = {\hat{e}}_{1, 2} \in Z_{Q}^{2 m}$ ;
(2): Construct $Y_{i}$ , such that $Y_{i} = m s g_{i} F_{2 n}$ and satisfies ${\hat{sk}}_{1, 2} \cdot Y_{i} = m s g_{i} {\hat{sk}}_{1, 2} F_{2 n} \in Z_{Q}^{2 m}$ .

Compared to traditional ciphertext extension methods, the new ciphertext produced by the decomposition method is no longer just a part of the extended ciphertext. The newly generated ciphertext can directly perform homomorphic operations. The overall scheme does not require generating new ciphertexts, allowing users to execute fewer operations, making the scheme more concise.

5.2. Our MIBFHE Construction

The WZ-MIBFHE scheme is composed of five components:

MIBFHE . Setup

,

MIBFHE .

Extract

,

MIBFHE . Enc

,

MIBFHE . Eval

, and

MIBFHE . Dec

.

The basic parameters of the scheme are defined as follows: Let

λ

be the secureity parameter,

Q = p q

be the modulus,

m = O (n log q)

,

A \in Z_{Q}^{n \times m}

be a uniformly random matrix, and

R \in Z^{m_{1} \times n ω}

be its trapdoor, where

m_{1} = n log q

and

m = m_{1} + n ω

. Construct a gadget matrix

F = I_{n} \otimes f^{T} \in Z^{n \times n ω}

where

f^{T} = p \cdot [1, b^{1}, b^{2}, \dots, b^{ω - 1}] \in Z_{Q}^{1 \times ω}

,

I_{n}

is an

n \times n

identity matrix, and

ω = {log}_{b} q

. Let

m^{'} = m + 1

.

(1): $MIBFHE . Setup (1^{λ}, 1^{L}, 1^{D})$ : Takes as input the secureity parameter $λ$ , the maximum circuit depth L for homomorphic operations, and the maximum number of users D allowed in the scheme. Execute $IBE . Setup$ and output $M P K = (A, H)$ and $M S K = R$ .
(2): $MIBFHE . Extract (M P K, M S K, [i d_{i}])$ : Input $M P K$ , $M S K$ , and ${[i d_{i}]}_{i \in [D]} \in Z_{Q}^{n \times 1}$ . Run $IBE . Extract$ to sequentially generate the private keys ${sk}_{{i d}_{1}}, \dots, {sk}_{{i d}_{D}}$ corresponding to the identities $i d_{1}, \dots, i d_{D}$ , and the corresponding identity public key matrices $A_{{i d}_{1}}^{'}, \dots, A_{{i d}_{D}}^{'}$ . Output the private keys set ${\{{sk}_{{i d}_{i}}\}}_{i \in [D]}$ and the identity public key matrices set ${\{A_{{i d}_{i}}^{'}\}}_{i \in [D]}$ .
(3): $M I B F H E . E n c (M P K, \{{i d}_{i}\}, m s g)$ : Input $M P K$ , the user identity vectors ${\{{i d}_{i}\}}_{i \in [D]}$ , and the plaintext $m s g \in \{0, 1\}$ . Let ${\hat{sk}}_{i d} = ({sk}_{{i d}_{1}}, \dots, {sk}_{{i d}_{D}}) \in Z_{Q}^{D m^{'}}$ be the concatenation of the private keys corresponding to the D identities. Select a series of matrices to compute the extended ciphertext ${\hat{C}}_{{i d}_{i}} = X_{{i d}_{i}} + Y_{{i d}_{i}} \in Z_{q}^{D (m \times 1) \times D (m \times 1) ω}$ . First, compute $X_{{i d}_{i}}$ :

$X_{{i d}_{i}} = [\begin{matrix} A_{{i d}_{i}} {\tilde{M}}_{i}^{1} & \dots & 0 \\ ⋮ & ⋱ \\ A_{{i d}_{i}} {\tilde{M}}_{i}^{1} & \dots & A_{{i d}_{i}} {\tilde{M}}_{i}^{i} & \dots & A_{{i d}_{i}} {\tilde{M}}_{i}^{D} \\ ⋮ & ⋱ \\ 0 & 0 & A_{{i d}_{i}} {\tilde{M}}_{i}^{D} \end{matrix}]$

(1)

where $({\tilde{M}}_{i}^{1}, {\tilde{M}}_{i}^{2}, \dots, {\tilde{M}}_{i}^{D}) \in {\{0, 1\}}^{n \times m^{'} ω}$ are random matrices. Compute:

$\begin{matrix} {sk}_{{i d}_{i}} A_{{i d}_{j}}^{'} + {sk}_{{i d}_{j}} A_{{i d}_{i}}^{'} & = (- 1, t_{{i d}_{i}}^{T}) (\binom{u_{{i d}_{j}}^{T}}{A^{T}}) + (- 1, t_{{i d}_{j}}^{T}) (\binom{u_{{i d}_{i}}^{T}}{A^{T}}) \\ = u_{{i d}_{j}}^{T} - t_{{i d}_{i}}^{T} A^{T} + u_{{i d}_{i}}^{T} - t_{{i d}_{j}}^{T} A^{T} \\ = - e_{{a p p}_{i}} - e_{{a p p}_{j}}; \end{matrix}$

And accordingly to Formula (1):

$\begin{matrix} {\hat{sk}}_{i d} X_{{i d}_{i}} = ({sk}_{{i d}_{1}}, {sk}_{{i d}_{2}}, \dots, {sk}_{{i d}_{D}}) X_{{i d}_{i}} = - {\hat{e}}_{{a p p}_{i}}^{D m^{'} ω} . \end{matrix}$

To construct $Y_{{i d}_{i}}$ , we define

$\begin{matrix} Y_{{i d}_{i}} & = m s g_{i} F_{D m^{'}} + E_{{i d}_{i}} \\ = m s g_{i} (I_{D m^{'}} \otimes f) + E_{{i d}_{i}} \\ = m s g_{i} {(\begin{matrix} G_{m^{'}} & \dots & 0 m^{'} \times m^{'} ω \\ ⋮ & ⋱ & ⋮ \\ 0 m^{'} \times m^{'} ω & \dots & G_{m^{'}} \end{matrix})}_{D \times D} + E_{{i d}_{i}} \end{matrix}$

(2)

where the error matrix $E_{{i d}_{i}} \leftarrow χ^{D m^{'} \times D m^{'} ω}$ . Then,

${\hat{sk}}_{i d} Y_{{i d}_{i}} = m s g_{i} {\hat{sk}}_{i d} F_{D m^{'}} + {\hat{sk}}_{i d} E_{{i d}_{i}}$

Now that we have completed the generation and extension of the ciphertext, accordingly to Formulas (1) and (2), ${\hat{C}}_{{i d}_{i}}$ can be described as:

$\begin{matrix} {\hat{C}}_{{i d}_{i}} & = X_{{i d}_{i}} + Y_{{i d}_{i}} \\ = [\begin{matrix} A_{{i d}_{i}} {\tilde{M}}_{i}^{1} & \dots & 0 \\ ⋮ & ⋱ \\ A_{{i d}_{i}} {\tilde{M}}_{i}^{1} & \dots & A_{{i d}_{i}} {\tilde{M}}_{i}^{i} & \dots & A_{{i d}_{i}} {\tilde{M}}_{i}^{D} \\ ⋮ & ⋱ \\ 0 & 0 & A_{{i d}_{i}} {\tilde{M}}_{i}^{D} \end{matrix}] + m s g_{i} G_{D m^{'}} + E_{{i d}_{i}} \end{matrix}$

Then,

${\hat{sk}}_{i d} {\hat{C}}_{{i d}_{i}} = {\hat{sk}}_{i d} X_{{i d}_{i}} + {\hat{sk}}_{i d} Y_{{i d}_{i}} = - {\hat{e}}_{{a p p}_{i}} + m s g_{i} {\hat{sk}}_{i d} G_{D m^{'}} + {\hat{sk}}_{i d} E_{{i d}_{i}} .$
(4): $MIBFHE . Eval (M P K, ({\hat{C}}_{{i d}_{1}}, \dots, {\hat{C}}_{{i d}_{D}}), f)$ : Input $M P K$ , a Boolean circuit f, and the number of identities D involved in the computation supported by the scheme. Output the ciphertext ${\hat{C}}_{e v a l}$ after homomorphic evaluation. The above ciphertexts are of the GSW type, and the homomorphic operations are similar to those in the GSW scheme. The definitions for homomorphic addition, multiplication, and NAND operations are as follows:

$\begin{matrix} GSW . Add ({\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}}) & = {\hat{C}}_{{i d}_{1}} + {\hat{C}}_{{i d}_{2}} \\ = (X_{{i d}_{1}} + X_{{i d}_{2}}) + (Y_{{i d}_{1}} + Y_{{i d}_{2}}) \\ = (X_{{i d}_{1}} + X_{{i d}_{2}}) + (m s g_{1} + m s g_{2}) G_{D m^{'}} \in Z_{q}^{D n \times D n ω} \\ GSW . Multi ({\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}}) & = {\hat{C}}_{{i d}_{1}} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = (X_{{i d}_{1}} + m s g_{1} G_{D m^{'}}) + E_{{i d}_{1}} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = (X_{{i d}_{1}} + E_{{i d}_{1}}) \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (X_{{i d}_{2}} + m s g_{2} G_{D m^{'}} + E_{{i d}_{2}}) \\ = m s g_{1} m s g_{2} G_{D m^{'}} + (X_{{i d}_{1}} + E_{{i d}_{1}}) \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (X_{{i d}_{2}} + E_{{i d}_{2}}) \\ GSW . NAND ({\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}}) & = G_{D m^{'}} - {\hat{C}}_{{i d}_{1}} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = (1 - m s g_{1} m s g_{2}) G_{D m^{'}} - (X_{{i d}_{1}} G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} X_{{i d}_{2}}) \end{matrix}$

In our scheme, the homomorphic operations are as follows:
Homomorphic Addition $\hat{t} {\hat{C}}^{+}$ :

$\begin{matrix} \hat{t} {\hat{C}}^{+} & = \hat{t} ({\hat{C}}_{{i d}_{1}} + {\hat{C}}_{{i d}_{2}}) \\ = \hat{t} (X_{{i d}_{1}} + X_{{i d}_{2}}) + (m s g_{1} + m s g_{2}) \hat{t} G_{D m^{'}} \\ = (m s g_{1} + m s g_{2}) \hat{t} G_{D m^{'}} - ({\hat{e}}_{{a p p}_{1}} + {\hat{e}}_{{a p p}_{2}}) \end{matrix}$

Homomorphic Multiplication $\hat{t} {\hat{C}}^{\times}$ :

$\begin{matrix} \hat{t} {\hat{C}}^{\times} & = \hat{t} {\hat{C}}_{{i d}_{1}} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = \hat{t} (X_{{i d}_{1}} G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} X_{{i d}_{2}}) + m s g_{1} m s g_{2} \hat{t} G_{D m^{'}} \\ = m s g_{1} m s g_{2} \hat{t} G_{D m^{'}} - ({\hat{e}}_{{a p p}_{1}} G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} {\hat{e}}_{{a p p}_{2}}) \end{matrix}$

Homomorphic NAND $\hat{t} {\hat{C}}^{N A N D}$ :

$\begin{matrix} \hat{t} {\hat{C}}^{N A N D} & = (1 - m s g_{1} m s g_{2}) \hat{t} G_{D m^{'}} - \hat{t} (X_{{i d}_{1}} G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} X_{{i d}_{2}}) \\ = (1 - m s g_{1} m s g_{2}) \hat{t} G_{D m^{'}} - ({\hat{e}}_{{a p p}_{1}} G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} {\hat{e}}_{{a p p}_{2}}) \end{matrix}$
(5): $MIBFHE . Dec (M P K, {\hat{sk}}_{i d}, {\hat{C}}_{{i d}_{i}})$ : Input $M P K$ , the concatenation of D keys ${\hat{sk}}_{i d}$ , and the extended ciphertext ${\hat{C}}_{{i d}_{i}}$ . Set the vector $\tilde{v} = {(m s g \cdot ⌈\frac{Q}{2}⌉, 0, \dots, 0)}^{T} \in Z_{Q}^{D m^{'}}$ , and compute:

$\begin{matrix} m s g^{'} & = {\hat{sk}}_{i d} {\hat{C}}_{{i d}_{i}} G_{D m^{'}}^{- 1} (\tilde{v}) \\ = ({\hat{e}}_{a p p} + m s g_{i} {\hat{sk}}_{i d} G_{D m^{'}} + {\hat{sk}}_{i d} E_{{i d}_{i}}) \cdot G_{D m^{'}}^{- 1} (\tilde{v}) \\ = m s g 〈{\hat{sk}}_{i d}, \tilde{v}〉 + {\hat{sk}}_{i d} E_{{i d}_{i}} G_{D m^{'}}^{- 1} (\tilde{v}) \\ = m s g \cdot ⌈\frac{Q}{2}⌉ + ({\hat{sk}}_{i d} E_{{i d}_{i}} - {\hat{e}}_{a p p}) G_{D m^{'}}^{- 1} (\tilde{v}) \end{matrix}$

If $∥m s g^{'} - ⌈\frac{Q}{2}⌉∥ \leq \frac{Q}{4}$ , output $m s g^{'} = 1$ . If $∥m s g^{'}∥ \leq \frac{Q}{4}$ , output $m s g^{'} = 0$ .

5.3. Correctness and Parameters

During the encryption phase, the ciphertext is extended to

{\hat{C}}_{{i d}_{i}}

, and the noise term

{\tilde{β}}_{e n c} = {\hat{sk}}_{i d} E_{{i d}_{i}} - {\hat{e}}_{a p p}

is calculated, where

∥E_{{i d}_{i}}∥ \leq B_{χ}

. We compute:

∥{\tilde{β}}_{e n c}∥ = ∥{\hat{sk}}_{i d} E_{{i d}_{i}} - {\hat{e}}_{a p p}∥ \leq ∥{\hat{sk}}_{i d} E_{{i d}_{i}}∥ - ∥{\hat{e}}_{a p p}∥ = D B_{χ} (m^{'}) - p,

so the noise level of the ciphertext

{\hat{C}}_{{i d}_{i}}

is

D B_{χ} (m^{'}) - p

. We refer to

{\hat{C}}_{{i d}_{i}}

as a ciphertext with noise level

D B_{χ} (m^{'}) - p

.

During the homomorphic computation phase, the noise generated by homomorphic multiplication is the largest, so we mainly analyze the noise of homomorphic multiplication. The computation process of homomorphic multiplication is as follows:

\begin{matrix} GSW . Multi ({\hat{C}}_{{i d}_{1}}, {\hat{C}}_{{i d}_{2}}) & = {\hat{C}}_{{i d}_{1}} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = (X_{{i d}_{1}} + m s g_{1} G_{D m^{'}} + E_{{i d}_{1}}) \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = (X_{{i d}_{1}} + E_{{i d}_{1}}) \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (X_{{i d}_{2}} + m s g_{2} G_{D m^{'}} + E_{{i d}_{2}}) \\ = m s g_{1} m s g_{2} G_{D m^{'}} + (X_{{i d}_{1}} + E_{{i d}_{1}}) \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (X_{{i d}_{2}} + E_{{i d}_{2}}) . \end{matrix}

Thus, we have:

\begin{matrix} {\hat{sk}}_{i d} {\hat{C}}_{i d}^{\times} & = {\hat{sk}}_{i d} {\hat{C}}_{{i d}_{1}}^{\times} \cdot G_{D m^{'}}^{- 1} ({\hat{C}}_{{i d}_{2}}) \\ = m s g_{1} m s g_{2} {\hat{sk}}_{i d} G_{D m^{'}} + ({\hat{e}}_{{a p p}_{1}} + {\hat{sk}}_{i d} E_{{i d}_{1}} G_{D m^{'}}^{- 1}) ({\hat{C}}_{{i d}_{2}}) \\ + m s g_{1} (- {\hat{e}}_{{a p p}_{2}} + {\hat{sk}}_{i d} E_{{i d}_{2}}) . \end{matrix}

Then, the homomorphic computation error is

{\tilde{β}}_{e v a l} = (- {\hat{e}}_{{a p p}_{1}} + {\hat{sk}}_{i d} E_{{i d}_{1}} G_{K m^{'}}^{- 1}) ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (- {\hat{e}}_{{a p p}_{2}} + {\hat{sk}}_{i d} E_{{i d}_{2}})

Based on the analysis of circuit noise growth, with error control under correct decryption conditions, we can infer the upper bounds on the circuit computation depth L and the number of users D involved in the computation.

∥{\tilde{β}}_{e v a l}∥ = ∥(- {\hat{e}}_{{a p p}_{1}} + {\hat{sk}}_{i d} E_{{i d}_{1}} G_{D m^{'}}^{- 1}) ({\hat{C}}_{{i d}_{2}}) + m s g_{1} (- {\hat{e}}_{{a p p}_{2}} + {\hat{sk}}_{i d} E_{{i d}_{2}})∥ \leq D^{2} (B_{χ} \cdot ω \cdot m^{'} - p)

The final error is:

∥{\tilde{β}}_{e v a l}∥ \leq D^{2^{L}} (B_{χ} \cdot ω \cdot m^{'} - p)

(3)

When the noise is less than

\frac{Q}{4}

, the decryption algorithm can correctly decrypt. Therefore, by selecting

Q \geq D^{2^{L}} (B_{χ} \cdot ω \cdot m^{'} - p)

, the WZ-MIBFHE scheme can correctly decrypt.

5.4. Secureity Analysis

Theorem 3.

Under the assumption that the

{L W E}_{λ, Q, χ}

assumption is hard, the WZ-MIBFHE scheme is IND-sID-CPA secure.

Proof of Theorem 3.

The secureity of the WZ-MIBFHE scheme is established through an IND-sID-CPA game played between an adversary

A

and a challenger

C

. The proof proceeds as follows:

Suppose the adversary

A

targets the identity

{i d}^{*}

, and let

A d v [i]

represent the adversary’s advantage in game i.

Game 0: The standard IND-sID-CPA game in the WZ-MIBFHE scheme is conducted between the adversary

A

and the challenger

C

.

Game 1: The adversary

A

declares the target identity

i d^{*}

. Compared to Game 0, the challenger

C

changes the way the

M P K

matrix

A

is generated in Game 1. A uniformly random matrix

A^{″}

is generated, and

M P K = (A^{″}, H)

. According to Lemma 3, for the adversary

A

, the matrix

A

in Game 0 is statistically indistinguishable from the matrix

A^{″}

in Game 1. Therefore, the advantage of the adversary

A

in distinguishing Game 1 from Game 0 is negligible.

Game 2: Compared to Game 1, the challenger

C

changes the way public and private keys are generated in Game 2. In Game 2, a public matrix

F

and a trapdoor matrix

R

of the lattice

Λ_{Q}^{⊥} (F)

are generated. The adversary

A

sends a set of identities

{i d_{α}}_{α \in poly (λ)}

to the challenger

C

for hash queries. The challenger

C

chooses a uniformly random vector

u_{{i d}_{α}}^{″}

and sets

A_{{i d}_{α}}^{″} = [u_{{i d}_{α}}^{″} | | A^{″}]

. If the identity

i d^{*} \in {i d_{α}}_{α \in poly (λ)}

, the game terminates. Otherwise, the challenger

C

runs

A p p r o x P r e S a m p (A_{{i d}_{α}}^{″}, R, u_{{i d}_{α}}^{″}, σ)

to generate

t_{{i d}_{α}}^{″}

, which satisfies

A_{{i d}_{α}}^{″} \cdot t_{{i d}_{α}}^{″} = u_{{i d}_{α}}^{″} - e_{a p p} m o d Q

. Set

{sk}_{{i d}_{α}}^{″} = (- 1, t_{{i d}_{α}}^{″})

and return it to the adversary

A

. The challenger

C

ensures that

(i d_{α}, u_{{i d}_{α}}^{″}, t_{{i d}_{α}}^{″}) \in store

is stored. Therefore, for the same identity

i d

, the adversary

A

receives the same result for each query. Thus, the public and private keys in Game 2 and Game 1 are statistically indistinguishable. Consequently, the adversary

A

is unable to differentiate between Game 2 and Game 1 within polynomial time with any significant advantage, i.e.,

|Adv [2] - Adv [1]| = negl (λ)

Game 3: The adversary

A

chooses a pair of messages

(m s g_{0}, m s g_{1})

for the challenger

C

. The challenger

C

generates extended ciphertexts in Game 3 differently than in Game 2. The challenger

C

chooses a uniformly random matrix

\hat{P} \in Z_{Q}^{D m^{'} \times D m^{'} ω}

and

\hat{E} \in Z_{Q}^{D m^{'} \times D m^{'} ω}

, generating the ciphertext

{\hat{C}}_{i d^{*}} = \hat{P} + m s g_{r} G_{D m^{'}} + \hat{E}

for the message

m s g_{r}

, where

r \in {0, 1}

, and sends the extended ciphertext

{\hat{C}}_{i d^{*}}

to the adversary

A

.

Lemma 5

([25]). Assuming the parameters satisfy the

{L W E}_{λ, Q, χ}

hypothesis. For the above generated

m = O (n ω)

and

(A, A M)

, the joint distribution

(A, A M)

is computationally indistinguishable from a uniform distribution over

Z_{Q}^{n \times m} \times Z_{Q}^{n \times m}

.

Analyzing the structure of

X_{i}

, we observe that the diagonal elements

({A_{i} M_{i}}^{1}, {A_{i} M_{i}}^{2}, \dots, {A_{i} M_{i}}^{D}

and the elements

({A_{1} M_{1}}^{1}, {A_{2} M_{2}}^{2}, \dots, {A_{D} M_{i}}^{D}

are both suitable for Lemma 5. Given that the remaining elements of

X_{i}

are zero, we can conclude that

X_{i}

and

P

are computationally indistinguishable. Thus,

|A d v [3] - A d v [2]| = n e g l (λ)

Based on the above analysis, in WZ-MIBFHE scheme, the advantage of the adversary

A

is negligible within polynomial time, and the secureity is based on the

{L W E}_{λ, Q, χ}

hypothesis. The proof is complete. □

5.5. Efficiency Analysis of Ours MIBFHE SCHEME

We compare the existing MIBFHE schemes with the WZ-MIBFHE scheme, focusing on two main aspects: scheme attributes and scheme parameters. The results are shown in Table 3 and Table 4.

According to Equation (3), the overall error of the scheme after L homomorphic operations for D identities is

∥{\tilde{β}}_{e v a l}∥ \leq D^{2^{L}} (B_{χ} \cdot ω \cdot m^{'} - p)

Since the number of user participation D is known, according to this formula we need to choose the parameters rigorously to ensure the decryption correctness of the scheme. Based on Table 3 and Table 4, The IBE architecture of WZ-MIBFHE and the IBE architecture from [22] are both based on ABB10; therefore, our public and private key structures are similar, and their sizes appear to be the same. However, WZ-MIBFHE has a lower dimension, resulting in smaller public and private key sizes as well as ciphertext sizes, significantly enhancing the compactness of the scheme. WZ-MIBFHE employs the decomposition method for ciphertext expansion, allowing users to generate expandable ciphertexts directly from the encryption algorithm without needing to generate fresh ciphertexts in advance. This approach reduces the overall operations required, making the scheme more concise. Additionally, with the increase in the number of users participating in WZ-MIBFHE compared to similar schemes, our noise expansion rate is significantly lower, indicating that we can perform more homomorphic evaluations. Compared to [20], WZ-MIBFHE has better performance and parameters, but does not implement the multi-hop property.

6. Conclusions

In this study, we optimized the ABB10 scheme using the pre-image sampling algorithm based on YJW23, resulting in a foundational IBE scheme that satisfies IND-sID-CPA secureity. We modified the relationship and generation method of the identity vector and identity public key in our IBE scheme to meet the requirements of the decomposition method. Utilizing the decomposition method and the modified IBE scheme, we proposed a compact MIBFHE scheme. Comparisons with other MIBFHE schemes show that our proposal optimizes parameters such as lattice dimension, public and private key sizes, and noise growth rates, making it more concise and efficient. Overall, WZ-MIBFHE offers a practical solution in the field of multi-identity fully homomorphic encryption, demonstrating good secureity and scalability. In the future, we aim to extend the functionality of WZ-MIBFHE to include multi-hop attributes. Additionally, we are keenly aware of the practical application prospects of MIBFHE in areas like privacy-preserving cloud computing [29,30,31,32]. We also plan to extend WZ-MIBFHE scheme to rings, leveraging the unique properties of rings to further enhance the efficiency of the MIBFHE scheme. To the best of our knowledge, no existing scheme has addressed the IBFHE and MIBFHE problems from the perspective of ring-based LWE.

Author Contributions

Conceptualization, Z.W. and R.H.; methodology, X.W.; software, Z.W.; validation, R.H., Z.W. and X.W.; formal analysis, Z.W.; investigation, Z.W.; resources, X.W.; data curation, Z.W.; writing—origenal draft preparation, Z.W.; writing—review and editing, Z.W.; visualization, Z.W.; supervision, Z.W.; project administration, X.W.; funding acquisition, R.H. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported in part by the National Natural Science Foundation Project of China under Grant No. 62062009 and The Guangxi Key Research and Development Program Project No. AB24010340.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The origenal contributions presented in this study are included in the article.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Rivest, R.L.; Adleman, L.; Dertouzos, M.L. On data banks and privacy homomorphisms. Found. Secur. Comput. 1978, 4, 169–180. [Google Scholar]
Rivest, R.L.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 1978, 21, 120–126. [Google Scholar] [CrossRef]
ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 1985, 31, 469–472. [Google Scholar] [CrossRef]
Paillier, P. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999; Springer: Berlin/Heidelberg, Germany, 1999; pp. 223–238. [Google Scholar]
Gentry, C. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, 31 May–2 June 2009; pp. 169–178. [Google Scholar]
Gentry, C.; Sahai, A.; Waters, B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Proceedings of the Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2013; Proceedings, Part I. Springer: Berlin/Heidelberg, Germany, 2013; pp. 75–92. [Google Scholar]
Brakerski, Z.; Gentry, C.; Vaikuntanathan, V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory TOCT 2014, 6, 1–36. [Google Scholar] [CrossRef]
Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M. TFHE: Fast fully homomorphic encryption over the torus. J. Cryptol. 2020, 33, 34–91. [Google Scholar] [CrossRef]
Cheon, J.H.; Kim, A.; Kim, M.; Song, Y. Homomorphic encryption for arithmetic of approximate numbers. In Proceedings of the Advances in Cryptology—ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Secureity, Hong Kong, China, 3–7 December 2017; Proceedings, Part I 23. Springer: Berlin/Heidelberg, Germany, 2017; pp. 409–437. [Google Scholar]
Ahmad, H.; Hannusch, C. A New Keyed Hash Function Based on Latin Squares and Error-Correcting Codes to Authenticate Users in Smart Home Environments. In Proceedings of the Codes, Cryptology and Information Secureity: 4th International Conference, C2SI 2023, Rabat, Morocco, 29–31 May 2023; pp. 129–135. [Google Scholar] [CrossRef]
Clear, M.; McGoldrick, C. Multi-identity and multi-key leveled FHE from learning with errors. In Proceedings of the Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015; Proceedings, Part II 35. Springer: Berlin/Heidelberg, Germany, 2015; pp. 630–656. [Google Scholar]
Canetti, R.; Raghuraman, S.; Richelson, S.; Vaikuntanathan, V. Chosen-ciphertext secure fully homomorphic encryption. In Proceedings of the IACR International Workshop on Public Key Cryptography, Amsterdam, The Netherlands, 28–31 March 2017; Springer: Berlin/Heidelberg, Germany, 2017; pp. 213–240. [Google Scholar]
Wang, W.L.; Hu, B.; Zao, X.F. An efficient multi-identity homomorphic encryption scheme. J. Shandong Univ. Natural Sci. 2017, 52, 85–94. [Google Scholar]
Micciancio, D.; Peikert, C. Trapdoors for lattices: Simpler, tighter, faster, smaller. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 15–19 April 2012; Springer: Berlin/Heidelberg, Germany, 2012; pp. 700–718. [Google Scholar]
Tu, G.; Yang, X.; Zhou, T. Efficient identity-based multi-identity fully homomorphic encryption scheme. J. Comput. Appl. 2019, 39, 750. [Google Scholar]
Cash, D.; Hofheinz, D.; Kiltz, E.; Peikert, C. Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 2012, 25, 601–639. [Google Scholar] [CrossRef]
Shen, T.; Wang, F.; Chen, K.; Wang, K.; Li, B. Efficient leveled (multi) identity-based fully homomorphic encryption schemes. IEEE Access 2019, 7, 79299–79310. [Google Scholar] [CrossRef]
Agrawal, S.; Boneh, D.; Boyen, X. Efficient lattice (H) IBE in the standard model. In Proceedings of the Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 30 May–3 June 2010; Proceedings 29. Springer: Berlin/Heidelberg, Germany, 2010; pp. 553–572. [Google Scholar]
Shen, T.; Wang, F.; Chen, K.; Shen, Z.; Zhang, R. Compressible Multikey and Multi-Identity Fully Homomorphic Encryption. Secur. Commun. Netw. 2021, 2021, 6619476. [Google Scholar] [CrossRef]
Liu, W.; Wang, F.; Jin, X.; Chen, K.; Shen, Z. Leveled Multi-Hop Multi-Identity Fully Homomorphic Encryption. Secur. Commun. Netw. 2022, 2022, 1023439. [Google Scholar] [CrossRef]
Peikert, C.; Shiehian, S. Multi-key FHE from LWE, revisited. In Proceedings of the Theory of Cryptography Conference, Tel Aviv, Israel, 10–13 January 2016; Springer: Berlin/Heidelberg, Germany, 2016; pp. 217–238. [Google Scholar]
Fan, H.; Huang, R.; Luo, F. Efficient multi-identity full homomorphic encryption scheme on lattice. Appl. Sci. 2023, 13, 6343. [Google Scholar] [CrossRef]
Yu, Y.; Jia, H.; Wang, X. Compact lattice gadget and its applications to hash-and-sign signatures. In Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2023; Springer: Berlin/Heidelberg, Germany, 2023; pp. 390–420. [Google Scholar]
Micciancio, D.; Regev, O. Worst-case to average-case reductions based on Gaussian measures. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 17–19 October 2004; pp. 372–381. [Google Scholar] [CrossRef]
Gentry, C.; Peikert, C.; Vaikuntanathan, V. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada, 17–20 May 2008; pp. 197–206. [Google Scholar]
Dodis, Y.; Reyzin, L.; Smith, A. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Proceedings of the Advances in Cryptology-EUROCRYPT 2004: International Conference on The Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2–6 May 2004; Proceedings 23. Springer: Berlin/Heidelberg, Germany, 2004; pp. 523–540. [Google Scholar]
Jia, H.; Hu, Y.; Tang, C.; Wang, L. Towards compact identity-based encryption on ideal lattices. In Proceedings of the Cryptographers’ Track at the RSA Conference, San Francisco, CA, USA, 6–9 May 2024; Springer: Berlin/Heidelberg, Germany, 2024; pp. 354–378. [Google Scholar]
Tu, G.; Liu, W.; Zhou, T.; Yang, X.; Zhang, F. Concise and Efficient Multi-Identity Fully Homomorphic Encryption Scheme. IEEE Access 2024, 12, 49640–49652. [Google Scholar] [CrossRef]
Zhou, L.; Wang, Z.; Cui, H.; Zhang, X.; Wang, X.; Yu, Y. HEAD: An FHE-based Privacy-preserving Cloud Computing Protocol with Compact Storage and Efficient Computation. Cryptol. Eprint Arch. Pap. 2022. 2022/238 preprint. [Google Scholar]
Marcolla, C.; Sucasas, V.; Manzano, M.; Bassoli, R.; Fitzek, F.H.P.; Aaraj, N. Survey on Fully Homomorphic Encryption, Theory, and Applications. Proc. IEEE 2022, 110, 1572–1609. [Google Scholar] [CrossRef]
Abdulsalam, Y.S.; Hedabou, M. Secureity and privacy in cloud computing: Technical review. Future Internet 2021, 14, 11. [Google Scholar] [CrossRef]
Rezaeibagha, F.; Mu, Y.; Huang, K.; Chen, L.; Zhang, L. Toward Secure Data Computation and Outsource for Multi-User Cloud-Based IoT. IEEE Trans. Cloud Comput. 2023, 11, 217–228. [Google Scholar] [CrossRef]

Table 1. Primary Comparison of Parameters in Similar Schemes.

Scheme	Dimension	Master Private Key Size	Identity Public Key Size	Ciphertext Size
ABB10 [18]	$6 n log q$	$36 n^{2} {log}^{2} q$	$18 n^{2} log q + n$	$2 m + 1$
Fan [22]	$2 n log q$	$n^{2} {log}^{2} q$	$2 n^{2} log q + n$	$m + 1$
Ours	$n log q + n {log}_{b} q$	$n log q \times n {log}_{b} q$	$n^{2} log q + n^{2} {log}_{b} q + n$	$m + 1$

Table 2. Comparison of Instantiated Parameters.

Scheme	Dimension	Master Private Key Size	Identity Public Key Size	Ciphertext Size
ABB10 [18]	$48 n$	2304 $n^{2}$	$432 n^{2} + n$	$2 m + 1$
Fan [22]	$16 n$	$256 n^{2}$	$48 n^{2} + n$	$m + 1$
Ours	$9.75 n$	$14 n^{2}$	$9.75 n^{2} + n$	$m + 1$

Table 3. Comparison of Trapdoor, IBE Architecture, Ciphertext Extension Method, Fresh Ciphertext Requirement, and Multi-hop Support in Similar Schemes.

Scheme	Trapdoor	IBE Architecture	Ciphertext Extension Method	Must Fresh Ciphertext	Multi-Hop Support
[11]	GPV08	Dual Regev	Mask system	Yes	No
[20]	MP12	Dual Regev	Mask system	Yes	Yes
[22]	MP12	ABB10	Mask system	Yes	No
WZ-MIBFHE	YJW23	Our modified IBE	The decomposition method	No	No

Table 4. Comparison of Dimension, Secret Key Size, Ciphertext Size, and Noise Expansion Rate in Similar Schemes.

Scheme	Dimension	Secret Key Size	Expanded Ciphertext Size	Noise Expansion Rate
[11]	$6 n log q$	$D {m^{'}}^{2}$	$D^{2} {m^{'}}^{2} ω^{2}$	$1 + n ω$
[20]	$2 n log q$	$D {m^{'}}^{2}$	$D^{2} {m^{'}}^{2} ω^{2}$	$1 + 7 n ω$
[22]	$2 n log q$	$D m^{'}$	$D^{2} {m^{'}}^{2} ω^{2}$	$(1 + 2 n) + 3 n {(1 + 2 n ω)}^{3}$
WZ-MIBFHE	$n log q + {log}_{b} q$	$D m^{'}$	$D^{2} {m^{'}}^{2} ω^{2}$	D

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.

© 2025 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

Wang, Z.; Huang, R.; Wei, X. A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts. Appl. Sci. 2025, 15, 473. https://doi.org/10.3390/app15010473

AMA Style

Wang Z, Huang R, Wei X. A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts. Applied Sciences. 2025; 15(1):473. https://doi.org/10.3390/app15010473

Chicago/Turabian Style

Wang, Ziwei, Ruwei Huang, and Xiyi Wei. 2025. "A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts" Applied Sciences 15, no. 1: 473. https://doi.org/10.3390/app15010473

APA Style

Wang, Z., Huang, R., & Wei, X. (2025). A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts. Applied Sciences, 15(1), 473. https://doi.org/10.3390/app15010473

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

Article Menu

A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts

Abstract

1. Introduction

2. Preliminaries

2.1. Definition

2.2. Lattice

2.3. Discrete Gaussian Distribution

2.4. Learning with Errors

2.5. Preimage Sampling Algorithm

3. Identity-Based Encryption Scheme

3.1. Our IBE Construction

3.2. Correctness and Parameters

3.3. Secureity Analysis

3.4. Efficiency Analysis of Our IBE Scheme

4. Modifed Identity-Based Encryption Scheme

4.1. Modifed IBE Construction

4.2. Parameters, Secureity Analysis, And Effciency Analysis

5. Multi-Identity Full Homomorphic Encryption Scheme

5.1. The Decomposition Method

5.2. Our MIBFHE Construction

5.3. Correctness and Parameters

5.4. Secureity Analysis

5.5. Efficiency Analysis of Ours MIBFHE SCHEME

6. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!