An efficient and probabilistic secure bit-decomposition

Bharath K.K. Samanthula, Hu Chun, Wei Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

Many secure data analysis tasks, such as secure clustering and classification, require efficient mechanisms to convert the intermediate encrypted integers into the corresponding encryptions of bits. The existing bit-decomposition algorithms either do not offer sufficient security or are computationally inefficient. In order to provide better security as well as to improve efficiency, we propose a novel probabilistic-based secure bit-decomposition protocol for values encrypted using public key additive homomorphic encryption schemes. The proposed protocol guarantees security as per the semi-honest security definition of secure multi-party computation (MPC) and is also very efficient compared to the existing method. Our protocol always returns the correct result, however, it is probabilistic in the sense that the correct result can be generated in the first run itself with very high probability. The computation time of the proposed protocol grows linearly with the input domain size in bits. We theoretically analyze the complexity of the proposed protocol with the existing method in detail.

Original languageEnglish
Title of host publicationASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security
Pages541-546
Number of pages6
DOIs
StatePublished - 27 May 2013
Event8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013 - Hangzhou, China
Duration: 8 May 201310 May 2013

Publication series

NameASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security

Other

Other8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013
CountryChina
CityHangzhou
Period8/05/1310/05/13

    Fingerprint

Keywords

  • bit-decomposition
  • encryption
  • security

Cite this

Samanthula, B. K. K., Chun, H., & Jiang, W. (2013). An efficient and probabilistic secure bit-decomposition. In ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security (pp. 541-546). (ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security). https://doi.org/10.1145/2484313.2484386