Positional Characteristics for Efficient Number Comparison over the Homomorphic Encryption

Abstract

Modern algorithms for symmetric and asymmetric encryptions are not suitable to
provide security of data that needs data processing. They cannot perform calculations
over encrypted data without first decrypting it when risks are high. Residue Number
System (RNS) as a homomorphic encryption allows ensuring the confidentiality of the
stored information and performing calculations over encrypted data without
preliminary decoding but with unacceptable time and resource consumption. An
important operation for encrypted data processing is a number comparison. In RNS, it
consists of two steps: the computation of the positional characteristic of the number
in RNS representation and comparison of its positional characteristics in the
positional number system. In this paper, we propose a new efficient method to compute
the positional characteristic based on the approximate method. The approximate method
as a tool to compare numbers does not require resource-consuming non-modular
operations that are replaced by fast bit right shift operations and taking the least
significant bits. We prove that in case when the dynamic range of RNS is an odd
number, the size of the operands is reduced by the size of the module. If one of the
RNS moduli is a power of two, then the size of the operands is less than the dynamic
range. We simulate proposed method in the ISE Design Suite environment on the FPGA
Xilinx Spartan-6 SP605 and show that it gains 31% in time and 37% in the area on
average with respect to the known approximate method. It makes our method efficient
for hardware implementation of cryptographic primitives constructed over a prime
finite field.