Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Copyright: © 2012
|Pages: 9

DOI: 10.4018/978-1-4666-1649-3.ch008

Chapter Preview

TopLet us consider a case where entity S calculates the average of salaries of persons P_{1}, P_{2}, ---, P_{N}. In this case, usually salaries of persons are their secrets and they do not want to disclose them to others. Therefore mechanisms, which enable S to calculate the average of salaries without knowing those of individual persons, are necessary. Theoretically, there are protocols that enable N entities Q_{1}, Q_{2}, ---, Q_{N} to jointly calculate any function *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) while maintaining values of *x*_{1}, *x*_{2}, ---, *x*_{N} as secrets of their owners Q_{1}, Q_{2}, ---, Q_{N} (Goldreich, 1987, Yao, 1986). Then, entity S in the above case, can know the average of salaries while preserving privacies of P_{1}, P_{2}, ---, P_{N}, by asking each P_{j} to carry out these protocols. However, these protocols are complicated and as a consequence cannot be used in real applications. Although efficient protocols exist, they are applicable only when *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) is a Boolean expression (Naor, 1999). As practical schemes, this chapter discusses mechanisms based on encryption functions with the homomorphic property. But it must be noted that they are efficient only for limited kind of anonymous statistics calculations.

In the following, the above requirement is satisfied through 3 ways. The 1st way is the blind sum/product calculation scheme, the simplest one. There are 2 entities P and Q, where P encrypts its data *x*_{1}, *x*_{2}, ---, *x*_{N} to E(k_{P}, *x*_{1}), E(k_{P}, *x*_{2}), ---, E(k_{P}, *x*_{N}) by its encryption key k_{P}, and Q calculates *f*(E(k_{P}, *x*_{1}), E(k_{P}, *x*_{2}), ---, E(k_{P}, *x*_{N})) to be decrypted to *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) by P that knows decryption key k_{P}^{-1}. Then, P can calculate *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) without disclosing its owning data, and on the other hand, Q can conceal function *f*. Here, function *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) must have the specific forms, e.g. *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) = *x*_{1}+*x*_{2}+ --- +*x*_{N}, *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) = *x*_{1}*x*_{2} --- *x*_{N}, etc. of course.

The 2nd and the 3rd ones are general multi party computation schemes, where multiple entities P_{1}, P_{2}, ---, P_{N} jointly calculate *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) while maintaining the secrets of their owning values *x*_{1}, *x*_{2}, ---, *x*_{N}. In the 2nd way, each entity P_{j} that owns *x*_{j} (j = 1, 2, ---, N) divides E(k_{C}, *x*_{j}) (here, encrypted form E(k_{C}, *x*_{j}) calculated based on publicly known key k_{C} is a representation of *x*_{j}) into H-parts E(k_{C}, *x*_{j})_{1}, E(k_{C}, *x*_{j})_{2}, ---, E(k_{C}, *x*_{j})_{H} so that no one can know *x*_{j} without knowing all H-parts and anyone that knows k_{C} can reconstruct *x*_{j} when it knows all H-parts, and distributes individual parts E(k_{C}, *x*_{j})_{1}, E(k_{C}, *x*_{j})_{2}, ---, E(k_{C}, *x*_{j})_{H} to H-entities Q_{w1}, Q_{w2}, ---, Q_{wH} selected from Q_{1}, Q_{2}, ---, Q_{N}, respectively. Then, each Q_{wh} calculates *f*(E(k_{C}, *x*_{1})_{h}, E(k_{C}, *x*_{2})_{h}, ---, E(k_{C}, *x*_{N})_{h}), and finally, coordinating entity C gathers calculation results of Q_{w1}, Q_{w2}, ---, Q_{wH} to calculate *f*(E(k_{C}, *x*_{1}), E(k_{C}, *x*_{2}), ---, E(k_{C}, *x*_{N})), and from that *f*(*x*_{1}, *x*_{2}, ---, *x*_{N}) is reconstructed, where it is assumed that relation E(k_{C}, *f*(*x*_{1}, *x*_{2}, ---, *x*_{N})) = *f*(E(k_{C}, *x*_{1}), E(k_{C}, *x*_{2}), ---, E(k_{C}, *x*_{N})) is satisfied.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved