An efficient and probabilistic secure bit-decomposition

Bharath Kumar Samanthula, Hu Chun, Wei Jiang

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

29 Citations (Scopus)

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

Other

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

Fingerprint

Decomposition
Cryptography

Keywords

  • bit-decomposition
  • encryption
  • security

Cite this

Samanthula, B. 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) https://doi.org/10.1145/2484313.2484386
Samanthula, Bharath Kumar ; Chun, Hu ; Jiang, Wei. / An efficient and probabilistic secure bit-decomposition. ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013. pp. 541-546
@inproceedings{75f1d52b693c44ad9057b1b023df126d,
title = "An efficient and probabilistic secure bit-decomposition",
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.",
keywords = "bit-decomposition, encryption, security",
author = "Samanthula, {Bharath Kumar} and Hu Chun and Wei Jiang",
year = "2013",
month = "5",
day = "27",
doi = "10.1145/2484313.2484386",
language = "English",
isbn = "9781450317672",
pages = "541--546",
booktitle = "ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security",

}

Samanthula, BK, 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, 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013, Hangzhou, China, 8/05/13. https://doi.org/10.1145/2484313.2484386

An efficient and probabilistic secure bit-decomposition. / Samanthula, Bharath Kumar; Chun, Hu; Jiang, Wei.

ASIA CCS 2013 - Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013. p. 541-546.

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

TY - GEN

T1 - An efficient and probabilistic secure bit-decomposition

AU - Samanthula, Bharath Kumar

AU - Chun, Hu

AU - Jiang, Wei

PY - 2013/5/27

Y1 - 2013/5/27

N2 - 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.

AB - 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.

KW - bit-decomposition

KW - encryption

KW - security

UR - http://www.scopus.com/inward/record.url?scp=84877991754&partnerID=8YFLogxK

U2 - 10.1145/2484313.2484386

DO - 10.1145/2484313.2484386

M3 - Conference contribution

AN - SCOPUS:84877991754

SN - 9781450317672

SP - 541

EP - 546

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

ER -

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