SCAM: Secured Content Addressable Memory Based on Homomorphic Encryption
Song Bian, Masayuki Hiromoto, and Takashi Sato
Deptartment of Communications and Computer Engineering, School of Informatics, Kyoto University Yoshida-hon-machi, Sakyo, Kyoto 606-8501, Japan.
paper@easter.kuee.kyoto-u.ac.jp
ABSTRACT
We propose an implementation of a secured content addressable memory (SCAM) based on homomorphic encryption (HE), where HE is used to compute the word matching function without the processor knowing what is being searched and the result of matching. By exploiting the shallow logic structure (XNOR followed by AND) of content addressable memory (CAM), we show that SCAM can be implemented with only additive homomorphism, greatly improving the efficiency of the HE algorithm. In the proposed method, the logic of homomorphic XNOR-AND is replaced with homomorphic XOROR, requiring only simple additions to be performed on the ciphertext. We also show that our scheme can be implemented by highly parallelizable and simple hardware architecture. Through experiment, we demonstrate that our software implementation is already 403x faster than the fastest known algorithm. With the help of hardware, we can achieve an energy reduction per word match by a factor of 477 million times, making our SCAM scheme much more practical.
