A more efficient leveled strongly-unforgeable fully homomorphic signature scheme

A more efficient leveled strongly-unforgeable fully homomorphic signature scheme

Information Sciences 480 (2019) 70–89 Contents lists available at ScienceDirect Information Sciences journal homepage: www.elsevier.com/locate/ins ...

744KB Sizes 0 Downloads 1 Views

Information Sciences 480 (2019) 70–89

Contents lists available at ScienceDirect

Information Sciences journal homepage: www.elsevier.com/locate/ins

A more efficient leveled strongly-unforgeable fully homomorphic signature scheme Fucai Luo a,b, Fuqun Wang c,d,e,∗, Kunpeng Wang a,b, Kefei Chen c,d,e a

State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China c Department of Mathematics, Hangzhou Normal University, Hangzhou, China d Guangxi Key Laboratory of Cryptography and Information Security, Guilin, China e Westone Cryptologic Research Center, Beijing, China b

a r t i c l e

i n f o

Article history: Received 11 July 2018 Revised 18 October 2018 Accepted 13 December 2018 Available online 14 December 2018 Keywords: Homomorphic signatures Adaptive chosen-message attacks Small integer solution

a b s t r a c t Homomorphic signatures (HS) allow anyone to perform arbitrary efficient computation on signed data, whose output can be verified using the corresponding public verification key, without needing to have the underlying data. Existing HS schemes (e.g., Gorbunov et al., 2015; Fiore et al., 2016) are however inefficient in generating signatures, due to the fact that the signing algorithm can only generate one signature for an individual message at a time. In this work, we propose a new leveled fully homomorphic signature scheme, which only needs to call the signing algorithm twice for generating signatures for all messages in a dataset. This is a significant improvement in efficiency over the previous HS schemes that need to call the signing algorithm for polynomial times. We achieve this by using a vector encoding technique, which encodes all messages in a dataset into two matrices. Furthermore, we prove that our construction is secure against fully adaptive chosen-message attacks under the standard small integer solution (SIS) assumption. © 2018 Elsevier Inc. All rights reserved.

1. Introduction Homomorphic signature (HS) scheme is a very attractive cryptographic primitive that can be used to solve many problems in cloud computing [21,22,31,41], such as remote data integrity checking, computation on authenticated data, electronic voting, electronic health records, and so forth. In particular, fully homomorphic signatures (FHS), supporting arbitrary computation on signed data, enable an untrusted server to run more complex data mining algorithms on the given data set [10,32]. In a HS scheme, a user uses his secret signing key to generate signature vector σ = (σ1 , · · · , σ ) for message vector μ = (μ1 , · · · , μ ) in a so-called dataset, and then stores the signature vector and message vector on a remote server. The server then performs computation y = f (x ) on the message vector, in the meantime/after that, he produces a short signature σ f homomorphically using the public key and the signature vector. The signature σ f should be short, with length independent of the size of the message vector μ. Anybody can verify the tuple (f, f(μ), σ f ) using his public verification key and become convinced that f(μ) is indeed the correct output of the computation f over the message vector μ, without needing to download the entire messages from the server. In particular, this allows the user to verify computations over his



Corresponding author at: Department of Mathematics, Hangzhou Normal University, Yuhangtang Road No. 2318, Hangzhou, Zhejiang 311121, China. E-mail address: [email protected] (F. Wang).

https://doi.org/10.1016/j.ins.2018.12.025 0020-0255/© 2018 Elsevier Inc. All rights reserved.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

71

outsourced data with low communication complexity and with minimal interaction consisting of a single message from the server to the user. 1.1. Previous work HS schemes have been initially designed to establish authentication in network coding and to address pollution attacks [11,35]. Johnson et al. [33] first introduced a formal definition and a precise framework for homomorphic signatures. Thereafter, a flurry of works have been proposed, which however are restricted to only supporting linear function (e.g., [17,20,26,44]) and constant-degree polynomial function (e.g., [10,18]). To overcome these restrictions, Gorbunov et al. [31] used the homomorphic techniques developed in [4,12] to construct the first leveled FHS scheme. Their leveled FHS scheme can evaluate arbitrary polynomial-depth circuits over signed data and allow further homomorphic evaluations on evaluated signatures (henceforth, they refer to the evaluated signatures after homomorphic evaluations). They furthermore introduced a new notion called homomorphic trapdoor functions (HTDF) to unite homomorphic encryption [43] and signatures conceptually. In particular, in [31], the size of the evaluated signature grows polynomially in maximal depth d, so does our leveled FHS scheme in this paper. Unfortunately, the leveled FHS scheme [31] is only secure in the selective security model assuming the hardness of the small integer solution (SIS) problem in the standard lattices, as the adversary must announce ahead of time a challenge tag and a message vector in a dataset identified by the tag on which the adversary will make a forgery. Though it is possible to convert a HS scheme satisfying selective security into one that satisfies adaptive security by the standard complexity leveraging arguments (e.g., as used in attribute-based encryption [30]), it will lead to a rather large multiplicative overhead - polynomial in the security parameter. Moreover, the resulting security reduction will suffer a loss proportional to both the length of the tag and the number of messages allowed in each dataset. Subsequently, focusing on the security problem existed in [31], Boyen et al. [14] presented an adaptively secure leveled FHS scheme, using the “lattice mixing” trick by Boyen [13]. More precisely, they modified the leveled FHS scheme in [31] by incorporating a mixing of public-key matrices in a message-dependent manner, so as to divide message space into “known” and “unknown” parts at an appropriate scale. In the security proof, the simulator is able to answer the adversary’s signing queries by using a publicly known trapdoor of “gadget matrix [38]”, and finally solves the SIS problem by exploiting the forgery the adversary has made. This is due to the fact that: in the “known” part, the trapdoor does not disappear, so that the simulator can sign so as to answer the signing queries; while the trapdoor disappears in the “unknown” part, then the simulator cannot sign, but it can solve the SIS problem by exploiting the forgery. It works because, the probability that, the signing queries fall in the “known” part while the forgery falls in the “unknown” part, is non-negligible. Technically, the security proof is achieved by taking advantage of the “partitioning technique” prevalently used in constructing compact identity-based encryption (IBE) schemes (see [1,5,23,34]). It is worth noting that, to make this “partitioning technique” work with sufficient probability, the simulator has to use the double public-key matrices (compared with Gorbunov et al. [31]) to pre-generate signatures so as to answer all possible signing queries even when the trapdoor has vanished. However, the security proof requires random tags, rather than the tags chosen by the adversary, so Boyen et al. [14] first considered constructing and proving a relaxed notion of adaptive security (only adaptive queries at the dataset level but not at message level). They then modified their original scheme by assembling and using the tag carefully to achieve fully adaptive security. We refer interested reader to Boyen et al. [14] for more details. Note that the FHS schemes (including our FHS scheme) mentioned above are “leveled” homomorphic but not fully fledged ones. The “leveled” means that these FHS schemes can only evaluate circuits of a-priori polynomial-depth, hence, the number of messages in a dataset has to be pre-defined and using tag as the dataset identifier is necessary. In particular, the tag can be embedded into the public key, which plays an important role in the security proof. 1.2. Our results Our start point is Boyen et al.’ adaptively secure leveled FHS scheme [14]. As remarked above, the authors in [14] only improves the security, but not the efficiency, of Gorbunov et al.’ leveled FHS scheme [31]. In this work, we would like to improve the efficiency of generating signatures in a leveled FHS scheme while still achieving fully adaptive security. Indeed, in the previous leveled FHS schemes, whenever one wants to obtain a fresh signature (rather than the evaluated signature after homomorphic evaluations) for a message, he always has to run the signing algorithm. Since the messages in a dataset are restricted to binary values, that raises a question: can we call the signing algorithm a few times to get a few signatures, and then use these few signatures to generate signatures for all messages in a dataset (recall that the number of messages in a dataset is bounded by a pre-defined polynomial), as is the case in batch processing or packing? We give a positive response by showing the following results: • We propose a more efficient leveled strongly-unforgeable FHS scheme, using the vector encoding technique. Specifically, to generate signatures for all of the messages in a dataset, our leveled FHS scheme only needs to run the signing algorithm twice. This is a significant improvement in efficiency over the previous leveled FHS schemes that need to invoke the signing algorithm for polynomial times. • The signatures in our leveled FHS scheme are compact, in the sense that the size of the evaluated signature depends at most logarithmically on the size of the input dataset. Specifically, for the security parameter λ and the maximum size  of inputs for the circuits, the size of the evaluated signature is not more than p(λ) · log .

72

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

• We prove that our leveled FHS scheme is secure against fully adaptive chosen-message attacks under the standard small integer solution (SIS) assumption, without a cumbersome modification required by Boyen et al. [14]. • We use the Barrington’s Theorem [8] to transform the Boolean circuit involved in our leveled FHS scheme into a polynomial length, width-5 permutation branching program. This largely reduces the size of the evaluated signature from mO(dmax ) to O(m · 4dmax ), where dmax is the maximum depth of the circuit. The smaller size of the evaluated signature implies a smaller modulus q, and hence the efficiency and security of the proposed leveled FHS scheme can be further improved. Moreover, our leveled FHS scheme can also be made context hiding (for its definition, see [14,31]), so that a signature

σ f does not reveal any additional information about the underlying data x beyond the output y = f (x ). Our approach for achieving context hiding is the same as that used by Gorbunov and co-workers [14,31], so we will not present it in this paper. As for the verification efficiency, our leveled FHS scheme is almost the same as Gorbunov and co-workers [14,31] that also allows for fast amortized verification of a computation f on many different datasets, even if the datasets belong to different users with different verification keys. In particular, the verifier only needs to perform work proportional to the circuit size of f once to verify arbitrarily many signatures under arbitrary verification keys. While in reality, this work can be performed offline prior to receiving the signatures, and can be amortized when verifying the same computation over many datasets, and then the online verification can be much more efficient than computing f. 1.3. Overview of our techniques In order to reduce the number of times of running the signing algorithm, we employ the vector encoding technique proposed by Apon et al. [5]. This vector encoding technique utilizes an extended gadget matrix defined by Micciancio and Peikert [38]. Specifically, for a vector v = (v1 , · · · , v ) ∈ Zq , the encoding algorithm computes Ev = encode(v ) =

×m n×m [v1 In | · · · |v In ]Gn ∈ Zn , where Gn is an extended gadget matrix. Then we can compute Evi = Ev G−1 , q n (Pi Gn ) = vi Gn ∈ Zq T where Pi is an n × n extended unit matrix: Pi = [0n | · · · |0n |In |0n | · · · |0n ]. Recall that in the previous leveled FHS schemes, for example, in [14], the signature σ i corresponding to the message μi is obtained by running the PPT algorithm SampleLeft(A∗ , A + Tτ , TA∗ , Di,b[i] + μi Gn , s ) (the SampleLeft algorithm was initially proposed by Agrawal et al. [1], skip to Lemma 3.3), where A∗ , A and Di, b[i] are the public-key matrices, TA∗ is the secret-key matrix, i is the index of message μi in a dataset identified by a tag τ , and Tτ is computed from a sequence of the public-key matrices {Ti }i ∈ [λ] and the tag τ . Then it holds that [A∗ |A + Tτ ] · σi = Di,b[i] + μi Gn , where the matrix Di, b[i] binds the signature σ i to the message μi indexed by i. Therefore, given a message vector μ = (μ1 , · · · , μ ) ∈ {0, 1} , we have to run the above PPT algorithm SampleLeft  times to get a signature vector σ = (σ1 , · · · , σ ). This is very inefficient in the face of massive amounts of data in cloud. At first sight, we can directly apply the above vector encoding technique to Boyen et al. [14]. In more details, given a message vector μ = (μ1 , · · · , μ ) ∈ {0, 1} , we first encode the message vector, resulting in a matrix [μ1 In ||μ In ]Gn . Then we run the PPT algorithm SampleLeft(A∗ , A + Tτ , TA∗ , D + [μ1 In | · · · |μ In ]Gn , s ) to get a “pre-signature” σ (note that at this point we just need one public-key matric D), which satisfies

[A∗ |A + Tτ ] · σ = D + [μ1 In | · · · |μ In ]Gn .

(1)

Finally, for the index i ∈ [] of message μi , we multiply Eq. (1) by G−1 n (Pi Gn ), and obtain the equation

[A∗ |A + Tτ ] · σi = DG−1 n (Pi Gn ) + μi Gn , −1 where σi = σ · G−1 n (Pi Gn ). This is reasonable because Gn is a deterministic inversion function (which will be defined in −1 Section 3), and for any i = j, it holds that Gn (Pi Gn ) ∩ G−1 n (P j Gn ) = ∅, and hence we have σi ∩ σ j = ∅. In particular, since there is at most one number 1 in each column of matrix G−1 n (Pi Gn ), while the remainder is zero, then every σ i is made up of some parts of σ and is thus very “sparse”. However, the above construction can only satisfy selective security, in the sense that the adversary must announce ahead of time a challenge tag and a message vector in a dataset identified by the tag on which the adversary will make a forgery. This is because, there is only one public matrix D, then the simulator cannot pre-generate signature for any message μ if the message is unknown (note that the message μ = 0 or μ = 1 that brings about two possibilities in generating signature). Concretely, we assume that the message vector submitted by the adversary is μ = (μ1 , · · · , μζ ) ∈ {0, 1}ζ . We also assume w.l.o.g that ζ < , and then encode the message vector to [μ1 In ||μζ In |In ||In ]Gn by padding unit matrix or [μ1 In ||μζ In |0n ||0n ]Gn by padding null matrix. The simulator can answer the adversary’s signing queries by running the SampleLeft algorithm or pre-generating some signatures for the challenge tag. In the adaptive security model, the simulator has to pre-generate two signatures for messages 0 and 1 without knowing the message μ, and this will result in two different public-key matrices D0 and D1 . While the two different public-key matrices contradict the above construction containing only one public matrix D. From the above, we can conclude that there are some challenges in applying the vector encoding technique to the existing leveled FHS schemes. Aiming at the challenges, this paper puts forward a new solution. Specifically, we encode two vectors 1 = (1, · · · , 1 ) ∈ 1 and 0 = (0, · · · , 0 ) ∈ 0 to [In ||In ]Gn and [0n ||0n ]Gn , respectively. Then given a message vector μ = (μ1 , · · · , μ ) ∈ {0, 1} in a dataset identified by a tag τ , we run the PPT algorithm SampleLeft

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

73

(A∗ , A + Bτ , TA∗ , Dk + [kIn | · · · |kIn ]Gn , s ) twice, resulting in two “pre-signatures” σ k for k = 0, 1, satisfying [A∗ |A + Bτ ] · σk = Dk + [kIn | · · · |kIn ]Gn . For i ∈ [] and any message μi ∈ {0, 1} indexed by i, let k = μi and compute σk,i = σk · G−1 n (Pi G ), then we have

[A∗ |A + Bτ ] · σk,i = Dk G−1 n (Pi G ) + μi Gn . At last, we take σ k,i as the signature of the message μi . 1.4. Overview of the security proof As for the security of our leveled FHS scheme, the technique we employ is very similar to the “partitioning technique”. In particular, some parts of our security proof are the same as that of Apon et al. [5]. This is because we use the key technique by Apon et al. [5] to generate the above matrix Bτ ; though, the identity information is taken as input for generating the matrix Bτ by Apon et al. [5] while we input the tag τ to generate the matrix Bτ . This matrix Bτ plays a central role in helping the simulator answer the adversary’s signing queries and solve the SIS problem by utilizing the adversary’s forgery in the security proof. More precisely, we have to call the algorithm PubEval(τ ,ν,t ) (B, B , hz,α ,β ) by Apon et al. [5] to generate Bτ ,

which satisfies Bτ = ARτ + Eτ Gν n , where, ν , t, B and B are the public keys, Eτ = [hz1 ,α1 ,β1 (τ )In | · · · |hzu ,αu ,βu (τ )In |0n | · · · |0n ],  ), A, R, R , h ,β and the matrix Rτ can be computed by running the algorithm TrapEval(τ ,ν,t ) ((z, α  ) by Apon et al.  ,β z,α [5] (skip to Lemma 3.9). The signing queries must contain a tag τ , i.e., the signing queries are of the form (τ j , μi ), in that messages are allocated to different datasets identified by tags. Then for j ∈ [|Q|], where |Q| is the maximum number of tags involved in the signing queries, the simulator can answer the signing queries and solve the SIS problem successfully, so long as the probability that, Eτ j is a non-zero vector for the tag τ j of the signing queries while Eτ ∗ is a zero vector for the tag τ ∗ of the adversary’s forgery, is non-negligible. This is mainly due to the fact that the simulator can use the Gν n -trapdoor (skip to Lemma 3.5) to generate signatures for answering the signing queries when Eτ ∗ = 0; while once the Gν n -trapdoor disappears (i.e., Eτ ∗ = 0), the simulator can solve the SIS problem by setting up the public-key matrices appropriately in advance. 1.5. Related work HS schemes with restricted homomorphisms. A range of prior works (see [6,10,17,26]) constructed homomorphic message authentication codes (MACs with private verification) and homomorphic signatures (public verification) for restricted homomorphisms, and almost exclusively for linear functions [19,36]. These MACs and signatures have interesting applications in network coding and proofs of retrievability. In some cases, however, linear functions are not enough, e.g., some problems in secure multi-party computation. Boneh and Freeman [10] proposed the first HS scheme that is capable of evaluating multivariate polynomials on signed data, where the maximal degree k of the polynomial is fixed a priori and the size of the evaluated signature grows (polynomially) with k. Their system uses ideal lattices in a way that is a “signature analogue” of Gentry’s fully homomorphic encryption [27], and the security is based on hard problems on ideal lattices similar to those in Gentry’s system. Catalano et al. [18] gave a HS scheme using multi-linear maps that removes the need for random oracles at the cost of having large public parameters. Leveled FHS schemes and MACs. In the aspects of extension of leveled FHS, Wang et al. [42] extended the HTDF, the underlying primitive of leveled FHS in [31], to identity-based setting with stronger security and better parameters. The stronger security is achieved by building an identity-based HTDF (IBHTDF) that is not only claw-free, but also collisionresistant; while the better parameters is achieved by using a permutation branching program to replace Boolean circuit in performing homomorphic computation on signed data. Fiore et al. [25] proposed multi-key homomorphic authenticators (HAs) by extending the leveled FHS in [31] to multi-key homomorphic signatures (M-HS) based on standard lattice assumptions, and introduced multi-key homomorphic MAC based on pseudorandom functions. HAs allow a user to authenticate a vector of data elements μ = {μ1 , · · · , μ } and outsource them, along with the corresponding authenticators, to an untrusted server. The server can generate a short authenticator vouching for the correctness of the output y = f (μ ). Multi-key HAs are similar to HAs, except with the extra feature of allowing the server to compute on data authenticated under different secret keys. But the two schemes mentioned above are only secure in the selective security model, and hence have to resort to the standard complexity leveraging arguments for achieving fully adaptive security. HS schemes via SNARKs. One method that would allow us to design FHS (publicly verifiable) is to rely on CS-Proofs [37] or, more generally, succinct non-interactive arguments of knowledge for NP (SNARKs) [9,24,40]. This primitive allows us to non-interactively generate a short “argument” π for any NP statement so that π proves “knowledge” of the corresponding witness. The length of π is independent of the statement/witness size, and the complexity of verifying π only depends on the size of the statement. Then use SNARKs, we create a short argument π that proves the knowledge of “data x along with valid signature of x, such that f(x) = y”, and then we can authenticate the output y = f (x ) of any computation f over any signed data x. As for the security of the SNARK-based scheme, since this is an argument of knowledge, a forged signature for the output of the function f allows us to extract out a forged signature for the underlying input data, which breaks the security of signatures. One obvious advantage of the SNARK-based scheme is that a signature can be verified very efficiently, independently

74

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

of the complexity of the computation f, as long as f has a short Turing-Machine description. In contrast, in this work, we can only achieve efficient verification in an amortized sense, when verifying a computation f over many different datasets. Unfortunately, constructing succinct non-interactive arguments for NP, even without a “knowledge” requirement, is known to require the use of non-standard assumptions [29]. Current constructions either rely on the random-oracle heuristic and the use of PCP machinery or on various “knowledge of exponent” assumptions. Other types of homomorphic authentication. Johnson et al. [33] proposed redactable signatures and set-homomorphic signatures. In redactable signatures scheme, given a signature on a long message x, anyone can derive a signature on a subset/substring of x. Redactable signatures were studied later in various works [7,16]. Hyun Ahn et al. [2] gave a general notion of P-homomorphic signature schemes for various predicates P, but efficient constructions were only known for a few specific instances. 2. Preliminaries We say that a function is negligible, written negl(n), if negl(n) is smaller than all polynomial fractions for sufficiently large n. Let PPT denote probabilistic polynomial-time. For a positive integer q, we define the set Zq  [−q/2, q/2 ) ∩ Z. In this paper, all logarithms on q are to base 2, and all discrete Gaussian distributions D are centered at zero, unless otherwise stated. We denote vectors in bold lowercase (e.g., x) and matrices in bold uppercase (e.g., A); AT (resp. xt ) denotes the  transpose of the matrix A (resp. x). We denote by [A|B] ∈ Rn×(m+m ) the column concatenation of matrices A ∈ Rn×m and  n ×m B∈R . For ease of use, we let [n]{1, , n} and |x| denote the number of bits in a string or the number of elements of vector x. For any matrix A ∈ Rn×m , A ∈ X n×m (resp. A ← X n×m ) denotes that for i ∈ [n], j ∈ [m] its entry A[i][ j] ∈ X (resp. A[i][ j] ← X ), where X is a set or a distribution. This also applies to vector. For matrix A ∈ Rm×k , its matrix norm is defined as ||A|| := max{||Ax|| : ||x|| = 1}, where || · || denotes Euclidean norm for vectors. Moreover,  A denotes the Gram-Schmidt orthogonalization of A, and || A|| refers to the Gram-Schmidt norm of A. 2.1. Definition of fully homomorphic signatures In fact, the syntax of FHS is very similar to digital signatures, except that there is an additional polynomial-time algorithm

Eval in FHS. We now define FHS, along with the strong security notion that will be used throughout this work. We follow

the notation and syntax presented in [14,31]. We use λ ∈ N to denote the security parameter and  ∈ N to denote the maximum size of a dataset. Let M denote a message space and C denote a collection of circuits satisfying C : M → M that inputs  messages and outputs a result message in M. We remark that  also denotes the maximum size of inputs for the circuit family C. A FHS for the circuit family C (or called C-FHS) is a tuple of polynomial-time algorithms (Setup, KeyGen, Sign, Eval,Verify), which works as follows: • Setup(1λ , 1 ). On input the security parameter λ and the maximum size  of inputs for the circuit. Output a public key pk and a secret key sk. • KeyGen(pk, τ ). On input a public key pk, and a tag τ = {τ0 , · · · , τ|τ|−1 } ∈ {0, 1}|τ|≥λ of a dataset. Output a verification key vk. • Sign(sk, vk, τ , μi , i). On input a secret key sk, a verification key vk, a dataset tag τ , a message μi ∈ M and its index i ∈ [] (the message μ indexed by i belongs to the dataset specified by the tag τ ). Output a signature σ containing (μi , i) and the dataset tag τ . ,σ  , f ). On input a verification key vk, a dataset tag τ , a  -dimensional message vector μ = (μ1 , · · · , μ ) ∈ • Eval(vk, τ , μ  M , a  -dimensional signature vector σ = (σ1 , · · · , σ ), where  ≤ , and a circuit f ∈ C. Output an evaluated signature  ) and the circuit f. We reiterate that the tags are used to σ f along with the dataset tag τ , an evaluated message f (μ differentiate the datasets, which can also be regarded as dataset identifiers.  ), f ). On input a verification key vk, a dataset tag τ , an evaluated signature σ f , an evaluated message • Verify(vk, τ , σ f , f (μ  ) and a circuit f ∈ C. Output reject (0) or accept (1). f (μ In this work, we focus on FHS under multiple datasets and single-key, where different datasets correspond to different verification keys but the same secret key. The tag serves to distinguish between datasets and is embedded into the public key, resulting in the verification key. This implies that only signatures with the matching tag can be homomorphically computed, and that the evaluated signature can only be verified by the matching verification key. Definition 2.1 (Correctness). We say that a C-FHS scheme is correct if: • For all tags τ = {τ0 , · · · , τ|τ|−1 } ∈ {0, 1}|τ|≥λ , all messages μ ∈ M and all indices i ∈ [], we have





P r ( pk, sk ) ← Setup(1λ , 1 ); vk ← KeyGen( pk, τ ) : Verify(vk, τ , σ , μ ) = 1 = 1, where σ ← Sign(sk , vk , τ , μi , i ) and the probability is over the coins of the algorithms in the C-FHS scheme.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

75 

• For all tags τ = {τ0 , · · · , τ|τ|−1 } ∈ {0, 1}|τ|≥λ , all message vectors μ = (μ1 , · · · , μ ) ∈ M , where  ≤ , and all circuits f ∈ C, we have





 ), f ) = 1 = 1, P r ( pk, sk ) ← Setup(1λ , 1 ); vk ← KeyGen( pk, τ ) : Verify(vk, τ , σ f , f (μ ,σ  , f ) and the probability is over the coins of the where σi ← Sign(sk , vk , τ , μi , i ), σ = (σ1 , · · · , σ ), σ f ← Eval(vk, τ , μ algorithms in the C-FHS scheme.  ) = μi , the correctness of evaluated message signatures Note that when the circuit f is a projection circuit Pi , i.e., Pi (μ also implies the correctness of individual message signature. Definition 2.2 (Succinctness). We say that a C-FHS scheme is succinct if, for the security parameter λ, any tag τ =  {τ0 , · · · , τ|τ|−1 } ∈ {0, 1}|τ|≥λ , all message vectors μ = (μ1 , · · · , μ ) ∈ M , where  ≤ , and all circuits f ∈ C, we have



P r ( pk, sk ) ← Setup(1λ , 1 ); vk ← KeyGen( pk, τ ) :

 ||σ f || ≤ p(λ ) log  = 1,

,σ  , f ). where σi ← Sign(sk , vk , τ , μi , i ), σ = (σ1 , · · · , σ ) and σ f ← Eval(vk, τ , μ 2.2. Security definition At an intuitive level, we say that a homomorphic signature is secure if an adversary, without knowledge of the secret key, can only get signatures from legitimate signers, or evaluated signatures by running the Eval algorithm on signatures generated by legitimate signers. Formalizing this security notion turns out to be tricky because there exist several different possibilities concerned with the forgery the adversary will make. Boyen et al. [14] defined two adaptive security models: fully adaptive queries at the message level and adaptive queries at the dataset level, which depends on whether the adversary A is allowed to adaptively query signature of any individual message in a given dataset, and even interleave such queries across several datasets, or whether A is only allowed to adaptively query signatures of all messages in a given dataset at a time. These two security notions share the same security experiment between a challenger and an adversary A, while the only difference lies in what is considered a forgery. In this work, since our scheme satisfies the model of fully adaptive queries at the message level, we directly define the notion of Existential Unforgeability under Fully Adaptive Chosen-Message Attacks (EU-F-ACMA), using the following experiment ExptEU-F-ACMA ( 1λ ). A Setup. The challenger gets (pk, sk) by running ( pk, sk ) ← Setup(1λ , 1 ), and then sends pk to the adversary A. Signing Queries. The adversary A adaptively submits queries of the form (τ , μi , i), where the tag τ ∈ {0, 1}|τ | ≥ λ is a dataset identifier, the message μi ∈ M and its index i ∈ []. The challenger proceeds as follows: • If (τ , μi , i) is the first query for the tag τ , the challenger initializes an empty list Tτ = ∅ for τ and then adds the tuple (μi , i) to the list Tτ . Then, the challenger computes vk ← KeyGen( pk, τ ) and σ ← Sign(sk , vk , τ , μi , i ). Finally, the challenger sends σ to A and stores σ just in case the same query is requested again. If necessary, the verification key vk can be sent to A as well, though the adversary A can also generate the verification key by running the KeyGen algorithm. • If Tτ has not yet contained a tuple (μi , i), the challenger counts the number of tuples in Tτ . If the number is less than , the challenger computes vk ← KeyGen( pk, τ ) and σ ← Sign(sk , vk , τ , μi , i ). Then, the challenger returns σ to A, stores σ and updates the list Tτ ← Tτ ∪ (μi , i). Otherwise, the challenger aborts the experiment. This procedure is necessary, as the system requires the maximum size of messages in a dataset to be no more than . • If (μi , i) ∈ Tτ , the challenger replies with the same signature generated before. • If Tτ contains a tuple (μi , i ) but μi = μi , the challenger ignores the query. Note that the message μi is indexed by its index i. Forgery. The above signing queries are executed till the adversary A outputs a forgery tuple (τ ∗ , σ f∗∗ , μ∗ , f ∗ ), where

 ∗, σ  ∗ , f ∗ ). The experiment outputs 1 iff σ f∗∗ ← Eval(vk, τ ∗ , μ Verify(vk, τ ∗ , σ f∗∗ , μ∗ , f ∗ ) = 1, and either

• Type I forgery. For all j ∈ [|Q|], τ ∗ = τ j , where we denote by |Q| the upper bound on the number of tags involved in the adversary’s signing queries, or, • Type II forgery. τ ∗ = τ j for some j ∈ [|Q|], and one of the following properties is satisfied: (a) Type (a) forgery. All of the components of the forgery are the same as that generated honestly, except that μ∗ =  ∗ ). f ∗ (μ (b) Type (b) forgery. All of the components of the forgery are the same as that generated honestly, except that there is at least one message-index tuple (μ∗i , i ) which has not been queried, i.e., (μ∗i , i ) ∈ / Tτ j . (c) Type (c) forgery. All of the components of the forgery are the same as that generated honestly, except that there is at least one message-index tuple (μ∗i , i ) which is not equal to the counterparts in Tτ j , i.e., Tτ j contains the messageindex tuple (μi∗ , i ) but μi∗ = μ∗i .

76

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

(d) Type (d) forgery. All of the components of the forgery are the same as that generated honestly, except that σ f∗∗ = σ f ∗ , where σ f ∗ is generated honestly. Definition 2.3 (Unforgeability). We say that a homomorphic signature scheme is fully unforgeable against fully adaptive chosen-message attacks with respect to a family circuit C taking  ∈ N as input, if for the security parameter λ ∈ N, no PPT adversary A can win the experiment ExptEU-F-ACMA (1λ ) with non-negligible probability. A  ∗ ). By Note that in [14], the Type-B Forgery in their security experiment only considered one case that τ ∗ = τ j , μ∗ = f ∗ (μ contrast, the Type II forgery in the above security experiment describes four cases and is therefore more comprehensive. 2.3. Lattice background and small integer solution problem Lattices. Given a set of linearly independent vectors S = {s1 , · · · , sm } ⊂ Zm , the Z-linear combinations of the vectors constitute a full-rank m-dimensional integer lattice ⊂ Zm , which is a discrete additive subgroup whose linear span is Rm . For a matrix A ∈ Znq ×m , “q-ary” integer lattices are defined as:

⊥q (A ) = {x ∈ Zm : Ax = 0 mod q}, uq (A ) = {x ∈ Zm : Ax = u mod q}. In particular, if y ∈ uq (A ), then uq (A ) = ⊥ q ( A ) + y. Discrete Gaussian. Let L be a subset of Zm , for any s > 0, define the Gaussian function on Rm centered at c ∈ Rm with parameter s:

∀ x ∈ Rm , ρs,c (x ) = exp(−π ||x − c||2 /s2 ). Then the discrete Gaussian distribution over set L with center c ∈ Rm and parameter s is defined as:

∀ x ∈ L, Ds,c,L (x ) = where ρs,c (L ) =

 x∈L

ρs,c (x ) . ρs,c (L )

ρs,c (x ).

Lemma 2.4 ([1,38]). Regarding the Gaussian distribution defined above, we have the following results: √ 1. Let matrix U be chosen uniformly at random from {−1, 1}m×m , then P r[||U|| > 12 2m ] < e−2m . √ −

( m ) 2. Let matrix R be sampled from DZm×m ,s , then P r[||R|| > s m ] < 2 . 3. Gaussian distribution satisfies Pythagorean additivity: if X1 is Gaussian with parameter s1 , and X2 is Gaussian with  parameter s2 conditioned on any value of X1 (e.g., if X1 and X2 are independent), then X1 + X2 is Gaussian with parameter s21 + s22 . By induction this extends to the sum of any finite number of variables, each of which is Gaussian conditioned on any values of the previous ones. 4. Let R be sampled from DZm×m ,s (recall that we assume all Gaussian distributions are centered at zero in this paper), then for any matrix U chosen uniformly at random from {−1, 1}m×m , the distribution UR is statistically close to DZm×m ,s√m . Combining the above item 4 in Lemma 2.4 with Corollary 4.4 in [28], we can get the following Lemma 2.5. Lemma 2.5 (Adapted from Gentry et al. [28]). Let n and q > 2 be positive integers, and m ≥ 2nlog q. Let U be chosen uniformly at random from {−1, 1}m×m and R be sampled randomly from DZ2m×m ,s . For all but an at most 2q−n fraction of all A ∈ Znq ×m and for any s ≥ ω (



log m ), the distribution A([Im |U]R) is statistically close to uniform over Znq ×m .

Lemma 2.6 ([1]). Suppose that m > (n + 1 ) log q + ω (log n ) and that q > 2 is prime. Let U be chosen uniformly at random from {−1, 1}m×k for some polynomial k = k(n ). Let A, B be matrices chosen uniformly in Znq×m , Znq×k , respectively. Then, for all vectors T T w in Zm q , the distribution (A, AU, U w) is statistically close to distribution (A, B, U w). √ The small integer solution problem (SIS). Let n, m, q be integers and a real β ≥ mqn/m . Let A be matrix chosen n×m m uniformly at random from Zq . Find a non-zero integer vector z ∈ Z \ {0} such that Az = 0 mod q and ||z|| ≤ β . The SISq,n,m,β problem is known to be as hard as certain worst-case problems (e.g., SIVP) in standard lattices [3,39]. 3. Gadget matrix and some algorithms log q

Gadget matrix. For an integer q ≥ 2, we define the gadget matrix Gx := Ix gt , where g := (1, 2, · · · , 2log q−1 ) ∈ Zq x×m and Ix denotes the x-dimensional identity matrix. Moreover, we define the deterministic inversion function G−1 → x : Zq {0, 1}x×m where m = xlog q, which is equal to bit decomposition that decomposes x into its bit representation over Zq x×m and has the property that it holds that Gx · G−1 . Moreover, by padding zero, Gx ∈ Zxq×m can x (A ) = A for any matrix A ∈ Zq x×m  ¯ be padded into a matrix Gx ∈ Zq for m > xlog q, and the corresponding function G¯ −1 still works by padding zero. In x this work, there are several different gadget matrices, but we remark that the number of columns in these gadget matrices are set identically.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

77

Lemma 3.1 ([38], Lemma 5.3). Let n, q > 2 and m ≥ 2nlog q be integers, there is a PPT algorithm GenTrap(1n , 1m , q) that outputs a parity-check matrix A ∈ Znq ×m and a trapdoor X with a tag H such that the distribution of A is statistically close to ⊥ uniform. Then one can use the trapdoor X and any basis S for ⊥ q (Gn ) to generate a short basis TA for lattice q (A ), and the   parameters satisfy s (X ) ≤ 1.6 n log q and || T || ≤ 3.8 n log q, where s (X) is the largest singular value of X, which is defined 1

1

A

as s1 (X ) = max||u||=1 ||Xu||.

Remark 3.2. Note that it is easy to compute a basis S for ⊥ q (Gn ), whenever the modulus q is power-of-two or not, since Gn is gadget matrix whose trapdoor is publicly known. In particular, Micciancio and Peikert [38] built a short basis TGn for √ ⊥ q (Gn ) that satisfies ||TGn || ≤ 5. Lemma 3.3 ([1]). On input: (1) a rank-n matrix A ∈ Znq ×m , and any matrix B ∈ Znq ×m ; (2) a short basis TA for lattice ⊥ q ( A );  (3) a matrix D ∈ Znq ×m and a Gaussian parameter s > || TA || · ω ( log 2m ). Then there exists a PPT algorithm SampleLeft(A, B, TA , D, s) that outputs a matrix R ∈ Z2m×m distributed statistically close to D D (A ),s , where F = [A|B]. q

Definition 3.4 (Generalized G-trapdoor, [5]). Let A ∈ trapdoor for A is a matrix R ∈ Zm×m such that:

Znq ×2m

and Gν n ∈ Zνq n×m , where

ν ≥ 1 is an integer and m ≥ n. A Gν n -

 

A

R = HGν n Im

for some full row rank matrix H ∈ Znq ×ν n . We refer to H as the tag of the trapdoor, and we remark that this tag only needs to be full row rank, instead of being invertible as required in [38]. Lemma 3.5 ([5]). There exists an efficient PPT algorithm SampleDO (A¯ , R, H, D, s ), where R is a Gν n -trapdoor for matrix A = [A¯ | − A¯ R + HGν n ] ∈ Znq ×2m with full-rank tag H, a matrix D ∈ Znq ×m and an oracle O for Gaussian sampling over a desired coset ∗ 2m×m drawn from a distribution within negligible statistical distance of D ⊥ v (Gν n ). It outputs a matrix R ∈ Z D (A ),s , where q

s ≥ n4+ m4.5 .

In this paper, we briefly review Apon et al.’s [5] parallel repeated function H, encoding technique and packing/unpacking techniques. For simplicity, the PubEval and TrapEval algorithms are given as a lemma. These two algorithms will come in handy for constructing our leveled FHS scheme and proving its security. At a high level, a central step in constructing latticebased scheme in these works [1,5,34] is to design a hash function with “partition” property that can be homomorphically evaluated. The “partition” property implies: for the challenge identity x∗ and adaptively queried identities {x1 , , x|Q| }, the probability that, h(x∗ ) = 0 and h(xi ) = 0 for i ∈ [|Q|], is non-negligible (e.g., approximate 1 − 1/|Q |). Define a basic partition function that maps a boolean string τ = (τ0 , · · · , τ|τ|−1 ) ∈ {0, 1}|τ| to an integer in Zq as

hz,α ,β (τ ) = α fτ (z ) + β , where z ∈ [2|τ|2 ], α , β ∈ Zq and fτ (x ) = fined as

|τ|−1 i=0

τi xi . Then a parallel repetition function hz,α,β (τ ) : {0, 1}|τ| → Zνq can be de-

hz,α,β (τ ) = (hz1 ,α1 ,β1 (τ ), · · · , hzu ,αu ,βu (τ ), 0, · · · , 0 ),



where u ≤ ν, z ∈ 2|τ|2 following lemmas.



u

u

(2)

ν −u

, α, β ∈ Zuq and |τ |, ν , q are parameters that will be set later. In our security proof, we need the

Lemma 3.6 ([5], Lemma 6.1). Let Q ⊆ {0, 1}n , A, B be integers such that B ≤ A, |Q| ≤ δ B for some δ ∈ (0, 1), and let H : {0, 1}|τ| → Y be an almost pairwise independent hash function family which has the following parameters. • ∀ τ ∈ {0, 1}|τ| , P rh←H [hz,α,β (τ ) = 0] = 1/A.

• ∀ τ = τ ∗ ∈ {0, 1}|τ| , P rh←H [hz,α,β (τ ) = 0|hz,α,β (τ ∗ ) = 0] ≤ 1/B. Then for any element τ ∈ Q, we have

P rh←H [hz,α,β (τ ) = 0 ∧ hz,α,β (τ  ) = 0, ∀

τ  ∈ Q] ∈ ((1 − δ )/A, 1/A ).

Lemma 3.7 ([5], Lemma 6.3). For a random hash function hz,α,β (τ ) : {0, 1}|τ| ← Zνq , where u ≤ ν, z ∈ 2|τ|2 have

u

, α, β ∈ Zuq , we

1. ∀ τ ∈ {0, 1}|τ| , P r[hz,α,β (τ ) = 0] = (1/q )u .

2. ∀ τ = τ ∗ ∈ {0, 1}|τ| , P r[hz,α,β (τ ) = 0|hz,α,β (τ ∗ ) = 0] ≤ (1/|τ| )u . Note that in [5], the parameter u associated with the advantage  of the adversary has to be set appropriately to meet the condition that |τ |u approximates |Q|. Moreover, the above two lemmas result in the following lemma which the security of the scheme in [5] and our leveled FHS scheme rely on.

78

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

u

Lemma 3.8 ([5]). For a random hash function hz,α,β (τ ) : {0, 1}|τ| → Zνq , where u ≤ ν, z ∈ 2|τ|2 , α, β ∈ Zuq . Let Q⊆{0, 1}|τ | ,  ∈ [0, 1], A = qu , B = |τ|u be integers such that B ≤ A, |Q| ≤ δ B for some δ ∈ (0, 1). Let u = log|τ| (2|Q |/ ), it follows that |Q| ≤ 0.5 |τ |u . By setting δ = 0.5 , then for any element τ ∈ Q, we have

P rh←H [hz,α,β (τ ) = 0 ∧ hz,α,β (τ  ) = 0, ∀

τ  ∈ Q] ∈ ((1 − 0.5 )/qu , 1/qu ).

Moreover, it holds that (1 − 0.5 )/qu ≥ 0.5 /qu . This quantity is non-negligible as long as  is non-negligible for the polynomial parameter q and |Q| that is polynomially bounded. We remark that in this paper  denotes the probability that the adversary wins the security game. Encoding for vectors in Zq . For vector v = (v1 , · · · , v ) ∈ Zq , the encoding algorithm is defined as:

Ev = encode(v ) = [v1 In | · · · |v In ]Gn . Packing and unpacking. First, for i ∈ [], define matrix Pi as the n × n extended unit matrix:

Pi = [0n | · · · |0n |In |0n | · · · |0n ].

i−1

Let Evi = vi Gn , then the packing and unpacking algorithms are constructed as follows:  T • Pack({Evi }i=1 ). Output Ev = i∈[] Evi G−1 n (Pi Gn ) = [v1 In | · · · |v In ]Gn . • Unpack(Ev , i). Output Evi = Ev G−1 n (Pi Gn ) = vi Gn .

Using the above Packing method, Apon et al. [5] constructed a Recursive Packing algorithm to pack ν bits into one vector encoding for some ν = ω (1 ) and Recursive Unpacking algorithm to unpack the vector into its bits. This Packing method is the key step leading towards [5], and will be used to reduced the number of public-key matrices in our leveled FHS scheme and thus reduces the number of times of running the signing algorithm. But the number of columns of the public-key matrices grows linearly with the number of messages in a dataset. • Recursive Packing({Evi j }i∈[], j∈[ν ] ). Given the encoding {Evi j } for vij ∈ {0, 1}, the recursive packing does: ν  j 1. For i ∈ [], compute Evi = Evi j G−1 n ( 2 Gn ). j=1

2. Output Ev = Pack({Evi }i=1 ) = [v1 In | · · · |v In ]Gn , where vi is the decimal representation of {vi1 , , viν }. • Recursive Unpacking(Ev , (i, j)). Given the vector encoding Ev and index (i, j), the recursive unpacking does: 1. Run Evi = Unpack(Ev , i ). 2. Construct a set Sik = {vi ≤ 2ν | BD(vi )k = 1}, where BD(vi )k denotes the kth bit of bit-decomposition of integer vi .  3. Compute and output Evi j = x∈S EqTest(Evi , x ), where the EqTest will be presented in the following. ij

EqTest (Ex , c). Take as input an integer c ∈ {0, , 2ν } and an integer encoding Ex , the EqTest does: 1. Construct a Lagrange polynomial for integer c as

Lc ( y ) = where c =



 0≤i≤2ν ,i=c

y−i = c−i

0≤i≤2ν ,i=c (c

 0≤i≤2ν ,i=c

1 c−i



(y − i ) = c−1

0≤i≤2ν ,i=c



( y − i ),

0≤i≤2ν ,i=c

− i ) ∈ Zq .

−1 −1 −1 ν 2. Output ELc (x ) = Ex G−1 n (Ex − 1Gn ) · · · Gn (Ex − 2 Gn )Gn (c Gn ).

Next, for space reason, we will not recall the concrete PubEval and TrapEval algorithms, but give the following lemma to capture the main ingredients of these two algorithms. Before we present the lemma, we need the fact that: given a ×m random matrix A ∈ Znq ×m , for arbitrary matrix B ∈ Znq ×m , there always exist a matrix R ∈ Zm and an integer x such that q B = AR + xGn . Lemma 3.9 ([5]). Choose uniformly at random a matrix A from Znq ×m , for i ∈ [u] randomly pick integers zi ∈ [2|τ |2 ] (where |τ | is an integer), αi , βi ∈ Zq , and let zij denote the jth bit of zi for j ∈ [t], where t = 2 log 2|τ|. Choose uniformly at random two matrices R, R from {−1, 1}m×m , then set B = AR + E, where

E = [z1 In | · · · |zu In |0n | · · · |0n ]Gt ν n ,

ν t−2u

and set B = AR + E , where E = [α1 In |β1 In | · · · |αu In |βu In |0n | · · · |0n ]G2t ν n . Then given a parallel repetition function hz,α,β (τ ) defined by Eq. (2), it holds that

2ν t−2u

• There exists an algorithm PubEval(τ ,ν,t ) (B, B , hz,α ,β ) that outputs Bτ such that Bτ = ARτ + Eτ Gν n .   ), A, R, R , h ,β • There exists an algorithm TrapEval(τ ,ν,t ) ((z, α  ) that outputs Rτ .  ,β z,α Where Rτ = Rτ and Eτ = [hz1 ,α1 ,β1 (τ )In | · · · |hzu ,αu ,βu (τ )In |0n | · · · |0n ]. Moreover, the norm of matrix Rτ is bounded as ν

||Rτ || ≤ 2ν|τ|2 m3 2O(ν 2 ) log3 q||R||.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

79

4. Our leveled fully homomorphic signature scheme In this section, we use the vector encoding technique [5] to construct a more efficient leveled strongly-unforgeable FHS scheme. The structure of our scheme is almost the same as that of Gorbunov and co-workers [14,25,31], except that our scheme first needs to encode messages and then runs the SampleLeft algorithm to generate “pre-signatures”. Roughly speaking, since any single message belongs to the binary set {0, 1}, our scheme only needs to encode two vectors 1 = (1, · · · , 1 ) ∈ 1 and 0 = (0, · · · , 0 ) ∈ 0 , and then runs the signing algorithm twice to generate two “pre-signatures”. After that, it takes as input different messages to be signed and the corresponding indices, and then performs specific computations on one of the two “pre-signatures” to get signatures for the messages. 4.1. Our construction Our leveled FHS scheme for the circuit family C is constructed as follows: • Setup(1λ , 1|τ| , 1 , 1dmax ). On input the security parameter λ, the number of bits |τ | for the tag τ , the maximum size  of the dataset (or the maximum size of inputs for the circuit family C), and the maximum depth dmax of the circuit family C. The setup algorithm proceeds as follows: 1. Choose a lattice dimension n = n(λ, dmax ), parameters m = m(λ, , dmax ) and q = q(λ, dmax ). Choose parameters ν = log log |τ| and t = 2 log 2|τ|. Let the Gaussian parameters be s = s(n ) and s = s (n ), and let B = B(n, dmax ) ∈ Z denote an upper bound on the size of signature. 2. Choose uniformly at random three random matrices A and {Dk }k=0,1 in Znq ×m , and two random matrices B, B ∈ Znq ×m . Then call the PPT algorithm GenTrap(1n , 1m , q) to generate a parity-check matrix A∗ ∈ Znq ×m and a Gn -trapdoor X with a tag H such that the distribution of A∗ is statistically close to the uniform. Based on Lemma 3.1, use the Gn ⊥ ∗ trapdoor X and a random basis S for ⊥ q (Gn ) to generate a short basis TA∗ for lattice q (A ). Finally, output a public key pk = (A, A∗ , {Dk }k∈{0,1} , B, B , ν, t ) and a secret key sk = (TA∗ ). • KeyGen(pk, τ ). On input a public key pk, and a tag τ = {τ0 , · · · , τ|τ|−1 } ∈ {0, 1}|τ|≥λ of a dataset, the KeyGen algorithm proceeds as follows: 1. Compute Bτ ←− PubEval(τ ,ν,t ) (B, B , hz,α ,β ). 2. Assemble a dataset matrix Aτ = [A∗ |A + Bτ ]. 3. Output a verification key vk = (Aτ , {Dk }k∈{0,1} ). • Sign(sk, vk, τ , μi , i). On input a secret key sk, a public verification key vk, a dataset tag τ , a message μi ∈ {0, 1} and its index i ∈ [] (the message μi indexed by i belongs to a dataset specified by the tag τ ), the signing algorithm does: 1. For k = 0, 1, take as input {Dk }k ∈ {0, 1} and then generate two small norm matrices [Rk,T 1 |Rk,T 2 ] ∈ Z2m×m by running the PPT algorithm SampleLeft(A∗ , A + Bτ , TA∗ , Dk + [kIn | · · · |kIn ]Gn , s ) such that:





R 1 Aτ k, = Dk + [kIn | · · · |kIn ]Gn . Rk,2 We call the two small norm matrices “pre-signatures”.



2. For i ∈ [] and μi ∈ {0, 1}, let RTμ ,1,i |RTμ ,2,i i i





T



= RμT ,1 |RμT ,2 i i

T

G−1 n (Pi Gn ) such that:

R Aτ μi ,1,i = Dμi G−1 n (Pi Gn ) + μi Gn . Rμi ,2,i



T

3. Output a tag τ and a signature σi = ( RTμ ,1,i |RTμ ,2,i , μi , i ). i i ,σ  , f ). On input a public verification key vk, a dataset tag τ , a  -dimensional message vector μ = • Eval(vk, τ , μ (μ1 , · · · , μ ), a  -dimensional signature vector σ = (σ1 , · · · , σ ), where  ≤ , and a circuit f ∈ C, the evaluation algorithm computes an evaluated signature recursively gate by gate as follows: 1. Assemble the index tuple sets b = {(μi , i )}μi ∈{0,1},i∈[ ] , where μi , i ∈ σ i and σ i ∈ σ . 2. Since in this case the circuit can be converted to use only some NAND gates, we only need to implement a NAND gate. Let g = (u, v, w ) be a NAND gate carrying input messages x, y (correspond to two messages μa , μb in message vector μ). Let Di (selected by the μi ∈ {0, 1}) be one of the two public-key matrices {Dk }k ∈ {0, 1} . By reduction on the b-dependent public matrix associated with each wire, we have (Ru , Rv ) ∈ Z2m×m such that:

Aτ Ru = Du G−1 n (Pxi Gn ) + xGn

and

Aτ Rv = Dv G−1 n (Py j Gn ) + yGn ,

where xi , yj ∈ [ ] are indices of the messages x, y, respectively.   3. Compute a public matrix associated with the output wire as Dw := Dv G−1 n (Pyi Gn )Du − Gn , where Du = −1 −1 m ×m Gn (Du Gn (Pxi Gn )) ∈ Z . 4. Compute a homomorphic value:

Rw = Rv  Du − yRu .

80

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

The corresponding evaluated signature is σw = (Rw , {(μi , xi ), (μ j , y j ), 1 − xy} ). 5. Inductively proceed with the evaluation of all gates in f. Output an evaluated signature σ f =  )), a dataset tag τ and a circuit f. (R f , {(μi , i )}μi ∈{0,1},i∈[ ], f (μ • Verify(vk, τ , σ f , f). On input a public verification key vk, a dataset tag τ , a signature σ f and a circuit f ∈ C, the public verification algorithm accepts the signature σ f only if the following conditions are satisfied. 1. Verify ||Rf ||∞ ≤ B. 2. Compute a dataset matrix Aτ = [A∗ |A + Bτ ] as computed by the KeyGen algorithm described above, and compute a public matrix Df associated with the circuit f as computed by the Eval algorithm described above. Then verify  )Gn . Aτ R f = D f + f ( μ 4.2. Correctness We show that the public verification algorithm accepts an honestly computed evaluated signature. We consider w.l.o.g  ordered by their indexes i ∈ [ ], signature vector σ  and a circuit f. a particular dataset with its tag τ , message vector μ Then we can compute a dataset matrix Aτ and a public matrix Df associated with the circuit f. It suffices to analyze the correctness of the NAND gate g = (u, v, w ) carrying input messages x, y. Lemma 4.1. Let Aτ be the dataset matrix of tag τ , and Ru , Rv be signatures of messages x, y, respectively, under the corresponding −1 public matrices Du , Dv , such that, Aτ Ru = Du G−1 n (Pxi Gn ) + xGn and Aτ Rv = Dv Gn (Py j Gn ) + yGn . Then it holds that

Aτ Rw = Dw + (x NAND y )Gn −1 −1 m×m . Furthermore, we have ||R || ≤   where Rw = Rv  Du − yRu , Dw = Dv G−1 w n (Pyi Gn )Du − Gn and Du = Gn (Du Gn (Pxi Gn )) ∈ {0, 1} m||Rv || + ||Ru ||.

Proof.

Aτ Rw = Aτ ( Rv  Du − yRu )  = Aτ Rv Du − yAτ Ru

−1  = (Dv G−1 n (Uy j Gn ) + yGn )Du − y (Du Gn (Uxi Gn ) + xGn ) −1 −1  = Dv G−1 n (Uyi Gn )Du + yDu Gn (Uxi Gn ) − yDu Gn (Uxi Gn ) − xyGn

= Dw + Gn − xyGn = Dw + (1 − xy )Gn = Dw + (x NAND y )Gn . By induction and Lemma 4.1, for the signature σ f , we have

 )Gn , Aτ R f = D f + f ( μ where ||R f || ≤ B = mO(dmax ) .



Lemma 4.2. Let f be an arbitrary circuit taking at most  bits as input and outputting one bit. Let Aτ ∈ Znq ×m and the public matrices for all input wires be Dk = Aτ Uk + kGn for some low norm matrices {Uk }k ∈ {0, 1} . For each NAND gate g = (u, v, w ), assume the input public matrices are Du = Aτ Uu + xGn and Dv = Aτ Uv + yGn , and let

Dw = Dv  Du + Gn , m×m . Then it holds that where  Du = G−1 n (−Du ) ∈ {0, 1}

Dw = Aτ Uw + (x NAND y )Gn , where Uw = Uv  Du − yUu . By induction, the public matrix associated with the output wire of the circuit f is of the form Aτ U f + k f Gn , where Rf is of low norm and kf ∈ {0, 1}. Proof. This proof is very similar to the above proof, thus we omit it here to avoid redundancy.



4.3. Security Assuming there exists an adversary A that wins the fully adaptive chosen-message attacks experiment ExptEU-F-ACMA ( 1λ ) A defined in Section 2.2, then we can construct an algorithm B to solve the SISq,n,m,β problem for the lattice defined by the random matrix A∗ ∈ Znq ×m . As noted in security experiment ExptEU-F-ACMA (1λ ), there are two types of forgeries, therefore A different strategies have to be built to tackle different types of forgeries. More precisely, in the security proof, the algorithm B first guesses which type of forgery the adversary A will make, then based on the guess, B sets the “forgery-specific” public key pk associated with the SISq,n,m,β problem. For completeness, we give the following theorem to assure the security of our construction. Theorem 4.3. Assuming the hardness of the SISq,n,m,β problem, then the proposed leveled FHS scheme is fully unforgeable against fully adaptive chosen-message attacks.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

81

Proof. We construct an algorithm B that solves the SISq,n,m,β problem by exploiting a forged but valid signature submitted by the adversary A. Invocation. After receiving a random matrix A∗ ∈ Znq ×m from the SISq,n,m,β problem, the algorithm B is asked to output a non-zero integer vector z ∈ Zm \ {0} such that A∗ z = 0 mod q and ||z|| ≤ β . Setup. The algorithm B generates a public key (not a secret key) by running the setup algorithm Setup(1λ , 1|τ| , 1 , 1dmax ), as follows: 1. Take as input the parameters of SISq,n,m,β problem, B sets the parameters q,n,m,B. Let s = s(n ), s = s (n ) be Gaussian parameters and ν = log log |τ|, t = 2 log 2|τ| be global parameters. 2. Guess the type of forgery that the adversary A will make. Based on the guess, B continues to carry out one of the following two subroutines. • Type I forgery. Firstly, similar to that of Apon et al. [5], the algorithm B computes matrices B, B as follows: For i ∈ [u], randomly pick integers zi ∈ [2|τ |2 ], αi , βi ∈ Zq . For i ∈ [ν ], j ∈ [t], set matrix Eij as



Ei j =

zi j Gn , 0n×m ,

if i ≤ u; otherwise,

where the selection of parameter u will be given later. Then compute



E = RecPack {Ei j }i∈[t], j∈[u] , 0n×m , · · · , 0n×m ),





(ν −u )t



and set matrix E for encoding {α i } and {β i } as

E = [α1 In |β1 In | · · · |αu In |βu In |0n | · · · |0n ]G2t ν n .

2ν t−2u

Next, randomly choose R, R ∈ {−1, 1}m×m and then set

B = A∗ R + E, B = A∗ R + E . Randomly select three matrices U, U0 , U1 ∈ {−1, 1}m×m and then set A = A∗ U. Finally, output a public key:

pk = (A, A∗ , {Dk = A∗ Uk }k∈{0,1} , B, B , ν, t ). • Type II forgery. Firstly, choose uniformly at random two public-key matrices B, B ∈ Znq ×m . Then randomly choose a tag τ ∗ (which is regarded as the forgery tag in this case) and compute Bτ by invoking Bτ ∗ ←− ∗ PubEval(τ ,ν,t ) (B, B , hz,α ,β ). Randomly select a matrix U ∈ {−1, 1}m×m and then set A = A∗ U − Bτ ∗ . Randomly sam-

ple two matrices Rb,T1 |Rb,T2



Db = [A∗ |A∗ U]

T



←− (DZm ,s )2m for b ∈ {0, 1} as “pre-signatures”, and then let

Rb,1 − [bIn | · · · |bIn ]Gn Rb,2

for b ∈ {0, 1}.

Finally, output a public key:

pk = (A, A∗ , {Dk }k∈{0,1} , B, B , ν, t ). Note that the corresponding public verification key is vk = (Aτ ∗ = [A∗ |A∗ U], {Dk }k∈{0,1} ). Signing queries. The adversary A adaptively submits queries of the form (τ , μi , i), where the tag τ ∈ {0, 1}|τ | ≥ λ is dataset identifier, the message μi ∈ {0, 1} and its index i ∈ []. The algorithm B answers the signing queries sent from A as follows. We remark that the answers are constructed differently depending on the setup-time guess by B on the type of forgery A will make. • Type I forgery. When the tuple (τ , μi , i) is received, based on the corresponding public key that is set before, the algorithm B does: (a) If (τ , μi , i) is the first query for the tag τ , B initializes an empty list Tτ = ∅ for τ and then adds the tuple (μi , i) to the list Tτ . After that, B computes the corresponding signature σ i as follows: 1. compute a small norm matrix Rτ by invoking

 ), A∗ , R, R , h  ). ,β Rτ ←− TrapEval(τ ,ν,t ) ((z, α  ,β z ,α Abort the simulation if

hz,α ,β (τ ) = (hz1 ,α1 ,β1 (τ ), · · · , hzu ,αu ,βu (τ ), 0n , · · · , 0n ) = 0. 2. Otherwise, generate a matrix Bτ by running Bτ ← PubEval(τ ,ν,t ) (B, B , hz,α ,β ) such that:

Bτ = A∗ Rτ + Eτ Gν n ,

82

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

where

Eτ = [hz1 ,α1 ,β1 (τ )In | · · · |hzu ,αu ,βu (τ )In |0n | · · · |0n ]. By Lemma 3.9, it holds that Rτ = Rτ . Assemble a dataset matrix Aτ = [A∗ |A + Bτ ] and move on to the next step.

T 3. For k ∈ {0, 1}, compute two small norm matrices Rk,T 1 |Rk,T 2 by running SampleDO (A∗ , −U − Rτ , Eτ , Dk + [kIn | · · · |kIn ]Gn , s ) such that:





R 1 Aτ k, = Dk + [kIn | · · · |kIn ]Gn . Rk,2



4. For i ∈ [] and μi ∈ {0, 1}, let RTμ ,1,i |RTμ ,2,i i i





T





= RμT ,1 |RT μi ,2 i

T

G−1 n (Pi Gn ) such that:

Rμi ,1,i = Dμi G−1 n (Pi Gn ) + μi Gn . Rμi ,2,i



5. Send the signature σi = ( RTμ ,1,i |RTμ ,2,i i

T

i

, μi , i ) to A, and store the signature just in case the same query is re-

quested again. (b) If Tτ has not yet contained a tuple (μi , i), B counts the number of tuples in Tτ . If the number is less than , B computes the corresponding signature σ i using the same method as above (note that there is no need to generate the dataset matrix Aτ again). Then, B sends σ i to A, stores σ i and updates the list Tτ ← Tτ ∪ (μi , i). Otherwise, B aborts the experiment. This procedure is necessary, as our scheme requires the maximum number of messages in a dataset to be no more than . (c) If (μi , i) ∈ Tτ , B replies with the same signature generated before. (d) If Tτ contains a tuple (μi , i ) for μi = μi , B ignores the query. Note that the message μi is indexed by its index i. ?

• Type II forgery. When the tuple (τ , μ, i) is received, B checks τ = τ ∗ . If it fails, then B aborts the simulation. Otherwise, B does: (a) If (τ , μ, i) is the first query for the tag τ , B initializes an empty list Tτ = ∅ for τ and then adds the tuple (μi , i) to the list Tτ . After that, B computes the corresponding signature σ i as follows: 1. For i ∈ [] and μi ∈ {0, 1}, let

RTμi ,1,i |RTμi ,2,i



where Rμ ,1 |Rμ ,2 i i we have



T

= RμTi ,1 |RμTi ,2

T

T

G−1 n (Pi Gn ),

are taken from the “pre-signatures” pre-generated in the Type II forgery setup phase. Then



R Aτ μi ,1,i = Dμi G−1 n (Pi Gn ) + μi Gn . Rμi ,2,i



T

2. Send the signature σi = ( RTμ ,1,i |RTμ ,2,i , μi , i ) to A. i i (b) If Tτ has not yet contained a tuple (μi , i), B counts the number of tuples in Tτ . If the number is less than , B computes the corresponding signature σ i using the same method as above. Then B sends σ i to A and updates the list Tτ ← Tτ ∪ (μi , i). Otherwise, B aborts the experiment. (c) If (μi , i) ∈ Tτ , B replies with the same signature generated before. (d) If Tτ contains a tuple (μi , i ) for μi = μi , B ignores the query. Forgery. The above signing queries are executed until the adversary A outputs a forgery tuple (τ ∗ , σ f∗∗ , f ∗ ), where σ f∗∗ = for ∗ ≤ .

(R∗f ∗ , {(μ∗i , i∗ )}μ∗ ∈{0,1},i∗ ∈[∗ ], μ∗ ) i

1. If the type of forgery made by the adversary A is different than the type of forgery that the algorithm B guessed in setup phase, then abort the simulation. 2. Otherwise, match the type of forgery with the corresponding public key that is set in setup phase, then construct a solution for the SISq,n,m,β problem. • Type I forgery. In this case, for all j ∈ [|Q|], τ ∗ = τ j , where we denote by |Q| the upper bound on the number of tags  = (β , · · · , βu ), and the  = ( α1 , · · · , αu ) , β involved in signing queries. On input the parameters z = (z1 , · · · , zu ), α 1 forgery tag τ ∗ , output hz,α ,β (τ ∗ ). If

hz,α ,β (τ ∗ ) = (hz1 ,α1 ,β1 (τ ∗ ), · · · , hzu ,αu ,βu (τ ∗ ), 0n , · · · , 0n ) = 0,

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

83

abort the simulation. Otherwise, hz,α ,β (τ ∗ ) = 0, which happens with non-negligible probability according to Lemma 3.8. Then we have



[A∗ |A∗ U + Bτ ∗ ]



R∗f ∗ ,1 = D∗f ∗ + μ∗ Gn , R∗f ∗ ,2

where Bτ ∗ = A∗ Rτ ∗ + [hz1 ,α1 ,β1 (τ ∗ )| · · · |hzu ,αu ,βu (τ ∗ )|0n | · · · |0n ]Gν n is generated using the PubEval algorithm, and D∗f ∗

∗ is derived from {Dk }k ∈ {0, 1} , G−1 n (Ui Gn ) and f as per the homomorphic evaluation algorithm. According to Lemma 4.2, ∗ ∗ ∗ we have D f ∗ = A U f ∗ + kGn for some small norm matrix U∗f ∗ and integer k. Hence, we have

A∗ R∗f ∗ ,1 + A∗ (U + Rτ ∗ )R∗f ∗ ,2 = A∗ U∗f ∗ + kGn + μ∗ Gn . Rearranging, we obtain

A∗ (R∗f ∗ ,1 + (U + Rτ ∗ )R∗f ∗ ,2 − U∗f ∗ ) = (k + μ∗ )Gn . Since the matrices R, R are chosen uniformly at random from {−1, 1}m×m , B and B are distributed statistically close to uniform according to Lemma 2.6, the adversary A gets no information about the resulting matrix Rτ ∗ generated using the TrapEval algorithm, the probability that, R∗f ∗ ,1 + (U + Rτ ∗ )R∗f ∗ ,2 − U∗f ∗ = 0, is therefore negligible. If k + μ∗ = 0, then output the matrix R∗f ∗ ,1 + (U + Rτ ∗ )R∗f ∗ ,2 − U∗f ∗ as a solution for the SISq,n,m,β problem. Otherwise, output (R∗f ∗ ,1 + (U + Rτ ∗ )R∗f ∗ ,2 − U∗f ∗ )TGn as a solution. • Type II forgery. ∗ (a) Type (a) forgery. In this case, the forgery tag τ ∗ has been used for generating signatures of message vector μ ∗ ∗ ∗ ∗  ). If the forgery tag τ is not the tag chosen in the Type II forgery setup in the signing queries, but μ = f (μ phase, abort the simulation. Otherwise, using the “pre-signatures” pre-generated in the Type II forgery setup phase  ∗ )) (by implementing Eval(vk, τ ∗ , μ  ∗, σ  ∗ , f ∗ )) to obtain an evaluated signature σ f ∗ = (R f ∗ , {(μi , i )}μi ∈{0,1},i∈[∗ ] , f (μ such that:



Aτ ∗



R f ∗ ,1  ∗ )Gn . = D f ∗ + f ∗ (μ R f ∗ ,2

(3)

On the other hand, by the correctness of the forged signature σ f ∗ , we have



Aτ ∗



R∗f ∗ ,1 = D∗f ∗ + μ∗ Gn . R∗f ∗ ,2

(4)

Subtracting Eq. (4) by Eq. (3), and note that D f ∗ = D∗f ∗ in this case, we have



Aτ ∗





R f ∗ ,1 − R∗f ∗ ,1  ∗ ) − μ∗ ) G n , = ( f ∗ (μ R f ∗ ,2 − R∗f ∗ ,2

where (R f ∗ ,1 − R∗f ∗ ,1 )T |(R f ∗ ,2 − R∗f ∗ ,2 )T

T

 ∗ ) = μ∗ contradicting the definition of this type of = 0; otherwise, f ∗ (μ

forgery. Therefore, expanding the dataset matrix Aτ ∗ and rearranging, which results in

 ∗ ) − μ∗ ) G n . A∗ (R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 )) = ( f ∗ (μ

(R f ∗ ,1 − R∗f ∗ ,1

(5)

U(R f ∗ ,2 − R∗f ∗ ,2 ))TGn

Output + as a solution for the SISq,n,m,β problem. (b) Type (b) forgery. In this case, the forgery tag τ ∗ has been used for generating signatures of messages in the signing queries, but at least one message-index tuple that is assumed w.l.o.g to be (μ∗1 , 1 ) has not been queried, i.e., (μ∗1 , 1 ) ∈/ Tτ ∗ . If the forgery tag τ ∗ is not the tag chosen in the Type II forgery setup phase, abort the simulation. Otherwise, similar to Type (a) forgery, we can get Eqs. (3)–(5). For simplicity, we will not list them here any more. In the Type II forgery setup phase and an honest situation, the signature of message μ∗1 is σ1∗ =

 T  T  T  T T T ( RTμ∗ ,1,1 |RTμ∗ ,2,1 , μ∗1 , 1 ), where RTμ∗ ,1,1 |RTμ∗ ,2,1 = RμT∗ ,1 |RμT∗ ,2 G−1 n (P1 Gn ). Since the matrix Rμ∗ ,1 |Rμ∗ ,2 1

1

1

1

1

1

1

1

is sampled randomly from (DZm ,s )2m in the Type II forgery setup phase, the adversary A gets no informa-



tion about

RTμ∗ ,1,1 |RTμ∗ ,2,1 1

1

T



. On the other hand, the matrix

RTf ∗ ,1 |RTf ∗ ,2

T

is derived from { Rb,T1 |Rb,T2

T

}b∈{0,1} ,

and the matrix U is chosen uniformly at random from {−1, 1}m×m in the setup phase. Hence, the probability  ∗ ) = μ∗ , output that, R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) = 0, is negligible. By Eq. (5) and the fact that D f ∗ = D∗f ∗ , f ∗ (μ ∗ ∗ R f ∗ ,1 − R f ∗ ,1 + U(R f ∗ ,2 − R f ∗ ,2 ) as a solution for the SISq,n,m,β problem. (c) Type (c) forgery. In this case, the forgery tag τ ∗ has been used for generating signatures of messages in the signing queries, but at least one message-index (μ∗1 , 1 ) of index tuple sets {(μ∗i , i∗ )}μ∗ ∈{0,1},i∈[∗ ] is not equal to i

(μ1∗ , 1 ), which is the return value of the corresponding signing queries, i.e., Tτ ∗ contains the message-index tuple (μ1∗ , 1 ), but μ1∗ = μ∗1 . If the forgery tag τ ∗ is not the tag chosen in the Type II forgery setup phase, abort

84

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

the simulation. Otherwise, using the “pre-signatures” pre-generated in the Type II forgery setup phase to get an  ∗ )) (by implementing Eval(vk, τ ∗ , μ  ∗, σ  ∗ , f ∗ )) such that: evaluated signature σ f ∗ = (R f ∗ , {(μi , i )}μi ∈{0,1},i∈[∗ ] , f (μ



Aτ ∗



R f ∗ ,1  ∗ )Gn . = D f ∗ + f ∗ (μ R f ∗ ,2

(6)

On the other hand, for the forged signature σ f∗∗ , we have



Aτ ∗



R∗f ∗ ,1 = D∗f ∗ + μ∗ Gn . R∗f ∗ ,2

(7)

According to Lemma 4.2, we have D f ∗ = A∗ U f ∗ + kGn , D∗f ∗ = A∗ U∗f ∗ + k∗ Gn for some small norm matrix U f ∗ , U∗f ∗ and integer k, k∗ . Then, subtracting Eq. (7) by Eq. (6) and rearranging, we have

A∗ (R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) − U f ∗ + U∗f ∗ ) = (k − k∗ )Gn ,  ∗ ) = μ∗ . Note that in this case, the probability that, D f ∗ = D∗f ∗ , is negligible. This is because D f ∗ is due to f ∗ (μ ∗ derived from the public-key matrices {Dk }k ∈ {0, 1} , some deterministic matrices {G−1 n (Ui Gn )}i∈[∗ ] and f , where {Dk }k ∈ {0, 1} are distributed statistically close to uniform according to Lemma 4.4. Hence, if k = k∗ , then U f ∗ = U∗f ∗ .



On the other hand, the matrix

RTf ∗ ,1 |RTf ∗ ,2

T

is derived from { Rb,T1 |Rb,T2

T

}b∈{0,1} pre-generated in the Type II

forgery setup phase (which are sampled randomly from (DZm ,s )2m ), the public-key matrices {Dk }k ∈ {0, 1} , some de∗ T T terministic matrices {G−1 n (Ui Gn )}i∈[∗ ] and f , then the adversary A gets no information about [R f ∗ ,1 |R f ∗ ,2 ]. Based on the above analysis and combine the fact that the matrix U is chosen uniformly at random from {−1, 1}m×m in the setup phase, we can conclude that the probability that, R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) − U f ∗ + U∗f ∗ = 0, is negligible. Therefore, if k = k∗ , output R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) − U f ∗ + U∗f ∗ as a solution for the SISq,n,m,β problem. Otherwise, output (R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) − U f ∗ + U∗f ∗ )TGn as the solution.  ∗ in the (d) Type (d) forgery. In this case, the forgery tag τ ∗ has been used for generating signatures of messages μ ∗ queries phase, but R f ∗ = R f ∗ , where R f ∗ is obtained honestly using the “pre-signatures” pre-generated in the Type  ∗, σ  ∗ , f ∗ ) algorithm. If the forgery tag τ ∗ is not the tag choII forgery setup phase and implementing Eval(vk, τ ∗ , μ sen in the Type II forgery setup phase, abort the simulation. Otherwise, Similar to Type (c) forgery, the algorithm B uses the “pre-signatures” pre-generated in the Type II forgery setup phase, and gets the above Eqs. (6) and (7),  ∗ ) = μ∗ . Subtracting Eq. (7) by Eq. (6) and rearranging, we get but in this situation it holds that D f ∗ = D∗f ∗ , f ∗ (μ

A∗ (R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 )) = 0.



Since the matrix

RTf ∗ ,1 |RTf ∗ ,2

T

is derived from { Rb,T1 |Rb,T2

T

}b∈{0,1} pre-generated in the Type II forgery setup

(DZm ,s )2m ,

phase that are sampled randomly from the public-key matrices {Dk }k ∈ {0, 1} that are distributed statisti∗ cally close to uniform according to Lemma 4.4, some deterministic matrices {G−1 n (Ui Gn )}i∈[∗ ] and f , the adversary T T A gets no information about [R f ∗ ,1 |R f ∗ ,2 ]. Moreover, the matrix U is chosen uniformly at random from {−1, 1}m×m in the setup phase. Therefore, the probability that, R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) = 0, is negligible, then output R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) as a solution for the SISq,n,m,β problem.  Lemma 4.4. Let (pk, σ ) be the output in the real execution and (pk∗ , σ ∗ ) be the output in the simulated execution by the Setup and Queries algorithms. We show that these two distributions are statistically indistinguishable. Proof. We first analyse the Type I forgery simulation. We summarize the differences between the real execution and simulated execution as follows: 1. In the real Setup, the matrix A∗ is generated by the algorithm TrapGen together with its trapdoor TA∗ . By the property of the algorithm TrapGen shown in Lemma 3.1, A∗ is distributed statistically close to uniform. Whereas, in the simulated Setup algorithm, the matrix A∗ is distributed uniformly over Znq ×m since it is chosen from the SISq,n,m,β problem. Therefore, the matrix A∗ in the real Setup is statistically indistinguishable from the counterpart in the simulated Setup algorithm. 2. In the real Setup, the matrices (A, {Dk }k ∈ {0, 1} , B, B ) are chosen uniformly at random from Znq ×m . Whereas, in the simulated Setup algorithm, the matrix A = A∗ U for a random matrix U ∈ {−1, 1}m×m , {Dk = A∗ Uk }k∈{0,1} for two random matrices {Uk }k∈{0,1} ∈ {−1, 1}m×m and B = A∗ R + E, B = A∗ R + E for two random matrix R, R ∈ {−1, 1}m×m . By Lemma 2.6, it holds that

(A∗ U, {Dk = A∗ Uk }k∈{0,1} , A∗ R + E, A∗ R + E ) ≈ (A, {Dk }k∈{0,1} , B, B ) for random matrices A, {Dk }k∈{0,1} , B, B ∈ Znq ×m . Therefore, we conclude that the public key pk in the simulated Setup algorithm is indistinguishable from pk in the real Setup.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

85

3. In the real Sign algorithm, every signature σi is obtained by running the SampleLeft algorithm, whereas the signature σ i is obtained using the SampleDO in the simulated Signing Queries algorithm. For the common Gaussian parameter s set appropriately in Section 4.4, the outputs of the SampleLeft algorithm and SampleDO algorithm are both distributed statistically close to D uq (Aτ ),s by Lemma 3.3 and Lemma 3.5. Therefore, every signature σi in the real Sign algorithm is statistically indistinguishable from the signature σ i in the simulated Signing Queries algorithm.

Similarly, as for the indistinguishability between the real execution and the Type II forgery simulation, we summarize the differences as follows: 1. In the real Setup, the matrix A∗ is generated by the algorithm TrapGen together with its trapdoor T∗A . By the property of the algorithm TrapGen shown in Lemma 3.1, A∗ is distributed statistically close to uniform. Whereas, in the simulated Setup algorithm, the matrix A∗ is distributed uniformly over Znq ×m since it is chosen from the SISq,n,m,β problem. Therefore, the matrix A∗ in the real Setup is statistically indistinguishable from the counterpart in the simulated Setup algorithm. 2. In the real Setup, the matrices (A, {Dk }k ∈ {0, 1} , B, B ) are chosen uniformly at random from Znq ×m . Whereas, in the    R 1 ∗ m ×m ∗ ∗ simulated Setup algorithm, the matrix A = A U − Bτ ∗ for a random matrix U ∈ {−1, 1} , {Db = [A |A U] b, − Rb,2



T [bIn | · · · |bIn ]Gn }b∈{0,1} for two matrices { Rb,T1 |Rb,T2 }b∈{0,1} sampled randomly from (DZm ,s )2m and matrices B, B chosen uniformly at random from Znq ×m . By Lemmas 2.5 and 2.6, it holds that





R 1 (A = A U − Bτ ∗ , {Db = [A |A U] b, − [bIn | · · · |bIn ]Gn }b∈{0,1} ) ≈ (A, {Dk }k∈{0,1} ) Rb,2 ∗





for random matrices A, {Dk }k∈{0,1} ∈ Znq ×m . Therefore, we conclude that the public key pk in the simulated Setup algorithm is indistinguishable from pk in the real Setup. 3. In the real Sign algorithm, every signature σi is obtained by running the SampleLeft algorithm, whereas in the simulated Signing Queries algorithm the signature σ i is pre-generated in the Type II forgery setup phase, while the “pre-

T

signatures” { Rb,T1 |Rb,T2 }b∈{0,1} are sampled randomly from (DZm ,s )2m . For the Gaussian parameter s set appropriately in Section 4.4, the output of the SampleLeft algorithm is distributed statistically close to D uq (Aτ ),s by Lemma 3.3. Hence, every signature σi in the real Sign algorithm is statistically indistinguishable from the signature σ i in the simulated Signing Queries algorithm. 

4.4. Parameters selection For the security parameter λ, we set n = poly(λ ). Let parameter |τ| = n, and  then we have ν = log log n and t = 2 log 2n. For the SampleLeft algorithm, by Lemmas 3.1 and 3.3, we have || TA || ≤ 3.8 n log q, then the sampling width parameter s





satisfies s > 3.8 n log q · ω ( log 2m ). This parameter s also meets the Gaussian parameter requirement in Lemma 2.5. For the SampleDO algorithm, by Lemma 3.5, we can set s ≥ n4+ m4.5 , where  ∈ (0, 1). In order to achieve the indistinguishability between the algorithms SampleLeft and SampleDO , we can set the common parameter s = n4+ m4.5 . The size of evaluated signature should be bounded by the parameter B in our construction. While looking back on the security proof, we note that the size of matrix as a solution for SISq,n,m,β problem is larger than the size of the evaluated signature. Specifically, there are two types of solutions corresponding to two types of forgeries: • For Type I forgery, the size of matrix as the solution for SISq,n,m,β problem is bounded as

||(R∗f ∗ ,1 + (U + Rτ ∗ )R∗f ∗ ,2 − U∗f ∗ )TGn || ≤ O(mO(dmax ) ), √ 3 due to ||R∗f ∗ ,1 ||, ||R∗f ∗ ,2 ||, ||U∗f ∗ || ≤ sm 2 (m + 1 )dmax by Lemmas 4.1 and 4.2, ||U|| ≤ 12 2m by Lemma 2.4, ||Rτ ∗ || ≤ √ √ 3 3 24 2nO(log log n ) m 2 log q log log n by Lemma 3.9, and ||TGn || ≤ 5 by Remark 3.2 in Section 3. • For Type II forgery, the size of matrix as the solution for SISq,n,m,β problem is bounded as

||(R f ∗ ,1 − R∗f ∗ ,1 + U(R f ∗ ,2 − R∗f ∗ ,2 ) − U f ∗ + U∗f ∗ )TGn || ≤ O(mO(dmax ) ), √ 3 where ||R f ∗ ,1 ||, ||R∗f ∗ ,1 ||, ||R f ∗ ,2 ||, ||R∗f ∗ ,2 ||, ||U f ∗ ||, ||U∗f ∗ || ≤ sm 2 (m + 1 )dmax by Lemmas 4.1 and 4.2, ||U|| ≤ 12 2m by √ Lemma 2.4 and ||TGn || ≤ 5 by Remark 3.2 in Section 3. In conclusion, for the circuit f of polylog (λ)-depth (i.e., dmax is of polylog (λ)-size), we only need a standard SISq,n,m,β assumption. We set the following parameters: q = nO(dmax ) , n = poly(λ ), d = poly log(λ ),  = poly(λ ), m = O(ndmax ).

86

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

While for the circuit f of poly(λ)-depth (i.e., dmax is of poly(λ)-size), we need a sub-exponential SISq,n,m,β assumption

that is still widely believed to be hard, where β = 2poly(λ ) and q > β . We set the parameters as follows: 

 ndmax ). q = n(dmax ) , n = 2λ ( ∈ (0, 1 )), d = poly(λ ),  = 2poly(λ) , m = ( 

5. Optimizing the parameters Brakerski and Vaikuntanathan [15] and Wang et al. [42] used the Barrington’s Theorem [8] to transform any polylogdepth circuit into a polynomial length, width-5 permutation branching program, resulting in better parameters. In our leveled FHS scheme, we can also use the Barrington’s Theorem to optimize the parameters. Roughly speaking, we use the Barrington’s Theorem to transform the Boolean circuit f involved in our leveled FHS scheme into a polynomial length, width5 permutation branching program. This largely reduces the size of the evaluated signature from mO(dmax ) to O(m · 4dmax ), where dmax is the maximum depth of the circuit, and therefore we get better parameters which in turn further improves the efficiency and security of our leveled FHS scheme. Theorem 5.1 (Barrington’s Theorem [8]). Every Boolean NAND circuit  that acts on  inputs and has depth d can be computed by a width-5 permutation branching program  of length 4d . Given the description of the circuit  , the description of the branching program  can be computed in poly(, 4d ) time. Width-5 permutation branching programs. A permutation branching program  of length L with input space {0, 1} is a sequence of L tuples of the form (σ (t), π t,0 , π t,1 ), where • σ : [L] → [] is a function that associates the tth tuple with an input bit xσ (t) . • π t,0 and π t,1 are permutations on 5 elements, which are bijective functions from the set {1, 2, 3, 4, 5} to itself. More details about the process of this program  can be found in [15], here we only present the main result of the program . For t ∈ [L] and j ∈ [5], we have the following formula: −1 vt [ j] = vt−1 [πt,−1 0 ( j )] · xσ (t ) + vt−1 [πt,1 ( j )] · (xσ (t ) − 1 )

= vt−1 [γt, j,0 ] · xσ (t ) + vt−1 [γt, j,1 ] · (xσ (t ) − 1 ),

πt,−10 ( j )

(8)

πt,−11 ( j )

where γt, j,0  and γi, j,1  are publicly computable given the description of the program . From the above formula, we get a valid description {σ (t), γ t, j, 0 , γ t, j, 1 }t ∈ [L], j ∈ [5] for the program . In our construction, for the NAND gate g = (u, v, w ), by Lemmas 4.1 and 4.2, we have that Dw is publicly computed (in general, computed by the verifiers), while Rw is computed by someone who has the signature (in general, computed by the provers, for example, the cloud servers). Hence, for the circuit f, in order to get Df and Rf , we should establish two sub-programs using the program . Homomorphic evaluation Eval(D , D1 , , D ). In our construction, we have Di = Dμ G−1 n (Pi Gn ) for i ∈ [], satisfying Di = Aτ Ri − xi Gn . We define the homomorphic evaluation procedure as follows: • Initialization. The form of D∗ = Aτ R∗ − x∗ Gn will be maintained in the program D for every step t. We denote this by Dt = (Dt,1 , Dt,2 , Dt,3 , Dt,4 , Dt,5 ), where Dt, j = Aτ Rt, j − vt [ j]Gn : 1. For j ∈ [5], sample R0, j ← (DZm ,s )2m and set D0, j = Aτ R0, j − v0 [ j]Gn . Note that v0 [j] depends on the initialization of the program . 2. Choose a matrix D0, k corresponding to v0 [k] = 1. This v0 [k] is unique since other v0 [j] are zero for j = k. 3. Set  Di = Di − D0,k , then we have  Di = Aτ (Ri − R0,k ) − (xi − 1 )Gn . • Evaluation. The homomorphic evaluation algorithm proceeds iteratively for t ∈ [L]. Assume that at step t − 1, we have Dt−1 = (Dt−1,1 , Dt−1,2 , Dt−1,3 , Dt−1,4 , Dt−1,5 ). Then for j ∈ [5], we compute

Dt, j = Dσ (t )  Dt−1,γt, j,0 +  Dσ (t )  Dt−1,γt, j,1 ,

(9)

−1  where  Dt−1,γt, j,0 = G−1 n (−Dt−1,γt, j,0 ), Dt−1,γt, j,1 = Gn (−Dt−1,γt, j,1 ). • Output. Upon finishing the homomorphic evaluation process, we get DL = (DL,1 , DL,2 , DL,3 , DL,4 , DL,5 ). Output DL,1 (i.e., Df ) corresponding to vL [1] as the final result of the homomorphic evaluation.

From the above homomorphic evaluation, we get the final result Df that satisfies D f = Aτ R f − x f Gn , given input {Di }i ∈ [] , where Di = Aτ Ri − xi Gn . However, we have not got the matrix Rf . Therefore, we need the following homomorphic evaluation procedure to compute this matrix. Homomorphic evaluation Eval(R , (x1 , D1 , R1 ), , (x , D , R )). Going back to Lemma 4.1 in Section 4.2, we have Rw = Rv  Du − yRu , hence, we can take (xi , Di , Ri ) as a bundled input. We define the homomorphic evaluation procedure as follows: • Initialization. In the program R , all of the outputs Rt satisfy Dt = Aτ Rt − xt Gn for t ∈ [L]. We denote this by Rt = (Rt,1 , Rt,2 , Rt,3 , Rt,4 , Rt,5 ), where Dt, j = Aτ Rt, j − vt [ j]Gn .

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

87

1. For j ∈ [5], sample R0, j ← (DZm ,s )2m and set D0, j = Aτ R0, j − v0 [ j]Gn . Then we get the initial state (v0 [j], D0, j , R0, j ). Note that v0 [j] depends on the initialization of the program . 2. Choose a matrix R0, k corresponding to v0 [k] = 1. This v0 [k] is unique since other v0 [j] are zero for j = k. 3. Set  Rt = Rt − R0,k , which can be seen as an input corresponding to xt − 1. • Evaluation. The homomorphic evaluation algorithm proceeds iteratively for t ∈ [L]. Assume that at step t − 1, we have Rt−1 = (Rt−1,1 , Rt−1,2 , Rt−1,3 , Rt−1,4 , Rt−1,5 ). Then for j ∈ [5], we compute

Rt, j =Rσ (t )  Dt−1,γt, j,0 + xσ (t ) Rt−1,γt, j,0 +  Rσ (t )  Dt−1,γt, j,1 + (xσ (t ) − 1 )Rt−1,γt, j,1 ,

(10)

−1  where  Dt−1,γt, j,0 = G−1 n (−Dt−1,γt, j,0 ), Dt−1,γt, j,1 = Gn (−Dt−1,γt, j,1 ). • Output. Upon finishing the homomorphic evaluation process, we get RL = (RL,1 , RL,2 , RL,3 , RL,4 , RL,5 ). Output RL, 1 (i.e., Rf ) corresponding to vL [1] as the final result of the homomorphic evaluation.

Next, we analyze the correctness of the above two sub-programs. It suffices to verify that Dt, j = Aτ Rt, j − vt [ j]Gn for t ∈ [L], j ∈ [5]. Moreover, we analyze the size of the matrix RL, 1 outputted by the second program, as the two programs are aiming at reducing the size of matrix Rf , which therefore improves the parameters and enhances the security. Lemma 5.2. Given Eval(D , {D0, j }j ∈ [5] , D1 , , D ) → DL, 1 and Eval(R , {(v0 [j], D0, j , R0, j )}j ∈ [5] , (x1 , D1 , R1 ), , (x , D , R )) → RL, 1 such that, D0, j = Aτ R0, j − v0 [ j]Gn and Di = Aτ Ri − xi Gn for j ∈ [5], i ∈ []. Then, it holds that Dt, j = Aτ Rt, j − vt [ j]Gn for t ∈ [L], j ∈ [5], where L is the length of the branching program . In particular, we have DL,1 = Aτ RL,1 − vL [1]Gn . Proof. By Eqs. (8)–(10), for t ∈ [L], j ∈ [5], we have



Aτ Rt, j − vt [ j]Gn = Aτ Rσ (t )  Dt−1,γt, j,0 + xσ (t ) Rt−1,γt, j,0 + Rσ (t )  Dt−1,γt, j,1 + (xσ (t ) − 1 )Rt−1,γt, j,1







− vt−1 [γt, j,0 ]xσ (t ) + vt−1 [γt, j,1 ](xσ (t ) − 1 ) Gn



= Dσ (t )  Dt−1,γt, j,0 − xσ (t ) Dt−1,γt, j,0





+ xσ (t ) Dt−1,γt, j,0 + xσ (t ) vt−1 [γt, j,0 ]Gn





+  Dσ (t )  Dt−1,γt, j,1 − (xσ (t ) − 1 )Dt−1,γt, j,1





+ (xσ (t ) − 1 )Dt−1,γt, j,1 + (xσ (t ) − 1 )vt−1 [γt, j,1 ]Gn







− vt−1 [γt, j,0 ]xσ (t ) + vt−1 [γt, j,1 ](xσ (t ) − 1 ) Gn = Dσ (t )  Dt−1,γt, j,0 +  Dσ (t )  Dt−1,γt, j,1 = Dt, j . In particular, we have DL,1 = Aτ RL,1 − vL [1]Gn .



Lemma 5.3. Given Eval(R , {(v0 [j], D0, j , R0, j )}j ∈ [5] , (x1 , D1 , R1 ), , (x , D , R )) → RL, 1 such that, D0, j = Aτ R0, j − v0 [ j]Gn and Di = Aτ Ri − xi Gn for j ∈ [5], i ∈ [], where ||R0, j ||, ||Ri || ≤ β . Then we have ||RL,1 || ≤ (3mL + 1 )β . Proof. It suffices to verify that ||Rk, j || ≤ (3mk + 1 )β for k ∈ {0} ∪ [L], j ∈ [5]. We prove this by inductive argument: 1. When k = 0, by the initialization of the branching program , we have ||R0, j || ≤ β for j ∈ [5]. 2. Assume that we have ||Rk−1, j || ≤ (3m(k − 1 ) + 1 )β for j ∈ [5]. According to Eq. (10), we have

||Rk, j || = ||Rσ (k)  Dk−1,γt, j,0 + xσ (k ) Rk−1,γt, j,0 +  Rσ ( k )  Dk−1,γt, j,1 + (xσ (k ) − 1 )Rk−1,γt, j,1 || ≤ ||Rσ (k )  Dk−1,γt, j,0 || + ||xσ (k ) Rk−1,γt, j,0 || + || Rσ ( k )  Dk−1,γt, j,1 || + ||(xσ (k ) − 1 )Rk−1,γt, j,1 || ≤ mβ + |xσ (k ) |((3m(k − 1 ) + 1 )β ) + 2mβ + |xσ (k ) − 1|((3m(k − 1 ) + 1 )β )

= (3mk + 1 )β .

This is due to the fact that exactly one of xσ (k) and xσ (k ) − 1 is non-zero. By reduction, we have ||RL,1 || ≤ (3mL + 1 )β .



By Lemma 4.1, the size of Rf is bounded by mO(dmax ) , then by Theorem 5.1 and Lemma 5.3, we have that the boundary is reduced to O(m · 4dmax ) due to L = 4dmax . This means that, for the SISq,n,m,β problem, we can set smaller parameters β and q, which not only improves our leveled FHS’s efficiency but also results in stronger security.

88

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

6. Conclusion In this work, we propose a more efficient strongly-unforgeable leveled FHS scheme, using the vector encoding technique. The proposed leveled FHS scheme only needs to run the signing algorithm twice to generate signatures for all messages in a dataset. This solution is very similar to batch processing. We also prove that the proposed leveled FHS scheme is secure against fully adaptive chosen-message attacks under the standard small integer solution (SIS) assumption, without a cumbersome modification required by the previous adaptively secure leveled FHS scheme. Additionally, we use Barrington’s Theorem to transform the Boolean circuit involved in our leveled FHS scheme into a polynomial length, width-5 permutation branching program, which largely reduces the size of the evaluated signature and hence results in smaller parameters. However, our leveled FHS scheme, like the previous leveled FHS schemes, only supports leveled homomorphic computations. We believe that, designing a (pure) FHS scheme getting rid of the “leveled” constraint, i.e., there is no a-priori bound on the depth of the circuit that can be evaluated, is still deserving of more cryptographic efforts. Acknowledgments This work was supported in part by the National Key Research and Develepment Program of China (No. 2017YFB08020 0 0), the National Natural Science Foundation of China (No. 61672030, No. U1705264 and No. 61272040), the Research Foundation of Hangzhou Normal University (No. 2017QDL002), Zhejiang Provincial Natural Science Foundation of China (No. LY19F020019), the Scientific Research Fund of Zhejiang Provincial Education Department (No. Y201737292), and the Research Fundation of Guangxi Key Laboratory of Cryptography and Information Security (No. GCIS201725). References [1] S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in: Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings, 2010, pp. 553–572, doi:10.1007/978- 3- 642- 13190- 5_28. [2] J.H. Ahn, D. Boneh, J. Camenisch, S. Hohenberger, A. Shelat, B. Waters, Computing on authenticated data, in: Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012. Proceedings, 2012, pp. 1–20, doi:10.1007/978- 3- 642- 28914- 9_1. [3] M. Ajtai, Generating hard instances of lattice problems (extended abstract), in: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22–24, 1996, 1996, pp. 99–108, doi:10.1145/237814.237838. [4] J. Alperin-Sheriff, C. Peikert, Faster bootstrapping with polynomial error, in: Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2014, Proceedings, Part I, 2014, pp. 297–314, doi:10.1007/978- 3- 662- 44371- 2_17. [5] D. Apon, X. Fan, F. Liu, Vector encoding over lattices and its applications, IACR Cryptol. ePrint Arch. 2017 (2017) 455. [6] G. Ateniese, S. Kamara, J. Katz, Proofs of storage from homomorphic identification protocols, in: Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009. Proceedings, 2009, pp. 319–333, doi:10.1007/978- 3- 642- 10366- 7_19. [7] N. Attrapadung, B. Libert, T. Peters, Computing on authenticated data: new privacy definitions and constructions, in: Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2–6, 2012. Proceedings, 2012, pp. 367–385, doi:10.1007/978- 3- 642- 34961- 4_23. [8] D.A.M. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in nc1 , J. Comput. Syst. Sci. 38 (1) (1989) 150–164, doi:10.1016/0 022-0 0 0 0(89)90 037-8. [9] N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth, Succinct non-interactive arguments via linear interactive proofs, in: Theory of Cryptography 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3–6, 2013. Proceedings, 2013, pp. 315–333, doi:10.1007/978- 3- 642- 36594- 2_ 18. [10] D. Boneh, D.M. Freeman, Homomorphic signatures for polynomial functions, in: Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15–19, 2011. Proceedings, 2011, pp. 149–168, doi:10. 1007/978- 3- 642- 20465- 4_10. [11] D. Boneh, D.M. Freeman, J. Katz, B. Waters, Signing a linear subspace: Signature schemes for network coding, in: Public Key Cryptography, 5443, Springer, 2009, pp. 68–87. [12] D. Boneh, C. Gentry, S. Gorbunov, S. Halevi, V. Nikolaenko, G. Segev, V. Vaikuntanathan, D. Vinayagamurthy, Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits, in: Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11–15, 2014. Proceedings, 2014, pp. 533–556, doi:10.1007/ 978- 3- 642- 55220- 5_30. [13] X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in: Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26–28, 2010. Proceedings, 2010, pp. 499–517, doi:10.1007/978- 3- 642- 13013-7_29. [14] X. Boyen, X. Fan, E. Shi, Adaptively secure fully homomorphic signatures based on lattices, IACR Cryptol. ePrint Arch. 2014 (2014) 916. [15] Z. Brakerski, V. Vaikuntanathan, Lattice-based FHE as secure as PKE, in: Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12–14, 2014, 2014, pp. 1–12, doi:10.1145/2554797.2554799. [16] C. Brzuska, M. Fischlin, T. Freudenreich, A. Lehmann, M. Page, J. Schelbert, D. Schröder, F. Volk, Security of sanitizable signatures revisited, in: Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18–20, 2009. Proceedings, 2009, pp. 317–336, doi:10.1007/978- 3- 642- 00468- 1_18. [17] D. Catalano, D. Fiore, L. Nizzardo, Programmable hash functions go private: Constructions and applications to (homomorphic) signatures with shorter public keys, in: Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part II, 2015, pp. 254–274, doi:10.1007/978- 3- 662- 48000- 7_13. [18] D. Catalano, D. Fiore, B. Warinschi, Homomorphic signatures with efficient verification for polynomial functions, in: Advances in Cryptology CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2014, Proceedings, Part I, 2014, pp. 371–389, doi:10.1007/ 978- 3- 662- 44371- 2_21. [19] W. Chen, H. Lei, K. Qi, Lattice-based linearly homomorphic signatures in the standard model, Theor. Comput. Sci. 634 (2016) 47–54, doi:10.1016/j.tcs. 2016.04.009. [20] X. Chen, J. Li, X. Huang, J. Li, Y. Xiang, D.S. Wong, Secure outsourced attribute-based signatures, IEEE Trans. Parallel Distrib. Syst. 25 (12) (2014) 3285–3294, doi:10.1109/TPDS.2013.2295809.

F. Luo, F. Wang and K. Wang et al. / Information Sciences 480 (2019) 70–89

89

[21] X. Chen, J. Li, X. Huang, J. Ma, W. Lou, New publicly verifiable databases with efficient updates, IEEE Trans. Dependable Sec. Comput. 12 (5) (2015) 546–556, doi:10.1109/TDSC.2014.2366471. [22] X. Chen, J. Li, J. Ma, Q. Tang, W. Lou, New algorithms for secure outsourcing of modular exponentiations, IEEE Trans. Parallel Distrib. Syst. 25 (9) (2014) 2386–2396, doi:10.1109/TPDS.2013.180. [23] X. Chen, F. Zhang, W. Susilo, H. Tian, J. Li, K. Kim, Identity-based chameleon hashing and signatures without key exposure, Inf. Sci. 265 (2014) 198–210, doi:10.1016/j.ins.2013.12.020. [24] A. Chiesa, Succinct non-Interactive arguments, Massachusetts Institute of Technology, Cambridge, MA, USA, 2014 Ph.D. thesis. [25] D. Fiore, A. Mitrokotsa, L. Nizzardo, E. Pagnin, Multi-key homomorphic authenticators, in: Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4–8, 2016, Proceedings, Part II, 2016, pp. 499–530, doi:10.1007/978- 3- 662- 53890- 6_17. [26] D.M. Freeman, Improved security for linearly homomorphic signatures: a generic framework, in: Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21–23, 2012. Proceedings, 2012, pp. 697–714, doi:10.1007/978- 3- 642- 30057- 8_41. [27] C. Gentry, Fully homomorphic encryption using ideal lattices, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009, pp. 169–178, doi:10.1145/1536414.1536440. [28] C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17–20, 2008, 2008, pp. 197–206, doi:10.1145/1374376.1374407. [29] C. Gentry, D. Wichs, Separating succinct non-interactive arguments from all falsifiable assumptions, in: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, June 6–8, 2011, 2011, pp. 99–108, doi:10.1145/1993636.1993651. [30] S. Gorbunov, V. Vaikuntanathan, H. Wee, Attribute-based encryption for circuits, in: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1–4, 2013, 2013, pp. 545–554, doi:10.1145/2488608.2488677. [31] S. Gorbunov, V. Vaikuntanathan, D. Wichs, Leveled fully homomorphic signatures from standard lattices, in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14–17, 2015, 2015, pp. 469–477, doi:10.1145/2746539.2746576. [32] H. Huang, X. Chen, Q. Wu, X. Huang, J. Shen, Bitcoin-based fair payments for outsourcing computations of fog devices, Future Gener. Comput. Syst. 78 (2018) 850–858, doi:10.1016/j.future.2016.12.016. [33] R. Johnson, D. Molnar, D.X. Song, D.A. Wagner, Homomorphic signature schemes, in: Topics in Cryptology - CT-RSA 2002, The Cryptographer’s Track at the RSA Conference, 2002, San Jose, CA, USA, February 18–22, 2002, Proceedings, 2002, pp. 244–262, doi:10.1007/3- 540- 45760- 7_17. [34] S. Katsumata, S. Yamada, Partitioning via non-linear polynomial functions: more compact ibes from ideal lattices and bilinear maps, in: Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4–8, 2016, Proceedings, Part II, 2016, pp. 682–712, doi:10.1007/978- 3- 662- 53890- 6_23. [35] T. Li, W. Chen, Y. Tang, H. Yan, A homomorphic network coding signature scheme for multiple sources and its application in iot, Secur. Commun. Netw. 2018 (2018) 9641273:1–9641273:6, doi:10.1155/2018/9641273. [36] Q. Lin, H. Yan, Z. Huang, W. Chen, J. Shen, Y. Tang, An id-based linearly homomorphic signature scheme and its application in blockchain, IEEE Access 6 (2018) 20632–20640, doi:10.1109/ACCESS.2018.2809426. [37] S. Micali, CS proofs (extended abstracts), in: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, 1994, pp. 436–453, doi:10.1109/SFCS.1994.365746. [38] D. Micciancio, C. Peikert, Trapdoors for lattices: simpler, tighter, faster, smaller, in: Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15–19, 2012. Proceedings, 2012, pp. 700–718, doi:10.1007/978- 3- 642- 29011- 4_41. [39] D. Micciancio, O. Regev, Worst-case to average-case reductions based on gaussian measures, in: 45th Symposium on Foundations of Computer Science (FOCS 2004), October 17–19, 2004, Rome, Italy, Proceedings, 2004, pp. 372–381, doi:10.1109/FOCS.2004.72. [40] B. Parno, J. Howell, C. Gentry, M. Raykova, Pinocchio: nearly practical verifiable computation, Commun. ACM 59 (2) (2016) 103–112, doi:10.1145/ 2856449. [41] G. Traverso, D. Demirel, J.A. Buchmann, Homomorphic signature schemes - a survey, Springer Briefs in Computer Science, Springer, 2016, doi:10.1007/ 978- 3- 319- 32115- 8. [42] F. Wang, K. Wang, B. Li, Y. Gao, Leveled strongly-unforgeable identity-based fully homomorphic signatures, in: Information Security - 18th International Conference, ISC 2015, Trondheim, Norway, September 9–11, 2015, Proceedings, 2015, pp. 42–60, doi:10.1007/978- 3- 319- 23318- 5_3. [43] J. Xu, L. Wei, Y. Zhang, A. Wang, F. Zhou, C. Gao, Dynamic fully homomorphic encryption-based merkle tree for lightweight streaming authenticated data structures, J. Netw. Comput. Appl. 107 (2018) 113–124, doi:10.1016/j.jnca.2018.01.014. [44] A. Yun, J.H. Cheon, Y. Kim, On homomorphic signatures for network coding, IEEE Trans. Comput. 59 (9) (2010) 1295–1296, doi:10.1109/TC.2010.73.