article

COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS

Authors:

Benny Applebaum,

Yuval Ishai,

Eyal KushilevitzAuthors Info & Claims

Computational Complexity, Volume 15, Issue 2

Pages 115 - 162

https://doi.org/10.1007/s00037-006-0211-8

Published: 01 June 2006 Publication History

Abstract

Randomizing polynomials allow representing a function f ( x ) by a low-degree randomized mapping $$\hat{f}(x, r)$$ whose output distribution on an input x is a randomized encoding of f ( x ). It is known that any function f in uniform $$\bigoplus$$ L/poly (and in particular in NC ¹) can be efficiently represented by degree-3 randomizing polynomials. Such a degree-3 representation gives rise to an NC ₄ ⁰ representation, in which every bit of the output depends on only four bits of the input.

In this paper, we study the relaxed notion of computationally private randomizing polynomials, where the output distribution of $$\hat{f}(x, r)$$ should only be computationally indistinguishable from a randomized encoding of f ( x ). We construct degree-3 randomizing polynomials of this type for every polynomial-time computable function, assuming the existence of a cryptographic pseudorandom generator (PRG) in uniform $$\bigoplus$$ L/poly. (The latter assumption is implied by most standard intractability assumptions used in cryptography.) This result is obtained by combining a variant of Yao's garbled circuit technique with previous "information-theoretic" constructions of randomizing polynomials.

We present several applications of computationally private randomizing polynomials in cryptography. In particular, we relax the sufficient assumptions for parallel constructions of cryptographic primitives, obtain new parallel reductions between primitives, and simplify the design of constant-round protocols for multiparty computation.

Cited By

View all

Brakerski ZYuen HLeonardi SGupta A(2022)Quantum garbled circuitsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520073(804-817)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520073
Kitagawa FNishimaki RTanaka K(2022)Obfustopia Built on Secret-Key Functional EncryptionJournal of Cryptology10.1007/s00145-022-09429-z35:3Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00145-022-09429-z
Shiehian S(2022)mrNISC from LWE with Polynomial ModulusSecurity and Cryptography for Networks10.1007/978-3-031-14791-3_21(481-493)Online publication date: 12-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14791-3_21
Show More Cited By

Recommendations

On Pseudorandom Generators with Linear Stretch in NC0

We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC 0 , namely ones in which each bit of the output depends on just a constant number of input bits. Previous constructions of such PRGs were limited to stretching a ...
From randomizing polynomials to parallel algorithms
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference

Randomizing polynomials represent a function f(x) by a low-degree randomized mapping p(x, r) over a finite field F such that, for any input x, the output distribution of p(x, r) depends only on the value of f(x). We study the class of functions f which ...
Computationally Private Randomizing Polynomials and Their Applications
CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity

Randomizing polynomials allow to represent a function f(x) by a low-degree randomized mapping f(x, r) whose output distribution on an input x is a randomized encoding of f(x). It is known that any function f in L/poly (and in particular in NC ) can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Computational Complexity Volume 15, Issue 2

June 2006

104 pages

ISSN:1016-3328

Issue’s Table of Contents

Publisher

Birkhauser Verlag

Switzerland

Publication History

Published: 01 June 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Brakerski ZYuen HLeonardi SGupta A(2022)Quantum garbled circuitsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520073(804-817)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520073
Kitagawa FNishimaki RTanaka K(2022)Obfustopia Built on Secret-Key Functional EncryptionJournal of Cryptology10.1007/s00145-022-09429-z35:3Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00145-022-09429-z
Shiehian S(2022)mrNISC from LWE with Polynomial ModulusSecurity and Cryptography for Networks10.1007/978-3-031-14791-3_21(481-493)Online publication date: 12-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14791-3_21
Kitagawa FNishimaki RTanaka K(2021)Simple and Generic Constructions of Succinct Functional EncryptionJournal of Cryptology10.1007/s00145-021-09396-x34:3Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00145-021-09396-x
Halevi SHazay CPolychroniadou AVenkitasubramaniam M(2021)Round-Optimal Secure Multi-party ComputationJournal of Cryptology10.1007/s00145-021-09382-334:3Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00145-021-09382-3
Chvojka PJager TSlamanig DStriecks C(2021)Versatile and Sustainable Timed-Release Encryption and Sequential Time-Lock Puzzles (Extended Abstract)Computer Security – ESORICS 202110.1007/978-3-030-88428-4_4(64-85)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-88428-4_4
Phalakarn KSuppakitpaisarn VAttrapadung NMatsuura K(2020)Constructive t-secure Homomorphic Secret Sharing for Low Degree PolynomialsProgress in Cryptology – INDOCRYPT 202010.1007/978-3-030-65277-7_34(763-785)Online publication date: 13-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65277-7_34
Ünal AAkgün MPfeifer N(2019)A Framework with Randomized Encoding for a Fast Privacy Preserving Calculation of Non-linear Kernels for Machine Learning Applications in Precision MedicineCryptology and Network Security10.1007/978-3-030-31578-8_27(493-511)Online publication date: 25-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-31578-8_27
Agrawal S(2019)Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and InstantiationAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17653-2_7(191-225)Online publication date: 19-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17653-2_7
Bitansky NVaikuntanathan V(2018)Indistinguishability Obfuscation from Functional EncryptionJournal of the ACM10.1145/323451165:6(1-37)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3234511
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On Pseudorandom Generators with Linear Stretch in NC0

From randomizing polynomials to parallel algorithms

Computationally Private Randomizing Polynomials and Their Applications