TY - GEN

T1 - Efficient binary conversion for Paillier encrypted values

AU - Schoenmakers, B.

AU - Tuyls, P.T.

PY - 2006

Y1 - 2006

N2 - We consider the framework of secure n-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgård, and Nielsen at Eurocrypt 2001. When used with Paillier’s cryptosystem, this framework allows for efficient secure evaluation of any arithmetic circuit defined over , where N is the RSA modulus of the underlying Paillier cryptosystem.
In this paper, we extend the scope of the framework by considering the problem of converting a given Paillier encryption of a value into Paillier encryptions of the bits of x. We present solutions for the general case in which x can be any integer in {0,1,...,N – 1}, and for the restricted case in which x <N/(n2¿) for a security parameter ¿. In the latter case, we show how to extract the l least significant bits of x (in encrypted form) in time proportional to l, typically saving a factor of log2N /l compared to the general case.
Thus, intermediate computations that rely in an essential way on the binary representations of their input values can be handled without enforcing that the entire computation is done bitwise. Typical examples involve the relational operators such as <and =. As a specific scenario we will consider the setting for (approximate) matching of biometric templates, given as bit strings.

AB - We consider the framework of secure n-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgård, and Nielsen at Eurocrypt 2001. When used with Paillier’s cryptosystem, this framework allows for efficient secure evaluation of any arithmetic circuit defined over , where N is the RSA modulus of the underlying Paillier cryptosystem.
In this paper, we extend the scope of the framework by considering the problem of converting a given Paillier encryption of a value into Paillier encryptions of the bits of x. We present solutions for the general case in which x can be any integer in {0,1,...,N – 1}, and for the restricted case in which x <N/(n2¿) for a security parameter ¿. In the latter case, we show how to extract the l least significant bits of x (in encrypted form) in time proportional to l, typically saving a factor of log2N /l compared to the general case.
Thus, intermediate computations that rely in an essential way on the binary representations of their input values can be handled without enforcing that the entire computation is done bitwise. Typical examples involve the relational operators such as <and =. As a specific scenario we will consider the setting for (approximate) matching of biometric templates, given as bit strings.

U2 - 10.1007/11761679_31

DO - 10.1007/11761679_31

M3 - Conference contribution

SN - 3-540-34546-6

T3 - Lecture Notes in Computer Science

SP - 522

EP - 537

BT - Advances in Cryptology - Eurocrypt 2006 (Proceedings 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Saint Petersburg, Russia, May 28-June 1, 2006)

A2 - Vaudenay, S.

PB - Springer

CY - Berlin

ER -