International Association
for Cryptologic Research

In the context of fully-homomorphic-encryption, we consider the representation of large integers by their decomposition over a product of rings (through the Chinese Remainder Theorem) and introduce a new algorithm for the determination of the sign solely through the knowledge of ring-components. Our implementation with 128 bits of security delivers a correct result and a probability higher than 1-1.e-9 in less than 100 milliseconds for 32-bit integers on a laptop.