NDLI: Randomizing polynomials: A new representation with applications to round-efficient secure computation

Content Provider	IEEE Xplore Digital Library
Author	Ishai, Y. Kushilevitz, E.
Copyright Year	2000
Abstract	Motivated by questions about secure multi-party computation, we introduce and study a new natural representation of functions by polynomials, which we term randomizing polynomials. "Standard" low-degree polynomials over a finite field are easy to compute with a small number of communication rounds in virtually any setting for secure computation. However, most Boolean functions cannot be evaluated by a polynomial whose degree is smaller than their input size. We get around this barrier by relaxing the requirement of evaluating f into a weaker requirement of randomizing f: mapping the inputs of f along with independent random inputs into a vector of outputs, whose distribution depends only on the value of f. We show that degree-3 polynomials are sufficient to randomize any function f, relating the efficiency of such a randomization to the branching program size of f. On the other hand, by characterizing the exact class of Boolean functions which can be randomized by degree-2 polynomials, we show that 3 is the minimal randomization degree of most functions. As an application, randomizing polynomials provide a powerful, general, and conceptually simple tool for the design of round-efficient secure protocols. Specifically, the secure evaluation of any function can be reduced to a secure evaluation of degree-3 polynomials. One corollary of this reduction is that two (respectively, three) communication rounds are sufficient for k parties to compute any Boolean function f of their inputs, with perfect information-theoretic [k-1/3]-privacy (resp., [k-1/2]-privacy), and communication complexity which is at most quadratic in the branching program size of f (with a small probability of one-sided error).
Starting Page	294
Ending Page	304
File Size	1207563
Page Count	11
File Format	PDF
ISBN	0769508502
ISSN	02725428
DOI	10.1109/SFCS.2000.892118
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-11-12
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Boolean functions Complexity theory Computer applications Protocols Computer errors Computer science Computational modeling Input variables Galois fields
Content Type	Text
Resource Type	Article

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