Article

Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority

Authors:

Takahiro Matsuda,

Koji ChidaAuthors Info & Claims

Information Security and Privacy: 23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, July 11-13, 2018, Proceedings

Pages 64 - 82

https://doi.org/10.1007/978-3-319-93638-3_5

Published: 11 July 2018 Publication History

Abstract

In this paper, we propose secret-sharing-based bit-decomposition and modulus-conversion protocols for a prime order ring with an honest majority: an adversary can corrupt parties of n parties and . Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an -bit element and, where in the passive security and in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are tuple of shares in and a share in, respectively, where is the modulus after the conversion. If k and n are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are bits and bits, respectively. Our key observation is that a quotient of additive shares can be computed from the least significant bits. If a secret a is “shifted” and additively shared as s so that, the least significant bits of determine q since p is an odd prime and the least significant bits of are 0s.

References

[1]

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS, pp. 805–817. ACM (2016)

[2]

Beimel, A.: Secure schemes for secret sharing and key distribution. Ph.D. thesis, Israel Institute of Technology (1996)

[3]

Bogdanov, D., Jõemets, M., Siim, S., Vaht, M.: Privacy-preserving tax fraud detection in the cloud with realistic data volumes. Cybernetica research report (2016)

[4]

Bogdanov D, Niitsoo M, Toft T, and Willemson J High-performance secure multi-party computation for data mining applications Int. J. Inf. Sec. 2012 11 6 403-418

Digital Library

[5]

Bos, J.W., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Efficient SIMD arithmetic modulo a Mersenne number. In: Antelo, E., Hough, D., Ienne, P. (eds.) 20th IEEE Symposium on Computer Arithmetic, ARITH 2011, 25–27 July 2011, Tübingen, Germany, pp. 213–221. IEEE Computer Society (2011)

[6]

Cramer R, Damgård I, and Ishai Y Kilian J Share conversion, pseudorandom secret-sharing and applications to secure computation Theory of Cryptography 2005 Heidelberg Springer 342-362

Digital Library

[7]

Damgård I, Fitzi M, Kiltz E, Nielsen JB, and Toft T Halevi S and Rabin T Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation Theory of Cryptography 2006 Heidelberg Springer 285-304

Digital Library

[8]

From, S.L., Jakobsen, T.: Secure multi-party computation on integers. Ph.D. thesis, University of Aarhus (2006)

[9]

Furukawa J, Lindell Y, Nof A, and Weinstein O Coron J-S and Nielsen JB High-throughput secure three-party computation for malicious adversaries and an honest majority Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 225-255

[10]

Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation. In: Shmoys, D.B. (ed.) STOC, pp. 495–504. ACM (2014)

[11]

Goldreich O The Foundations of Cryptography: Basic Applications 2004 Cambridge Cambridge University Press

[12]

Ikarashi, D., Kikuchi, R., Hamada, K., Chida, K.: Actively private and correct MPC scheme in from passively secure schemes with small overhead. IACR Cryptology ePrint Archive, vol. 2014, p. 304 (2014)

[13]

Ito M, Saito A, and Nishizeki T Secret sharing scheme realizing general access structure IEICE Trans. 1989 72 56-64

[14]

Kimura, E., Hamada, K., Kikuchi, R., Chida, K., Okamoto, K., Manabe, S., Kuroda, T., Matsumura, Y., Takeda, T., Mihara, N.: Evaluation of secure computation in a distributed healthcare setting. In: Proceedings of MIE2016 at HEC2016, pp. 152–156 (2016)

[15]

Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 259–276. ACM (2017)

[16]

Nishide T and Ohta K Okamoto T and Wang X Multiparty computation for interval, equality, and comparison without bit-decomposition protocol Public Key Cryptography – PKC 2007 2007 Heidelberg Springer 343-360

[17]

Reistad T and Toft T Lee D and Hong S Linear, constant-rounds bit-decomposition Information, Security and Cryptology – ICISC 2009 2010 Heidelberg Springer 245-257

[18]

Schoenmakers B and Tuyls P Vaudenay S Efficient binary conversion for Paillier encrypted values Advances in Cryptology - EUROCRYPT 2006 2006 Heidelberg Springer 522-537

Digital Library

[19]

Shamir A How to share a secret Commun. ACM 1979 22 11 612-613

Digital Library

[20]

Toft T Fischlin M Constant-rounds, almost-linear bit-decomposition of secret shared values Topics in Cryptology – CT-RSA 2009 2009 Heidelberg Springer 357-371

Digital Library

Cited By

Bobo WYang HHao MZhang JHe HZhang W(2025)SEPPDL: A Secure and Efficient Privacy-Preserving Deep Learning Inference Framework for Autonomous DrivingACM Transactions on Autonomous and Adaptive Systems10.1145/3708505Online publication date: 9-Jan-2025
https://doi.org/10.1145/3708505
Anderson EChase MDurak FLaine KWeng CLuo BLiao XXu JKirda ELie D(2024)Precio: Private Aggregate Measurement via Oblivious ShufflingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670280(1819-1833)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670280
Asharov GHamada KKikuchi RNof APinkas BTomida JMeng WJensen CCremers CKirda E(2023)Secure Statistical Analysis on Multiple Datasets: Join and Group-ByProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623119(3298-3312)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623119
Show More Cited By

Recommendations

Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest
CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted ...
Fast Large-Scale Honest-Majority MPC for Malicious Adversaries
Abstract
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. ...
High-Throughput Secure Three-Party Computation with an Honest Majority
Abstract
In the setting of secure multiparty computation, a set of parties wish to carry out a joint computation of their inputs while keeping them private. In this paper, we describe new information-theoretic protocols for secure three-party computation ... $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Information Security and Privacy: 23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, July 11-13, 2018, Proceedings

Jul 2018

836 pages

ISBN:978-3-319-93637-6

DOI:10.1007/978-3-319-93638-3

Editors:
Willy Susilo
University of Wollongong, Wollongong, NSW, Australia
,
Guomin Yang
University of Wollongong, Wollongong, NSW, Australia

© Springer International Publishing AG, part of Springer Nature 2018.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 July 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bobo WYang HHao MZhang JHe HZhang W(2025)SEPPDL: A Secure and Efficient Privacy-Preserving Deep Learning Inference Framework for Autonomous DrivingACM Transactions on Autonomous and Adaptive Systems10.1145/3708505Online publication date: 9-Jan-2025
https://doi.org/10.1145/3708505
Anderson EChase MDurak FLaine KWeng CLuo BLiao XXu JKirda ELie D(2024)Precio: Private Aggregate Measurement via Oblivious ShufflingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670280(1819-1833)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670280
Asharov GHamada KKikuchi RNof APinkas BTomida JMeng WJensen CCremers CKirda E(2023)Secure Statistical Analysis on Multiple Datasets: Join and Group-ByProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623119(3298-3312)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623119
Attrapadung NMorita HOhara KSchuldt JTeruya TTozawa KYin HStavrou ACremers CShi E(2022)Secure Parallel Computation on Privately Partitioned Data and ApplicationsProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560695(151-164)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560695
Asharov GHamada KIkarashi DKikuchi RNof APinkas BTakahashi KTomida JYin HStavrou ACremers CShi E(2022)Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy HittersProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560691(125-138)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560691
Attrapadung NMorita HOhara KSchuldt JTozawa KSuga YSakurai KDing XSako K(2022)Memory and Round-Efficient MPC Primitives in the Pre-Processing Model from Unit VectorizationProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3517407(858-872)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3517407
Lu YHara KOhara KSchuldt JTanaka K(2022)Efficient Two-Party Exponentiation from Quotient TransferApplied Cryptography and Network Security10.1007/978-3-031-09234-3_32(643-662)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-09234-3_32
Attrapadung NHanaoaka GMatsuda TMorita HOhara KSchuldt JTeruya TTozawa KKim YKim JVigna GShi E(2021)Oblivious Linear Group Actions and ApplicationsProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484584(630-650)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484584

View Options

View options

Figures

Tables

Media

View Table of Conten