TY - GEN
T1 - Modulo reduction for Paillier encryptions and application to secure statistical analysis
AU - Guajardo, J.
AU - Mennink, B.
AU - Schoenmakers, B.
PY - 2010
Y1 - 2010
N2 - For the homomorphic Paillier cryptosystem we construct a protocol for secure modulo reduction, that on input of an encryption [[x]] with x of bit length l x and a public ‘modulus’ a of bit length l a outputs an encryption . As a result, a protocol for computing an encrypted integer division [[x div a]] is obtained. Surprisingly, efficiency of the protocol is independent of l x : the broadcast complexity of the protocol varies between O(nkl a ) and , for n parties and security parameter k, and it is very efficient in case of small l a (in practical cases l a often is much smaller than l x ). Our protocol allows for efficient multiparty computation of statistics such as the mean, the variance and the median, and it is therefore very applicable to surveys for the benefit of statistical analysis.
AB - For the homomorphic Paillier cryptosystem we construct a protocol for secure modulo reduction, that on input of an encryption [[x]] with x of bit length l x and a public ‘modulus’ a of bit length l a outputs an encryption . As a result, a protocol for computing an encrypted integer division [[x div a]] is obtained. Surprisingly, efficiency of the protocol is independent of l x : the broadcast complexity of the protocol varies between O(nkl a ) and , for n parties and security parameter k, and it is very efficient in case of small l a (in practical cases l a often is much smaller than l x ). Our protocol allows for efficient multiparty computation of statistics such as the mean, the variance and the median, and it is therefore very applicable to surveys for the benefit of statistical analysis.
U2 - 10.1007/978-3-642-14577-3_32
DO - 10.1007/978-3-642-14577-3_32
M3 - Conference contribution
SN - 978-3-642-14576-6
T3 - Lecture Notes in Computer Science
SP - 375
EP - 382
BT - Financial Cryptography and Data Security (14th International Conference, FC 2010, Tenerife, Canary Islands, January 25-28, 2010. Revised Selected Papers)
A2 - Sion, R.
PB - Springer
CY - Berlin
ER -