## Linear Mix-net and a Scheme for Collecting Data from Anonymous Data Holders

**Shinsuke Tamura**^{1,}, **Shuji Taniguchi**^{1}

^{1}School of Engineering, University of Fukui, Fukui, Japan

### Abstract

To make e-society, e-governance and cloud computing systems be utilized more widely, this paper proposes a scheme to collect attribute values belong to same data holders and calculate functions of them without knowing correspondences between the attribute values and their holders or links among attribute values of same holders. Different from most of other schemes the proposed scheme is based on linear Mix-net that exploits secret key encryption functions such as linear equation based (LE-based) and multidimensional array based (MA-based) ones, therefore it can handle real numbers that appear in many important business and engineering applications efficiently in the same way as integers. In addition, anonymous tag based credentials used in the scheme ensure the correctness of calculation results. Although the scheme can calculate only linear combinations of attribute values when LE-based encryption functions are used, if they are replaced with MA-based ones, it can calculate also general polynomial functions of attribute values.

### At a glance: Figures

**Keywords:** E-society, E-governance, cloud computing, privacy, homomorphic encryption functions, anonymous tag based credentials

*Information Security and Computer Fraud*, 2014 2 (3),
pp 39-47.

DOI: 10.12691/iscf-2-3-2

Received October 13, 2014; Revised November 01, 2014; Accepted November 04, 2014

**Copyright**© 2013 Science and Education Publishing. All Rights Reserved.

### Cite this article:

- Tamura, Shinsuke, and Shuji Taniguchi. "Linear Mix-net and a Scheme for Collecting Data from Anonymous Data Holders."
*Information Security and Computer Fraud*2.3 (2014): 39-47.

- Tamura, S. , & Taniguchi, S. (2014). Linear Mix-net and a Scheme for Collecting Data from Anonymous Data Holders.
*Information Security and Computer Fraud*,*2*(3), 39-47.

- Tamura, Shinsuke, and Shuji Taniguchi. "Linear Mix-net and a Scheme for Collecting Data from Anonymous Data Holders."
*Information Security and Computer Fraud*2, no. 3 (2014): 39-47.

Import into BibTeX | Import into EndNote | Import into RefMan | Import into RefWorks |

### 1. Introduction

Data collection systems are ones that collect attribute values belong to same data holders and calculate functions of them, and by using these systems, government agencies can quickly and correctly calculate taxes of citizens for example. However, many people do not want such systems because their all information are linked and may be used for other purposes. Same difficulties exist in many applications in e-society and e-governance systems. To make e-society, e-governance and cloud computing systems be utilized more widely, this paper proposes a scheme that enables entities (e.g. servers in cloud computing systems) to collect attribute values belong to same data holders and calculate functions of them without knowing links between attribute values and their holders or among attribute values of same holders.

The above scheme can be developed by using Mix-nets ^{[2, 4, 5]} as shown in Figure 1 that consist of data holders, authority *A*, and mix-servers M_{1}, M_{2}, ---, M_{N} in the encryption and the decryption stages. Here, each data holder P owns its attribute values X_{P}(1), X_{P}(2), ---, X_{P}(Q), and although each X_{P}(q) is disclosed by some reasons (e.g. if X_{P}(q) is the amount of P’s deposit in a bank P must disclose it to the bank) P wants to conceal the fact that X_{P}(q) belongs to it from others including *A* and mix-servers (actually, P must conceal also links among X_{P}(1), ---, X_{P}(Q) because they are good clues to identify P). On the other hand, *A* needs to calculate functions of attribute values of same data holders and let data holders take actions according to the calculation results (e.g. pay taxes).

**Fig**

**ure**

**1.**Configuration of a data collection system

To satisfy these requirements, mix-servers M_{1}, ---, M_{N} in the encryption and the decryption stages repeatedly encrypt individual attribute values and decrypt encrypted function values respectively while disclosing their encryption and decryption results publicly so that they can convince others of their correct encryptions and decryptions. An important things here are firstly encryption functions are probabilistic (this means they generate different encryption forms even for same plain texts) and secondly each M_{h} shuffles its encryption or decryption results before it discloses them. Therefore no one can know the correspondence between attribute values received by M_{1} in the encryption stage and final decryption results calculated by M_{1} in the decryption stage unless all mix-servers conspire.

In detail, each data holder P informs 1st mix-server M_{1} in the encryption stage of its q-th attribute value X_{P}(q) without disclosing its identity, and provided that k_{h} is an encryption key of M_{h}’s encryption function E(k_{h}, *x*) for each h, M_{1}, ---, M_{N} repeatedly encrypt each X_{P}(q) to E(k_{N*}, X_{P}(q)) = E(k_{N}, E(k_{N-1}, --- E(k_{1}, X_{P}(q)) --- )) while shuffling their encryption results. After that, authority *A* collects E(k_{N*}, X_{P}(1)), E(k_{N*}, X_{P}(2)), ---, E(k_{N*}, X_{P}(Q)) that correspond to anonymous data holder P, and calculates E(k_{N*}, *f*(X_{P}(1), ---, X_{P}(Q))), an encryption form of function value *f*(X_{P}(1), ---, X_{P}(Q)). Then, M_{N}, M_{N-1}, ---, M_{1} in the decryption stage repeatedly decrypt each E(k_{N*}, *f*(X_{P}(1), ---, X_{P}(Q))) to *f*(X_{P}(1), ---, X_{P}(Q)) so that P that owns X_{P}(1), ---, X_{P}(Q) can know value* **f*(X_{P}(1), ---, X_{P}(Q)), and finally *A* asks individual anonymous data holders to take actions according to their function values.

But to implement this scheme the following difficulties must be removed. The 1st difficulty is about the anonymity of data holders, i.e. each data holder P must convince 1st mix-server M_{1} of its eligibility without disclosing its identity. About the 2nd and the 3rd difficulties, authority *A* must collect P’s encrypted attribute values E(k_{N*}, X_{P}(1)), ---, E(k_{N*}, X_{P}(Q)) from all encryption results in the encryption stage, on the other hand, P must identify its function value *f*(X_{P}(1), ---, X_{P}(Q)) from all decryption results in the decryption stage. The 4th and the 5th difficulties relate to mechanisms to calculate encryption form E(k_{N*}, *f*(X_{P}(1), ---, X_{P}(Q))) and to ensure mix-servers’ correct handlings of attribute values. Namely, each encryption function E(k_{h}, *x*) must have specific features to enable *A* to calculate E(k_{N*}, *f*(X_{P}(1), ---, X_{P}(Q))) from E(k_{N*} X_{P}(1)), ---, E(k_{N*}, X_{P}(Q)). Also, even if some entities behave dishonestly, *A* and data holders must detect incorrect calculation results and identify entities liable for them to re-calculate correct values.

Among these difficulties, the 1st difficulty can be removed by anonymous authentication schemes ^{[6, 7, 12]}, in addition some of them can handle also the 2nd, the 3rd and the 5th difficulties. But currently available schemes are not practical for handling the 4th difficulty. Namely, although simple ElGamal re-encryption schemes ^{[4]} enable authority *A* to calculate encrypted weighted sum of attribute values E(k_{N*}, *a*_{1}X_{P}(1)+ --- +*a*_{Q}X_{P}(Q)) as E(k_{N*}, *a*_{1}X_{P}(1))+ --- +E(k_{N*}, *a*_{Q}X_{P}(Q)) and recent fully homomorphic encryption functions ^{[8, 9]} may enable *A* to calculate arbitrary function E(k_{N*}, *f*(X_{P}(1), ---, X_{P}(Q))) as *f*(E(k_{N*}, X_{P}(1)), ---, E(k_{N*}, X_{P}(Q))), they are designed for handling integer values. Therefore they are not practical to handle real number attribute values that appear in many important business and engineering applications.

The scheme proposed in this paper exploits linear equation based (LE-based) encryption functions ^{[10]} to enable authority *A* to efficiently calculate weighted sums of real number attribute values. *A* can calculate also their general polynomial functions, when LE-based encryption functions are replaced with multidimensional array based (MA-based) ones ^{[10]} which are both additive and multiplicative.

### 2. LE-based Encryption Functions

A linear equation based (LE-based) encryption function considers information as integers or real numbers, and encrypts an (H+G)-dimensional vector of integers or real numbers *X* = {*x*_{1}, *x*_{2}, ---, *x*_{H}, r_{1}, r_{2}, ---, r_{G} } to (H+G)-dimensional vector *X*_{*} = {*x*_{*1}, *x*_{*2}, ---, *x*_{*H+G}} by using secret (H+G)x(H+G)-dimensional coefficient matrix Q = {q_{ij}}, i.e.* **x*_{*i} = q_{i1}*x*_{1}+q_{i}_{2}*x*_{2}+ --- +q_{i}_{H}*x*_{H}+q_{i}_{(H+1}_{)}r_{1}+ --- +q_{i}_{(H+G}_{)}r_{G} for each i ^{[10]}. Where, each *x*_{j }constitutes a real term that corresponds to information to be encrypted, on the other hand, each r_{h}_{ }is a random number secret of the information holder and constitutes a dummy term.

Then, for an entity that does not know matrix Q it is difficult to calculate *X* from *X*_{*}; but when Q is known, anyone can calculate *X* from *X*_{*} by solving the linear equations provided that Q has its inverse. Therefore, coefficient matrices Q and Q^{-1} work as an encryption and a decryption keys. Here, it is apparent that encryption function E(Q, *X*) is additive, i.e. provided that *s* and *t* are real numbers and *sX* represents the product of scalar number *s* and vector *X*, when *X* and *Y* are encrypted to, E(Q, *X*) and E(Q, *Y*), *s*E(Q, *X*)+*t*E(Q, *Y*) is decrypted to *sX*+*tY*. Also, because each *x*_{j}, r_{h} and elements of matrix Q are not limited to integers, LE-based encryption functions can handle real numbers in totally the same way as integers.

However the above additive feature introduces a serious drawback, i.e. LE-based encryption functions are weak against plain text attacks. When mutually independent (H+G)-dimensional vectors *A*_{1*}, *A*_{2*}, ---, *A*_{(H+G)*} are known as encryption forms of known vectors *A*_{1}, *A*_{2}, ---, *A*_{H+G}, because arbitrarily given (H+G)-dimensional vector *X*_{*} is represented as *X*_{*} = g_{1}*A*_{1*}+ ---- +g_{H+G}*A*_{(H+G)*}, *X*_{*} can be easily decrypted to *X* = g_{1}*A*_{1}+ ---- +g_{H+G}*A*_{H+G} without knowing coefficient matrix Q. Therefore, LE-based encryption functions must be used in applications where data are encrypted and decrypted by same entities, i.e. in these applications entities that encrypt information do not need to disclose at least dummy term values to others in their plain forms and plain text attacks become difficult (it must be noted that by various reasons real part values must be disclosed in their plain forms in many applications). Because entities that encrypt and decrypt data are same, a fact that lengths of encryption keys are prone to being long is not a disadvantage either.

LE-based encryption functions can be intensified further by inserting secret dummy elements at random positions in encrypted vectors, i.e. elements of encryption form {*x*_{*1}, *x*_{*2}---, *x*_{*H+G}} and secret dummy vector {*w*_{*1}, *w*_{*2}, ---, *w*_{*L}} are merged while being shuffled to constitute (H+G+L)-dimensional encryption form {*X*_{*}’} = {*w*_{*1}, *w*_{*2}, *x*_{*3} *w*_{*3}, *x*_{*1}---, *w*_{*4}} for example. As a consequence, positions where *x*_{*1}, *x*_{*2}---, *x*_{*G+H} are located in {*X*_{*}’} must be determined in order to decrypt {*X*_{*}’}. When L-dummy elements {*w*_{*1}, *w*_{*2}---, *w*_{*L}} are added to (H+G)-dimensional vector {*x*_{*1}, *x*_{*2}---, *x*_{*H+G}}, _{H+G+L}P_{H+G} number of possibilities must be examined to remove the dummy elements, and when (H+G) and L are set to 50, _{H+G+L}P_{H}_{+G} is _{100}P_{50} > 2^{500}.

On the other hand, solving linear equations is not difficult when the coefficient matrix is given. For example, LU-decomposition ^{[3]} solves linear equations with sufficient performance in terms of both computation speed and accuracy. Computation speed is fast enough compared with that of modern asymmetric key encryption functions such as RSA even the dimensions of coefficient matrices are more than 100, also computation errors are small enough.

However, it is still easy to generate consistent encryption forms even without knowing encryption keys. By linearly combining known encryption forms, anyone can generate consistent encryption forms of variety of data without knowing the key as same as man in the middle attacks in environments where public key encryption functions are used. But many mechanisms are available to remove these threats, e.g. implicit transaction links (ITLs) ^{[10]} enable entities to detect forged encryption forms without examining individual forms.

About the verifiability, although LE-based encryption functions are secret key based, correctness of E(Q, *x*) can be verified by using the additive property as follow. Conceptually, entity V that verifies E(Q, *x*^{*}), encryption form of *x*, generates arbitrary vectors {E(Q,* T*_{1}), ---, E(Q,* T*_{m})} as a set of encryption forms of test values, and asks P, which had calculated E(Q, *x*^{*}), to decrypt them to {*T*_{1}, ---, *T*_{m}}. After that, V calculates = w_{0}E(Q,* x*^{*})+w_{1}E(Q,* T*_{1})+ --- +w_{m}E(Q,* T*_{m}) while generating random numbers w_{0}, w_{1}, ----, w_{m} secret from P, and asks P to decrypt . Then, because E(Q, *x*) is additive must be decrypted to *X* = w_{0}*x*+w_{1}*T*_{1}+ ---- +w_{m}*T*_{m} if E(Q,* x*^{*}) and E(k,* T*_{1}), ---, E(k,* T*_{m}) are correct. But if they are incorrect, P that does not know w_{0}, w_{1}, ---, w_{m} cannot calculate *X* from .

Here, actually , E(Q, *x*^{*}), E(Q,* T*_{1}), ---, E(Q,* T*_{m}) in the above are vectors, therefore P obtains multiple relations about (m+1)-variables w_{0}, w_{1}, ---- w_{m}, which may enable P to calculate w_{0}, w_{2}, ---- w_{m} when m is small. But a slight extension disables P to calculate w_{0}, w_{1}, ---- w_{m} even when m is small. This means P does not need to disclose numbers of plain and encryption forms pairs of test values. P does not need to disclose dummy terms of vector *X* and each test vector *T*_{j} either; in other words, verification of dummy terms has no meaning for V because they can have any values without making real terms inconsistent. Then, encryption function E(Q,* x*) can be protected from plain text attacks even in environments where correctness of numbers of encryption forms are verified.

### 3. Linear Mix-net

A scheme that enables authority *A* to calculate linear combinations of attribute values belong to same data holders without knowing correspondences between attribute values and their holders can be developed by linear Mix-nets as below ^{[11]}. As mentioned before, one of advantages of linear Mix-nets is they use LE-based or MA-based encryption functions and can handle real numbers and integers efficiently totally in the same way.

Here, implementation of a re-encryption scheme based on LE-based encryption functions E(k_{1}, *x*), E(k_{2}, *x*), ---, E(k_{N},* x*) is straightforward, i.e. 1st mix-server M_{1} encrypts real number or integer *x* to z_{1}-dimensional vector {(1), (2), ---, (z_{1})} based on its secret coefficient matrix {q_{1}(i, j)} and dummy terms, and merges it and dummy elements {(z_{1}+1), (z_{1}+2), ---, (z^{*}_{1})} to construct z^{*}_{1}-dimensional vector E(k_{1}, *x*) = {x_{1}(1), x_{1}(2), ---, x_{1}(z^{*}_{1})}. Then 2nd mix-server M_{2} adds dummy terms to {x_{1}(1), ---, x_{1}(z^{*}_{1})} to construct z_{2}-dimensional (z_{2} > z^{*}_{1}) vector {x_{1}(1), ---, x_{1}(z^{*}_{1}), x_{1}(z^{*}_{1}+1), ---, x_{1}(z_{2})}, encrypts it to {(1), (2), ---, (z_{2})} by calculating each (s) as a linear combination of x_{1}(1), ---, x_{1}(z_{2}) while using secret coefficient matrix {q_{2}(i, j)}, and merges it and dummy elements {(z_{2}+1), (z_{2}+2), ---, (z^{*}_{2})} to construct z^{*}_{2}-dimensional vector E(k_{2}, E(k_{1}, *x*)) = {x_{2}(1), x_{2}(2), ---, x_{2}(z^{*}_{2})}. Remaining mix-servers behave in the same way.

In the remainder, a linear Mix-net is configured based on LE-based encryption functions, and notation E(k_{h*}, *x*) is used to represent re-encryption form E(k_{h}, E(k_{h-1}, --- E(k_{1}, *x*) --- )).

**3.1. Configuration of LE-based Linear Mix-net**

In LE-based linear Mix-net, mix-servers are arrayed also in the verification stage and numbers of mix-servers in the encryption and the decryption stages are not equal, i.e. it consists of data holders, authority *A*, mix-servers M_{1}, ---, M_{T} in the encryption and the verification stages and M_{1}, ---, M_{N} (N < T) in the decryption stage as shown in Figure 2. As same as in Figure 1 mix-servers in the encryption stage repeatedly encrypt individual attribute values, and based on the encryption results, authority *A* calculates encrypted weighted sums of individual data holders’ attribute values to be repeatedly decrypted by mix-servers in the decryption stage. But different form Figure 1 mix-servers in the encryption stage encrypt single attribute value X_{P}(q) into multiple different forms, also before entering the decryption stage mix-servers in the verification stage decrypt individual encrypted attribute values to convince others of their honest encryptions.

**Fig**

**ure**

**2.**

**Configuration of LE-based linear Mix-net**

Where, although each M_{h} in all stages discloses its encryption and decryption results publicly despite E(k_{h}, *x*) is weak against plain text attacks to prove its correct handlings of attribute values, E(k_{h}, *x*) is protected because M_{h} in each stage shuffles its encryption or decryption results. For an entity that does not know shuffling rules, every possible input and output values pair of M_{h} is a candidate of plain and encryption (or encryption and plain) forms pair of E(k_{h}, *x*), and provided that Ω and Ψ are the number of data holders and the dimension of vector E(k_{h}, *x*) respectively, _{Ω}P_{Ψ} number of possibilities must be examined for obtaining Ψ-mutually independent plain and encryption forms pairs (_{Ω}P_{Ψ} is greater than 10^{1}^{00}^{0} when Ω = 200 and Ψ = 100).

Figure 3 shows the data structure of data holder P’s q-th attribute value X_{P}(q) that P puts in the encryption stage. Attribute ID and attribute parts correspond to q-th attribute name *I*_{q} (e.g. height of persons) and attribute value X_{P}(q) itself (e.g. height of a particular person P). About copy ID part value d, P generates multiple copies for single X_{P}(q) and d is the identifier of the d-th copy. The holder part value Z^{r(q}^{, d}^{)∙R}_{mod B} is calculated by P from publicly known integer Z^{r(q}^{, d}^{)}_{mod B} as a used seal of P’s anonymous tag based credential S(P, R) ^{[12]} (B is a publicly known sufficiently large appropriate integer and notation_{ mod B} is omitted in the remainder).

**Fig**

**ure**

**3.**Data structure of attribute values

In detail, for its q-th attribute value X_{P}(q), P shows D-quadruplets E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r}^{(q}^{, d}^{)∙R}} (d =, 1, 2, ---, D) to 1st mix-server M_{1} to be encrypted repeatedly to quadruplets E_{1}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{1}, X_{P}(q)_{d}), Z^{r}^{(q}^{, d}^{)∙R∙}^{u(1)}}, ---, E_{N}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{N*}, X_{P}(q)_{d}), Z^{r}^{(q}^{, d}^{)∙R∙}^{u*(N)}}, ---, E_{T}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{T*}, X_{P}(q)_{d}), Z^{r}^{(q}^{, d}^{)∙R∙}^{u*(T)}}, (d =, 1, 2, ---, D) by M_{1}, ---, M_{N}, ---, M_{T} in the encryption stage, where E(k_{h*}, X_{P}(q)_{d}) represents a re-encryption form of X_{P}(q) that is generated based on dummy terms and dummy elements corresponding to copy ID value d, therefore although E(k_{h*}, X_{P}(q)_{1}), ---, E(k_{h*}, X_{P}(q)_{D}) are decrypted to same value X_{P}(q) they have different forms.

About the verification stage, authority *A* collects quadruplets E_{T}(X_{P}(q, 1)), ---, E_{T}(X_{P}(q, D)), which are calculated from E_{0}(X_{P}(q, 1)), ---, E_{0}(X_{P}(q, D)) in the encryption stage corresponding to attribute value X_{P}(q), to construct single triplet E_{T}(X_{P}(q)) = {*I*_{q}, E(k_{T*}, X_{P}(q)_{*}), Z^{r}^{(q)∙R∙}^{u*(T)}^{∙}^{w(}^{A}^{)}} that has the same structure as in Figure 3 except it does not include the copy ID part. Then, M_{T}, ---, M_{1} decrypt E_{T}(X_{P}(q)) repeatedly to triplets E_{T-1}(X_{P}(q)), ---, E_{0}(X_{P}(q)). Important things are firstly E(k_{T*}, X_{P}(q)_{*}) in triplet E_{T}(X_{P}(q)) is decrypted also to X_{P}(q), and secondly, each mix-server M_{h} cannot identify the correspondence between E_{h}(X_{P}(q, d)) in the encryption stage and E_{h}(X_{P}(q)) in the verification stage for each d, in other words, attribute and holder parts values in triplets E_{T}(X_{P}(q)), ---, E_{1}(X_{P}(q)) have different forms from those in quadruplets E_{T}(X_{P}(q, d)), ---, E_{1}(X_{P}(q, d)).

Finally, the data structure of the weighted sum of P’s attribute values X(P) = *a*_{1}X_{P}(1)+ --- +*a*_{Q}X_{P}(Q) put in the decryption stage consists of attribute part and holder part values pair E_{N}(X(P)) = {E(k_{N*}, X(P)), Z^{R∙}^{u*(N)}^{∙}^{r*}}. Its attribute part and holder part values are aggregations of those in 1st copies of re-encrypted quadruplets E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) in the encryption stage, i.e. E(k_{N*}, X(P)) = *a*_{1}E(k_{N*}, X_{P}(1)_{1})+ --- +*a*_{Q}E(k_{N*}, X_{P}(Q)_{1}) and Z^{R∙u*}^{(N)}^{∙r*} = Z^{R∙u*}^{(N)}^{∙}^{r(1, 1)}^{∙}^{r(2, 1)---}^{∙}^{r(Q, 1)}. Here, it must be noted that authority *A* generates E_{N}(X(P)) from E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) instead of E_{T}(X_{P}(1, 1)), ---, E_{T}(X_{P}(Q, 1)).

Under the above settings, first 3 difficulties in Introduction are removed by anonymous credential S(P, R) and holder part values of quadruplets in the encryption stage and pairs in the decryption stage. In detail, to register itself as an authorized entity, each data holder P shows its exact identity to authority *A*, and *A* issues integers Z^{r(1}^{, d}^{)}, ---, Z^{r(Q}^{, d}^{)} (d = 1, 2, ---, D) and anonymous credential S(P, R) that includes P’s secret unique integer R to P. After that, P generates secret integer y(P, q), calculates S(P, R)^{y(P, q)}, and shows S(P, R)^{y(P, q)} together with X_{P}(q) to 1st mix-server M_{1} in the encryption stage. At the same time, P calculates holder part value Z^{r(q}^{, d}^{)∙R} from Z^{r(q}^{, d}^{)} for each d as a used seal of S(P, R) to be incorporated in each quadruplet E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r(q}^{, d}^{)∙R}}, where, anonymous credential S(P, R) forces P to honestly calculate holder part value Z^{r(q}^{, d}^{)∙R} from Z^{r(q}^{, d}^{)} by using secret integer R in S(P, R). About integers Z and r(q, d), Z is common to all attribute vales of all data holders and publicly known, on the other hand, r(q, d) is unique to q-th attribute values for each d and it is secret from all entities including *A* and mix-servers.

Then the 1st difficulty is removed, i.e. anonymous credential S(P, R) enables P to convince M_{1} of its eligibility without disclosing its identity or secret integer R ^{[12]}. Here, P assigns different values to secret integers y(P, 1), ---, y(P, Q), also each holder part value Z^{r(}^{q, d}^{)∙R} is constructed by integers Z, r(q, d) and R with the above properties. Therefore entities other than P cannot identify links among P’s attribute values X_{P}(1), ---, X_{P}(Q) even if they examine credential forms S(P, R)^{y(P, }^{1}^{)}, ---, S(P, R)^{y(P, }^{Q}^{)} or used seals Z^{r(}^{1, d}^{)∙R}, ---, Z^{r(}^{Q, d}^{)∙R}. When difficulties of solving discrete logarithm problems are considered, to know that the above credential forms or used seals are calculated from same S(P, R) or R is computationally infeasible for entities that do not know y(P, q), R or r(q, d).

About the 2nd and the 3rd difficulties, holder part value Z^{r(}^{q, d}^{)∙R} in initial quadruplet E_{0}(X_{P}(q, d)) is transformed to Z^{r(q}^{, d}^{)∙R∙}^{u(1)}^{∙}^{u(2)---u(N)} = Z^{r(q}^{, d}^{)∙R∙}^{u*(N)} by M_{1}, ---, M_{N} in the encryption stage as a holder part value of re-encrypted quadruplet E_{N}(X_{P}(q, d)), and before entering the decryption stage, *A* asks mix-servers to calculate (Z^{r(}^{q, 1}^{)∙R∙}^{u*(N)})^{r(}^{1, 1}^{)∙}^{r(2, 1)---}^{r(}^{q-1, 1}^{)∙}^{r(q+1, 1)---r(Q, 1)} = Z^{R∙}^{u*(N)}^{∙}^{r(1, 1)}^{∙}^{r(2, 1)---r(Q, 1)} = Z^{R∙}^{u*(N)}^{∙}^{r*} from Z^{r(q}^{, 1}^{)∙R∙}^{u*(N)} for each q. Therefore, value Z^{R∙}^{u*(N)}^{∙}^{r*} becomes common to P’s all encrypted quadruplets E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)), and as a result, to calculate pair E_{N}(X(P)) = {E(k_{*}, X(P)), Z^{R∙}^{u*(N)}^{∙}^{r*}} *A* can collect E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) despite that M_{1}, ---, M_{N} shuffle their encryption results. Here, u(h) is mix-server M_{h}’s secret integer common to all attribute values of all data holders, and although no one knows each r(q, d) mix-servers can calculate Z^{R∙}^{u*(N)}^{∙}^{r*} from Z^{r(}^{q, 1}^{)∙R∙}^{u*(N)} as in Sec. 3.2.3.

In the same way, *A* can collect all quadruplets E_{T}(X_{P}(q, 1)), ---, E_{T}(X_{P}(q, D)) corresponding to X_{P}(q) to construct triplet E_{T}(X_{P}(q)) to be decrypted in the verification stage. Also, P can identify finally decrypted pair E^{*}_{0}(X(P)) = {X(P), Z^{R∙}^{u*(N)}^{∙}^{r*}^{∙}^{v*}} in the decryption stage based on its holder part value Z^{R∙u*}^{(N)}^{∙r*∙v*}, i.e. provided that mix-servers calculate Z^{u*}^{(N)}^{∙r*∙v*} separately, only P that knows R can calculate Z^{R∙u*}^{(N)}^{∙r*∙v*} in pair E^{*}_{0}(X(P)) from Z^{u*}^{(N)}^{∙r*∙v*}. Moreover although R is P’s secret, P must calculate it honestly as a used seal of its credential S(P, R).

In the above, unique integer r(q, d) secret from all entities can be generated easily. In detail, each M_{h} generates its secret integer r(q, d; h) and calculates Z^{r(q, d; 1}^{)}^{∙r(q, d; 2)---r(q, d; h-1)∙r(q, d; h)} from Z^{r(q, d; 1}^{)}^{∙r(q, d; 2)---r(q, d; h-1)} received from M_{h}_{-1} to forward the result to M_{h}_{+1} so that finally M_{T} can calculate Z^{r(q, d; 1}^{)}^{∙r(q, d; 2)---r(q, d; T)} = Z^{r(q, d)}. Namely, no one knows all r(q, d; 1), ---, r(q, d; T) and calculating r(q, d) from Z^{r(q, d)} is a discrete logarithm problem. Also uniqueness of r(q, d) can be maintained by discarding r(q, d) to replace it with new one when mix-servers had calculated same value Z^{r(q, d)} before. Integers u^{*}(N), v^{*} and r^{*} are generated in the same way. Therefore, no one can know values of r(q, d), u^{*}(N), v^{*} or r^{*}, and as a result, anyone including P itself cannot examine holder part values to know the correspondence between P and encrypted quadruplet E_{N}(X_{P}(q, d)) or between finally decrypted pair E^{*}_{0}(X(P)) and each E_{N}(X_{P}(q, d)).

LE-based encryption functions and the verification stage remove the remaining difficulties. Firstly, encryption function E(k_{N*}, *x*) is additive because each E(k_{h}, *x*) is LE-based. Therefore, authority *A* can calculate encryption form E(k_{N*}, *a*_{1}X_{P}(1)+*a*_{2}X_{P}(2)+ --- +*a*_{Q}X_{P}(Q)) from encrypted attribute values E(k_{N*}, X_{P}(1)_{1}), E(k_{N*}, X_{P}(2)_{1}), ---, E(k_{N*}, X_{P}(Q)_{1}) as E(k_{N*}, *a*_{1}X_{P}(1)+ --- +*a*_{Q}X_{P}(Q)) = E(k_{N*}, X_{P}(1)_{1})+ --- +E(k_{N*}, X_{P}(Q)_{1}). Namely, the 4th difficulty is removed if function *f*(*x*_{1}, ---, *x*_{Q}) is a linear combination of attribute values* x*_{1}, ---, *x*_{Q}.

About the 5th difficulty, mix-servers in the encryption and the verification stages transform each attribute value in different ways, i.e. corresponding to same attribute value X_{P}(q), mix-server M_{h} in the encryption stage calculates quadruplet E_{h}(X_{P}(q, d)), and M_{h}_{+1} in the verification stage calculates triplet E_{h}(X_{P}(q)) so that no one can identify the correspondence between them. Therefore, if initial quadruplet E_{0}(X_{P}(q, d)) was dishonestly transformed to E_{h}(X^{*}_{P}(q, d)) by M_{h} in the encryption stage, even M_{h} in the verification stage cannot replace E(k_{h*}, X^{*}_{P}(q)_{*}) in E_{h}(X^{*}_{P}(q)) with E(k_{h*}, X_{P}(q)_{*}) that is finally decrypted to X_{P}(q), because it does not know triplet E_{h}(X^{*}_{P}(q)) corresponding to E_{h}(X^{*}_{P}(q, d)). This means authority *A* can verify the correct encryption of each E_{0}(X_{P}(q, d)) by comparing X_{P}(q) in it and X^{*}_{P}(q) in decrypted triplet E_{0}(X^{*}_{P}(q)) in the verification stage, i.e. E_{N}(X^{*}_{P}(q)) is incorrect when X_{P}(q) ≠ X^{*}_{P}(q). Here, data holder P can identify triplet E_{0}(X^{*}_{P}(q)) corresponds to it in the same way as it finds pair E^{*}_{0}(X(P)) in the decryption stage.

By exploiting, integers Z^{r(}^{1, d}^{)}, ---, Z^{r(}^{Q, d}^{)}, verifiable features of LE-based encryption functions and features of anonymous tag based credentials, *A* and data holders also can detect dishonesties in the decryption stage, identify liable entities, and re-calculate correct results without knowing secrets of honest entities, i.e. the 5th difficulty is removed.

**3.2. Behaviours of the LE-based Linear Mix-net**

After quadruplets E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r(q}^{, d}^{)∙R}} (d = 1, 2, ---, D) were disclosed publicly corresponding to attribute value X_{P}(q) of anonymous data holder P, individual mix-servers and authority *A* behave as below. In the remainder, u_{*}(h), v_{*}(h) and w_{*}(h) represent products u(1)u(2)---u(h), v(N)v(N-1)---v(h) and w(*A*)w(N)w(N-1)---w(h), and as a special case v_{*} = v_{*}(1) and w_{*} = w_{*}(1). Where, u(h), v(h) and w(h) are integers common to all attribute values of all data holders and secrets of h-th mix-server M_{h}, and w(*A*) is a secret integer of authority *A* and common to all attribute values of all data holders.

**3.2.1. Encryption Stage**

1st mix-server M_{1} in the encryption stage that picks disclosed E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r(q}^{, d}^{)∙R}} encrypts X_{P}(q) to E(k_{1}, X_{P}(q)_{d}) by encryption key k_{1}, calculates M^{r(q}^{, d}^{)∙R∙u(1)} from M^{r(q}^{, d}^{)∙R} by using secret integer u(1), and constructs quadruplet E_{1}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{1}, X_{P}(q)_{d}), Z^{r(q}^{, d}^{)∙R∙u(1)}}. Other mix-servers behave in the same way, i.e. each M_{h} picks E_{h-1}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{(h-1)*}, X_{P}(q)_{d}), Z^{r(q}^{, d}^{)∙R∙u*(h-1)}} disclosed by M_{h-1}, encrypts E(k_{(h-1)*}, X_{P}(q)_{d}) to E(k_{h*}, X_{P}(q)_{d}) and calculates Z^{r(q}^{, d}^{)∙R∙u*(h)} from Z^{r(q}^{, d}^{)∙R∙u*(h-1)} by its secret key k_{h} and secret integer u(h), and constructs E_{h}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{h*}, X_{P}(q)_{d}), Z^{r(q}^{, d}^{)∙R∙u*(h)}} to disclose it publicly. As a result, E_{0}(X_{P}(q, d)) received by M_{1} is finally transformed to E_{N}(X_{P}(q, d)) and E_{T}(X_{P}(q, d)) by M_{N} and M_{T} respectively, where each M_{h} shuffles its generating quadruplets of course.

Then, because no one knows all keys k_{1}, ---, k_{N} , ---, k_{T} nor integers u(1), ---, n(N), ---, u(T), anyone cannot link E_{0}(X_{P}(q, d)) to E_{N}(X_{P}(q, d)) or E_{T}(X_{P}(q, d)) unless all mix-servers conspire. Anyone except P cannot know links among P’s attribute values X_{P}(1), X_{P}(2), ---, X_{P}(Q) either. About encryption function E(k_{h}, *x*), although each M_{h} shuffles its encryption results, anyone can obtain a plain and encryption forms pair of E(k_{h}, *x*). Namely, if an entity calculates X_{h-1} and X_{h} as sums of all attribute part values in quadruplets that M_{h} receives and generates respectively, {X_{h-1}, X_{h}} is a plain and encryption forms pair because E(k_{h}, *x*) is additive. But, M_{h} can protect E(k_{h}, *x*) from plaintext attacks because known pair is only {X_{h-1}, X_{h}}.

**3.2.2. Verification Stage**

After the encryption stage, authority *A* conducts the verification stage to examine whether individual quadruplets were honestly encrypted or not, and when dishonestly handled quadruplets are detected it asks mix-servers to carry out the encryption stage again while using new secret values including encryption keys. Also, *A* identifies dishonest mix-servers if necessary to replace them with new ones as will be discussed in Sec. 3.4.2. Therefore, the encryption stage eventually generates correct encryption results.

To examine individual quadruplets, firstly authority *A* collects E_{T}(X_{P}(q, 1)) = {*I*_{q}, 1, E(k_{T*}, X_{P}(q)_{1}), Z^{r(q}^{, 1}^{)∙R∙u*}^{(T)}}, ---, E_{T}(X_{P}(q, D)) = {*I*_{q}, D, E(k_{T*}, X_{P}(q)_{D}), Z^{r(q}^{, D}^{)∙R∙u*}^{(T)}} corresponding to each attribute value X_{P}(q) of each data holder P. Here, provided that^{ }r(q, ; h) and r(q) represent products r(q, 1; h)∙r(q, 2; h)---r(q, d-1; h)∙r(q, d+1; h)---r(q, D; h) and r(q, 1)∙r(q, 2)---r(q, D) respectively, each M_{h} receives from M_{h-1} and calculates by using its secret integer r(q, , h) to forward it to M_{h+1}. As a result, M_{T} calculates . Therefore, *A* can collect E_{N}(X_{P}(q, 1)), ---, E_{N}(X_{P}(q, D)) that include as their holder part values.

After that, each M_{h} (h ≤ Y < N) calculates d_{h1}E(k_{T*}, X_{P}(q)_{1})+ --- +d_{hD}E(k_{T*}, X_{P}(q)_{D})+E(k_{T*}, 0_{h}(P, q)) = E(k_{T*}, d_{h1}X_{P}(q)_{1}+ --- +d_{hD}X_{P}(q)_{D}+0_{h}(P, q)) = E(k_{T*}, X_{P}(q; h)), and *A* calculates {E(k_{T*}, X_{P}(q; 1))+ --- +E(k_{T*}, X_{P}(q; Y))}/Y = E(k_{T*}, X_{P}(q)_{*}). Here, d_{h1}, d_{h2}, ---, d_{hD} are real numbers secrets of M_{h} and relation d_{h1}+ --- +d_{hD} = 1 holds, and E(k_{T*}, 0_{h}(P, q)) is M_{h}’s secret encryption form of value 0. Therefore each E(k_{T*}, X_{P}(q; h)) is decrypted to X_{P}(q). In addition, E(k_{T*}, X_{P}(q)_{*}) is also represented as E(k_{T*}, X_{P}(q)_{*}) = E(k_{T*}, d_{1}X_{P}(q)_{1}+ --- +d_{D}X_{P}(q)_{D}+0_{*}(P, q)) for some real number coefficients d_{1}, ---, d_{D} that satisfy d_{1}+ --- +d_{D} = 1 (where E(k_{T*}, 0_{*}(P, q)) = {E(k_{T*}, 0_{1}(P, q)+ --- +0_{Y}(P, q))}/Y), and this means E(k_{T*}, X_{P}(q)_{*}) is also decrypted to X_{P}(q). But no one knows coefficients d_{1}, ---, d_{D} or encryption form E(k_{T*}, 0_{*}(P, q)) because d_{h1}, d_{h2}, ---, d_{hD} and E(k_{T*}, 0_{h}(P, q)) are known only to M_{h}.

About encryption form E(k_{T*}, 0_{h}(P, q)), each M_{h} can generate it by choosing data holders P_{(h1)}, ---, P_{(h}_{S}_{)}, attribute IDs *I*_{q}_{(h1)}, ---, *I*_{q}_{(h}_{S}_{)} and copy IDs pairs {d_{(h1)}, }, ---, {d_{(h}_{S}_{)}, } arbitrarily as its secrets and linearly combining by its secret coefficients, i.e. E(k_{T*}, X_{P}_{(hs)}(q_{(hs)})_{d(hs)}) and are encryption forms of same value X_{P}_{(hs)}(q_{(hs)}). M_{h} also can identify pair {E(k_{T*}, X_{P}_{(hs)}(q_{(hs)})_{d(hs)}), } because they are accompanied by same holder part value Z^{r(q(hs))}^{∙R}^{(hs)}^{∙u*}^{(T)}.

Then *A* generates secret integer w(*A*), and constructs triplet E_{T}(X_{P}(q)) = {*I*_{q}, E(k_{T*}, X_{P}(q)_{*}), Z^{r(q)∙R∙u*}^{(T)}^{∙w(}^{A}^{)}} to disclose it publicly, and mix-servers M_{T}, ---, M_{1} in the verification stage repeatedly decrypt E_{T}(X_{P}(q)) to E_{0}(X_{P}(q)) = {*I*_{q}, X_{P}(q), Z^{r(q)∙R∙u*}^{(T)}^{∙w*}}. In detail, each M_{h} picks E_{h}(X_{P}(q)) = {*I*_{q}, E(k_{h*}, X_{P}(q)_{*}), Z^{r(q)∙R∙u*}^{(T)}^{∙w*(h+1)}} disclosed by M_{h+1}, decrypts E(k_{h*}, X_{P}(q)_{*}) to E(k_{(h-1)*}, X_{P}(q)_{*}) calculates Z^{r(q)∙R∙u*}^{(T)}^{∙w*(h)} = Z^{r(q)∙R∙u*}^{(T)}^{∙w*(h+1)∙w(h)} by using key k_{h}^{-1} and integer w(h), constructs triplet E_{h-1}(X_{P}(q)) = {*I*_{q}, E(k_{(h-1)*}, X_{P}(q)_{*}), Z^{r(q)∙R∙u*}^{(T)}^{∙w*(h)}}, and discloses it to be picked by M_{h-1}. As a consequence, M_{1} generates decrypted triplet E_{0}(X_{P}(q)) = {*I*_{q}, X_{P}(q), Z^{r(q)∙R∙u*}^{(T)}^{∙w*}}.

Here, although *A* and M_{N}, ---, M_{1} shuffle their calculation results, links among copies of quadruplets E_{T}(X_{P}(q, 1)), ---, E_{T}(X_{P}(q, D)) are revealed. Nevertheless, P can preserve its privacy, i.e. they are encryption forms of same attribute value X_{P}(q). Also, mix-servers can protect their encryption functions from plain text attacks despite anyone can obtain plain and encryption forms pair {0, E(k_{T*}, 0)} as above, i.e. no one knows its dummy term values.

**<Detecting dishonesties in the encryption stage>**

In the above, because no one knows coefficients d_{1}, ---, d_{D}, encryption form E(k_{h*}, 0_{*}(P, q)) or integer w_{*}(h), anyone cannot link triplet E_{h}(X_{P}(q)) = {*I*_{q}, E(k_{h*}, X_{P}(q)_{*}), Z^{r(q)∙R∙u*}^{(T)}^{∙w*(h}^{+1}^{)}} to corresponding quadruplet E_{h}(X_{P}(q, d)) = {*I*_{q}, d, E(k_{h*}, X_{P}(q)_{d}), Z^{r(q}^{, d}^{)∙R∙u*}^{(h)}}. This means if initial quadruplet E_{0}(X_{P}(q, d)) is dishonestly encrypted to E_{T}(X^{*}_{P}(q, d)) in the encryption stage, any M_{h} in the verification stage cannot modify corresponding triplet E_{h}(X^{*}_{P}(q)) to E_{h}(X_{P}(q)) so that it is finally decrypted to E_{0}(X_{P}(q)) = {*I*_{q}, X_{P}(q), Z^{r(q)∙R∙u*}^{(T)}^{∙w*}} (actually, 1st mix-server M_{1} can do as will be discussed later).

Authority *A* detects dishonesties in the encryption stage by using this property. In detail, firstly *A* requests mix-servers to calculate integer Z^{r(q)∙u*}^{(T)}^{∙w*} for each q to disclose it publicly. After that for each q, each data holder P calculates used seals Z^{r(q}^{, 1}^{)∙R} and Z^{r(q)∙R∙u*}^{(T)}^{∙w*} of its credential S(P, R) from Z^{r(q}^{, 1}^{)} and Z^{r(q)∙u*}^{(T)}^{∙w*}, and based on Z^{r(}^{q, 1}^{)∙R} and Z^{r(}^{q}^{)∙R∙u*}^{(T)}^{∙w*} finds E_{0}(X_{P}(q, 1)), i.e. 1st copy of the initial quadruplet corresponding to attribute value X_{P}(q), and triplets E_{0}(X^{*}_{P}(q)) in the verification stage.

Then, P shows initial quadruplet and decrypted triplet pair <E_{0}(X_{P}(q, 1)), E_{0}(X^{*}_{P}(1))> to *A* while convincing *A* of its ownership of the pair by used seals Z^{r(}^{q, 1}^{)∙R} and Z^{r(}^{q}^{)∙R∙u*}^{(T)}^{∙w*}, and *A* determines pair <E_{0}(X_{P}(q, 1)) = {*I*_{q}, 1, X_{P}(q), Z^{r(}^{q, 1}^{)∙R}}, E_{0}(X^{*}_{P}(q)) = {*I*_{q}, X^{*}_{P}(q), Z^{r(}^{q}^{)∙R∙u*}^{(T)}^{∙w*}}> is inconsistent, i.e. at least one copy E_{0}(X_{P}(q, d)) was dishonestly handled, when X_{P}(q) ≠X^{*}_{P}(q). Here, correctness of X_{P}(q) in E_{0}(X_{P}(q, 1)) is ensured because P shows X_{P}(q) to M_{1} in its plain form. About privacy preservation, P must report pairs separately and without disclosing its identity of course.

*A* also can force all data holders to report their all pairs, i.e. when no one appears as the holder of pair <E_{0}(X_{P}(q, 1)), E_{0}(X_{P}(q))>, it asks all data holders to calculate used seals of their credentials from Z^{r(q}^{, 1}^{)} and Z^{r(q)∙u*}^{(T)}^{∙w*} while disclosing their identities as will be discussed in Sec. 3.4.3. In a case where mix-servers transform holder part value Z^{r(q}^{, d}^{)∙R} in E_{0}(X_{P}(q, d)) to an invalid value P cannot identify its decrypted triplet in the verification stage, but even in this case *A* can detect the dishonestly handled quadruplet as E_{0}(X_{P}(q, 1)) that is not paired with any triplet.

In the above, mix-servers M_{1}, ---, M_{T} can calculate Z^{r(q)∙u*}^{(T)}^{∙w*} as same as Z^{r(q)}^{∙R∙u*}^{(T)} at the beginning of this subsection. Namely provided that r(q; h) represents product r(q, 1; h)∙r(q, 2; h)---r(q, D; h), each M_{h} calculates Z^{{r}^{(q}^{; 1}^{)∙}^{r(q; 2)----r(q; h-1)}^{∙}^{r(q; h)}}^{∙}^{{u}^{(}^{1}^{)∙}^{u(2)----u(h-1)}^{∙}^{u(h)}}^{∙}^{{w}^{(}^{A}^{)∙}^{w}^{(}^{1}^{)∙}^{w(2)----w(h-1)}^{∙}^{w(h)}} from Z^{{r}^{(q}^{; 1}^{)}^{----r(q; h-1)}}^{∙}^{{u}^{(}^{1}^{)}^{----u(h-1)}}^{∙}^{{w}^{(}^{A}^{)∙}^{w}^{(}^{1}^{)}^{----w(h-1)}} given by M_{h}_{-1} to forward it to M_{h}_{+1} so that finally M_{T} calculates Z^{{r}^{(q}^{; 1}^{)}^{----r(q; T)}}^{∙}^{{u}^{(}^{1}^{)}^{----u(T)}}^{∙}^{{w}^{(}^{A}^{)∙}^{w}^{(}^{1}^{)}^{----w(T)}} = Z^{r(q)∙u*}^{(T)}^{∙w*}. Here, although P knows integer R, it cannot identify triplet E_{h}(X_{P}(q)) = {*I*_{q}, E(k_{h*}, X_{P}(q)_{*}), Z^{r(}^{q}^{)∙R∙u*}^{(T)}^{∙w*}^{(h+1)}} based on Z^{{r}^{(q}^{; 1}^{)}^{----r(q; h)}}^{∙}^{{u}^{(}^{1}^{)}^{----u(h)}}^{∙}^{{w}^{(}^{A}^{)∙}^{w}^{(}^{1}^{)}^{----w(h)}} disclosed by M_{h} for h > 1, because r(q; 1)----r(q; h)u(1)----u(h)w(*A*)w(1)----w(h) and r(q)u_{*}(T)w_{*}(h+1) are different.

About privacy of data holder P, P is anonymous, and because it reports pairs <E_{0}(X_{P}(1, 1)), E_{0}(X_{P}(1))>, ---, <E_{0}(X_{P}(Q, 1)), E_{0}(X_{P}(Q))> separately, anyone other than P cannot know links among X_{P}(1), ---, X_{P}(Q). Although E_{0}(X_{P}(q)) includes plain attribute value X_{P}(q), X_{P}(q) is publicly known from the beginning.

**<Dishonest 1st mix-server M**

_{1}>1st mix-server M_{1} in the encryption stage can encrypt E_{0}(X_{P}(q, d)) dishonestly while making triplet E_{0}(X_{P}(q)) in the verification stage include consistent attribute value X_{P}(q). For example, provided that X^{*}_{P}(q) is a unique value, even if M_{1} dishonestly encrypted E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r(q}^{, d}^{)∙R}} to E_{1}(X^{*}_{P}(q, d))= {*I*_{q}, d, E(k_{1}, X^{*}_{P}(q)), Z^{r(q}^{, d}^{)∙R∙u(1)}} in the encryption stage for each d, because X^{*}_{P}(q) is unique it can identify incorrect triplet E_{0}(X^{*}_{P}(q)) = {*I*_{q}, X^{*}_{P}(q), Z^{r(q)∙R∙u*}^{(T)}^{∙w*}} in the verification stage and replace X^{*}_{P}(q) in it with X_{P}(q) to produce correct decrypted triplet E_{0}(X_{P}(q)) = {*I*_{q}, X_{P}(q), Z^{r(q)∙R∙u*}^{(T)}^{∙w*}}.

To disable above dishonesties, in other words, to convince others that M_{1} is honest, after completing the verification stage,* A* discloses its secret integer w(*A*) and asks mix-servers M_{1}, M_{2}, ---, M_{Y} (Y < N) to disclose their encryption keys k_{1}, k_{2}, ---, k_{Y}, and secret integers u(1), u(2), ----, u(Y), w(1), W(2), ---, w(Y). Namely, by the disclosed information, anyone can confirm M_{1} is honest. On the other hand, encryption keys k_{Y+1}, ---, k_{N}, ---, k_{T} and integers u(Y+1), ---, u(N), ---, u(T), w(Y+1), ---, w(N), ---, w(T) are still secrets of M_{Y+1}, ---, M_{T}, therefore secrets of honest data holders can be preserved. Also, *A* and mix-servers replace secret integers w(*A*), u(1), ---, u(T), w(1), ---, w(T) and encryption keys k_{1}, ---, k_{T} with new ones for handling new sets of attribute values.

About last mix-server M_{T}, if it conspires with authority *A*, it also can encrypt E_{T}_{-1}(X_{P}(q, d)) to E_{T}(X^{*}_{P}(q, d)) dishonestly and decrypt E_{T}(X^{*}_{P}(q)) to E_{T-1}(X_{P}(q)) that is finally decrypted to correct value X_{P}(q), but incorrect E_{T}(X^{*}_{P}(q, d)) does not affect the final calculation results because M_{N}_{+1}, M_{N}_{+2}, ---, M_{T} are not involved in the decryption stage.

**3.2.3. Calculating Encrypted Weighted Sums of Attribute Values**

To calculate encrypted weighted sums of attribute values corresponding to individual data holders, provided that^{ }r_{q}(h) and r_{*} represent products {r(1, 1; h)∙r(2, 1; h)--- r(q-1, 1; h)∙r(q+1, 1; h)---r(Q, 1; h)} and {r(1, 1)∙r(2, 1)---r(Q, 1)} respectively, authority* A* asks mix-servers M_{1}, ---, M_{T} to transform the holder part value of each quadruplet E_{N}(X_{P}(q, 1)) = {*I*_{q}, 1, E(k_{N*}, X_{P}(q)_{1}), Z^{r(q}^{, 1}^{)∙R∙u*}^{(N)}} from Z^{r(q}^{, 1}^{)∙R∙u*}^{(N)} to Z^{R∙u*}^{(N)}^{∙r*}, i.e. each M_{h} calculates Z^{r(q}^{, 1}^{)∙R∙u*}^{(N)}^{∙}^{r}^{q(1)}^{∙r}^{q}^{(}^{2}^{)}^{---}^{r}^{q}^{(h}^{-1}^{)}^{∙}^{r}^{q}^{(h)} from Z^{r(q}^{, 1}^{)∙R∙u*}^{(N)}^{∙}^{r}^{q}^{(}^{1)}^{∙r}^{q}^{(}^{2}^{)}^{---}^{ r}^{q}^{(h}^{-1}^{)} received from M_{h-1} to forward the result to M_{h+1}. Therefore, finally M_{T} calculates Z^{r(q}^{, 1}^{)∙R∙u*}^{(N)}^{∙}^{r}^{q}^{(}^{1)---}^{r}^{q}^{(}^{T}^{)} = Z^{R∙u*}^{(N)}^{∙}^{r(}^{1, 1)---}^{r(}^{Q, 1}^{)} = Z^{R∙u*}^{(N)}^{∙}^{r}^{*}, and same value Z^{R∙u*}^{(N)}^{∙r*} is assigned to P’s quadruplets E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) as their holder part values. Then, *A* can collect E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) from all quadruplets disclosed by M_{N} to calculate the encrypted weighted sum of P’s attribute values as E(k_{N*}, X(P)) = E(k_{N*}, *a*_{1}X_{P}(1)_{1}+ --- +*a*_{Q}X_{P}(Q)_{1}) = *a*_{1}E(k_{N*}, X_{P}(1)_{1})+ --- +*a*_{Q}E(k_{N*}, X_{P}(Q)_{1}) and to construct pair E^{*}_{N}(X(P)) = {E(k_{N*}, X(P)), Z^{R∙u*∙r*}}.

**3.2.4. Decryption Stage**

In the decryption stage, mix-servers M_{N}, M_{N}_{-1}, ---, M_{1} repeatedly decrypt pair E^{*}_{N}(X(P)) to E^{*}_{N-1}(X(P)) = {E(k_{(N-1)*}, X(P)), Z^{R∙u*}^{(N)}^{∙r*∙v(N)}}, E^{*}_{N-2}(X(P)) = {E(k_{(N-2)*}, X(P)), Z^{R∙u*}^{(N)}^{∙r*∙v*(N-1)}}, ---, E^{*}_{0}(X(P)) = {X(P), Z^{R∙u*}^{(N)}^{∙r*∙v*}}. Here, although each M_{h} shuffles its decryption results *A* can verify correct decryptions of E^{*}_{N}(X(P)) partially without knowing secrets of mix-servers by exploiting additive feature of each E(k_{h}, *x*). Namely, if *A* calculates sums of attribute part values in all pairs received and generated by M_{h} as and respectively, both and must be encryption forms of , weighted sum of all attribute values of all data holders. This means is a plain and encryption forms pair of E(k_{h}, *x*), and additive (as a result verifiable) feature of E(k_{h}, *x*) enables *A* to force mix-servers to decrypt pairs so that sums of their decrypted attribute part values coincide with even if they decrypt individual pairs dishonestly.

About encryption function E(k_{h}, *x*) of each mix-server M_{h}, because M_{h} shuffles its decryption results, no one other than M_{h} can identify plain and encryption forms pair {E(k_{(h-1)*}, X(P)), E(k_{h}_{*}, X(P))} except the above pair . Therefore, M_{h} can protect E(k_{h}, *x*) from plain text attacks also in the decryption stage.

Nevertheless, data holder P can find its pair E^{*}_{0}(X(P)) = {X(P), Z^{R∙u*}^{(N)}^{∙r*∙v*}} to take actions for the pair. Firstly, *A* asks mix-servers to calculate Z^{u*}^{(N)}^{∙r*∙v*} in the same way as in Sec. 3.2.3. Then, each P calculates (Z^{u*}^{(N)}^{∙r*∙v*})^{R} = Z^{R∙u*}^{(N)}^{∙r*∙v*} from Z^{u*}^{(N)}^{∙r*∙v*} based on integer R in its credential S(P, R), finds pair E^{*}_{0}(X(P)) according to Z^{R∙u*}^{(N)}^{∙r*∙v*}, and convinces *A* of its ownership of E^{*}_{0}(X(P)). Where, although P is anonymous, *A* can confirm P’s ownership of pair E^{*}_{0}(X(P)), because P must calculate Z^{R∙u*}^{(N)}^{∙r*∙v*} honestly as a used seal of S(P, R).

**3.3. Detecting Dishonesties**

In the encryption stage, data holder P puts its initial quadruplet E_{0}(X_{P}(q, d)) = {*I*_{q}, d, X_{P}(q), Z^{r(q}^{, d}^{)∙R}} honestly, because P shows X_{P}(q) in its plain form and it calculates Z^{r(q}^{, d}^{)∙R} from Z^{r(q}^{, d}^{)} as a used seal of its credential. This means P cannot behave dishonestly in any stage. Also, the verification stage ensures that mix-servers in the encryption stage eventually generate correct encryption results. Therefore, remaining dishonesties to be detected are ones in the decryption stage, i.e. each mix-server M_{h} may replace elements of pair E^{*}_{h}(X(P)) with those of other pair E^{*}_{h}(X(P_{*})) and may simply decrypt E^{*}_{h}(X(P)) incorrectly.

Provided that volume of duties P must accomplish increases (or decreases) when weighted sum of P’s attribute values X(P) increases, authority *A* can easily detect above dishonesties as below. Namely as mentioned in the previous subsection, each mix-server M_{h} in the decryption stage must decrypt each pair E^{*}_{h}(X(P)) it receives from M_{h}_{+1} so that , sum of attribute part values in all pairs it generates, is finally decrypted to , the weighted sum of attribute values of all data holders. Therefore, if dishonesties bring any benefit to a data holder some other data holder necessarily suffers loss. For example, if X(P_{*}) is the amount data holder P_{*} must pay, when X(P_{*}) becomes less than the actual value, for at least one other data holder P, weighted sum of its attribute values X(P) becomes larger than the actual value. As a result, P claims decrypted pair E^{*}_{0}(X(P)) is incorrect. It is also possible to endow each P with the ability to automatically notice *A* that E^{*}_{0}(X(P)) is incorrect by distributing adequate computer programs to data holders.

Also, each data holder P must appear to take actions for E^{*}_{0}(X(P)) as will be discussed in Sec. 3.4.3, although X(P) in it may not be correct. Here, M_{h} may transform a holder part value of E^{*}_{h}(X(P)) = {E(k_{h}_{*}, X(P)), Z^{R∙u*}^{(N)}^{∙r*∙v(}^{h+1}^{)}} in the decryption stage to an invalid value or to the one corresponding to data holder P_{*} different from P. But decrypted pairs accompanied by invalid holder part values are detected as the ones of which holders cannot be identified by the procedure in Sec. 3.4.3. In the latter case, some data holders claim that weighted sums of their attribute values are incorrect.

**3.4. Identifying Dishonest Entities**

**3.4.1. Dishonest Mix-servers in the Decryption Stage**

When authority *A* determines some decrypted pairs include invalid holder part values or some data holders claim that decrypted pairs corresponding to them are incorrect, *A* can identify liable entities and re-calculate correct pairs without knowing secrets of honest entities. In the following, pair E^{*}_{0}(X^{*}(P)) = {X^{*}(P), Z^{R∙u*}^{(N)}^{∙r*∙v*}} in the decryption stage is assumed incorrect, i.e. it is a pair that includes an invalid holder part value or that is claimed as inconsistent by anonymous data holder P.

To identify mix-servers liable for each incorrect pair E^{*}_{0}(X^{*}(P)), authority *A* requests mix-servers M_{1}, ---, M_{N} to prove their correct decryptions. In detail, M_{1} finds pair E^{*}_{1}(X^{*}(P)) = {E(k_{1}, X^{*}(P)), Z^{R∙u*}^{(N)}^{∙r*∙v*(}^{2}^{)}} that corresponds to E^{*}_{0}(X^{*}(P)), and *A* confirms that M_{1} certainly had received E^{*}_{1}(X^{*}(P)) from M_{2} in the decryption stage and E^{*}_{0}(X^{*}(P)) is the correct decryption form of E^{*}_{1}(X^{*}(P)). In the same way, each M_{h} finds pair E^{*}_{h}(X^{*}(P)) = {E(k_{h*}, X^{*}(P)), Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}} corresponds to E^{*}_{h-1}(X^{*}(P)) = {E(k_{(h-1)*}, X^{*}(P)), Z^{R∙u*}^{(N)}^{∙r*∙v*(h)}} forwarded by M_{h-1}, and *A* confirms M_{h} certainly had received E^{*}_{h}(X^{*}(P)) from M_{h+1} and E^{*}_{h-1}(X^{*}(P)) is the correct decryption form of E^{*}_{h}(X^{*}(P)). Namely, M_{h} is dishonest when E^{*}_{h}(X(P)) that is decrypted to E^{*}_{h-1}(X^{*}(P)) does not exist.

Here, *A* can examine the consistency of pair <E^{*}_{h}(X^{*}(P)), E^{*}_{h}_{-1}(X^{*}(P))> without knowing secrets of M_{h}. Namely, consistency of attribute part values E(k_{h*}, X^{*}(P)) and E(k_{(h-1)*}, X^{*}(P)) can be verified because E(k_{h}, *x*) is additive and verifiable (moreover, encryption keys of M_{1}, ---, M_{Y} are disclosed as in Sec. 3.2.2). About holder part values, pair {Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}, Z^{R∙u*}^{(N)}^{∙r*∙v*(h)}} is consistent if Z^{R∙u*}^{(N)}^{∙r*∙v*(h)} is calculated from Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)} by using M_{h}’s secret integer v(h) that is common to all attribute values of all data holders. Therefore, when *A* calculates product of holder part values in all pairs M_{h} had generated in the decryption stage as Z_{*}^{R}^{*}^{∙u*}^{(N)}^{∙r*∙v*(h)} for each h and defines , along the scheme of Diffie and Hellman ^{[1]}, it can determine pair {Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}, Z^{R∙u*}^{(N)}^{∙r*∙v*(h)}} is consistent if Z^{R∙u*}^{(N)}^{∙r*∙v*(h)} and are calculated as (Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)})^{v}^{(h)} and by same unknown integer v(h).

In the following notations Z_{P}(h+1), Z_{-}(h+1), Z_{P}(h) and Z_{-}(h) represent Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}, , Z^{R∙u*}^{(N)}^{∙r*∙v*(h)} and Z_{-}^{R}^{∙u*}^{(N)}^{∙r*∙v*(h)} respectively, therefore pair {Z^{R∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}, Z^{R∙u*}^{(N)}^{∙r*∙v*(h)}} is consistent if relations Z_{P}(h+1)^{v(h)} = Z_{P}(h) and Z_{-}(h+1)^{v(h)} = Z_{-}(h) hold for same unknown v(h). Also it must be noted that Z_{P}(h+1)Z_{-}(h+1)_{ }= Z_{*}^{R}^{*}^{∙u*}^{(N)}^{∙r*∙v*(h}^{+1}^{)}. Then, to confirm relations Z_{P}(h+1)^{v(h)} = Z_{P}(h) and Z_{-}(h+1)^{v(h)} = Z_{-}(h), *A* generates its secret integers δ_{1}, δ_{2}, δ_{3}, calculates pairs {Z_{P}(h+1)^{δ}^{1}, Z_{P}(h)^{δ}^{1}}, {Z_{-}(h+1)^{δ}^{2}, Z_{-}(h)^{δ}^{2}}, {(Z_{P}(h+1)Z_{-}(h+1))^{δ}^{3}, (Z_{P}(h)Z_{-}(h))^{δ}^{3}}, and shows Z_{P}(h+1)^{δ}^{1}, Z_{-}(h+1)^{δ}^{2}, (Z_{P}(h+1)Z_{-}(h+1))^{δ}^{3} to M_{h}. After that M_{h} calculates (Z_{P}(h+1)^{δ}^{1})^{v(h)}, (Z_{-}(h+1)^{δ}^{2})^{v(h)}, {(Z_{P}(h+1)Z_{-}(h+1))^{δ}^{3}}^{v(h)} from them and its secret integer v(h), and finally* **A* confirms that Z_{P}(h) and Z_{-}(h) were calculated by same v(h) if relations (Z_{P}(h+1)^{δ}^{1})^{v(h)} = Z_{P}(h)^{δ}^{1}, (Z_{-}(h+1)^{δ}^{2})^{v(h)} = Z_{-}(h)^{δ}^{2} and {(Z_{P}(h+1)Z_{-}(h+1))^{δ}^{3}}^{v(h)} = {Z_{P}(h)Z_{-}(h)}^{δ}^{3} hold.

In the above, even if M_{h} had calculated Z_{P}(h) and Z_{-}(h) as Z_{P}(h+1)^{λ} and Z_{-}(h+1)^{v(h)} respectively while using different integers λ and v(h), it still can satisfy relations (Z_{P}(h+1)^{δ}^{1})^{λ} = Z_{P}(h)^{δ}^{1} and (Z_{-}(h+1)^{δ}^{2})^{v(h)} = Z_{-}(h)^{δ}^{2} despite it does not know δ_{1} or δ_{2}. But according to the difficulty of solving discrete logarithm problems, it cannot find integer λ_{*} that satisfies relation {(Z_{P}(h+1)(Z_{-}(h+1))^{δ}^{3}}^{λ*} = (Z_{P}(h)Z_{-}(h))^{δ}^{3} = (Z_{P}(h+1)^{λ}Z_{-}(h+1)^{v(h)})^{δ}^{3}, because it cannot represent Z_{P}(h+1) or Z_{-}(h+1) as a function of Z_{-}(h+1) or Z_{P}(h+1) respectively.

Then, once M_{h} was identified as dishonest, M_{h}, ---, M_{1} must honestly decrypt E^{*}_{h}(X(P)) to generate correct decrypted pair E^{*}_{0}(X(P)) = {X(P), Z^{R∙u*}^{(N)}^{∙r*∙v*}} (because *A* can verify correct decryption of M_{h} as above). About data holder P, it can conceal the correspondence between X(P) and it because it is still anonymous. But it must be noted that to protect E(k_{h}, *x*) from plain text attacks (in other words not to disclose many plain and encryption forms pairs)* A* can examine only predefined number of incorrect decrypted pairs even if many decrypted pairs are determined as incorrect as will be discussed in Sec. 3.4.2. In addition, in cases where last mix-server M_{N} is dishonest, incorrect pair <E^{*}_{N}(X(P)), E^{*}_{N-1}(X^{*}(P))> is disclosed, and corresponding data holder P may obtain plain and encryption forms pairs {X_{P}(1), E(k_{N*}, X_{P}(1)_{1})}, ---, {X_{P}(Q), E(k_{N*}, X_{P}(Q)_{1})}, i.e. P knows its attribute values X_{P}(1), ---, X_{P}(Q) and can know encrypted quadruplets E_{N}(X_{P}(1, 1)), ---, E_{N}(X_{P}(Q, 1)) as *A* collects them to calculate E^{*}_{N}(X(P)). Despite E(k_{1}, *x*), ---, E(k_{N}, *x*) are weak against plain text attacks, still they can be protected because the number of disclosed pairs is not large except cases where many attribute values are assigned to each data holder. But when individual data holders have many attribute values *A* must carry out all stages again as below.

Namely, when *A* cannot identify dishonest mix-servers among M_{1}, M_{2}, ---, M_{U} (U < N), it conducts all stages again from the encryption stage while arraying mix-servers in the different order so that M_{U+1}, M_{U+2}, ---, M_{N} are allocated before M_{1}, M_{2}, ---, M_{U} in the encryption stage. Then, if M_{N} behaves dishonestly again *A* can identify it without worrying about the disclosure of numbers of pairs {X_{P}(1), E(k_{N*}, X_{P}(1)_{1})}, ---, {X_{P}(Q), E(k_{N*}, X_{P}(Q)_{1})}. Fortunately, usually authority *A* or mix-servers do not behave dishonestly, because they are not anonymous, their dishonesties are necessarily revealed and they cannot continue their businesses after their dishonesties are revealed. This means that in actual applications authority *A* can conduct all stages again from the start without degrading the performance. Another fortunate thing is data holders are not required to put their attribute values again to re-conduct individual stages.

**3.4.2. Dishonest Mix-servers in the encryption and the verification stages**

As in Sec. 3.2.2, authority *A* conducts the encryption stage again when initial quadruplet E_{0}(X_{P}(q, 1)) is not paired with any triplet in the verification stage or some data holder P claims pair <E_{0}(X_{P}(q, 1)), E_{0}(X^{*}_{P}(q))> is inconsistent. But if *A* wants to remove dishonest mix-servers or replace them with new ones, it must identify dishonest mix-servers. *A* can identify dishonest mix-servers in the encryption and the verification stages without knowing secrets of honest entities as below.

Provided that pair <E_{0}(X_{P}(q, 1)), E_{0}(X^{*}_{P}(q))> is inconsistent or E_{0}(X_{P}(q, 1)) is not accompanied by any triplet, to identify dishonest mix-servers, firstly 1st mix-server M_{1} encrypts E_{0}(X_{P}(q, 1)), ---, E_{0}(X_{P}(q, D)) to E_{1}(X_{P}(q, 1)), ---, E_{1}(X_{P}(q, D)) by using secret parameters that it had used in the encryption stage. In the same way, each M_{h} encrypts quadruplets E_{h-1}(X_{P}(q, 1)), ---, E_{h-1}(X_{P}(q, D) forwarded by M_{h-1} to E_{h}(X_{P}(q, 1)), ---, E_{h}(X_{P}(q, D)) to forward the result to M_{h+1}, and M_{h} is determined as dishonest if it cannot show consistent pair <E_{h-1}(X_{P}(q, d)), E_{h}(X_{P}(q, d))>.

Authority* A* identifies dishonest mix-servers in the verification stage in the same way. Here, *A* can verify M_{h}’s correct encryption of E_{h-1}(X_{P}(q, d)) and correct decryption of E_{h}(X^{*}_{P}(q)) without knowing secrets of M_{h} as same as in the decryption stage. But when the number of inconsistent pairs is large, many plain and encryption forms pairs are disclosed. Therefore, *A* examines only predefined number of inconsistent pairs even if many pairs are inconsistent as same as in Sec. 3.4.1. Namely, after identifying dishonest mix-servers based on the limited number pairs, it conducts the encryption and the verification stages again, and identifies remaining dishonest mix-servers if exist. Here, re-executions of the stages do not degrade the performance in actual applications because usually *A* or mix-servers do not behave dishonestly as discussed previously.

**3.4.3. Data Holders without Responses**

In the decryption stage, authority *A* can force each anonymous data holder P to honestly report decrypted pair E^{*}_{0}(X(P)) = {X(P), Z^{R∙u*}^{(N)}^{∙r*∙v*}} corresponds to it as below. *A* in the verification stage also can force each P to report pair <E_{0}(X_{P}(q, 1)), E_{0}(X_{P}(q))> honestly in the same way.

When no one appears as the holder of pair E^{*}_{0}(X(P)), conceptually, *A* asks all registered data holders to calculate used seals of their credentials from value Z^{u*}^{(N)}^{∙r*∙v*}, which is calculated by M_{1}, ---, M_{T} as same as Z^{R}^{∙}^{u*(N)}^{∙}^{r}^{*} in Sec. 3.2.3, while disclosing their identities, and identifies P that calculates (Z^{u*}^{(N)}^{∙r*∙v*})^{R} as the holder. Namely, only P that knows R in credential S(P, R) can calculate holder part value Z^{R∙u*}^{(N)}^{∙r*∙v*} in E^{*}_{0}(X(P)) from Z^{u*}^{(N)}^{∙r*∙v*} and P must calculate it honestly.

But if honest data holder P_{j} calculates (Z^{u*}^{(T)}^{∙r*∙v*})^{R}^{(j)}, because P_{j} is disclosing its identity *A* can know that pair E^{*}_{0}(X(P_{j})) = {X(P_{j}), Z^{R}^{(j)}^{∙u*}^{(N)}^{∙r*∙v*}} belongs to P_{j} despite P_{j} is honest. Therefore instead of (Z^{u*}^{(N)}^{∙r*∙v*})^{R}^{(j)}, P_{j} calculates used seal (Z^{u*}^{(N)}^{∙r*∙v*∙}^{μ})^{R}^{(j)} while generating its secret integer μ. In detail, P_{j} calculates pair {Z_{*}^{μ} = Z^{u*}^{(N)}^{∙r*∙v*∙}^{μ}, Z_{R}^{μ} = Z^{R∙u*}^{(N)}^{∙r*∙v*∙}^{μ}} from Z_{*} = Z^{u*}^{(N)}^{∙r*∙v*} and Z_{R} = Z^{R∙u*}^{(N)}^{∙r*∙v*}, and calculates used seal (Z_{*}^{μ})^{R}^{(j)} to show it with pair{Z_{*}^{μ}, Z_{R}^{μ}}, after that *A* compares (Z_{*}^{μ})^{R}^{(j)} and Z_{R}^{μ}. Then, P_{j} can conceal the correspondence between it and E^{*}_{0}(X(P_{j})) because P_{j} did not calculate (Z_{*}^{μ})^{R}^{(j)} before.

Here, *A* can confirm that P_{j} used same μ for calculating Z_{*}^{μ} and Z_{R}^{μ} without knowing μ as same as in Sec. 3.4.1 ^{[12]}. But it must be noted that different from pair in Sec. 3.4.1, P that knows its secret integer R can calculate Z_{R} in pair {Z_{*}, Z_{R}} as a function of Z_{*}, i.e. Z_{R} = Z_{*}^{R}. Therefore, when P defines integers μ_{*} and μ_{2} arbitrarily, calculates μ_{1} as μ_{1} = (R+1)μ_{*}-Rμ_{2} and reports pair {Z_{*}^{μ}^{1}, Z_{R}^{μ}^{2}} instead of {Z_{*}^{μ}, Z_{R}^{μ}}, for Z_{*}^{δ1}, Z_{R}^{δ}^{2} and (Z_{*}Z_{R})^{δ3} that *A* calculates by using its secret integers δ_{1}, δ_{2}, δ_{3}, P can show consistent values (Z_{*}^{δ1})^{μ}^{1}, (Z_{R}^{δ}^{2})^{μ}^{2} and {(Z_{*}Z_{R})^{δ3}}^{μ}^{*}. Namely, (Z_{*}^{δ1})^{μ}^{1} = Z_{*}^{μ}^{1∙δ1}, (Z_{R}^{δ}^{2})^{μ}^{2} = Z_{R}^{μ2}^{∙δ2} and {(Z_{*}Z_{R})^{δ3}}^{μ}^{*} = {(Z_{*}^{R+1})^{δ3}}^{μ}^{*} = (Z_{*}^{μ}^{1+R∙}^{μ2})^{δ3} = (Z_{*}^{μ1}Z_{R}^{μ2})^{δ3}.

To disable P to use relation Z_{R} = Z_{*}^{R}, *A* defines integer β and examines consistencies of 2 pairs {β^{μ}, Z_{*}^{μ}} and {β^{μ}, Z_{R}^{μ}}. Then, because P cannot represent β or Z_{*} as a function of Z_{*} or β, P must calculate β^{μ} and Z_{*}^{μ} by using same integer μ. In the same way, P must calculate β^{μ} and Z_{R}^{μ} by using same integer μ, as a consequence, *A* can convince itself that Z_{*}^{μ} and Z_{R}^{μ} were calculated by same integer μ.

### 4. Conclusion

As above, linear Mix-nets based on LE-based encryption functions can calculate linear combinations of real numbers owned by same data holders while preserving privacies of data holders and protecting encryption functions from plain text attacks. Here, it is apparent that linear Mix-nets can have totally the same features even if MA-based encryption functions are used instead of LE-based ones. Therefore, when LE-based encryption functions are replaced with MA-based ones which are both additive and multiplicative, they can calculate also general polynomial functions of attribute values.

About dishonesties of relevant entities, proposed linear Mix-net successfully detects inconsistent encryption and decryption results, and identifies dishonest entities to generate correct results without disclosing secrets of honest entities. An advantage in handling dishonesties is data holders cannot behave dishonestly. Therefore, together with the fact that authority *A* or mix-servers do not behave dishonestly usually (because they are not anonymous and their dishonesties are necessarily revealed), procedures including re-executions of stages for identifying dishonest entities and re-calculating correct encryption and decryption results do not degrade the performance in actual applications.

### References

[1] | Diffie, W. and Hellman, M. E., “New directions in cryptography,” IEEE Trans. On Information Theory, IT-22 (6). 644-654. 1976. | ||

In article | CrossRef | ||

[2] | Chaum, D., “Untraceable electronic mail, return address and digital pseudonyms,” Communications of the ACM, 24 (2). 84-88. 1981. | ||

In article | CrossRef | ||

[3] | Cormen, T., Leiserson, C., Rivest, R. and Stein, C., Introduction to algorithms, MIT Press and McGraw-Hill, 2001. | ||

In article | |||

[4] | Lee, B., Boyd, C., Dawson, E., Kim, K., Yang, J., and Yoo, S., “Providing receipt-freeness in Mixnet-based voting protocols,” Proc. of the ICISC ’03, 261-274. 2003. | ||

In article | |||

[5] | Golle, P. and Jakobsson, M., “Reusable anonymous return channels,” Proc. of the 2003 ACM Workshop on Privacy in the Electronic Society, 94-100. 2003. | ||

In article | |||

[6] | Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A. and Shacham, H., “Randomizable proofs and delegatable anonymous credentials,” Proc. of the 29th Annual International Cryptology Conference on Advances in Cryptology, 108-125. 2009. | ||

In article | |||

[7] | Shahandashti, S. F. and Safavi-Naini, R., “Threshold attribute-based signatures and their application to anonymous credential systems,” Proc. of the 2nd International Conference on Cryptology in Africa: Progress in Cryptology, 198-216. 2009. | ||

In article | |||

[8] | Gentry, C., “Fully homomorphic encryption using ideal lattices,” Proc. of Symposium on theory of computing –STOC 2009, 169-178. 2009. | ||

In article | |||

[9] | Chung, K., Kalai, Y. and Vadhan, S., “Improved Delegation of Computation Using Fully Homomorphic Encryption,” CRYPT 2010, LNCS 6223, 483-501. 2010. | ||

In article | |||

[10] | Tamura, S., Anonymous Security Systems and Applications: Requirements and Solutions, Information Science Reference, 2012. | ||

In article | CrossRef | ||

[11] | Tamura, S. and Taniguchi, S., “A scheme for collecting anonymous data,” Proc. of IEEE-ICIT2013, 1210-1215. 2013. | ||

In article | |||

[12] | Tamura, S. and Taniguchi, S., “Enhanced Anonymous Tag Based Credentials,” Information Security and Computer Fraud, 2 (1). 10-20. 2014. | ||

In article | |||