Open AccessArticle

Attribute-Based Verifiable Conditional Proxy Re-Encryption Scheme

Yongli Tang

Minglu Jin

Hui Meng

^*,

Li Yang

and

Chengfu Zheng

College of Software, Henan Polytechnic University, Jiaozuo 454000, China

Author to whom correspondence should be addressed.

Entropy 2023, 25(5), 822; https://doi.org/10.3390/e25050822

Submission received: 15 March 2023 / Revised: 12 May 2023 / Accepted: 18 May 2023 / Published: 19 May 2023

(This article belongs to the Special Issue Information Security and Privacy: From IoT to IoV)

Download

Browse Figures

Versions Notes

Abstract

There are mostly semi-honest agents in cloud computing, so agents may perform unreliable calculations during the actual execution process. In this paper, an attribute-based verifiable conditional proxy re-encryption (AB-VCPRE) scheme using a homomorphic signature is proposed to solve the problem that the current attribute-based conditional proxy re-encryption (AB-CPRE) algorithm cannot detect the illegal behavior of the agent. The scheme implements robustness, that is the re-encryption ciphertext, can be verified by the verification server, showing that the received ciphertext is correctly converted by the agent from the original ciphertext, thus, meaning that illegal activities of agents can be effectively detected. In addition, the article demonstrates the reliability of the constructed AB-VCPRE scheme validation in the standard model, and proves that the scheme satisfies CPA security in the selective security model based on the learning with errors (LWE) assumption.

Keywords:

proxy re-encryption; homomorphic signature; learning with errors; re-encryption verifiable

1. Introduction

As a new resource sharing in the field of information, cloud computing is constantly changing people’s lives. As an important technology in cloud computing, cloud storage is used to organize a series of different types of network storage devices to facilitate data sharing. To ensure the confidentiality of data, before being uploaded to a cloud server, user data are encrypted, however, this poses difficulties in sharing data between different users. When dealing with a significant quantity of data recipients, general encryption algorithms can significantly increase the computational and communication expenses incurred by the data owner. Proxy re-encryption (PRE) effectively solves this problem.

In 1998, Blaze et al. [1] first introduced the concept of PRE at the Euromonitor Conference. PRE is a data cipher conversion in cloud computing, which ensures both user data security and flexible access and sharing of data. However, in the traditional PRE system, it is usually one delegator that corresponds to another delegator, that is, a one-to-one model; this implies that only one client’s message can be re-encrypted at a time, necessitating a large amount of communication overhead and computation expense, which is contrary to the initial aim of cloud computing customers wanting to save money. In 2007, GREEN et al. [2] simplified the public key certificate authentication process by proposing an encryption scheme based on user identity information instead of a public key. However, the encryption process is specific to particular users and requires explicit information about the recipient. In 2009, JIAN et al. [3] suggested a strategy for conditional PRE (CPRE) based on identity proxy re-encryption. By designing a conditional ciphertext conversion method, the ciphertext can only be converted when the ciphertext meets the set conditions, enabling the assignment of partial decryption rights, but it is still in the form of a one-to-one assignment between the authorizer and the authorized person, which not only severely restricts users’ ability to selectively share data with other users at a fine-grained level, but it also has the problems of high communication costs and high computational overhead when a large number of users need to access that shared data, as well as wasting a large amount of local memory space to hold a large number of decryption keys.

Being a novel cryptographic technique that differs from conventional public key cryptography, attribute-based encryption (ABE) [4] is ideally suited for resolving data confidentiality protection and access control of ciphertext problems in cloud storage applications [5]. ABE technology can provide an effective one-to-many, fine-grained ciphertext access control solution for cloud storage data security. AB-CPRE schemes have been presented that demonstrate the advantages and properties of ABE and CPRE. However, the existing AB-PRE schemes and AB-CPRE schemes are mostly based on constructs such as linear mappings or discrete logarithmic puzzles [6,7]. Due to the advent of quantum computers, the security of traditional number theory puzzles is threatened and these schemes will become insecure. To solve this problem, a lattice cipher is proposed. It is believed that lattice-based cryptography can resist quantum attacks and has high computational efficiency. Therefore, lattice-based public key cryptography schemes have attracted wide attention in recent years.

However, all the AB-CPRE schemes [8,9,10] that are currently in use are semi-trusted agents, so they may perform unreliable calculations, which bring security problems to data sharing. Most AB-CPRE efforts focus on data privacy and access control without considering re-encryption authentication, which can lead to incorrect results for users.

Therefore, it is of interest to ensure that the re-encryption ciphertext is converted correctly from the original ciphertext. In a homomorphic encryption algorithm, the user can perform some kind of secure proxy calculation with the untrusted remote server. In this process, the server cannot see any private information. The homomorphic signature algorithm supports the signature operation consistent with the message, and the generated signature does not disclose any information related to the data set, which can meet the security requirements in the cloud environment, and is very suitable for the sensor network, network coding, and other message operation scenarios to ensure information security. This paper introduces homomorphic signature techniques in AB-CPRE, provides a verification mechanism for re-encryption performed by a verification server, and proposes a verifiable PRE scheme.

Our main contributions in this article are as follows:

An AB-VCPRE scheme based on LWE is proposed. The scheme ensures by verification that the re-encryption ciphertext is correctly converted from the encryption ciphertext;
Fine-grained access control is implemented. In combination with fully homomorphic encryption, the delegation policy supports any polynomial-depth boolean circuit;
Robustness is achieved. The scheme uses a validation algorithm to achieve robustness. Forged or incorrectly shared ciphertexts can be detected by validating the re-encryption ciphertext with a validation server;
The scheme satisfies CPA security. The ciphertext in our scheme needs to be signed and verified using an unforgeable homomorphic signature. This paper demonstrates that the constructed AB-VCPRE scheme is CPA security based on a LWE problem.

The rest of the paper is organized into seven sections. In Section 2, the related studies are described. In Section 3, the relevant definitions are introduced. In Section 4 and Section 5, we state the details of the scheme and the security analysis. Section 6 presents the efficiency analysis. The last section is a summary of the paper.

2. Related Work

Liang et al. [7] present an AB-PRE cryptographic primitive based on the augmented decisional bilinear Diffie–Hellman (DBDH) problem combining ABE and PRE for the first time, which empowers users to authorize in an access control environment. Li et al. [11] propose a proxy re-encryption scheme for a re-splitable threshold multi-agent, which is different from the encryption scheme on the ciphertext input and output plane and the re-encryption surface, which means the noise boundary has a wider range of choices and can ensure the security of the re-encryption key. Nunez et al. [12] propose a typical threshold proxy re-encryption scheme, which is based on a DBDH assumption, vulnerable to quantum attacks. Luo et al. [13] construct a standard lattice multi-hop AB-PRE scheme, which supports circuit access, has a short key, the key size is dependent on the depth of the circuit policy, and satisfies CPA security requirements based on the LWE problem in the selection security model. However, these PRE schemes may not show sufficient flexibility and practicality when the data owner wishes to select some but not all of the data for dissemination to certain users. Weng et al. [3] proposed a CPRE scheme where only those that satisfy the conditions can be re-encrypted, but it can only be applied to simple keyword-based conditions and will be limited in practical applications. Then, Yang et al. [8] propose a ciphertext policy-based AB-CPRE scheme, which supports a fine-grained decryption delegation. The ciphertext in the scheme is related to the access policy while the re-encryption key is related to the attributes, and the ciphertext can be re-encrypted only when the access policy satisfies the attributes. Huang et al. [14] propose PRECISE, which combines AB-CPRE with IBBE to support fine-grained re-encryption conditions for IBBE ciphertexts. Yao et al. [15] combine ciphertext authorization, key update, and ciphertext evolution to propose an improved revocable, identity-based ciphertext evolution conditional proxy re-encryption scheme for secure and efficient cloud data sharing.

The universal CPRE algorithm cannot ensure the cloud server’s integrity during the re-encryption procedure, while the homomorphic signature algorithm has unforgettable security and privacy, which can effectively verify the honesty of the proxy during the re-encryption. Therefore, this paper uses a homomorphic signature algorithm to propose a PRE scheme with encryption validating on the lattice, which can effectively detect the illegal behavior of the proxy and provide a guarantee for the safe sharing of data.

3. Preliminaries

3.1. Lattice

Definition 1 (lattice).

The lattice is a linear combination of group

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

’s linearly independent vectors’

n (m \geq n)

integer coefficients in m-dimensional Euclidean space

R^{m}

, which is defined as:

L (B) = \{\sum_{i = 1}^{n} x_{i} b_{i} : x_{i} \in ℤ, i = 1, \dots, n\} .

(1)

Lemma 1

([16]). Take integer

q \geq 3

m \geq 6 n \log q

σ \geq m^{2} ω (\sqrt{\log m})

, there exists a

P P T

algorithm

T r a p G e n (1^{n}, 1^{m}, q)

that generates a matrix

A \in ℤ_{q}^{n \times m}

and a trapdoor

T_{A} \in ℤ^{m \times m}

for the lattice

\land_{q}^{⊥} (A)

, i.e., there is

A T_{A} = 0 \mod q

, such that the distribution statistics satisfied by the matrix

A

are close to a uniform distribution on

ℤ_{q}^{n \times m}

, and

| | {\tilde{T}}_{A} | | \leq O (\sqrt{n \log q})

holds by an absolute margin.

Lemma 2

([17]). Let

q > 2

and

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

. Select three uniform matrices

D \in {\{- 1, 1\}}^{m \times k}

E \in ℤ_{q}^{n \times m}

, and

F \in ℤ_{q}^{n \times k}

at random for some polynomials with

k = k (n)

. Distribution

(E, E D, D^{T} r)

and

(E, F, D^{T} r)

are statistically indistinguishable for any vector

r \in ℤ_{q}^{m}

LWE is a difficult problem under lattice. Regev [18] first proposed this in 2005 and proved that the average case is just as difficult to solve for several standard cells.

Definition 2 (LWE).

Given positive integer

n

, integer

m \geq n

and

q \geq 2

, choosing uniform random matrix

A \in ℤ_{q}^{n \times m}

and vector

s \in ℤ_{q}^{n}

, vector

e \leftarrow χ^{m}

follows the error distribution. Given

(A, A^{T} s + e)

, the LWE problem is to find

s

with non-negligible probability.

Definition 3 (Small integer solutions problem, SIS).

Let the defining parameters be

β

q

is a prime number, given positive integers

m

and

n

, select a matrix

A \in ℤ_{q}^{n \times m}

at random, solve for a non-zero vector of integers

z \in ℤ^{m} \ \{0\}

with

| | z | | \leq β

. In 1996, Ajtai presented the SIS problem in the literature [16]. The homomorphic signature used for robustness in the paper is based on the SIS problem.

3.2. Related Functions and Tools

3.2.1. Functions of Bits and Power2

According to the article [19], decomposing the vector into the form of an inner product can effectively control the error range of the vector. The following describes how to decompose vectors into bit representations.

For any

x \in ℤ^{N}

, let

x = \sum_{i = 0}^{g - 1} 2^{i} \cdot x^{i} \mod q

x_{i} \in {\{0, 1\}}^{N}

. Output vector

B i t (x) = (x_{0}, x_{1}, \dots, x_{g - 1}) \in {\{0, 1\}}^{1 \times N g}

, where

g = ⌈\log q⌉

. For any

y = [y_{1} | y_{2} | \dots | y_{ℓ}] \in ℤ^{N \times ℓ}

, where

y_{i}

is a column vector, output matrix

P o w e r 2 (y) = [\begin{matrix} y_{1} & y_{2} & \dots & y_{ℓ} \\ 2 y_{1} & 2 y_{2} & \dots & 2 y_{ℓ} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 2^{g - 1} y_{1} & 2^{g - 1} y_{2} & \dots & 2^{g - 1} y_{ℓ} \end{matrix}] \in ℤ_{q}^{N g \times ℓ} .

(2)

It can be verified that for any

q \in ℤ

, there is

〈B i t (x), P o w e r 2 (y)〉 = 〈x, y〉 \in ℤ_{q}^{1 \times ℓ}

3.2.2. Discrete Gaussian Distribution

For integer vectors

c \in ℤ^{m}

σ > 0

, the discrete Gaussian distribution on the m-dimensional lattice

Λ

is:

D_{\land, σ, c} (x) = \frac{ρ_{σ, c} (x)}{ρ_{σ, c} (\land)} = \frac{ρ_{σ, c} (x)}{\sum_{x \in \land} ρ_{σ, c} (x)}, \forall x \in ℤ^{m} .

(3)

Lemma 3

([17]). Let

q \geq 2

B

is a matrix over

ℤ_{q}^{n \times m}

and

m > n

. Let

T_{B}

is the base of

\land_{q}^{⊥} (B)

σ \geq | | {\tilde{T}}_{B} | | ω (\sqrt{\log_{2} m})

. For

u \in ℤ_{q}^{n}

, there are:

Set the rank of $B \in ℤ_{q}^{n \times m}$ is $n$ , $E \in ℤ_{q}^{n \times m}$ , $R \in {\{- 1, 1\}}^{m \times m}$ , $σ \geq | | {\tilde{T}}_{B} | | ω (\sqrt{\log_{2} m})$ . Let $F = (B | B R + E) \in ℤ_{q}^{n \times (2 m)}$ , PPT algorithms $S a m p l e B a s i s L e f t (B, B R + E, T_{B}, σ)$ , where $T_{B}$ is the base of $\land_{q}^{⊥} (B)$ , output a short base $T_{F} \in \land_{q}^{⊥} (F)$ statistical distribution to $ψ_{σ}^{(2 m) \times (2 m)}$ ;
$S a m p l e \Pr e (B, T_{B}, σ, u)$ : There is trapdoor $T_{B}$ of lattice $\land_{q}^{⊥} (B)$ , the real number $σ \geq | | {\tilde{T}}_{B} | | \cdot ω (\sqrt{\log n})$ , for any vector $u \in ℤ_{q}^{n}$ , a PPT algorithm $S a m p l e \Pr e (B, T_{B}, σ, u)$ capable of generating a vector $e$ from a distribution that is statistically close to $D_{ℤ^{m}, σ} (x)$ , satisfying $B e = u (\mod q)$ ;
Let the rank of $G \in ℤ_{q}^{n \times m}$ be $n$ , $B \in ℤ_{q}^{n \times m}$ , a low-dimensional matrix $S \in {\{- 1, 1\}}^{m \times m}$ , a trapdoor for the lattice $\land_{q}^{⊥} (G)$ , and $σ \geq | | {\tilde{T}}_{E} | | \cdot | | R | | ω (\sqrt{\log_{2} m})$ . PPT algorithm $S a m p l e B a s i s R i g h t (B, G, S, T_{G}, σ)$ output a short base $T_{(B | B S + G)} \in \land_{q}^{⊥} (B | B S + G)$ with a statistical distribution close to $Ψ_{σ}^{(2 m) \times (2 m)}$ .

3.3. Key Homomorphism

By embedding algorithmic circuits in LWE matrices, Boneh et al. suggested an ABE approach for algorithmic circuits in their paper [20], and the method was used in many LWE-based structures, for example, predicate encryption [21], constraint PRFs [22], watermarks for PRFs [23], etc.

Definition 4.

For any positive integer

k

d

, a

g

d e p t h \leq d

boolean circuit, defining families of functions

F_{k, d} = \{g : {\{0, 1\}}^{k} \to \{0, 1\}\}

Lemma 4

(Fully homomorphic encryption [20,24]). Given parameters

t, h, k, d, q, χ

, where

χ

is a B-bounded noise distribution,

h

is a security parameter,

h \geq ⌈t \log q⌉

. For any matrices

B_{1}, B_{2}, \dots, B_{ℓ} \in ℤ_{q}^{t \times h}

, any boolean circuit

g : {\{0, 1\}}^{k} \to \{0, 1\}

for any depth

\leq d

x \in {\{0, 1\}}^{k}

, matrix

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

, vector

s \in ℤ_{q}^{t}

e_{i} \leftarrow χ^{h}

for

i \in [k]

, if

p_{i} = {(x_{i} G + B_{i})}^{T} s + e_{i}, \forall i \in [k]

$E v a l_{p k} (g, (B_{1}, \dots B_{k}))$ : Taking a circuit $g$ , $k$ matrices ${\{B_{i}\}}_{i \in [k]}$ as input, outputs a matrix $B_{g}$ ;
$E v a l_{c t} (g, {\{(x_{i}, p_{i}, B_{i})\}}_{i \in [k]})$ : Given a circuit $g$ , $k$ matrices ${\{B_{i}\}}_{i \in [k]}$ , a vector $x \in {\{0, 1\}}^{k}$ and $k$ vectors $\{p_{1}, \dots, p_{k}\}$ , outputs a vector $p_{g}$ , satisfying $p_{g} = {(B_{g} + g (x) G)}^{T} s + e_{g}$ , where $B_{g} = E v a l_{p k} (g, \{B_{1}, \dots, B_{k}\})$ , $| | e_{g} | | \leq B \sqrt{h} {(1 + h)}^{d}$ with all but negligible probability;
$E v a l_{s i m} (g, {\{S_{i}, x_{i}^{*}\}}_{i \in [k]}, A)$ : On input a circuit $g$ , a vector $x^{*} \in {\{0, 1\}}^{k}$ , $k$ matrices ${\{S_{i}\}}_{i \in [k]}$ , a matrix $A \in ℤ_{q}^{t \times h}$ , outputs a matrix $S_{g}$ satisfying $A S_{g} - g (x^{*}) = B_{g}$ , where $| | S_{g} | |_{2} \leq 20 \sqrt{h} {(1 + h)}^{d} < {(1 + h)}^{d + 1}$ with all but negligible probability.

3.4. Homomorphic Signature

A homomorphic signature is a valid signature that permits any entity to conduct a sequence of operations on the original message and its signature without the signing private key.

Definition 5 (Homomorphic signature).

The probabilistic polynomial-time algorithm

(K G, S i g n, S i g n E v a l, V e r i f y)

is included in the following tuple is the homomorphic signature (HS) scheme:

$H S . K G (p, d, N)$ : Take a safety parameter $p$ , a circuit depth $d$ , and a message length $N$ as input, output a signature private key $h s s k$ and a verification key $h s v k$ ;
$H S . S i g n (h s s k, M)$ : Accept as inputs the message $M$ requiring signature and $h s s k$ , output the signature $σ$ ;
$H S . S E v a l (g, σ)$ : Take an evaluation circuit $g : {\{0, 1\}}^{N} \to \{0, 1\}$ and signature $σ$ as input, output a homomorphic calculation signature $σ^{*}$ ;
$H S . V e r i f y (h s v k, y, g, σ^{*})$ : Take $h s v k$ , a message $y$ , a circuit $g$ and a signature $σ^{*}$ , the verification algorithm either accepts the signature (outputs 1) or rejects it (outputs 0).

Correctness. On input

p, d, N \in ℤ

H S . K G (p, d, N) \to (h s v k, h s s k)

M \in {\{0, 1\}}^{N}

H S . S i g n (h s s k, M) \to σ

, any circuit

g : {\{0, 1\}}^{N} \to \{0, 1\}

with a depth

d

g (M) \to y

, the equation below holds:

\Pr [H S . V e r i f y (h s v k, y, g, H S . S E v a l (g, σ)) = 1] = 1 .

(4)

3.5. Robustness

A key component of the AB-VCPRE design is robustness. The fundamental tenet is that by re-encryption key sharing, an adversary cannot create ciphertext that is falsely obtained yet can be correctly authenticated. The following game

E x p t_{A}^{R b}

describes the robustness of the AB-VCPRE scheme.

During the guessing phase, the adversary outputs the appropriate ciphertext

C T^{*}

satisfies

V e r f y (h s v k, C T^{*}) = 1

while

S e t u p

K e y G e n q u e r y

Re K e y G e n q u e r y

, and

Re E n c q u e r y

interact as specified in Definition 6.

The adversary’s advantage is characterized as

A d v_{A}^{R b} = \Pr [E x p t_{A}^{R b} (λ) = 1] .

4. The Model of AB-VCPRE with Re-Encryption Verification

4.1. Scheme Definition

An AB-VCPRE scheme consists of seven algorithms. The specific flow chart is shown in Figure 1. In comparison to the standard AB-VCPRE, a verification method called

Re E n c - V e r

is added to check for an honest transformation of the ciphertext. The

Re E n c - V e r

algorithm is publicly verifiable because all that is required are the original ciphertext and the corresponding re-encryption ciphertext.

$S e t u p (n)$ : Input security parameter $n$ , output public parameters $p p$ ;
$K e y G e n (p p, α)$ : Given $p p$ , output the public/private key pair $(p k_{α}, s k_{α})$ for user $α$ ;
$E n c (p p, p k_{α}, μ, x)$ : Taking $p p$ , $p k_{α}$ , plaintext $μ$ , and an attribute vector $x$ as input, output a related ciphertext $C T_{α}$ with $x$ ;
$D e c (p p, s k_{α}, C T_{α})$ : Taking $p p$ , $s k_{α}$ , and $C T_{α}$ as input, output a message $μ$ ;
$Re K e y G e n (p p, s k_{α}, p k_{β}, f)$ : Input $p p$ , $s k_{α}$ of user $α$ , $p k_{β}$ of user $β$ , and a control policy/function $f$ , returns the re-encryption key $R K_{α, f \to β}$ related to $f$ and the corresponding signature, outputs the re-encryption verification key $V K_{α \to β}$ from user $α$ to user $β$ ;
$Re E n c (p p, R K_{α, f \to β}, C T_{α})$ : With $p p$ , $p k_{α}$ of user $α$ , $C T_{α}$ associated with $x$ , and $R K_{α, f \to β}$ as input. When $f (x) = 0$ remains constant, output the converted ciphertext $C T_{β}$ , otherwise output $⊥$ ;
$Re E n c - V e r (V K_{α \to β}, C T_{α}, C T_{β})$ : If the original ciphertext’s conversion to the re-encryption ciphertext is performed correctly, the output of the authentication algorithm is valid, otherwise output $⊥$ (invalid ciphertext).

Correctness. In an AB-VCPRE scheme, correctness has the following two requirements:

Decryption correctness.

For security parameter n, attribute vectors

x = {\{x_{i}\}}_{i \in [l]}

, message

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

, the equations below hold

D e c (pp, s k_{α}, E n c (p p, p k_{α}, μ, x)) = μ;

(5)

D e c (p p, s k_{β}, Re E n c (p p, R K_{α, f \to β}, C T_{α})) = μ,

(6)

where the decryption error is negligible.

2.: Verification correctness.

Verification correctness is satisfied using an AB-VCPRE scheme. We have the probability

\Pr [Re E n c - V e r (V K_{α \to β}, C T_{α}, C T_{β}) = 1] = 1

if all converted ciphertexts

C T_{β}

are produced by the re-encryption keys

R K_{α, f \to β}

and

Re E n c (p p, R K_{α, f \to β}, C T_{α})

Figure 1. Flow chart of AB-VCPRE.

4.2. Security Model

Definition 6.

To demonstrate the CPA security of the AB-VCPRE scheme, the game between challenger

C

and adversary

A

is used.

Init. Before seeing the public parameter

p p

, adversary

A

declares a vector of attributes

x^{*}

Setup. Initialize the public parameters

p p

in Challenger

C

and use the

K e y G e n

algorithm to obtain

(s k_{θ}, p k_{θ})

, and transmit

p p

and

p k_{θ}

A

Query phase 1.

A

chooses some queries as the following:

$K e y G e n q u e r y$ $O_{K e y G e n}$ : $A$ performs a key query. $C$ runs $K e y G e n (p p, β)$ to produce the $(p k_{β}, s k_{β})$ ;
$Re K e y G e n q u e r y$ $O_{Re K e y G e n}$ : $C$ runs $Re K e y G e n (p p, s k_{α}, p k_{β}, f)$ to provide $r k_{α, f \to β}$ when $C$ receives a re-encryption key query, where $f (x^{*}) = 0$ and $p k_{β} = K e y G e n (p p, β)$ . And $C$ responds with verification key by running algorithm $H S . K e y G e n (n, d^{h s}, N)$ ;
$Re E n c q u e r y$ $O_{Re E n c}$ : $A$ sends $(C T_{α}, x, f)$ to $C$ where $x \neq x^{*}$ and $f (x) = 0$ , $C$ computes a re-encryption key $r k_{α, f \to β}$ as in $O_{Re K e y G e n}$ and returns a re-encrypted ciphertext $C T_{β}$ by running $Re E n c (p p, R K_{α, f \to β}, C T_{α})$ .

Challenge phase.

A

chooses two messages of the same length

μ_{0}^{*}

and

μ_{1}^{*}

(

μ_{0}^{*} \neq μ_{1}^{*}

C

executives

C T^{*} \leftarrow E n c (p p, p k_{θ}, x^{*}, μ_{b}^{*})

, where

b \in \{0, 1\}

, and gives back the original ciphertext from

C T^{*}

A

Query phase 2. Similar to phase 1,

A

keeps asking the query.

Guess.

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

is guessed by

A

, and if

b = b^{'}

, the game winner is

A

The benefits of

A

are described as

\Pr [b^{'} = b] = 1 / 2 + n e g l (n) .

5. Our Scheme

5.1. Our Scheme Composition

Using the LWE difficulty problem as a basis and the homomorphic signature algorithm, this paper proposes an AB-VCPRE scheme.

$S et u p (n)$

Let security parameters

n \in Z

, where

m \geq ⌈6 n \log (q)⌉

q / 4 \geq B \cdot {(m + 1)}^{O (d)}

$①$: Central agency generates random security parameters prime $q$ , an error sampling algorithm $χ$ for B-bounded distributions, $B \geq \sqrt{n} \cdot ω (\log n)$ . The boolean circuit’s maximum depth is $d$ , the number of attributes is $ℓ$ , and the Gaussian parameter is $σ$ , $σ = ω ({(m + 1)}^{d + 1}) \cdot ω (\sqrt{\log m})$ ;
$②$: Create the corresponding trapdoor matrix $T_{A_{α}} \in ℤ_{q}^{m \times m}$ and the matrix $A_{α} \in ℤ_{q}^{n \times m}$ by running algorithm $T r a p G e n (1^{n}, 1^{m}, q)$ ;
$③$: Select $ℓ$ uniform matrices $B_{1}, \dots, B_{ℓ} \in ℤ_{q}^{n \times m}$ with random.
$④$: Output public parameters $p p : = ({\{B_{i}\}}_{i \in [ℓ], χ}, χ)$ .

2.: $K e y G e n (p p, α)$

Randomly select a matrix

D_{α} \in ℤ_{q}^{n \times m}

, and run

R_{α} \leftarrow S a m p l e \Pr e (A_{α}, T_{α}, D_{α}, σ)

, such that

A_{α} R_{α} = - D_{α}

Output

p k_{α} = (A_{α}, D_{α}), s k_{α} = (R_{α}, T_{α})

3.: $E n c (p p, p k_{α}, μ, x)$

$①$: Given the plaintext $μ \in {\{0, 1\}}^{m}$ , attribute vectors $x \in {\{0, 1\}}^{ℓ}$ , where $x = {\{x_{i}\}}_{i \in [ℓ]}$ . Select random vectors $s \leftarrow ℤ_{q}^{n}$ , error vectors $e_{1}, e_{2} \leftarrow χ^{m}$ ;
$②$: Compute $c c = (c_{1}, c_{2})$ :

c_{1} = A_{α}^{T} s + e_{1}, c_{2} = D_{α}^{T} s + e_{2} + ⌊q / 2⌋ μ .;

(7)

$③$: $ca$ should be set to $\emptyset$ if $x$ is null or none. Or else randomly choose $ℓ$ uniform matrices $S_{i} \leftarrow {\{- 1, 1\}}^{m \times m}$ at random, calculate

c a = ({\{c_{i} = {(x_{i} G + B_{i})}^{T} s + S_{i}^{T} e_{1}\}}_{i \in [ℓ]}) \in ℤ_{q}^{ℓ m} .

(8)

Output ciphertext

C T_{α} : = (c c, c a)

;

4.: $D e c (p p, s k_{α}, C T_{α})$

Input

s k_{α} = (R_{α}, T_{α})

C T_{α} = (c c, c a)

$①$: Compute $\hat{μ} = c_{2} + R_{α}^{T} c_{1}$ . Set $μ_{i} = 1$ for $i \in [m]$ if $| q / 2 - {\hat{μ}}_{i} | < q / 4$ , or else set $μ_{i} = 0$ .

Output

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

;

5.: $Re K e y G e n (p p, s k_{α}, p k_{β}, f)$

Input

p k_{β} = (A_{β}, D_{β})

s k_{α} = (T_{α}, R_{α})

p p = ({\{B_{i}\}}_{i \in [ℓ], χ}, χ)

, a policy

f \in F_{ℓ . d}

$①$: Randomly selected matrices $E_{1} \leftarrow χ^{2 k m \times n}$ , $E_{2}, E_{3} \leftarrow χ^{2 k m \times m}$ , $s$ is the Gaussian parameter, and $s = ω ({(m + 1)}^{d + 3 / 2})$ .
$②$: Let $B_{f} = E v a l_{p k} (f, B_{1}, \dots, B_{ℓ})$ , $F = (A_{α} | B_{f}) \in ℤ^{n \times 2 m}$ . Running $T_{α, f} \leftarrow S a m p l e B a s i s L e f t (A_{α}, B_{f}, T_{α}, s)$ . Generate the basic $T_{α, f}$ for $F$ .
$③$: Execute algorithm $S a m p l e \Pr e (F, T_{α, f}, - D_{α}, σ)$ to produce $R_{α, f}$ , in order to obtain $F R_{α, f} = - D_{α}$ , of which $R_{α, f} \in ℤ^{2 m \times m}$ . Compute the re-encryption key:

Q = [\begin{array}{c} E_{1} A_{β} + E_{2} & E_{1} D_{β} + E_{3} + P o w e r 2_{q} (R_{α, f}) \\ 0_{m \times m} & I_{m \times m} \end{array}] \in ℤ_{q}^{(2 k m + m) \times 2 m};

(9)

$④$: Creating the verification key using algorithm $H S . K e y G e n (n, d^{h s}, N)$ and signature private key $(h s v k, h s s k)$ , parse each line of $Q$ as $w_{i} \in ℤ_{q}^{2 m} (1 \leq i \leq 2 m k + m)$ , then use the signature algorithm to sign $w_{i}$ as $σ_{i} = H S . S i g n (h s s k, w_{i})$ ;
$⑤$: To validate the signature, publish $h s v k$ . Deliver $Q$ and the associated signature $\{R K_{α, f \to β} = Q, σ_{i} (1 \leq i \leq 2 m k + m)\}$ across a secure channel to the proxy server;

6.: $Re E n c (p p, R K_{α, f \to β}, C T_{α})$

Input

p p = ({\{B_{i}\}}_{i \in [ℓ], χ}, χ)

R K_{α, f \to β} = Q

C T_{α} = (c c, c a)

$①$: Output $⊥$ if $f (x) \neq 0$ or $c a = \emptyset$ , or else $c_{3} = E v a l_{c t} (f, {\{(x_{i}, B_{i}, p_{i})\}}_{i \in [ℓ]})$ , ${\tilde{c}}_{1, 3} =$ $([c_{1}; c_{3}])$ . The proxy performs the ciphertext conversion $(c_{1}^{^{'} T} | c_{2}^{^{'} T}) = [{\tilde{c}}_{1, 3}^{T} | c_{2}^{T}] \cdot Q$ ;
$②$: The valuation circuit is $g_{C_{α}} (Q) = [{\tilde{c}}_{1, 3}^{T} | c_{2}^{T}] \cdot Q$ , and the evaluation algorithm from HS creates a signature $σ_{α \to β} = H S . S i g n E v a l (g_{C_{α}}, σ_{i} (1 \leq i \leq 2 m k + m))$ .

Output

C T_{β} = (c c^{'} = (c^{'}_{1}, c^{'}_{2}), c a^{'} = \emptyset, σ_{α \to β})

as converted ciphertext;

7.: $Re E n c - V e r (h s v k, C T_{α}, C T_{β})$

Input verification key

h s v k

, original ciphertext

C T_{α} = (c c = (c_{1}, c_{2}), σ_{* \to β})

, converted ciphertext

C T_{β} = (c c^{'} = (c^{'}_{1}, c^{'}_{2}), σ_{α \to β})

Verification algorithm output

H S . V e r i f y (h s v k, g_{C_{α}}, c c^{'}, σ_{α \to β})

Figure 2 depicts the new AB-VCPRE scheme’s workflow. If Bob wants to share Alice’s content stored on the cloud server, first KGC generates a public key and private key for Alice and Bob and sends the keys to them. Then, Alice generates the re-encryption key and original ciphertext, which are sent to the cloud server and executes the re-encryption algorithm. The cloud server delivers both the original and the re-encryption ciphertext to the authentication server after the re-encryption operation is finished. The authentication server verifies the algorithm for re-encryption. If the verification algorithm outputs 1, the authentication server sends Bob the ciphertext, Bob recovers the message by decrypting the ciphertext matching to it, otherwise output

⊥

5.2. Correctness and Parameters

5.2.1. The Correctness of the Original Ciphertext

With the private key

R_{α}

, the original ciphertext can be decrypted.

\begin{matrix} \hat{μ} & = c_{2} + R_{α}^{T} c_{1} \\ = D_{α}^{T} s + e_{2} + ⌊q / 2⌋ μ + R_{α}^{T} (A_{α}^{T} s + e_{1}) \\ = \underset{n o i s e}{\underset{︸}{e_{2} + e_{1} R_{α}}} + ⌊q / 2⌋ μ \end{matrix} .

(10)

Only if the error

e_{2} + e_{1} R_{α}

does not exceed

q / 4

the decryption algorithm is able to correctly recover the plaintext

μ

. In fact,

| | e_{2} + e_{1} R_{α} | | \leq \sqrt{m} B + m \sqrt{m} σ B \leq B \cdot {(1 + m)}^{O (d)}

\leq q / 4

5.2.2. Correctness of Conversion Ciphertext

After passing one conversion, the corresponding conversion cipher is decrypted as follows:

\begin{matrix} (c_{1}^{^{'} T} & | c_{2}^{^{'} T}) = [{\tilde{c}}_{1, 3}^{T} | c_{2}^{T}] \cdot Q \\ = [{\tilde{c}}_{1, 3}^{T} | c_{2}^{T}] \cdot [\begin{matrix} E_{1} A_{β} + E_{2} & E_{1} D_{β} + E_{3} + P o w e r 2_{q} (R_{α, f}) \\ 0_{m \times m} & I_{m \times m} \end{matrix}] \\ = [{\tilde{c}}_{1, 3}^{T} \cdot (E_{1} A_{β} + E_{2}) | {\tilde{c}}_{1, 3}^{T} \cdot (E_{1} D_{β} + E_{3} + P o w e r 2_{q} (R_{α, f})) + c_{2}^{T}] \\ = [{\tilde{c}}_{1, 3}^{T} \cdot (E_{1} A_{β} + E_{2}) | {\tilde{c}}_{1, 3}^{T} \cdot (E_{1} D_{β} + E_{3}) + {\tilde{c}}_{1, 3}^{T} \cdot P o w e r 2_{q} (R_{α, f}) + D_{α} s^{T} + e_{2}^{T} + ⌊q / 2⌋ μ^{T}] \\ = [{\tilde{c}}_{1, 3}^{T} \cdot (E_{1} A_{β} + E_{2}) | {\tilde{c}}_{1, 3}^{T} \cdot (E_{1} D_{β} + E_{3}) + [e_{1}^{T} | e_{f}^{T}] R_{α, f} + e_{2}^{T} + ⌊q / 2⌋ μ^{T}] \end{matrix}

(11)

Where

A_{β}

and

D_{β}

are the user

β

‘s public keys,

| | E_{1} | | \leq \sqrt{2 k} m B

| | E_{2} | | \leq \sqrt{2 k} m B

| | E_{3} | | \leq \sqrt{2 k} m B

with overwhelming probability. By the theorem we have:

\begin{matrix} {\tilde{c}}_{1, 3}^{T} \cdot P o w e r 2_{q} (R_{α, f}) & = {[c_{1}; c_{3}]}^{T} \cdot R_{α, f} \\ = [c_{1}^{T} | c_{3}^{T}] \cdot R_{α, f} \\ = [(s^{T} A + e_{1}^{T}) | (s^{T} (f (x) G + B_{f}) + e_{f}^{T})] \cdot R_{α, f} \\ = [(s^{T} A + e_{1}^{T}) | (s^{T} B_{f} + e_{f}^{T})] \cdot R_{α, f} \\ = [s^{T} [A_{α} | B_{f}] + [e_{1}^{T} | e_{f}^{T}]] \cdot R_{α, f} \\ = - s^{T} D_{α} + [e_{1}^{T} | e_{f}^{T}] \cdot R_{α, f} \end{matrix}

(12)

where

R_{α, f} \leq \sqrt{2} m σ

| | e_{f} | | \leq B \sqrt{m} {(m + 1)}^{d}

with overwhelming probability.

The conversion ciphertext is decrypted by the private key

R_{β}

\begin{matrix} [c_{1}^{^{'} T} | c_{2}^{^{'} T}] \cdot [\begin{array}{l} R_{β} \\ I \end{array}] = {\tilde{c}}_{1, 3}^{T} (E_{1} A_{β} + E_{2}) \cdot R_{β} + {\tilde{c}}_{1, 3}^{T} (E_{1} D_{β} + E_{3}) + [e_{1}^{T} | e_{f}^{T}] R_{α, f} + e_{2}^{T} + ⌊q / 2⌋ μ^{T} \\ = \underset{n o i s e}{\underset{︸}{{\tilde{c}}_{1, 3}^{T} E_{2} R_{β} + {\tilde{c}}_{1, 3}^{T} E_{3} + [e_{1}^{T} | e_{f}^{T}] R_{α, f} + e_{2}^{T}}} + ⌊q / 2⌋ μ^{T} \end{matrix}

(13)

where:

| | {\tilde{c}}_{1, 3}^{T} E_{2} R_{β} + {\tilde{c}}_{1, 3}^{T} E_{3} + [e_{1}^{T} | e_{f}^{T}] R_{α, f} + e_{2}^{T} | | \leq 2 k m^{2} \sqrt{m} σ B + 2 k m \sqrt{m} B + 2 m \sqrt{m} {(m + 1)}^{d} σ B + \sqrt{m} B \leq B {(m + 1)}^{O (d)} \leq q / 4

(14)

with overwhelming probability. Therefore, the value of

μ

can be decrypted correctly, i.e., the transformed ciphertext can be decrypted correctly.

In fact, the algorithm can only obtain single-hop, because in

Re E n c

, we set

c a^{'} = \emptyset

, which means that the re-encryption ciphertext cannot be encrypted again. This design is our first work and we will investigate this problem and extend it to multi-hop schemes in future work.

5.2.3. Correctness of Ciphertext Verification

In the HS scheme, the re-encryption verifiability is carried out using the algorithm

H S . V e r i f y

. In

A B - V C P R E . Re E n c (p p, R K_{α, f \to β}, C T_{α})

, input the ciphertext

C T_{α}

and the re-encryption key

R K_{α, f \to β}

, using

g_{C_{α}} (Q) = [B i t s_{q} {([c_{1}; c_{3}])}^{T} | c_{2}^{T}] \cdot Q

as a valuation circuit, re-encryption key as circuit input,

(c_{1}^{^{'} T} | c_{2}^{^{'} T}) = [B i t s_{q} {([c_{1}; c_{3}])}^{T} | c_{2}^{T}] \cdot Q

can be seen as some computation at the message level and in

σ_{α \to β} = H S . S i g n E v a l (g_{C_{α}}, σ_{i} (1 \leq i \leq

2 m k + m))

, with signature

σ_{i} (1 \leq i \leq 2 m k + m)

as input, and it can be interpreted as a computation of the signature level. If

σ_{α \to β}

is in fact the outcome of an honest computation based on

H S . S i g n E v a l (g_{C_{α}}, σ_{i} (1 \leq i \leq 2 m k + m)) = σ_{α \to β}

, the concept of correctness for homomorphic signature schemes holds. Then

H S . V e r i f y (h s v k, g_{C_{α}}, c c^{'}, σ_{α \to β})

can pass the verification and the verification algorithm’s accuracy is demonstrated.

5.3. Security

Theorem 1 (Security).

The scheme we construct is CPA security under

L W E_{n, q, χ}

assumption.

Proof of Theorem 1.

A game-based approach is used in this proof. A challenger

C

can be built to resolve the LWE presumption if it is possible for an adversary

A

to breach the CPA’s security.

Game 0: In the original CPA attack paradigm described in Section 3, this is a true game between

A

and

C

Game 1: Same as game 0, but with a change in the way the common matrix

{\{B_{i}\}}_{i \in [ℓ]}

is generated. On receipt of

x^{*}

C

generates

ℓ

uniformly random small parametric matrices

S_{1}^{*}, \dots, S_{ℓ}^{*} \in {\{- 1, 1\}}^{m \times m}

, calculate

B_{i} = A^{*} S_{i}^{*} - x_{i}^{*} G

where

i \in [ℓ]

. □

Lemma 5.

Game 0 is statistically indistinguishable from game 1.

Proof of Lemma 5.

In game 0,

{\{B_{i}\}}_{i \in [ℓ]}

is a random uniform matrix on

ℤ_{q}^{n \times m}

. In the challenge query,

{\{S_{i}^{*}\}}_{i \in [ℓ]}

is the construction of the generated challenge ciphertext

c^{*}

random matrix. However, in game 1,

e \in χ^{m}

serves as the error vector and

S_{i}

is used to generate

B_{i}

and

c^{*}

. By Lemma 2, the distribution

(A^{*}, {\{A^{*} S_{i}^{*}\}}_{i \in [ℓ]}, e)

and

(A^{*}, {\{A_{i}^{*}\}}_{i \in [ℓ]}, e)

are statistically equivalent for any

{\{A_{i}^{*}\}}_{i \in [ℓ]} \in ℤ_{q}^{n \times m}

. Hence, no statistically significant difference exists between the common matrix

{\{B_{i}\}}_{i \in [ℓ]}

in games 0 and 1. This shows that there is no statistically significant difference between games 0 and 1. □

Game 2: Challenger

C

randomly selects

A_{θ}

ℤ_{q}^{n \times m}

with no trapdoor and utilizes the

T r a p G e n

to produce

B

and its trapdoor

T_{B}

KeyGen query

O_{K e y G e n}

A

performs a key query.

C

run

K e y G e n (p p, β)

to produce the

(p k_{θ}, s k_{θ})

, output

p k_{β}

A

ReKeyGen query

O_{Re K e y G e n}

. When adversary

A

interrogates

O_{Re K e y G e n} (p k_{α}, p k_{β}, f)

to make

f (x^{*}) \neq 0

, challenger

C

executes

E v a l_{s i m}

of Lemma 4 to create a re-encryption key.

$p p = ({\{B_{i}\}}_{i \in [ℓ]}, χ)$ , $p k_{β} = (A_{β}, D_{β})$ , policy $f \in F_{ℓ, d}$ , set $B_{f} = E v a l_{p k} (f, (B_{1}, \dots, B_{ℓ}))$ , a policy $F = (A_{θ} | B_{f}) \in ℤ^{n \times 2 m}$ ;
Run $S_{f}^{*} \leftarrow E v a l_{s i m} (f, {\{(S_{i}^{*}, x_{i}^{*})\}}_{i \in [ℓ]}, A)$ to make $A S_{f}^{*} - f (x^{*}) G = B_{f}$ . It follows from the definition of $E v a l_{s i m}$ that there is $| | S_{f}^{*} | |_{2} < {(1 + m)}^{d + 1}$ ;
$C$ executive $S a m p l e B a s i s R i g h t (A_{θ}, G, S_{f}^{*}, T_{G}, s)$ to generate short basic $T_{θ, f}$ of $(A_{θ} | B_{f})$ . Run $S a m p l e \Pr e (F, T_{θ, f}, - D_{θ}, σ)$ to produce $R_{θ, f} \in ℤ^{2 m \times m}$ , hence, an equals $F R_{θ, f} = - D_{θ}$ ;
When $f (x^{*}) \neq 0$ , let ${\bar{R}}_{α, f} = P o w e r 2_{q} (R_{α, f})$ , matrix $E_{1} \leftarrow χ^{2 k m \times n}$ , $E_{2}, E_{3} \leftarrow χ^{2 k m \times m}$ , create the matrix

Q = [\begin{array}{c} E_{1} A_{β} + E_{2} & E_{1} D_{β} + E_{3} + P o w e r 2_{q} ({\bar{R}}_{θ, f}) \\ 0_{m \times m} & I_{m \times m} \end{array}] \in ℤ_{q}^{(2 k m + m) \times 2 m};

(15)

5.: When $f (x^{*}) = 0$ , let ${\bar{R}}_{α, f} = P o w e r 2_{q} (R_{α, f})$ , matrix $E_{1} \leftarrow χ^{2 k m \times n}$ , $E_{2}, E_{3} \leftarrow χ^{2 k m \times m}$ , select a random uniform distribution matrix $M \in ℤ_{q}^{2 k m \times m}$ , create the matrix

Q = [\begin{array}{c} E_{1} A_{β} + E_{2} & M + {\bar{R}}_{θ, f}) \\ 0_{m \times m} & I_{m \times m} \end{array}] \in ℤ_{q}^{(2 k m + m) \times 2 m} .

(16)

Then

A

send the challenger

C

some re-encryption verification questions, who will then carry out the operation honestly and report the results to the adversary

A

ReEnc query

O_{Re E n c}

C

output

Re E n c (p p, C T_{α}, R K_{θ, f \to β})

Lemma 6.

Game 1 is computationally indistinguishable from game 2.

Proof of Lemma 6.

The technique employed to generate the re-encryption key differs between games 1 and 2. When

f (x^{*}) = 0

hold, here is the re-encryption key:

r k_{θ, f \to β} = \{\begin{cases} [\begin{array}{c} E_{1} A_{β} + E_{2} & E_{1} D_{β} + E_{3} + {\bar{R}}_{θ, f} \\ 0_{m \times m} & I_{m \times m} \end{array}] i n G a m e 1 \\ [\begin{array}{c} E_{1} A_{β} + E_{2} & M + {\bar{R}}_{θ, f}) \\ 0_{m \times m} & I_{m \times m} \end{array}] i n G a m e 2 \end{cases}

(17)

Corollary 1.

By applying the standard mixing parameters, the ensuing distributions cannot be distinguished computationally. Otherwise, there is a useful algorithm for resolving the

L W E_{n, q, χ}

problem.

1.: $(D, D Y + F)$ and $(D, V)$ , where $D \leftarrow ℤ_{q}^{n \times m}$ , $Y \leftarrow χ^{m \times ℓ}$ , $F \leftarrow χ^{n \times ℓ}$ , $V \leftarrow ℤ_{q}^{n \times ℓ}$ ;
2.: $(D, K, D Y + F, K Y + F^{'})$ and $(D, K, D Y + F, K Y^{'} + F^{'})$ , where $D, K \leftarrow ℤ_{q}^{n \times m}$ , $Y, Y^{'}, F, F^{'} \leftarrow χ^{n \times m}$ ;
3.: $(D, {D Y_{i} + F_{i}}_{i \in [t]})$ and $(D, {V_{i}}_{i \in [t]})$ , where $D \leftarrow ℤ_{q}^{n \times m}$ , $Y_{i} \leftarrow χ^{n \times m}$ , $F_{i} \leftarrow χ^{n \times ℓ}$ , $V_{i} \leftarrow ℤ_{q}^{n \times ℓ}$ for $i \in [t]$ , $t = p o l y (n)$ .

By Corollary 1, under the LWE assumption, it is evident that game 1 and game 2 are computationally indistinguishable.

Additionally, the private key creation mechanism is undetected from game 1 to game 2, and the produced private key continues to satisfy

A_{α} R_{α} = D_{α}

, while the re-encryption key is selected from the uniform distribution, which is similar to the standard LWE distribution. Furthermore, because homomorphic signatures are non-negligible, the adversary in the CPA game cannot offer an invalid ciphertext to pass re-encryption verification, that is, re-encryption verification provides no auxiliary capacity to the adversary.

On the other side, to demonstrate it, if

A

succeeds in the re-encryption verifiability game, then by interacting with challenger

C

, the simulator

S

can break the homomorphic signature’s unforgeability.

The verification key

h s v k

is first acquired by the simulator

S

from

C

. The re-encryption key

R K_{θ, f \to β}^{*}

is then chosen by adversary

A

as the one it wants to assault, and the simulator s is provided

R K_{θ, f \to β}^{*}

A

. To create the signature,

S

asks the message

R K_{θ, f \to β}^{*}

for a homomorphic signature to obtain

σ_{i} (1 \leq i \leq 2 m k + m)

and then gives it back to

A

. The challenger

C

then calculates

H S . V e r i f y (h s v k, g_{C_{α}}, c c^{*}, σ_{θ \to β}^{*})

whenever

A

outputs a false re-encryption ciphertext

C T_{β}^{*} = (c c^{*} = (c_{1}^{*}, c_{2}^{*}), c a^{*} = \emptyset, σ_{θ \to β}^{*})

after the simulator

S

has parsed it, where

g_{C_{α}}

is an evaluation circuit converted from the original ciphertext.

A

wins the verifiability of re-encryption, the forgery of

A

‘s signature

σ_{θ \to β}^{*}

can pass

H S . V e r i f y

, which also counts as a valid homomorphic signature. Therefore, breaking the unforgeability of the homomorphic signature provides the same advantage as breaking the re-encryption verifiability of the AB-VCPRE scheme. When all of the aforementioned factors are considered, game 1 and game 2 are similar from the standpoint of the adversary. □

Game 3: Similar to game 2, except that the challenge cipher

C T^{*} = (c_{1}^{*}, c_{2}^{*}) \in ℤ^{2 m \times 1}

given to the opponent is no longer honestly generated, but chosen evenly and randomly in

ℤ^{2 m \times 1}

. Due to the fact that the challenge cipher is a random factor in the cipher space, it is independent of

μ_{0}^{*}

and

μ_{1}^{*}

, so there is zero advantage to the

A

in this game.

Lemma 7.

Game 2 is statistically indistinguishable from game 3.

Proof of Lemma 7.

A

distinguishes game 2 from game 3 with a non-negligible advantage, then there is a simulator

S

that can use the information acquired by

A

to resolve the

L W E_{n, q, χ}

problem. □

LWE instance. The simulator

S

requests the LWE prophesy device to acquire an LWE instance

(Y, b) \in ℤ_{q}^{n \times 2 m} \times ℤ_{q}^{2 m}

, possibly

(Y, b)

is a truly random distribution or

b = Y^{T} s + e

is a pseudo-random distribution of noise

e \in χ^{m}

from the LWE.

Public parameters. Let

[A_{θ} | D_{θ}] : = Y

, sample a uniform matrix

D_{θ} \leftarrow ℤ_{q}^{n \times m}

to generate a randomly identified public key

A_{θ} \leftarrow ℤ_{q}^{n \times m}

, select

ℓ

random matrices

(S_{1}^{*}, \dots, S_{ℓ}^{*}) \leftarrow {\{- 1, 1\}}^{m \times m}

, and let

B_{i} = A_{θ} S_{i}^{*} - x_{i}^{*} G

for

i \in [ℓ]

. Then the common matrix

p p = ({B_{i} = A_{θ} S_{i}^{*} - x_{i}^{*} G}_{i \in [ℓ], χ})

, public key

p k : = (A_{θ}, D_{θ})

Queries. As with game 2,

B

answers all of

A

‘s queries.

Challenge ciphertext. Generate challenge cipher via LWE instance

[c_{1}; c_{2}] : = z;

(18)

[c_{11}^{T} | \dots | c_{ℓ ℓ}^{T}] = c_{1}^{T} [S_{1}^{*} | \dots | S_{ℓ}^{*}] .

(19)

The answer to

A

is then returned. In this case, the distribution of the challenge cipher is the same as that of game 2.

\begin{matrix} z & = [c_{1}; c_{2}] \\ = Y^{T} s + e \\ = {[A_{θ} | D_{θ}]}^{T} s + [e_{1}; e_{2}] \end{matrix}

(20)

where

Y \leftarrow ℤ_{q}^{n \times 2 m}

s \leftarrow ℤ_{q}^{n}

e \leftarrow χ^{2 m}

Challenge ciphertext:

c_{1} = A_{θ}^{T} s + e_{1}, c_{2} = D_{θ}^{T} s + e_{2} + ⌊q / 2⌋ μ;

(21)

c a = {\{c_{i} = {(x_{i}^{*} G + B_{i})}^{T} s + {(S_{i}^{*})}^{T} e_{1}\}}_{i \in [ℓ]} .

(22)

Then through

B_{i} = A_{θ} S_{i}^{*} - x_{i}^{*} G

, there is

\begin{matrix} [c_{11}^{T} | \dots | c_{ℓ ℓ}^{T}] & = [s^{T} A_{θ} S_{1}^{*} + e_{1}^{T} S_{1}^{*} | \dots \dots | s^{T} A_{θ} S_{ℓ}^{*} + e_{1}^{T} S_{ℓ}^{*}] \\ = (s^{T} A_{θ} + e_{1}^{T}) [S_{1}^{*} | \dots \dots | S_{ℓ}^{*}] . \end{matrix}

(23)

Statistically, the challenge ciphertext is indistinguishable in the alternative scenario if

Y

and

z

are chosen consistently, according to the leftover hash lemma [25].

Output. The simulator

S

outputs

A

‘s guess after

A

predicts whether it interacts with game 2 or game 3.

S

can solve the

L W E_{n, q, 2 m, χ}

problem with the same probability if

A

can distinguish between games 2 and 3. However, the

L W E_{n, q, 2 m, χ}

problem is mysterious, so game 3 cannot be won by

A

The Proof of Theorem 1 is completed by considering game 0 to game 3.

Theorem 2 (Robustness).

The new AB-VCPRE scheme fulfills robustness if the homomorphic signature

Π_{H S}

satisfies unforgeability.

Proof of Theorem 2.

Using a randomly selected evaluation circuit, a dishonest proxy server is able to obtain an invalid re-encryption ciphertext share and corresponding signature. However, the original ciphertext should describe the right evaluation circuit. When the correct evaluation circuit diverges from the forgery, verification fails, allowing the proxy server to convert the data truthfully.

Homomorphic signatures can be used to demonstrate the robustness of the new scheme. If

A

can defeat the game outlined in Definition 6, then by collaborating with

C

in the homomorphic signature security model, it is able to build a simulator

S

that compromises the homomorphic signatures’ unforgeability. Here is the procedure.

A

picks the re-encryption key it wishes to attack once the simulator

S

receives the challenger

C

‘s verification key

h s v k

. When

A

sends simulator

S

a forged re-encryption ciphertext share

C T_{β}^{*} = (c c^{*} = (c_{1}^{*}, c_{2}^{*}), c a^{*} = \emptyset, σ_{θ \to β}^{*})

S

processes it to obtain

(h s v k, c c^{*} = (c_{1}^{*}, c_{2}^{*}), g_{C_{α}}, σ_{θ \to β}^{*})

and submits it to an oracle as a forged homomorphic signature.

A

succeeds in the robustness game, then

C T_{β}^{*} \neq Re E n c (p p, R K_{θ, f \to β}, C T_{θ})

, but

H S . V e r i f y (h s v k, c c^{*}) = 1

, this also means that

H S . V e r i f y (h s v k, g_{C_{α}}, c c^{*}, σ_{θ \to β}^{*})

was able to pass the verification, so the simulator

S

successfully forged an illegal signature, which will be submitted to oracle later. This indicates that the homomorphic signature algorithm’s unforgeability has been compromised.

Thus, if the homomorphic signature algorithm

Π_{H S}

meets the requirement for unforgeability, the signature is considered unforgeable. The new AB-VCPRE is capable of achieving robustness. □

Theorem 3 (Weak collusion resistance).

The new AB-VCPRE scheme can realize weak collusion resistance, if the LWE problem is difficult.

Proof of Theorem 3.

Weak collusion resistance is that when an agent with a re-encryption key colludes with a trustee with a re-encryption key, the agent obtains only an approximate result, not an exact result.

The re-encryption key is

E_{1} A_{β} + E_{2}

and

E_{1} D_{β} + E_{3} + P o w e r 2_{q} (R_{α, f})

, which can be further expressed as

[\begin{array}{l} A_{β} \\ D_{β} \end{array}], E_{1} [\begin{array}{l} A_{β} \\ D_{β} \end{array}] + [\begin{array}{l} E_{2} \\ E_{3} + P o w e r 2_{q} (R_{α, f}) \end{array}]

(24)

This is a standard LWE distribution that is not different from unified distribution, nor can anyone obtain any useful information about private keys. After collusion, Bob encrypted the above equation with his private key

R_{β}

and got

E_{2} R_{β} + E_{3} + P o w e r 2_{q} (R_{α, f})

. As the noise generated during re-encryption is very low, the encryption message can be well restored by

E_{2} R_{β} + E_{3} + P o w e r 2_{q} (R_{α, f})

. Therefore, in the case of collusion, the private key seems to have all been compromised. However, this is not the case. We can restore an equivalent private key, but this equivalent private key is different from the original private key. We provide the following two explanations. On the one hand, any data that can initially be decrypted by

S K_{α}

can be easily re-encrypted and read by an enemy who possesses both

R K_{α, f \to β}

and

S K_{β}

. On the other hand, they are unable to determine the delegator’s precise private key

S K_{α}

from the equation above. Although Power2 is an easy-to-reverse feature, because it contains some noise from

E_{2} R_{β} + E_{3}

, you cannot obtain an exact private key from the first n-line of

E_{2} R_{β} + E_{3} + P o w e r 2_{q} (R_{α, f})

. Therefore, the method proposed in this project has weak collusion resistance. □

6. Efficiency Analysis

Paper [15] proposed a CPRE algorithm based on DBDH, which supports fine-grained authorization and collision resistance security, however, it cannot achieve robustness. Paper [11] and paper [12] are PRE schemes with verification, both of which are robust and the method for achieving robustness is zero-knowledge proof with a decisional discrete logarithm tool, but are not as low complexity as the schemes in this paper. In addition, paper [12] is based on discrete logarithmic constructions and is not resistant to quantum attacks. Although paper [11] is a scheme using lattice construction, which seems to be resistant to quantum attacks, the robustness verification tool is a decisional discrete logarithm, so in general the scheme is not resistant to quantum attacks. Table 1 demonstrates that the approach presented in this paper is not only robust to proxy re-encryption but also simple to implement and resistant to quantum attacks.

In Table 2, the efficiency of the scheme is analyzed through plaintext space, size of ciphertext, size of re-encryption key, encryption complexity, re-encryption complexity, and robustness verification complexity.

|ℤ_{q}|

represents an integer on modulo q.

T_{p}

T_{e}

T_{s}

T_{v}

, and

T_{m}

denote the computation of pairing, modular exponentiation, signature, ciphertext verification, and multiplication operation, respectively.

T_{h}

T_{G V P}

, respectively, represent the time spent for the hash function and the GVP algorithm. Table 2 demonstrates that the computational complexity of the literature [15] is worse than that of the proposed scheme, and is not robust. In terms of robustness verification complexity, when a boolean circuit evaluates the original signature, homomorphic signature computation is a boolean operation that is more straightforward and effective. Here, we choose the linear homomorphic signature scheme based on the difficult problem of SIS on the lattice proposed in paper [26] for comparison. Compared with the scheme [12], the proposed scheme has better re-encryption complexity, encryption complexity, and robustness verification complexity. Compared with the scheme [11], the proposed scheme in this paper only needs to pay some extra cost to encrypt the message vector, and the robustness verification complexity is lower.

7. Conclusions

By using homomorphic signatures, this paper proposes an AB-VCPRE scheme, which solves the problem of being unable to detect illegal proxy behavior in traditional PRE schemes. The scheme is robust enough to allow proxy servers that have sent invalid transformed ciphertext shares to be detected. In terms of security, the scheme is CPA security based on a LWE problem and is resistant to quantum attacks. In terms of efficiency, the scheme has advantages in re-encryption and robustness verification computational efficiency. In addition, there is some room for improvement in the performance of our solutions, and constructing a multi-hopping PRE scheme will be the focus of our next work.

Author Contributions

Conceptualization, Y.T., M.J. and H.M.; methodology, M.J. and H.M.; validation, M.J., Y.T. and H.M.; formal analysis, M.J. and L.Y.; writing—original draft preparation, M.J.; writing—review and editing, H.M., C.Z. and L.Y.; supervision, H.M. and C.Z.; funding acquisition, Y.T. All authors have read and agreed to the published version of the manuscript.

Funding

This research is partially supported by the Henan Key Laboratory of Network Cryptography Technology (LNCT2022-A11) and the Shaanxi Key Laboratory of Information Communication Network and Security (ICNS202006).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

Blaze, M.; Bleumer, G.; Strauss, M. Divertible protocols and atomic proxy cryptography. In Proceedings of the Advances in Cryptology—EUROCRYPT’98: International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, 31 May–4 June 1998; pp. 127–144. [Google Scholar] [CrossRef]
Green, M.; Ateniese, G. Identity-based proxy re-encryption. In Proceedings of the Applied Cryptography and Network Security: 5th International Conference, ACNS 2007, Zhuhai, China, 5–8 June 2007; pp. 288–306. [Google Scholar] [CrossRef]
Weng, J.; Deng, R.H.; Ding, X.; Chu, C.-K.; Lai, J. Conditional proxy re-encryption secure against chosen-ciphertext attack. In Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, Sydney, Australia, 10–12 March 2009; pp. 322–332. [Google Scholar] [CrossRef]
Sahai, A.; Waters, B. Fuzzy identity-based encryption. In Proceedings of the Advances in Cryptology–EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 24–26 May 2005; pp. 457–473. [Google Scholar] [CrossRef]
Zamite, J.; Domingos, D.; Silva, M.J.; Santos, C. Group-based discretionary access control in health related repositories. J. Inf. Technol. Res. JITR 2014, 7, 78–94. [Google Scholar] [CrossRef]
Zhao, J.; Feng, D.; Zhang, Z. Attribute-based conditional proxy re-encryption with chosen-ciphertext security. In Proceedings of the 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, Miami, FL, USA, 6–10 December 2010; pp. 1–6. [Google Scholar] [CrossRef]
Liang, X.; Cao, Z.; Lin, H.; Shao, J. Attribute based proxy re-encryption with delegating capabilities. In Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, Sydney, Australia, 10–12 March 2009; pp. 276–286. [Google Scholar] [CrossRef]
Yang, Y.; Lu, H.; Weng, J.; Zhang, Y.; Sakurai, K. Fine-grained conditional proxy re-encryption and application. In Proceedings of the Provable Security: 8th International Conference, ProvSec 2014, Hong Kong, China, 9–10 October 2014; pp. 206–222. [Google Scholar] [CrossRef]
Mao, X.; Li, X.; Wu, X.; Wang, C.; Lai, J. Anonymous attribute-based conditional proxy re-encryption. In Proceedings of the Network and System Security: 12th International Conference, NSS 2018, Hong Kong, China, 27–29 August 2018; pp. 95–110. [Google Scholar] [CrossRef]
Ge, C.; Susilo, W.; Wang, J.; Huang, Z.; Fang, L.; Ren, Y. A key-policy attribute-based proxy re-encryption without random oracles. Comput. J. 2016, 59, 970–982. [Google Scholar] [CrossRef]
Li, J.; Ma, C.; Zhao, Q. Resplittable threshold multi-broker proxy re-encryption scheme from lattices. J. Commun. 2017, 38, 157–164. [Google Scholar]
Nunez, D. Umbral: A Threshold Proxy Re-Encryption Scheme; NuCypher Inc. and NICS Lab, University of Malaga: Málaga, Spain, 2018. [Google Scholar]
Luo, F.; Al-Kuwari, S.; Wang, F.; Chen, K. Attribute-based proxy re-encryption from standard lattices. Theor. Comput. Sci. 2021, 865, 52–62. [Google Scholar] [CrossRef]
Huang, Q.; Yang, Y.; Fu, J. PRECISE: Identity-based private data sharing with conditional proxy re-encryption in online social networks. Future Gener. Comput. Syst. 2018, 86, 1523–1533. [Google Scholar] [CrossRef]
Yao, S.; Dayot, R.V.J.; Kim, H.-J.; Ra, I.-H. A novel revocable and identity-based conditional proxy re-encryption scheme with ciphertext evolution for secure cloud data sharing. IEEE Access 2021, 9, 42801–42816. [Google Scholar] [CrossRef]
Ajtai, M. Generating hard instances of lattice problems. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 22–24 May 1996; pp. 99–108. [Google Scholar] [CrossRef]
Agrawal, S.; Boneh, D.; Boyen, X. Efficient lattice (h) ibe in the standard model. In Proceedings of the Eurocrypt 2010, Berlin, Heidelberg, 30 May–3 June 2010; pp. 553–572. [Google Scholar]
Regev, O. On lattices, learning with errors, random linear codes, and cryptography. J. ACM JACM 2009, 56, 1–40. [Google Scholar] [CrossRef]
Aono, Y.; Boyen, X.; Phong, L.T.; Wang, L. Key-private proxy re-encryption under LWE. In Proceedings of the Progress in Cryptology–INDOCRYPT 2013: 14th International Conference on Cryptology in India, Mumbai, India, 7–10 December 2013; pp. 1–18. [Google Scholar] [CrossRef]
Boneh, D.; Gentry, C.; Gorbunov, S.; Halevi, S.; Nikolaenko, V.; Segev, G.; Vaikuntanathan, V.; Vinayagamurthy, D. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Proceedings of the Advances in Cryptology–EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, 11–15 May 2014; pp. 533–556. [Google Scholar] [CrossRef]
Gorbunov, S.; Vaikuntanathan, V.; Wee, H. Predicate encryption for circuits from LWE. In Proceedings of the Advances in Cryptology—CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015; pp. 503–523. [Google Scholar] [CrossRef]
Brakerski, Z.; Vaikuntanathan, V. Constrained Key-Homomorphic PRFs from Standard Lattice Assumptions: Or: How to Secretly Embed a Circuit in Your PRF. In Proceedings of the Theory of Cryptography: 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, 23–25 March 2015; pp. 1–30. [Google Scholar] [CrossRef]
Kim, S.; Wu, D.J. Watermarking PRFs from lattices: Stronger security via extractable PRFs. In Proceedings of the Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2019; pp. 335–366. [Google Scholar] [CrossRef]
Liang, X.; Weng, J.; Yang, A.; Yao, L.; Jiang, Z.; Wu, Z. Attribute-based conditional proxy re-encryption in the standard model under LWE. In Proceedings of the Computer Security–ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, 4–8 October 2021; pp. 147–168. [Google Scholar] [CrossRef]
Håstad, J.; Impagliazzo, R.; Levin, L.A.; Luby, M. A pseudorandom generator from any one-way function. SIAM J. Comput. 1999, 28, 1364–1396. [Google Scholar] [CrossRef]
Deng, Y. A Linearly Homomorphic Signature Scheme on Lattice. Henan Sci. 2015, 33, 1346–1351. [Google Scholar]

Figure 2. The workflow of AB-VCPRE.

Table 1. Comparison of related work.

	Construction Tool	Resisting Quantum Attack	Robustness	Method for Robustness	Tool for Robustness
Scheme [15]	DBDH	No	No	None	None
Scheme [12]	Discrete logarithm	No	Yes	zero-knowledge proof	Decisional discrete logarithm
Scheme [11]	Lattice	No	Yes	zero-knowledge proof	Decisional discrete logarithm
Our scheme	Lattice	Yes	Yes	Homomorphic signature	Lattice

Table 2. Computational and communication complexity comparison.

	Message	Size of Ciphertext	Size of Re-Encryption Key	Encryption Complexity	Re-Encryption Complexity	Verification Complexity
Scheme [15]	${0, 1}$	8 $\|ℤ_{q}\|$	8 $\|ℤ_{q}\|$	$T_{p} + 8 T_{e} + T_{s}$	$2 T_{p} + T_{e} + T_{v}$	None
Scheme [12]	${0, 1}^{m}$	4 $\|ℤ_{q}\|$	6 $\|ℤ_{q}\|$	$3 T_{e} + T_{m}$	$3 T_{e} + T_{m}$	$2 T_{e} + T_{h}$
Scheme [11]	${0, 1}$	$(n + 1) \|ℤ_{q}\|$	$(n m + 1) (n + 1) \|ℤ_{q}\|$	$2 T_{m}$	$2 T_{m}$	$(n m + 1) (n + 1) T_{e}$
Our scheme	${0, 1}^{m}$	$(ℓ + 2) m \|ℤ_{q}\|$	$(4 k + 2) m^{2} \|ℤ_{q}\|$	$5 T_{m}$	$3 T_{m} + T_{s}$	$T_{h} + T_{G V P}$

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

Tang, Y.; Jin, M.; Meng, H.; Yang, L.; Zheng, C. Attribute-Based Verifiable Conditional Proxy Re-Encryption Scheme. Entropy 2023, 25, 822. https://doi.org/10.3390/e25050822

AMA Style

Tang Y, Jin M, Meng H, Yang L, Zheng C. Attribute-Based Verifiable Conditional Proxy Re-Encryption Scheme. Entropy. 2023; 25(5):822. https://doi.org/10.3390/e25050822

Chicago/Turabian Style

Tang, Yongli, Minglu Jin, Hui Meng, Li Yang, and Chengfu Zheng. 2023. "Attribute-Based Verifiable Conditional Proxy Re-Encryption Scheme" Entropy 25, no. 5: 822. https://doi.org/10.3390/e25050822

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

Article Menu

Attribute-Based Verifiable Conditional Proxy Re-Encryption Scheme

Abstract

1. Introduction

2. Related Work

3. Preliminaries

3.1. Lattice

3.2. Related Functions and Tools

3.2.1. Functions of Bits and Power2

3.2.2. Discrete Gaussian Distribution

3.3. Key Homomorphism

3.4. Homomorphic Signature

3.5. Robustness

4. The Model of AB-VCPRE with Re-Encryption Verification

4.1. Scheme Definition

4.2. Security Model

5. Our Scheme

5.1. Our Scheme Composition

5.2. Correctness and Parameters

5.2.1. The Correctness of the Original Ciphertext

5.2.2. Correctness of Conversion Ciphertext

5.2.3. Correctness of Ciphertext Verification

5.3. Security

6. Efficiency Analysis

7. 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