Masaya Yasuda
email: yasuda.masaya@jp.fujitsu.com

Takeshi Shimoyama

Jun Kogure
email: kogure@jp.fujitsu.com

Kazuhiro Yokoyama
email: kazuhiro@rikkyo.ac.jp

Takeshi Koshiba
email: koshiba@mail.saitama-u.ac.jp

Packed Homomorphic Encryption based on Ideal Lattices and its Application to Biometrics

Keywords: somewhat homomorphic encryption, ideal lattices, packed ciphertexts, secure Hamming distance, privacy-preserving biometrics

Among many approaches for privacy-preserving biometric authentication, we focus on the approach with homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In biometric authentication, the Hamming distance is often used as a metric to compare two biometric feature vectors. In this paper, we propose an efficient method to compute the Hamming distance on encrypted data using the homomorphic encryption based on ideal lattices. In our implementation of secure Hamming distance of 2048-bit binary vectors with a lattice of 4096 dimension, encryption of a vector, secure Hamming distance, and decryption respectively take about 19.89, 18.10, and 9.08 milliseconds (ms) on an Intel Xeon X3480 at 3.07 GHz. We also propose a privacy-preserving biometric authentication protocol using our method, and compare it with related protocols. Our protocol has faster performance and shorter ciphertext size than the state-of-the-art prior work using homomorphic encryption.

Introduction

Biometric authentication (or biometrics) is an identification of clients by their physical characteristics such as fingerprint, iris, vein and DNA. Since biometric authentication has the advantage that clients do not need to remember their long and complex passwords compared to the commonly used ID/password authentication, the use of biometric authentication is now expanding (see US-VISIT [29] for a typical example). On the other hand, concerns about the security and the privacy are increasing. Especially, it is important to protect templates, which are stored biometric feature data, since once leaked templates can be neither revoked nor replaced. At present, there are the following three main approaches for privacy-preserving biometric authentication (see [START_REF] Belguechi | An overview on privacy preserving biometrics[END_REF] or [START_REF] Jain | Biometric template security (review article)[END_REF] for the details):

-Feature transformation approach, in which biometric feature data are transformed to random data by using a client-specific key or password. Cancelable biometrics [26] and biohashing [START_REF] Belguechi | An overview on privacy preserving biometrics[END_REF]Section 3.3] are typical examples in this approach. This approach is practical in performance, but it is no longer secure if the client-specific key is compromised. -Biometric cryptosystem approach, which is based on error-correcting codes.

This approach includes fuzzy vault [START_REF] Juels | A fuzzy vault scheme[END_REF] and fuzzy commitment [START_REF] Juels | A fuzzy commitment scheme[END_REF]. Since this approach needs to have strong restriction of authentication accuracy, both practical and security issues are controversial. -Homomorphic encryption approach, on which we focus in this paper. In this approach, biometric feature data are protected by homomorphic encryption, and similarity of two feature data is measured on encrypted data by metrics such as the Hamming and the Euclidean distances. This approach enables biometric authentication system to be considerably secure as long as the secret key is securely managed by the trusted party. The performance and the encrypted data size are main issues for the practical use of this approach.

Related Work on Homomorphic Encryption Approach

We summarize privacy-preserving biometric authentication protocols known so far based on homomorphic encryption approach. In 2006, Schoenmakers and Tuyls in [27] proposed secure computations suitable for privacy-preserving biometric authentication using the Paillier scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF], which is additively homomorphic. In 2010, Osadchy et al. in [START_REF] Osadchy | SCiFI -A system for secure face identification[END_REF] designed a new face recognition algorithm and proposed an efficient secure face identification system, called SCiFI, with the Paillier scheme and the oblivious transfer protocol. Their secure two-party computation is based on the work in [START_REF] Jarrous | Secure hamming distance based computation and its applications[END_REF]. In SCiFI, a feature vector extracted from face image is always represented as a binary vector of 900-bit, and the Hamming distance is used as a metric to compare two feature vectors. Their implementation showed that it took 310 ms to compute their secure Hamming distance. At present, SCiFI is known as one of the state-of-the-art privacy-preserving biometric authentication systems suitable for real life. In 2011, Blanton and Gasti in [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF] developed secure protocols for iris and fingerprints. Their secure computation is similar to SCiFI, but they use the DGK scheme [START_REF] Damgård | Homomorphic encryption and secure comparison[END_REF], which is an additively homomorphic encryption with shorter ciphertexts than the Paillier scheme. In their protocol, an iris feature vector is always represented as a binary vector of 2048-bit and the Hamming distance is used as in SCiFI. Their implementation showed that it took 150 ms to compute their secure Hamming distance.

Our Contributions

After Gentry's breakthrough work [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] of constructing a fully homomorphic encryption (FHE) scheme, three main variants of FHE have been proposed so far; one based on ideal lattices [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF][START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF], another one based on integers [START_REF] Coron | Fully homomorphic encryption over the integers with shorter public-keys[END_REF][START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF], and the last one based on the ring learning with errors (ring-LWE) assumption [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Brakerski | Fully homomorphic encryption from ring-LWE and security for key dependent message[END_REF][START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF]. Those FHE schemes start from a somewhat homomorphic encryption (SHE) scheme, which can support only limited number of additions and multiplications on encrypted data but can be much more practical than FHE. To achieve faster secure Hamming distance, we rather use the SHE scheme based on ideal lattices (it is faster and easier to implement than the other SHE schemes). We propose an implementation of Gentry's scheme [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] for applying it to biometrics. Our variant is based mainly on Gentry-Halevi's [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF], but is somewhat different from it because ours is tailored to faster secure computation. We also note that our variant is still provably secure in the sense of IND-CPA under the assumption that the ideal coset problem (ICP) [13, Section 3.2] is intractable. In this work, we will not refer to how to generate feature vectors as in [27], and assume that feature vectors are always represented as binary vectors of 2048-bit, whose length can be applied to various biometrics. Our main contributions are as follows:

-Packing method for secure Hamming distance When we encrypt a feature vector bit by bit, we need to handle a large number of ciphertexts only for one feature vector and hence it would take much time to compute the Hamming distance on encrypted data. In contrast, we propose a new method to pack a feature vector into a single ciphertext, which also enables us to compute secure Hamming distance efficiently (our packing method can be applied in the SHE scheme based on the ring-LWE assumption, and results using the ring-LWE based scheme will be discussed in our next paper). -Privacy-preserving protocol using the SHE scheme We propose a new privacy-preserving biometric authentication protocol using our variant SHE scheme. We also give concrete parameters of our variant scheme with reasonable security, and demonstrate the efficiency of our packing method. Our implementation result shows that our protocol has both faster performance and shorter size of encrypted feature vectors than the state-of-the-art prior work. Furthermore, we believe that our protocol could give a new template protection technique due to our asymmetric packing methods to encrypt a feature vector in enrollment and authentication phases.

Comparison with Known Packing Methods Smart and Vercauteren in

[28] propose a packing method based on polynomial-CRT (Chinese Remainder Theorem) for packing many elements in a single ciphertext, which can be applied to perform SIMD (Single Instruction -Multiple Data) operations on encrypted data. The polynomial-CRT packing method is applied in the work [START_REF] Gentry | Homomorphic evaluation of the AES circuit[END_REF] to evaluate the AES circuit homomorphically with a leveled FHE scheme of [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF]. Furthermore, while the polynomial-CRT packing method can be applied only in ring-LWE based schemes, Brakerski, Gentry and Halevi extend the SIMD notions to the standard LWE based scheme of [START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF] using the packing method of [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF]. Unlike the polynomial-CRT packing method, our method cannot be applied for SIMD operations, but it is very easier to handle and much more efficient for evaluating fundamental computations such as the Hamming distance (it would be more interesting to combine our packing method with the polynomial-CRT method). In their work [START_REF] Lauter | Can homomorphic encryption be practical?[END_REF], Lauter, Naehrig and Vaikuntanathan also present some message encoding techniques in the ring-LWE based scheme, and their technique is to encode integers in a single ciphertext so that it enables us to efficiently compute their sums and products over the integers. When we ignore the difference of homomorphic encryption schemes, our packing method can be considered as an extension of their techniques. Our extension is to give two types of packed ciphertexts, and combinations of two types of our packed ciphertexts give efficient computations such as the inner product and the Hamming distance.

Preliminaries

We fix our standard notation. The symbols Z, Q, R, and C denote the ring of integers, the field of rational numbers, the field of real numbers, and the field of complex numbers, respectively. For a prime number p, the finite field with p elements is denoted by F p . For two integers z and d, let [z] d denote the reduction of z modulo d included in the interval [-d/2, d/2) as in [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF] (let z mod d denote the usual reduction included in the interval [0, d)). For a rational number q ∈ Q, we denote by ⌈q⌋ the rounding of q to the nearest integer, and by [q] the fractional part of q. These notations are extended to vectors and matrices in the natural way. For a vector a = (a

Definitions and Notation in Lattices

Fix an integer number n. Let B ∈ R n×n be a matrix and let b i ∈ R n denote the i-th row of B for i = 1, . . . , n. Denote by It is an index to measure the output quality of a lattice reduction algorithm (the output quality is better as the root Hermite factor is smaller). The most practical lattice reduction algorithms are the LLL and the BKZ algorithms.

L(B) = { n ∑ i=1 m i b i : m i ∈ Z } the set
P(B) = { n ∑ i=1 x i b i : x i ∈ [-1/2, 1 /

Basic Construction of SHE Scheme

We present the basic construction of our variant of the SHE scheme based on ideal lattices (see §3 for some improvements). Our variant is based mainly on Gentry-Halevi's [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF], but ours can use a more general ciphertext space for faster secure computation. For a 2-power integer n = 2 m , let R := Z[x]/(f n (x)) denote the polynomial ring modulo f n (x) := x n + 1, which is an irreducible polynomial. Since a map

∋ v(x) = v 0 + v 1 x + • • • v n-1 x n-1 → v = (v 0 , v 1 , . . . , v n-1 ) ∈ Z n (1)
gives an isomorphism R ≃ Z n as Z-modules, we can view each element of R as both a polynomial v(x) and a vector v.

Key Generation To generate the public and the secret keys, we need key parameters (n, t, s), where n = 2 m is the lattice dimension of 2-power, t is the bit length of coefficients in so called the generating polynomial v(x), and s is the size of the plaintext space. The following construction is based on the sub-optimal key generation described in [14, Section 3] (see §3.3 for our improved key generation):

Step 1. We first choose an n-dimensional vector v = (v 0 , v 1 , . . . , v n-1 ) ∈ Z n , where v i is randomly chosen satisfying the condition

|v i | ≤ 2 t for any i. Set v(x) = ∑ n-1 i=0 v i x i ∈
R as a generating polynomial. Consider the rotation matrix

V := rot(v) =        v 0 v 1 v 2 • • • v n-1 -v n-1 v 0 v 1 • • • v n-2 -v n-2 -v n-1 v 0 • • • v n-3 . . . . . . . . . . . . . . . -v 1 -v 2 -v 3 • • • v 0        . ( 2
)
Since the i-th row of V corresponds to the polynomial v(x) × x i ∈ R under the isomorphism (1), the subgroup L := L(V ) ⊂ Z n is a lattice of dimension n and we have the relation R ⊃ (v(x)) ≃ L ⊂ Z n , where (v(x)) denotes the principal ideal of R generated by v(x).

Step 2. By applying the extended Euclidean-GCD algorithm for polynomials, we compute the scaled inverse w(x) of v(x) modulo f n (x) satisfying

w(x) × v(x) ≡ d mod f n (x).
Note that d is the resultant of v(x) and f n (x), which is also equal to the determinant det(L) = | det(V )| of the lattice L. If gcd(d, s) ̸ = 1, go back to Step 1 and generate another v (we can decrypt a ciphertext without the secret key when s divides d). Let w = (w 0 , w 1 , . . . , w n-1 ) denote the vector corresponding to w(x). Then the matrix

W := rot(w) satisfies W × V = V × W = d • I,
where I is the n × n identity matrix. Step 3. We give the following definition and lemma given in [14, Section 3]:

Definition 1 (goodness of v(x)). We say that v(x) is good if the Hermite normal form basis

B := HNF(L) of the lattice L = L(V ) has the form B =        d 0 0 • • • 0 -r 1 0 • • • 0 * 0 1 • • • 0 . . . . . . . . . . . . . . . * 0 0 • • • 1        . ( 3
) Lemma 1. A generating polynomial v(x) is good if and only if L contains a vector of the form (-r ′ , 1, 0, . . . , 0). Furthermore, if v(x) is good, we have that r := w 1 /w 0 = w 2 /w 1 = • • • = w n-1 /w n-2 = -w 0 /w n-1 mod d and the element r satisfies the condition r n ≡ -1 mod d.
In this step, we check whether v(x) is good or not. For checking it, we only test that r := w 1 /w 0 mod d satisfies r n ≡ -1 mod d; If r n ≡ -1 mod d, go to the next step. Otherwise, go back to Step 1 and generate another v. Step 4. We set V, W (resp. B) as the secret key (resp. the public key). We here call V, W (resp. B) the secret key matrices (resp. the public key matrix ). Due to the special form (3) of B, we only need to set sk = w i as the secret key and pk = (d, r, n, s) as the public key, where w i is a single coefficient of w satisfying gcd(w i , s) = 1 (see Decryption below).

Encryption To encrypt a plaintext b ∈ Z/sZ = {0, 1, . . . , s -1} with pk = (d, r, n, s), we first choose a random "noise vector" u = (u 0 , u 1 , . . . , u n-1 ) with u i ∈ {0, ±1} chosen as 0 with some probability q and as ±1 with probability (1 -q)/2 each. Then the ciphertext of b is given by the integer

Enc(b) = [ b + s n-1 ∑ i=0 u i r i ] d .
Set a := su + be 1 = (su 0 + b, su 1 , . . . , su n-1 ) with e 1 = (1, 0, . . . , 0), and let a(x) ∈ R denote the corresponding polynomial. Then we have Enc(b) = [a(r)] d and the vector (Enc(b), 0, . . . , 0) is equal to

a mod B := a - ( ⌈a × B -1 ⌋ × B ) ∈ P(B)
, which is the ciphertext vector generated by the public key matrix B (see [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF]Section 5] for details).

Definition 2 (masked plaintext). We call the vector a (or the polynomial a(x)) the masked plaintext corresponding to a ciphertext ct.

We need to choose the probability q to make it hard to recover the original noise vector from a ciphertext c. Against exhaustive-search and birthday attacks, we set a security parameter λ, where we need to set q satisfying 2 (1-q)n • ( n qn ) > 2 2λ [14, Section 5.2]. Furthermore, Gentry and Halevi in [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF] considered the hybrid attack, whose method is to choose a random subset of the powers of r including all the noise coefficients and search for a small vector in this low-dimension lattice (e.g., dimension 200). It is sufficient to set q satisfying ( n 200

) qn ≥ 2 λ
against the hybrid attack. For λ = 80 and n ≥ 1024, the above two inequalities are satisfied if q = 1 3 . In this paper, we fix q = 1 3 for higher security. In contrast, Gentry and Halevi in [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF] take an aggressive setting where the number of nonzero entries in the noise vectors is between 15 and 20 for FHE public challenges).

Decryption To decrypt a ciphertext Enc(b) with the secret key matrices V, W , we first recover the corresponding masked plaintext by

a = c mod V = c - ( ⌈c × V -1 ⌋ × V ) = [c×W/d]
×V with the ciphertext vector c = (Enc(b), 0, . . . , 0). It follows from [14, Section 6] that we can recover the masked plaintext a if every entry in a × W is less than d/2 in absolute value. For a = (a 0 , a 1 , . . . , a n-1 ), we then output b = a 0 mod s ∈ Z/sZ as the decryption result.

In [14, Section 6.1], Gentry and Halevi proposed an optimized decryption procedure in the case s = 2. We can extend their method to our variant scheme; Let a = su + be 1 be the masked plaintext of a ciphertext Enc(b). From a similar argument of [14, Section 6.1], we have

[c × W ] d = a × W = su × W + b • (w 0 , w 1 , . . . , w n-1 ) if every entry in a × W is less than d/2 in absolute value. Since [c × W ] d = ([Enc(b) • w 0 ] d , [Enc(b) • w 1 ] d , . . . , [Enc(b) • w n-1 ] d ), we have [Enc(b) • w i ] d ≡ b • w i mod s for any i.
It is therefore sufficient to keep one coefficient w i of w with gcd(w i , s) = 1 as the secret key sk, and then we can recover b by computing

[Enc(b) • sk] d • sk -1 mod s. ( 4
)
Note that there always exists w i satisfying gcd(w i , s) = 1 if we take s = 2 k .

Homomorphic Operations For two ciphertexts Enc(b 1 ) and Enc(b 2 ), the homomorphic addition "∔" is defined by

Enc(b 1 ) ∔ Enc(b 2 ) := [Enc(b 1 ) + Enc(b 2 )] d .
The homomorphic subtraction is also defined by

Enc(b 1 ) -Enc(b 2 ) := [Enc(b 1 ) - Enc(b 2 )] d .
Similarly, the homomorphic multiplication " * " is defined by

Enc(b 1 ) * Enc(b 2 ) := [Enc(b 1 ) • Enc(b 2 )] d .
Let a 1 , a 2 ∈ R denote the masked plaintexts corresponding to Enc(b 1 ), Enc(b 2 ), respectively. Then we see that the vectors ([Enc(b 1 ) + Enc(b 2 )] d , 0, . . . , 0) and ([Enc(b 1 ) • Enc(b 2 )] d , 0, . . . , 0) are equal to a 1 + a 2 mod B and a 1 × a 2 mod B respectively, where "×" denotes the multiplication operation in the ring R. This shows that the homomorphic operations correspond to the ring structure of R, from which the homomorphic property of our variant scheme follows. However, homomorphic operations make the size of the noise vector in the corresponding masked plaintext larger. Therefore it is only possible to add and multiply ciphertexts before the size of the noise vector grows beyond the decryption range.

Some Improvements of SHE scheme

In this section, we give some improvements of our variant SHE scheme described in §2.2, mainly for an efficient computation of secure Hamming distance.

Theoretical Evaluation of Decryption Range

In applying the SHE scheme to a concrete application scenario, the size of its decryption range is the most important in choosing key parameters suitable for the scenario. Under the condition |v i | ≤ 2 t , Gentry and Halevi in [14, Section 7] experimentally estimate that the decryption range is roughly equal to 2 t and it succeeds to decrypt a ciphertext ct if the corresponding masked plaintext a satisfies ||a|| ≤ 2 t . In contrast, we give a theoretical evaluation of the range under a certain condition in choosing a generating polynomial v

(x) = ∑ n-1 i=0 v i x i ∈ R (cf. Key Generation in §2.2).
In the following, we give our technical result without a proof due to lack of space (a complete proof will be given in our forthcoming paper):

Proposition 1. Assume the condition (♣) : T = |v n-1 | = 2 t (1 + ε n-1 ) and v i = T ε i with |ε i | < 1 4n for 0 ≤ i ≤ n -2 and ε n-1 > 0.

Then the decryption of a ciphertext ct succeeds if the corresponding masked plaintext a satisfies either

||a|| 1 < 11 • 2 t-1 13 or ||a|| ∞ < 11n • 2 t-1 19n -6 . ( 5
)
Since we have |v n-1 | = T ≈ 2 t and |v i | < T /4n for 0 ≤ i ≤ n -2 under the condition (♣) for sufficiently small ε n-1 > 0, we can consider our condition as a restricted version of Gentry-Halevi's condition |v i | ≤ 2 t . Our theoretical evaluation gives the same level as Gentry-Halevi's experimental one, and especially it enables us to use the ∞-norm evaluation, which is independent of the noise probability q in encryption (Gentry-Halevi's evaluation uses the Euclidean norm, and it is deeply related with q). Hence our evaluation makes it easier to choose key parameters in applying our variant SHE scheme to a concrete scenario (in particular, the ∞-norm evaluation makes it easy in the noise management of ciphertexts).

Packing Method for Secure Hamming Distance

As described in Encryption of §2.2, we can only encrypt an element of Z/sZ in our variant scheme. In contrast, we propose a new method to pack a binary vector in a single ciphertext, which is also suitable for an efficient computation of both secure inner product and secure Hamming distance. Our packing method is to transform a binary vector into a certain polynomial of the ring R, and to encrypt the transformed polynomial. Furthermore, for efficient secure computation, we make use of polynomial operations in the ring R. As described in §1.2, our packing method can be considered as an extension of the method proposed in [START_REF] Lauter | Can homomorphic encryption be practical?[END_REF], and our main extension is to give two types of packed ciphertexts. However, our packing method causes a difficulty that it is not straightforward to apply the optimized decryption procedure (4) described in Decryption of §2.2. To overcome the problem, we need to take a generating polynomial v(x) satisfying a certain condition (see Proposition 3 below). We begin with our packing method and efficient computation of the secure inner product. As remarked in §1.2, we only consider 2048-bit binary vectors for securing the Hamming distance often used in biometrics.

Definition 3 (packing method vEnc i ).

Assume n ≥ 2048. We define two types of packing method as follows (cf. Encryption of §2.2):

Type 1 For a binary vector A, let

F 1 : A = (A 0 , . . . , A 2047 ) → ∑ 2047 i=0 A i x i ∈ R = Z[x]/(f n (x)).
Then its packed ciphertext is defined by the integer

vEnc 1 (A) := [F 1 (A)(r) + su 1 (r)] d = [ 2047 ∑ i=0 A i r i + su 1 (r) ] d (6)
using the public key pk = (d, r, n, s), where u 1 (x) ∈ R denotes a noise polynomial. We note that the masked plaintext of vEnc 1 (A) corresponds to the polynomial F 1 (A) + su 1 (x) ∈ R. Type 2 For a binary vector B, let F 2 : B = (B 0 , . . . , B 2047 ) → -∑ 2047 i=0 B i x n-i . Then its packed ciphertext is defined by the integer

vEnc 2 (B) := [F 2 (B)(r) + su 2 (r)] d = [ - 2047 ∑ i=0 B i r n-i + su 2 (r) ] d , ( 7
)
where u 2 (x) denotes a noise polynomial. We also note that the masked plaintext of vEnc 2 (B) corresponds to the polynomial

F 2 (B) + su 2 (x) ∈ R.
Proposition 2 (secure inner product). Assume n ≥ 2048. Let ct be the ciphertext given by the homomorphic multiplication of vEnc 1 (A) and vEnc 2 (B). Let a = (a 0 , . . . , a n-1 ) ∈ R = Z n denote the masked plaintext corresponding to ct. Then we have

a 0 ≡ 2047 ∑ i=0 A i B i mod s.
Proof. The homomorphic multiplication corresponds to the multiplication in the ring R. This shows that a = (F 1 (A) + su 1 (x)) × (F 2 (B) + su 2 (x)) ∈ R and we have a ≡ F 1 (A) × F 2 (B) mod s. We easily see that the constant term of

F 1 (A) × F 2 (B) = 2047 ∑ i=0 A i x i × 2047 ∑ j=0 B j x n-j is equal to ∑ 2047 i=0 A i B i since x n = -1 in the ring R. ⊓ ⊔
Let ct and a = (a 0 , . . . , a n-1 ) be as in Proposition 2. By Proposition 2, we only need to recover a 0 mod s with the secret key sk to obtain the inner product. However, it is not straightforward to apply the optimized decryption procedure (4) described in Decryption of §2.2 since the masked plaintext a ∈ R is not of the form su + be 1 , which we handle for the usual encryption Enc(b) described in Encryption of §2.2. To apply the optimized decryption (4) for the recovery of a 0 mod s with sk, we need the following result: Proposition 3 (suitable condition for decryption). Let ct and a be as in Proposition 2. For a generating polynomial v(x) =

∑ n-1 i=0 v i x i ∈ R, we assume v i ∈ sZ for i = 1, . . . , n -1 (but we take v 0 ̸ ∈ sZ). Let w = (w 0 , w 1 , . . . , w n-1 ) be the vector generated in Key Generation of §2.2, and we take w 0 as the secret key sk. Then we can recover a 0 mod s with sk by computing

[ct • sk] d • v 0 • d -1 mod s.
In particular, we can recover a 0 mod s with sk by computing

[ct • sk] d mod s if we take v 0 satisfying v 0 ∈ 1 + sZ.
Proof. For v = (v 0 , . . . , v n-1 ), let V = rot(v) and W = rot(w) be the secret key matrices. For the ciphertext vector c = (ct, 0, . . . , 0), it follows from a similar argument of Decryption of §2.2 that

[c × W ] d = a × W ⇐⇒ ([ct • w 0 ] d , . . . , [ct • w n-1 ] d ) • V = a × W × V = (da 0 , . . . , da n-1 ) (8)
if every entry in a × W is less than d/2 in absolute value (note that we have

W × V = d • I).
By comparing the first entry of the vectors in the right hand side of (8), we have [ct • w 0 ] d • v 0 ≡ da 0 mod s by the assumption v i ∈ sZ for i = 1, . . . , n-1. Hence we can recover a 0 mod s by computing

[ct•w 0 ] d •v 0 •d -1 mod s. In particular, if v 0 ∈ 1 + sZ, we have v 0 • d -1 ≡ 1 mod s since d ≡ v n 0 ≡ 1 mod s by d = det(V ) and v i ∈ sZ for i = 1, . . . , n -1. This completes the proof. ⊓ ⊔
Secure Hamming Distance We apply our packing method to compute the Hamming distance on encrypted data. Assume n, s ≥ 2048. For the guarantee of both the theoretical decryption range of Proposition 1 and the success of the decryption, we need to take a generating polynomial v(x) under the condition

(♠) : v 0 ∈ 1 + sZ, v i ∈ sZ for 1 ≤ i ≤ n -1,

and the condition (♣).

Take w 0 as the secret key sk as in Proposition 3. For two binary vectors A and B, the Hamming distance d H (A, B) can be computed by

∑ 2047 i=0 (A i + B i -2A i B i ) = HW(A) + HW(B) -2 ∑ 2047 i=0 A i B i
, where HW(•) denotes the Hamming weight of a binary vector. For computing the Hamming distance on encrypted data, we consider two integers

C 1 := [ n-1 ∑ i=0 r i ] d and C 2 := [-C 1 + 2] d with the public key pk = (d, r, n, s). Set c 1 (x) := ∑ n-1 i=0 x i and c 2 (x) := -c 1 (x) + 2 = 1 - ∑ n-1 j=1
x j in the ring R. From a similar argument in the proof of Proposition 2, the homomorphic multiplication of vEnc 1 (A) and C 2 (resp. vEnc 2 (B) and C 1 ) corresponds to the masked plaintext (F

1 (A) + su 1 (x)) × c 2 (x) (resp. (F 2 (B) + su 2 (x)) × c 1 (x))
, whose constant term modulo s is equal to HW(A) (resp. HW(B)). Therefore the encrypted Hamming distance is computed by --------→ vEnc 1 (A) ↘ c H defined by ( 9)

ct H = C 2 * vEnc 1 (A) ∔ C 1 * vEnc 2 (B) ∔ (-2vEnc 1 (A) * vEnc 2 (B)) = C 1 * (-vEnc 1 (A) ∔ vEnc 2 (B)) ∔ 2vEnc 1 (A) * (1 -vEnc 2 (B)) (9)
dec.

-

---→ d H (A, B) B --------→ packed enc. vEnc 2 (B) ↗ Remark 1.
As mentioned in §1.2, our variant is just an instantiation of Gentry's abstract scheme described in [13, Section 3.1] (of course, ours provides an "efficient" implementation). Since Gentry's scheme is provably secure in the sense of IND-CPA under the ICP assumption even in the abstract level (see [13, Section 3.2] for the detail). Thus ours inherits the provable security from Gentry's (we note that Gentry's scheme is not IND-CCA1 [START_REF] Loftus | On CCA-secure somewhat homomorphic encryption[END_REF]).

Improving Key Generation

The problem of the construction of our variant scheme described in §2.2 is the slow key generation. Based on Gentry-Halevi's optimized key generation [14, Section 4], we give some improvements for faster key generation than their one, and also guarantee the theoretical decryption range of Proposition 1. The main idea of Gentry-Halevi's optimized key generation is as follows: For a lattice dimension n = 2 m , fix a primitive 2n-th root ρ of f n (x) = x n + 1 and set ρ i = ρ 2i+1 for i = 0, 1, . . . , n -1, which are the roots of f n (x) in the field C of complex numbers. To generate the key pair (pk, sk), we consider two polynomials

g(z) := n-1 ∏ i=0 (v(ρ i ) -z) and h(z) := n-1 ∏ i=0 (v(ρ i ) -z/ρ i )
for a generating polynomial v(x). Although g(z) and h(z) are defined by ρ i ∈ C, the coefficients of g(z) and h(z) are all integers. Let g i (resp. h i ) denote the coefficient of z i in g(z) (resp. h(z)). By [14, Section 4], we have d = g 0 ,

w 0 = -g 1 /n and w 1 = -h 1 /n if v(x) is square-free. Since w 1 /w 0 = • • • = w n-1 /w n-2 = -w 0 /w n-1
mod d in the case where v(x) is good by Lemma 1, we can recover the rest of w i from the triple (d, w 0 , w 1 ). After recovering the triple (d, w 0 , w 1 ), we therefore compute the ratio r = w 1 /w 0 mod d and verify that r n ≡ -1 mod d, which is the condition for testing that r • w i = w i+1 mod d. In the following, we give our improvements:

Simultaneous Computation of g(z), h(z) mod z 2

From the above argument, we need to consider g(z), h(z) mod z 2 to obtain the triple (d, w 0 , w 1 ). In [14, Section 4.1], Gentry and Halevi showed a method to compute g(z), h(z) mod z 2 separately. In contrast, we give a method to compute g(z), h(z) mod z 2 at the same time:

Set U 0 (x) = 1, V 0 (x) = v(x) and W 0 (x) = -x n-1 . For 0 ≤ j ≤ m, let      V j (x) • V j (-x) mod f nj (x) = ∑ nj -1 i=0 a (j) i x i , U j (x) • V j (-x) + U j (-x) • V j (x) mod f nj (x) = ∑ nj -1 i=0 b (j) i x i , W j (x) • V j (-x) + W j (-x) • V j (x) mod f nj (x) = ∑ nj -1 i=0 c (j) i x i ,
and

U j+1 (x) = ∑ nj /2-1 k=0 b (j) 2k x k , V j+1 (x) = ∑ nj /2-1 k=0 a (j) 2k x k , W j+1 (x) = ∑ nj /2-1 k=0 c (j) 2k
x k , where f nj (x) := x nj + 1 with n j = n/2 j . Then we have

g j (z) := nj -1 ∏ i=0 ( V j (ρ 2 j i ) -zU j (ρ 2 j i ) ) ≡ g(z) mod z 2 , ( 11
)
h j (z) := nj -1 ∏ i=0 ( V j (ρ 2 j i ) -zW j (ρ 2 j i ) ) ≡ g(z) mod z 2 (12)
by a similar argument of [14, Section 4.1]. Since the degree of U m (x), V m (x) and W m (x) is equal to 0, we can consider these polynomials as integers U m , V m and W m respectively, and we have g 0 = h 0 = V m , g 1 = U m and h 1 = W m by the equations ( 11) and ( 12). Therefore we only need to compute U j (x), V j (x) and W j (x) to obtain the triple (d, w 0 , w 1 ).

Quick Test of Goodness

In the optimal key generation of [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF], after computing (d, w 0 , w 1 ), we test the condition r n ≡ -1 mod d to check that v(x) is not good (see also Key Generation of §2.2). In the case where r n ̸ ≡ -1 mod d, we need to compute the triple (d, w 0 , w 1 ) again for another generating polynomial v(x). Since the cost of computing the triple (d, w 0 , w 1 ) is dominant in the key generation, we consider a method to check that v(x) is not good without computing the triple (d, w 0 , w 1 ) exactly. We give the following lemma:

Lemma 2. If v(x)
v(x) • w(x) ≡ d mod f n (x), where w(x) = ∑ n-1 i=0 w i x i with r = w 1 /w 0 mod d and w i = r i • w 0 for i ≥ 1).

Guarantee of Theoretical Decryption Range

We give a method to choose a generating polynomial v(x) in order to guarantee the theoretical decryption range of Proposition 1. In the key generation, we choose a generating polynomial v(x) = ∑ n-1 i=0 v i x i ∈ R, where v i ∈ Z is randomly chosen with the condition (♠) for our secure Hamming distance (see Proposition 3). Then we can use the theoretical evaluation of the decryption range of Proposition 1.

Improved Key Generation Algorithm

In Algorithm 1, we give a concrete algorithm of our key generation. Using our key generation, we can generate a good generating polynomial v(x) with higher probability than the key generation of [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF]. Since v(x) with d ≡ 1 mod 2n satisfies the condition r n ≡ -1 mod d with very high probability, we hardly go back to Step 1 in Step 4 of Algorithm 1, which shows that Step 2 has the advantage of the processing performance. n particular, our experiment shows that our algorithm is 25% faster on average than the case without Step 2 for input (n, t, s) = (4096, 37, 2048).

Application to Biometric Authentication

In this section, we propose a privacy-preserving biometric authentication protocol using our variant SHE scheme with our packing method. We also compare our protocol with the related protocols described in §1.1, and demonstrate the efficiency of our packing method.

Protocol using SHE Scheme based on Ideal Lattices

Unlike SCiFI and the protocol of [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF], our protocol involves three parties, a client server C, a computation server S, and an authentication server A. We assume that the authentication server A is a trusted party to manage the secret key of homomorphic encryption. Our protocol is based on the work in [START_REF] Hattori | Provably-secure cancelable biometrics using 2-DNF evaluation[END_REF] using generic 2-DNF (disjunctive normal form) homomorphic encryption such as the BGN scheme [START_REF] Boneh | Evaluating 2-DNF formulas on ciphertexts[END_REF], which can support additions and one depth multiplications on encrypted data. In contrast to their work, we use the SHE scheme based on ideal lattices. In the following, we give a construction of our protocol of biometric authentication with ID, namely, one-to-one authentication protocol:

Setup Phase The authentication server A generates the public key pk and the secret key sk of our variant scheme. Then the server A distributes only the public key pk to both the client server C and the computation server S. Enrollment Phase 1. The client server C generates a feature vector A of 2048-bit from client's biometric data such as fingerprints, encrypts A using our packing method of type 1 (see Definition 3), and sends the encrypted feature vector vEnc 1 (A) with client's ID to the computation server S. 2. The computation server S stores the encrypted feature vector vEnc 1 (A) in the database D as a template with client's ID. Authentication Phase 1. As in the enrollment phase, the client server C generates a feature vector B of 2048-bit from client's biometric data, encrypts B using our packing method of type 2 (note that it is different from the encryption method in the enrollment phase), and sends the encrypted feature vector vEnc 2 (B) with client's ID to the computation server S. 2. The computation server S extracts the template vEnc 1 (A) corresponding to client's ID from the database D. Then the server S computes the encrypted Hamming distance ct H of vEnc 1 (A) and vEnc 2 (B) defined by the equation ( 9), and sends only the encrypted data ct H to the authentication server A. 3. The authentication server A decrypts the encrypted data ct H with the secret key sk to obtain the Hamming distance d H (A, B). Finally, the server A returns the authentication result 'OK' (resp. 'NG') if d H (A, B) ≤ σ (resp. otherwise), where let σ denote pre-defined threshold.

In our protocol, all feature vectors handled by the computation server S are protected by homomorphic encryption, and hence we hope that we could use the cloud as the server S for outsourcing storage of templates and computation resources of secure Hamming distance. Furthermore, since the method vEnc 1 (A) to encrypt a feature vector A in the enrollment phase is asymmetric to the method vEnc 2 (B) in the authentication phase, our protocol is expected to have the additional advantage that identity theft is harder than the conventional protocols even if templates are leaked to attackers (even if an attacker steals a template vEnc 1 (A) from the database D and sends it to the computation server S instead of vEnc 2 (B) in the authentication phase, the authentication would fail with very high probability since the decryption result in the authentication server A is not by the Hamming distance between A and A due to lack of vEnc 2 (A)). From the above discussions, we believe that our protocol would be secure as long as the authentication server A manages the secret key sk correctly.

Choosing Parameters and Security Analysis

In this section, we describe a method to choose key parameters for secure Hamming distance described in §3.2, and estimate their security level.

Key Parameters

We give key parameters (n, t, s) suitable for secure Hamming distance ct H given in the equation [START_REF] Coron | Fully homomorphic encryption over the integers with shorter public-keys[END_REF]. Our chosen key parameters are (n, t, s) = (2048, 37, 2048) and (4096, 37, 2048).

(

) 13
These key parameters are estimated to have more than 80-bit security against exhaustive-search and birthday attacks on v(x) generated under the condition (♠) since 2 t = 2 37 is enough large compared with 4n•s = 2 24 or 2 25 (for example, exhaustive-search attack takes (2 t /(4n • s)) n = (2 13 ) 2048 or (2 12 ) 4096 ).

The method to choose the key parameters ( 13) is as follows: Since 0 ≤ d H (A, B) ≤ 2048, we set s = 2048 to avoid expensive carry operations. To encrypt a 2048-bit binary vector in a single ciphertext, we should take n ≥ 2048 and we only consider the two cases n = 2048 and 4096 for the practical use (see also Definition 3). Let a H be the masked plaintext corresponding to the encrypted Hamming distance ct H as in §3.2. We let a 1 and b 1 denote the masked plaintexts corresponding to vEnc 1 (A) and vEnc 2 (B), respectively. We also let a 2 and b 2 denote the masked plaintexts corresponding to the homomorphically operated ciphertexts C 2 * vEnc 1 (A) and C 1 * vEnc 2 (B), respectively. Then we have

a H = a 2 + b 2 -2a 1 × b 1 ∈ R
by the equation [START_REF] Coron | Fully homomorphic encryption over the integers with shorter public-keys[END_REF]. By evaluating the ∞-norm size of a H , we determine suitable t for decryption success of the ciphertext ct H . For any two elements a, b ∈ R, we have ||a

+ b|| ∞ ≤ ||a|| ∞ + ||b|| ∞ , ||a × b|| ∞ ≤ n • ||a|| ∞ • ||b|| ∞ (see [21, Lemma 3.2]
). Since we only consider n = 2048 and 4096, we have

||a H || ∞ ≤ ||a 2 || ∞ + ||b 2 || ∞ + 2n • ||a 1 || ∞ • ||b 1 || ∞ ≤ 2n • (2 11 + 1) + 2n • (2 11 + 1) 2 ≤ 2 26 + 2 35 . Note that we have ||a 1 || ∞ , ||b 1 || ∞ ≤ 2 11 + 1 and ||a 2 || ∞ , ||b 2 || ∞ ≤ n • (2 11 + 1)
due to s = 2 11 . By the ∞-norm evaluation of Proposition 1, we estimate that the decryption of ct H succeeds if we take t ≥ 37, and then we fix t = 37 for better performance and shorter ciphertexts.

Security Analysis against Lattice Reduction Attack By using lattice reduction algorithms with considerably small root Hermite factor (see §2.1 for the root Hermite factor), we can recover the plaintext from a ciphertext without the secret key, which we simply call a lattice reduction attack. We note that the hardness of the lattice reduction attack is closely related to the ICP assumption, on which the provable security of our variant scheme relies (see Remark 1). We estimate the security level of our key parameters (13) against the attack. Its security is based on the hardness of the lattice problem γ-BDDP [14, Section 2.2] with the parameter

γ = d 1/n min ||a|| ≈ (2 tn ) 1/n s • √ 2n/3 = 2 t s • √ 2n/3 , ( 14
)
where min ||a|| denotes the minimal Euclidean norm of the masked plaintexts. Note that min ||a|| = ||a 1 || or ||b 1 || ≈ s • √ 2n/3 due to the probability q = 1 3 , where a 1 (resp. b 1 ) denotes the masked plaintext corresponding to vEnc 1 (A) (resp. vEnc 2 (B)). BDDP is intuitively the analogue of the lattice problem unique-SVP, and it can be solved by lattice reduction algorithms with the root Hermite factor smaller than γ [START_REF] Gama | Predicting lattice reduction[END_REF].

The case (n, t, s) = (2048, 37, 2048) We have γ = 1.0071 n by the equation [START_REF] Gentry | Implementing Gentry's fully-homomorphic encryption scheme[END_REF]. Since the root Hermite factor of LLL (resp. BKZ with β = 20) is practically 1.02 n (resp. 1.0128 n ) on average (see experimental results of the work in [START_REF] Gama | Predicting lattice reduction[END_REF]), it cannot be solved by LLL and BKZ with β = 20. At present, BKZ 2.0 is the state-of-the-art implementation of BKZ with large β ≥ 50. The approximate root Hermite factor achieved by BKZ 2.0 is shown in [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]Table 2]. According to [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]Table 2], the BKZ blocksize β ≈ 160 is needed to solve this case (the root Hermite factor of BKZ 2.0 with β = 168 is predicted to be 1.007 n ). The approximate running time of BKZ 2.0 is given by z × dim ×e, where z is the number of rounds, "dim" is the lattice dimension and e is the approximate running time of the enumeration subroutine of blocksize β (see [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] for details). Since a few rounds are sufficient to achieve an enough performance of BKZ 2.0, we assume z = 1 for simplicity. As for e, Chen and Nguyen in [8, Table 3] gave an estimated upper bound on the cost of the enumeration subroutine. From [8, Table 3], we have that the enumeration subroutine of BKZ 2.0 with β = 160 is estimated at 2 84.7 nodes at maximum. Since they also reported that one node requires about 200 clock cycles, we estimate that e ≤ 200 × 2 84.7 ≈ 2 92.3 clock cycles for BKZ 2.0 with β = 160. Therefore we estimate that the running time of BKZ 2.0 with β = 160 is at most 2 11 × 2 92.3 = 2 103.3 cycles in dimension 2048, which shows that this case may reach 80-bit security against BKZ 2.0. We remark that this estimation is just an upper bound cost of BKZ 2.0.

The case (n, t, s) = (4096, 37, 2048) We have γ = 1.0034 n in this case. The BKZ blocksize β ≥ 280 is needed to solve this case from [8, Table 2] (the root Hermite factor of BKZ 2.0 with β = 286 is predicted to be 1.005 n ). In contrast to [8, Table 3], they in [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]Table 4] also gave an estimated lower bound of the cost 3] that this case has more than 192-bit security against BKZ 2.0).

Implementation Results

We implemented our variant scheme for the key parameters [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. The performance and the ciphertext size are shown in Table 1. We remark that the packed encryption vEnc i is computed by the equation ( 6) or ( 7), the secure Hamming distance is computed by the equation ( 9) using the precomputed integer C 1 , and the decryption of the encrypted Hamming distance ct H is computed by [START_REF] Damgård | Homomorphic encryption and secure comparison[END_REF] with the secret key sk. In particular, the homomorphic addition takes about 0.004 ms (resp. 0.007 ms), and the homomorphic multiplication takes about 2.46 ms (resp. 9.00 ms) for (n, t, s) = (2048, 37, 2048) (resp. (n, t, s) = (4096, 37, 2048)). In our implementation, we used our software library written with assembly language x86 64 for all computations in the base ring R/(v(x)) ≃ Z/dZ (cf. see also [START_REF] Lauter | Can homomorphic encryption be practical?[END_REF] for its implementation result of the SHE scheme based on the ring-LWE problem).

Our experiments ran on an Intel Xeon X3480 at 3.07 GHz with 16 GByte memory. We also implemented Karatsuba Multiplication and Montgomery Reduction algorithm for efficient multiplication in the base ring Z/dZ. Furthermore, we used a precomputed table

T = {1, [r] d , [r 2 ] d , . . . , [r n-1
] d } to make the encryption and the homomorphic operations much faster.

Comparison to Related Work

In Table 2, we give a comparison of our protocol using a lattice of 4096 dimension with the related protocols described in §1.1, with respect to the performance and the ciphertext size, which are main issues for the practical use of homomorphic encryption as remarked in §1 (all encryption schemes in Table 2 are estimated to have 80-bit security). From Table 2, our protocol has faster performance and shorter size than SCiFI and the protocol of [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF]. In particular, our protocol is about 8 times faster and about 14 times shorter than the protocol of [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF] when we ignore the difference of the PC performance. This is mainly due to our [START_REF] Osadchy | SCiFI -A system for secure face identification[END_REF] 310 ms (a) 2048 times Paillier-1024 (900-bit) (230 KByte) (additive scheme) Protocol of [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF] 150 ms (b) 1024 times DGK-1024 (2048-bit) (262 KByte) (additive scheme) Ours 18.10 ms (c) ≈ 80 times ideal lattices-4096 (2048-bit) (19 KByte) (SHE scheme) * denotes the ratio of (encrypted feature vector size)/(plain feature vector size) (a) on an 8 core machine of 2.6 GHz AMD Opteron processors with 1 GByte memory (b) on an Intel Core 2 Duo 2.13 GHz with 3 GByte memory (c) on an Intel Xeon X3480 at 3.07 GHz with 16 GByte memory packing method since a feature vector can only be encrypted bit by bit due to the property of additive encryption schemes in SCiFI and the protocol of [START_REF] Blanton | Secure and efficient protocols for iris and fingerprint identification[END_REF].

Furthermore, let us compare our protocol with one using the BGN scheme [START_REF] Boneh | Evaluating 2-DNF formulas on ciphertexts[END_REF] such as the work in [START_REF] Hattori | Provably-secure cancelable biometrics using 2-DNF evaluation[END_REF]. The BGN scheme is based on bilinear pairings on elliptic curves, and it requires a pairing computation for its homomorphic multiplication. According to [21, Section 1.2], the homomorphic multiplication of the BGN scheme is very slower than that of lattice-based homomorphic encryption. Furthermore, we can not use our packing method in the BGN scheme, and hence it needs 2048 homomorphic multiplications for secure Hamming distance of two vectors of 2048-bit. Even if we use very fast implementation taking 1 ms for one pairing computation, it takes about 2048 ms ≈ 2 sec for secure Hamming distance. Therefore we estimate that our protocol is at least about 100 times faster than one using the BGN scheme (our protocol is also estimated to have shorter size than one using the BGN scheme due to our packing method).

26. N. Ratha, J. Connelle and R. Bolle, Enhansing security and privacy in biometricsbased authentication system, IBM Systems J. 37 [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF] set wi as the secret key sk (in using the condition (♠), we set w0 as sk).

2 )}

 2 denote its associated half-open parallelepiped. Every lattice L has a unique Hermite normal form basis HNF(L) = (b ij ), where b ij = 0 for all i < j, b jj > 0 for all j, and b ij ∈ [-b jj /2, b jj /2) for all i > j. Given any basis of L, we can compute the basis HNF(L) by Gaussian elimination. Note that the basis HNF(L) typically serves as the public key representation of the lattice. By lattice reduction, we mean an operation that computes a basis B = [b 1 , . . . , b n ] t of L with short and nearly orthogonal vectors b 1 , . . . , b n from a given basis of L. Lattice reduction algorithms are often used for breaking lattice cryptosystems. The root Hermite factor of a lattice reduction algorithm is defined by ||b 1 ||/ det(L) 1/n with the output basis [b 1 , . . . , b n ] t .

Algorithm 1 : 1 k=0t 3 : 4 :

 1134 Improved key generation of our variant SHE scheme Input: (n, t, s): key parameters (for simplicity, assume that s is a 2-power integer) Output: The public key pk = (d, r, n, s) and the secret key sk = w.1: Generate a random vector v = (v0, v1, . . . , vn-1) ∈ Z n , where vi ∈ Z is chosen under the condition (♣) (or (♠) for secure Hamming distance), and set v(x) = ∑ n-1 i=0 vix i . 2: By computing the followings, we verify that d = res(fn(x), v(x)) ≡ 1 mod 2n:(2-a) S0(x) ← v(x) mod 2n ∈ (Z/2nZ)[x]. (2-b) For j = 0 to m -1, do i. Set fn j (x) = x n j + 1 with nj = n/2 j . Compute Tj(x) = Sj(x) • Sj(-x) mod (2n, fn j (x)) = ∑ n j -1 i=0 tix i with ti ∈ {0, 1, . . . , 2n -1}. ii. Sj+1(x) ← ∑ n j /2-2k x k . (2-c) Then d ≡ Sm mod 2n. If Sm ̸ ≡ 1 mod 2n, go back to Step 1. Compute the triple (d, w0, w1) as follows: (3-a) U0(x) ← 1, V0(x) ← v(x), W0(x) ← -x n-1 . (3-b) For j = 0 to m -1, do i. As in (2-b), set fn j(x) = x n j + 1 with nj = n/2 j . Compute Aj(x) = Vj(x) • Vj(-x) mod fn j (x) = ∑ n j -1 i=0 aix i , Bj(x) = Uj(x) • Vj(-x) + Uj(-x)•Vj(x) mod fn j (x) = ∑ n j -1 i=0 bix i and Cj(x) = Wj(x)•Vj(-x)+ Wj(-x) • Vj(x) mod fn j (x) = ∑ n j -1 i=0 cix i . ii. Uj+1(x) ← ∑ n j /2-1 k=0 b 2k x k , Vj+1(x) ← ∑ n j /2-1 k=0 a 2k x k , Wj+1(x) ← ∑ n j /2-1 k=0 c 2k x k .(3-c) Then d = Vm, g1 = Um, h1 = Wm, and hence w0 = -g1/n, w1 = -h1/n. Set r = w1/w0 mod d and verify that r n ≡ -1 mod d. If r n ≡ -1 mod d, set pk = (d, r, n, s). Otherwise, go back to Step 1. 5: For i = 0 to n-1, find wi = r i •w0 mod d with gcd([wi] d , s) = 1. If gcd([wi] d , s) = 1,

  1 , a 2 , . . . , a n ) ∈ R n , let ||a|| denote the Euclidean norm

	defined by defined by	√ ∑ n i=1 a 2 i . Furthermore, we let ||a|| 1 and ||a|| ∞ denote the 1-norm ∑ n i=1 |a

i | and ∞-norm defined by max i |a i |, respectively.

  is good, we have d ≡ 1 mod 2n.

Proof. Assume that v(x) is good, namely, the public key matrix B has the form (3). Then we see that f n (x) mod d is split completely. This shows that f n (x) mod p is split completely for the primes p | d. By the theory of cyclotomic fields, we have that p ≡ 1 mod 2n for the primes p | d, which shows that d ≡ 1 mod 2n. ⊓ ⊔ To check that v(x) is not good, we test the condition d ≡ 1 mod 2n. In testing d ≡ 1 mod 2n, we only need to compute d mod 2n. By using V j (x) mod 2n ∈ (Z/2nZ)[x] to compute d mod 2n, we can check it in lower cost (after obtaining the triple (d, w 0 , w 1 ), we can check the goodness of v(x) exactly by testing the condition that

Table 1 .

 1 Performance and ciphertext size of our variant scheme According to[START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] Table 4], the cost of e for BKZ 2.0 with β = 280 is estimated at 2 79.8 nodes at lowest. From a similar argument as above, we estimate e ≥ 200 × 2 79.8 ≈ 2 87.4 clock cycles. Therefore we estimate that the running time of BKZ 2.0 with β = 280 is at least 2 12 × 2 87.4 ≈ 2 99.4 clock cycles in dimension 4096. Hence we conclude that this case is estimated at 80-bit security with an enough margin (we can estimate from[START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] Table

	Parameters	Key gen. Precomp. Packed	Secure	Dec.	Cipher. BDDP
	(n, t, s)	(Alg. 1) Table	Enc. Hamming		size	instance
	(2048, 37, 2048) 220 ms 5.20 sec 6.20 ms 4.98 ms 2.51 ms 9.5 KB 1.0071 n
	(4096, 37, 2048) 870 ms 38.15 sec 19.89 ms 18.10 ms 9.08 ms 19 KB 1.0034 n
	of e.

Table 2 .

 2 Comparison to protocols using homomorphic encryption

	Protocols	Performance of	Size increase rate by	Homomorphic
	(feature vector size) Secure Hamming encryption * (cipher. size) encryption scheme
	SCiFI

  , 2245-2255, 2001. 27. B. Schoenmakers and P. Tuyls, "Efficient binary conversion for paillier encrypted values", In Advances in Cryptology-EUROCRYPT 2006, Springer LNCS 4004, 522-537, 2006. 28. N. P. Smart and F. Vercauteren, "Fully homomorphic SIMD operations", To appear Designs, Codes and Cryptography. 29. U.S. Department of Homeland Security, "Privacy impact assessment for the biometric storage system", available at http://www.dhs.gov/xlibrary/assets/ privacy/privacy_pia_cis_bss.pdf (March 28, 2007).


Vaise Patu

Shuichiro Yamamoto
email: yamamotosui@icts.nagoya-u.ac.jp

A new approach to develop a dependable security case by combining real life security experiences (lessons learned) with D-Case development process

Modern information and distributed systems runs for extensive periods of time and are being constantly improved in service objectives under evolving technologies and changing regulations and standards. These systems have become extremely complex and therefore, it is very important that they are to be dependable in order for them to execute their functionalities and purposes correctly or to an acceptable level of services. However, due to the ever-growing complexity of information and distributed systems, it is very difficult to achieve dependability by relying only on conventional technologies such as development processes and formal methods. And therefore the idea of Assurance Case or D-Case (dependability case) has become more and more a popular notion. Recently, D-Case which is an extension form of Assurance Case, is more commonly associated with the safely aspect of dependability. And because of this regard, safety cases are more well known in comparison to other aspects of dependability such as availability, integrity and confidentiality witch are all related to the security domain. In this paper, we introduce our new approach to the development of a dependable security case.

Introduction

It is very difficult to define what exactly a secure system means, because the concerns in the security domain are too diverse. For example, some secure systems are more concerned with unauthorized access to information, while some are more concerned with denial-of-service attacks and so on. In this paper, we discussed how we developed a dependable security case for our e-learning distributed system by utilizing the knowledge we gained from previous occurred attacks as a mechanism to build solutions that counters any more future attacks of the same kind. As we all know, it is common for network systems to contain security vulnerabilities that allow unauthorized personnel to compromise the systems, steal intellectual property, or disclosure sensitive data. To combat these vulnerabilities, a proactive approach to building secure network systems and strong evident based security case is necessary. There are many well-written documents on how to write safety cases and reliability cases but very few on security cases. The reason for this is not the concern of this paper but to propose our method on how we developed our security case by complying with previous systems risks and attacks and the lessons we learned from it.

Our new approach to the development of a dependable security case

How we decide on the aspect of the system to be assured using an assurance case, is directly derives from the system under review risk analysis results and its set of requirements. However in our approach, we also added in our experience (lessons learned) gained from the attacks our system faced in the past as shown in figure 1. Since we are building a security case, it was close to impossible for us to predict the vulnerabilities and the security risks that reside in our system architecture when our distributed e-learning system starts its operation. But as we continued our operation for almost 6 years now, we gradually improved our system performance and security by building counter measures to any severe exploitation we faced in the past. As an example in Table 1, we have listed down some of the most common security vulnerabilities that are most popularly delt with in the domain of security especially when dealing with information and network systems. From the this known list of security vulnerabilities / claims, we build from it a correponding list of solutions or evidence that comes in handy when we go through the process of creating of our security case.

Fig.1.

To achieve the goal of system dependability, we proposed the addition of a 3 rd requirement, which are the reports of previous encountered system risks and attacks The solution column is a result of our discussion, on how we should change our system configurations in order to minimize the effects of these attacks if we encountered if we encounter them in the future. We developed our 4-step process to register new attacks once we discover them.

A) Identifying the type of attack B) Describe the nature of the attack C) Build a counter strategy for the attack via discussions D) Store the completed report to our system repository for future reference

Building of the Security D-Case

Our new approach of creating a dependable security case was first introduced and tested as experiment to provide assurance to the security aspect of our distributed e-learning system. However, more experiment and tests (trail and error) is still needed in order to take much of the work into the next stage. The good news is, security is no stranger to network and information systems. These systems have been associated with security for as long as networking and information systems existed. What is really new here is the urge to associate network systems with assurance case to give some kind of confidence to the system stakeholders that the system they are getting will behave as predicted and function well at a certain level when it faced by security risks and attacks in the future.

Phase 1 of the development process -Set a Top Goal

Depending on the aspect of dependability we are writing the assurance case for, we could easily identify the most upper goal or the top goal for your D-Case diagram. In our example, since we are building a security case, therefore our top goal also known as the main claim should be: "System is reasonably secure".

In support of the top goal or top claim, we need some input documents into the context nodes. These documents provide the environment information about the system. This includes any sort of attachment that helps to make the main argument truthful or convincing. For example, documents like the system requirements, which tells of what kind of security requirements that the system has in order to secure the system from unwanted attacks, or any kinds of security design architecture diagram if any, and so forth.

Phase 2 of the development process -Set an argument strategy to decompose the main goal to sub-goals

After the top goal is set with all the necessary contexts. What follows is the decomposition step or stage of the main argument or the 'main goal' into two or more sub-goals. However, prior to the decomposition stage, where the 'sub-goal nodes' comes into the picture, the node called 'strategy' is inserted between the main goal and the sub-goals. The strategy node should explain or give a sense of justification or reasoning to why the security case builders decided to decompose the main goal into such and such number of sub-goals. In figure 3, the strategy links us to some of the identified security vulnerabilities displayed in table 1. In this example, we took 6 identified security vulnerabilities as sub-goals. And the strategy is to argue over each of the 6 identified security vulnerabilities. No matter what the assurance case is, whether it is a safety case, reliability case or a security case, they all follow a kind of pattern. For example, security case patterns are claims-argument-evidence structures that can be reused in many different security cases. The security case method offers the opportunity for security and domain experts to organize security knowledge and mitigation strategies in the form of security case patterns. Such patterns can then be shared among the security community and other stakeholder communities and continually built upon, refined, and improved. A growing repository of security case patterns is a huge possibility for a variety of domains and operational contexts that not only would provide greater opportunities for reuse and standardization of assurance arguments, but also could allow the security community to associate an historical record of security performance and return on investment with particular security case patterns. In the last measure to our security case, we would see that some of the sub-goals got themselves a straight forward evident or solution that satisfy the final objective in supporting of the main goal, while in some sub-goals, they have to be expanded more widely in order to get to the heart of where the evident truly exist. Figure 4 shows how sub-goals one, two and three are decomposed until the evident that satisfy all the objectives of the security case main goal. And finally as shown in Figure 5, we decomposed sub-goal 4 into four more sub-goals of sub-goal 4.1, sub-goal 4.2, sub-goal 4.3 and sub-goal 4.4. Note that for sub-goal 4.1, we added one property of GSN called undeveloped which is truly meant that this sub-goal 4.1 is not yet completed within the security case. Many factors could contribute to be the reason why a sub-goal is labeled undeveloped. For example, one of the factors could be that the evident or evidence provided to satisfy the objective of sub-goal 4.1 is not well defined by both the networking engineers and the security case builders.

Evaluations and Conclusion

The nature of network system attacks are consequently unpredictable. Therefore relying solely on risk assessment and analysis results may not be sufficient enough to argue the security case of your system to its stakeholders. We definitely need to collect previous attacks reports (lessons learned) from systems with similar functions and design with your system. Because of this, the "Time factor" that took for developing our security case reduces significantly. Another benefit is Cost. Developing Assurance Cases at the moment can cost a lot according to a report from Carnegie Mellon University. Then Simplicity. Building a dependability case can be a major challenge to those who just entered the field of Assurance Cases. However, our approach has proven to be very straightforward and therefore easy to absorb by the newbies. We proposed the combination of security engineering knowledge and experiences with D-Case to develop strong and valid assessment security cases. This is done by integrating past experience of security breach and system development, in fact turning the security assurance cases into a system development tool. In this methodology, requirements and system goals become high-level goals in the security case tree, which is subsequently extended in a way that reflects each stage of development, later stages corresponding to lower level claims in the security case tree. Strategies for deriving sub-goals from parent goals can be based on the strategies for deriving more concrete views and models of the system under development, and should include an extensive vulnerability and risk analysis of the system view at hand. The sub-goals produced in this way at one stage of development should be regarded as requirements for the subsequent stages. For reuse, patterns of decomposition of goals/claims into sub-goals for different types of systems and security requirements might turn out to be a useful by-product. We conducted an experiment to prove our evaluation. 4 graduate students and 3 undergraduate students of Nagoya University carried out the experiment, plus 3 network engineers whom are looking after the KISSEL system. At the end of our experiment, we find out that more than 95% of the participants agreed that our new method was very straight forward and very easy to follow in creating their own security case diagram. 90% agreed that depending on the length of the teams' discussions, the new method takes very few hours to complete once the solutions are final from the discussions. Then about the cost of the work, 99% of the participant felt that the cost of the new method if applied to all the factors shown in the experiment, should be much less than predicted before the experiment was carried out. It's very difficult to collect previous attack reports from other similar systems. We find this quite a challenging task. On one occasion, we got a reply back from one of the system administrator we collaborated with saying that his University refuse to assist us with our request to use their network reports due to confidentiality reasons. However, some big companies like IBM for one are quite open about these kinds of reports. They even share them for free online via white papers. Also, we found out that our security cases diagram contains very sensitive information about our system. Therefore another new issue that arose after completing our work was to decide whether to save the assurance case diagrams via our system database or to store them as paper file documents.

In this paper we proposed a new approach for developing security cases. The ideas mentioned were (1) how we derived our security case diagram from complying with previous attacks reports and risk (lessons learned). (2) We shared our experiment of using our approach by applying it to our server distributed e-learning system called KISSEL. (3) Our new approach gives us the benefits in Time Efficiency, Low Cost and Simplicity. We have shown an experiment of using our method by non-experts on a web-server demo system. Currently we have preparing the feasibility experiments of our method on a few cases targeting university students and engineers. In the experiments we plan to do comparison evaluation with/without our method. Furthermore, applying our method to cyber-security issue is one of our important next goals. We would like to present the results in near future.

Figure 2

 2 is to provide a visualized view of what this paragraph is trying explain. Figure1shows only the top most part of our security case diagram.

Fig. 2 .

 2 Fig.2. The top part of the security case tree diagram

Fig. 3 .

 3 Fig.3. This figure shows the decomposition process from the top goal into sub-goals with the strategy node in between

Fig. 4 .

 4 Fig.4. This part of the Security Case shows how sub-goals 1,2 and 3 are being decomposed right down to the evident nodes

1 3 2 Fig. 5 .

 25 Fig.5. This figure shows how sub-goal 4 is decomposed into 4 more sub-goals of 4.1, 4.2, 4.3 and 4.4

Table 1 .

 1 Our completed table of the known list of the most common security vulnerabilities traced back to the risk initiated network component and the solutions we have to limit the risk causal

factors Network Component at Risk Proposed Solution / Evidence

	Boarder Router		All Router ACLs configurations should be
			checked and monitored constantly for
			accuracy
	Remote Access Server		(i) Limit the number of Remote Access
			Servers within the system. (ii) All Remote
			Access Servers should be under monitoring
			continuously
	Firewall		(i) Firewall ACLs configurations should be
			checked and monitored constantly for
			accuracy. (ii) Backup the completed
			configurations into a secure separate
			location.
	Internet / DMZ Server
			<Undeveloped>
			Limit the using of services such as RPD,
			FTP, DNS and SMTP
			(i) All CGI and ASP scripts should be
			double checked by a second party for
			accuracy before the system is deployed (ii)
			Forbid the use of FTP with anonymous
			accounts and passwords on the system
		Inadequate logging, monitoring and detection	Boost continuous monitoring of the full
		capabilities at the network and host level	system log-files in a daily or weekly bases
			to up the security threats early detection
			capability of the system
	Branch Office	Excessive trust relationships such as Windows
		Domain Trusts, UNIX rhosts, and SSH files can provide attackers with unauthorized access to	<Undeveloped>
		sensitive systems
	Workstation	Weak, easy to guess passwords at the
		workstation level can compromise your	<Undeveloped>
		company's server
		Unauthenticated services like X Windows allow
		users to capture remote keystrokes or
		workstation keystrokes after software is	<Undeveloped>
		installed
	Internal LAN Server	Excessive file and directory access controls
			<Undeveloped>

<Undeveloped>

Security Vulnerabilities (-Claims)

Misconfigured Internet servers, especially CGI and ASP scripts on web servers, anonymous FTP with world-writable directories and XSS vulnerabilities Hosts running unnecessary services such as RPC, FTP, DNS, SMTP are easily compromised.

Misconfigured firewall ACLs can allow access to internal systems directly or once a DMZ server is compromised.

Information leakage can provide the attacker with operating system and application versions, users, groups, shares, DNS information via zone transfers and running services like SNMP, finger, SMTP, telnet, rusers, rpcinfo, NetBIOS. (Windows shares and UNIX NFS exports) Software that is unpatched, outdated or left in default configurations, especially web servers are vulnerable to attacks Inadequate router access control: Misconfigured router ACLs can allow information leakage through ICMP, IP, NetBIOS and lead to unauthorized access to services on your DMZ servers.

Unmonitored remote access points provide one of the easiest means of access to your corporate network. Telecommuters often connect to the Internet with little protection, exposing sensitive files to attack.


Lidia Ogiela
email: logiela@agh.edu.pl

Marek R Ogiela
email: mogiela@agh.edu.pl

Intelligent UBMSS Systems for Strategic Information Management

Keywords: Strategic information management, security of information systems, cognitive systems in homeland security

In this publication will be described the most important features of UBMSS cognitive information systems, as well as security issues connected with these new generation information systems. Such systems are mainly designed to perform an intelligent information management based on semantic analysis of data merit content. In paper will be also presented some possibilities to develop such systems for strategic information management in state or government institution. The paper will describe both UMBSS internal safety features, and external possible application of authentication procedures along with intelligent information management.

Introduction

Intelligent UBMSS (Understanding Based Management Support Systems) systems are one of the modern classes of cognitive information systems. Cognitive analysis processes are characteristic of the intellectual processes running in the human brain, particularly those of analyzing, interpreting, reasoning, and forecasting about specific situations, meanings and the significance of information.

Cognitive reasoning consists in analyzing and understanding the contents and the semantics of the data examined. Such examination may be very important during strategic information management in different companies or institution.

In such systems the semantic analysis is based on a lexical analysis in which the structure of a given word is used to describe it, and to find the meaning of the content of the word. The basis for this analysis is a specific language to which the above element belongs, and the process of understanding results from comparing the previously recorded expectations concerning specific features of data with the features from the input information. The set of expectations concerning the anticipated features of the analyzed elements is produced by analyzing the knowledge of experts whose expectations of the meanings of particular situations are presented in the system database. This set of semantic hypotheses is compared with the stream of input data, and this leads to cognitive resonance [START_REF]Handbook of Categorization in Cognitive Science[END_REF][START_REF] Meystel | Intelligent Systems -Architecture, Design, and Control[END_REF][START_REF] Ogiela | Syntactic Approach to Cognitive Interpretation of Medical Patterns, 1st International Conference Intelligent Robotics and Applications[END_REF][START_REF] Ogiela | Cognitive systems for medical pattern understanding and diagnosis, 12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems[END_REF]. This process produces a list of selected inter-pretations which were found to correspond to the analyzed input data -this leads to the stage of understanding the analyzed data.

Presented cognitive resonance functions may be used to guarantee the security and safety features during management of strategic or secret information, both in layered and hierarchical management structures.

An Idea of UBMSS Cognitive Systems

The general goal of UBMSS is to support enterprise management and handling in secure manner of strategic information, as well as its distribution for authorized persons or participants of communication protocols. Such systems may also be used for another procedures mostly connected with economical task like focus on the correct choice of the right economic ratios and theirs prediction for near future. These ratios precisely reflect the business activity of a given enterprise, its standing, its financial result, and are also an expression of the record and the generalization of specific economic events.

During our research we could also analyze some security features of such systems and theirs possibility of theirs application for strategic information management in the form of secret information sharing for layered and hierarchical structures.

UBMSS Systems for Strategic Information Management

Using UBMSS systems, an information is divided within institutions or organizations regardless of its type or the purpose for which the organization collects it. The significance of information splitting may depend on the method of its splitting, the purpose of splitting it, and the type of information. The significance of information sharing, on the other hand, may depend on its importance and the meaning it contains for the specific organization. If information is important and of great materiality for the organization or for e.g. external organizations, then it makes sense to attempt sharing this information to protect it and secure it from disclosure to unauthorized persons (or organizations). When defining the type of information to undergo the splitting or sharing process, we should consider its 'character' determined by its confidentiality, significance and importance, because only important information justifies applying the method of its division and the effort to do so. Multi-level information division algorithms are named after the type of division applied. This division can be hierarchical or by layers. The principal difference between the presented types of divisions concerns the method of introducing the division itself. When a division is made within homogenous, uniform groups of layers, then it is a layer division, whereas if the division is made regardless of the homogeneity of the group or layer but by reference to several groups ordered hierarchically, it is a hierarchical division [START_REF] Ogiela | The use of mathematical linguistic methods in creating secret sharing threshold algorithms[END_REF].

A layer division is thus a division made relative to a given layer, while a hierarchical division accounts for the hierarchy (dependency) of the structure or more structures relative to one another.

Information can be divided both within the entire structure in which some hierarchical dependency is identified, within a given group, or within any homogenous layer. This is why, depending on the type of information divided, it makes sense to identify correctly selected information dividing algorithms.

The division of information between the members of a given group in which everyone has the same privileges is a layer division.

A hierarchical division is characterized by the ability to make any division of secret information in the way determined by the access rights at individual levels of a hierarchical structure.

Types of UBMSS Systems

There are various methods of information protecting from being accessed by persons not authorized to learn it. Based on such different approaches we can define two types of UBMSS systems. The first class may contain the procedures in which the secret information will be secured using some individual personal biometrics, and the second one based on mathematical linguistic formalisms [START_REF] Ogiela | Cognitive Techniques in Visual Data Interpretation[END_REF].

The first class of UBMSS systems are connected with biometric threshold schemes [START_REF] Ogiela | DNA-like linguistic secret sharing for strategic information systems[END_REF][START_REF] Ogiela | Linguistic Protocols for Secure Information Management and Sharing[END_REF], which particularly use some most important physical and biometric features like the iris, the shape of fingerprints, hand bones or veins [START_REF] Ogiela | Advances in Cognitive Information Systems[END_REF], anatomical features [START_REF] Bodzioch | New approach to gallbladder ultrasonic images analysis and lesions recognition[END_REF], face, the structure of blood vessels [START_REF] Ogiela | UBIAS Systems for Cognitive Interpretation and Analysis of Medical Images[END_REF] and also the DNA code [START_REF] Ogiela | DNA-like linguistic secret sharing for strategic information systems[END_REF].

The second class of UBMSS systems uses linguistic coding processes, which are based on the use of mathematical linguistic formalisms, particularly grammatical formalisms to record and interpret the meaning of the secured data. Linguistic coding processes are used because of the ability to execute generalised information coding similar to DNA cryptography [START_REF] Ogiela | DNA-like linguistic secret sharing for strategic information systems[END_REF], but in UBMSS systems it is also possible to code longer bit sequences containing more than 2 bits of information. This coding is done using terminal symbols introduced in special grammar.

Example of Application UBMSS System for Strategic Information Management

This section presents an example of information splitting using UBMSS system and the distribution of secret parts with the use of the linguistic or biometric threshold schemes. This example represents a simplified model aimed at demonstrating the opportunities offered by UBMSS systems to create and distribute secret information between persons at various management levels or employees at various organisational levels. The UBMSS schemes for information distribution enable generating and distributing parts of the shared information both in layered and hierarchical structures. For this reason, the discussion of the example shown in Fig. 1 will apply to executing precisely these sharing types. The first case presented in the example diagram in Fig. 1 concerns the method of sharing and distributing a secret for individual layers in a management pyramid.

These layers may be treated as completely independent, and then the highest authorities will share the secret in various layers independently, but the sharing will be done in various ways using linguistic threshold schemes based on various grammars, i.e. coding the shared input data with bit blocks of different lengths. In Fig. 1 this is marked with vertical red arrows of various lengths. In such layered sharing, employees at a given level are equal and have the same rights to access the secret data, but individual layers stay completely independent, so staff from a given management level cannot cooperate with individuals from other management layers when restoring the secret.

However, as the highest authorities of the enterprise or the arbitrator performing the sharing may also provide lower levels with information about the grammar used (or biometric information) for this sharing, an additional opportunity arises for information to flow between individual management layers, causing a transition from a layered structure to a hierarchical one.

Fig. 1 also demonstrates that hierarchical sharing can be executed in such a way that the secret shares obtained at various levels of the management hierarchy can be shared again using a selected threshold scheme and information about the chosen formal grammar (blue arrows of equal lengths joining individual layers of the man-agement pyramid). In this protocol, every share of the secret generated for a selected employee may be shared at the lower level between a greater number of staff of that lower level.

When we analyse the information sharing procedure in hierarchical structures, the Boss holds important information which can be shared between his/her subordinates observing layer relationships, i.e. employees of a given level are equal and have equal rights to access the secret data under consideration. However, individual layers are not completely separated from one another in information terms and in this regard to not retain their independence, as secret shares at a given management layer can, at subsequent steps, be shared between selected employees of a lower level. This procedure can be repeated for further, still lower layers.

Within such a structure, the original information can be reconstructed in any layer by combining the required number of shadows or using shares coming from different layers. In the second case, a greater number of shares from lower levels is required to reconstruct selected shares from higher layers.

Security Features of UBMSS Systems

As was noted before the UBMSS systems could guarantee the security of strategic information and also some safety features during performing secret distribution. The most important features of such systems are following:

• UBMSS systems are suitable for dividing important strategic data and assigning its shares to members of the authorized group; • UBMSS systems can handle any digital data (text or image) which needs to be intelligently divided among authorized persons and then possible to secretly reconstruct; • UBMSS systems may be used in different economical management structures e.g. hierarchical, divisional, functional etc.

Conclusions

In this paper were presented the cognitive UBMSS systems designed for the secure information management in various management structures. Such systems have the ability to perform a semantic analysis of information which allow to classify it for different semantic categories. Such semantic analysis may further supporting decision-making processes in particular institution or company. Such systems allow also to perform an intelligent information management especially for important, and strategic data. In this paper there were described such possibilities, and also defined two different classes of secure information sharing, especially based on linguistic approach as well as based on some personal biometric features [START_REF] Peters | Representing Humans in System Security Models: An Actor-Network Approach[END_REF]. It seems that in near future such systems will play an increasing role in developing new solutions in areas of very special and strategic information management, especially for government use or homeland security areas.

Fig. 1

 1 Fig. 1 An example of splitting a secret in the layered and hierarchical way

Acknowledgments. This work has been supported by the National Science Centre, Republic of Poland, under project number 2012/05/B/HS4/03625.