NDLI: Linear Round Bit-Decomposition of Secret-Shared Values

Content Provider	IEEE Xplore Digital Library
Author	Veugen, T.
Copyright Year	2005
Abstract	In the field of signal processing in the encrypted domain, linear operations are usually easy to perform, whereas multiplications, and bitwise operations like comparison, are more costly in terms of computation and communication. These bitwise operations frequently require a decomposition of the secret value into bits. To minimize the communication complexity, previous studies have focused on solutions that require a constant number of communication rounds, often at the cost of a large number of multiplications. We develop a bit-decomposition protocol within a linear secret sharing system, where sharings of the bits are computed from an integer that is secret-shared among multiple parties. We consider new solutions that require fewer multiplications, but where the number of communication rounds is linear in the input size. Although our basic solution requires m communication rounds to extract the m least significant bits, we present a way of reducing it by an arbitrary factor, using additional precomputations. Given that the best constant round solutions need at least 23 communication rounds, our solution is preferable for integers up to 165 bits, leading to fewer rounds and a smaller number of secure multiplications. In one variant, it is even possible to compute all I bits through only one opening and one additional communication round containing l multiplications, when a precomputation phase of 2 + log₂ I rounds and 2^I-l-1 secure multiplications has been performed.
Sponsorship	IEEE Signal Processing Society
Starting Page	498
Ending Page	506
Page Count	9
File Size	1216490
File Format	PDF
ISSN	15566013
Volume Number	10
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Protocols Cryptography Complexity theory Equations Materials Logic gates secure multi-party computations linear secret sharing bit-decomposition Linear secret sharing
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Safety, Risk, Reliability and Quality

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Framework for Secure Computations With Two Non-Colluding Servers and Multiple Clients, Applied to Recommendations

A Blakley Secret Sharing Scheme without Trusted Share Distributed Center

Optimum Pixel Expansions for Threshold Visual Secret Sharing Schemes

Secure Comparison Protocols in the Semi-Honest Model

A Secure Multi-Party Protocol for Sharing Valuable Information in Public Safety Networks

Oblivious radix sort: an efficient sorting algorithm for practical secure multi-party computation.

General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme (2000)

Secure multi-party computation from any linear secret sharing scheme (2003).

Distributed Secret Sharing for Discrete Memoryless Networks

Linear Round Bit-Decomposition of Secret-Shared Values

Similar Documents

A Framework for Secure Computations With Two Non-Colluding Servers and Multiple Clients, Applied to Recommendations

A Blakley Secret Sharing Scheme without Trusted Share Distributed Center

Optimum Pixel Expansions for Threshold Visual Secret Sharing Schemes

Secure Comparison Protocols in the Semi-Honest Model

A Secure Multi-Party Protocol for Sharing Valuable Information in Public Safety Networks

Oblivious radix sort: an efficient sorting algorithm for practical secure multi-party computation.

General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme (2000)

Secure multi-party computation from any linear secret sharing scheme (2003).

Distributed Secret Sharing for Discrete Memoryless Networks

Linear Round Bit-Decomposition of Secret-Shared Values