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. © 2013 ACM.
Recommended Citation
B. K. Samanthula et al., "An Efficient and Probabilistic Secure Bit-decomposition," ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, pp. 541 - 546, Association for Computing Machinery (ACM), May 2013.
The definitive version is available at https://doi.org/10.1145/2484313.2484386
Department(s)
Computer Science
Keywords and Phrases
bit-decomposition; encryption; security
International Standard Book Number (ISBN)
978-145031767-2
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Association for Computing Machinery, All rights reserved.
Publication Date
27 May 2013
