Automatically assigned DDC number: 004015113
Manually assigned DDC number: 00582

Number of references: 8

Title: How to Privatize Random Bits

Author:

Subject: Marius Zimand How to Privatize Random Bits

Description: The paper investigates the extent to which a public source of random bits can be used to obtain private random bits that can be safely used in cryptographic protocols. We consider two cases: (a) the case in which the part privatizing random bits is computationally more powerful than the adversary, and (b) the case in which the part privatizing random bits has a small number of private random bits. The first case corresponds to randomized hard functions and the second variant corresponds to randomized pseudo-random generators. We show the existence of strong randomized hard functions and pseudo-random generators. As a side effect, it is shown that relative to a random oracle P=poly is not measurable in EXP in the resource-bounded theoretical sense and a very strong separation between sublinear time and AC 0 is obtained. Keywords: one-way function, pseudo-random generator, hard function. Supported in part by grant NSF-CCR-8957604, NSF-INT-9116781/JSPS-ENG-207 and NSF-CCR9322513. 1 Int...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-04-29

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/174773.html

Source: http://hypatia.dcs.qmw.ac.uk/data/edu/cs.rochester.edu/theory/96.tr616.How_to_privatize_random_bits.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/21971.html" Type="article" CiteSeer_Book="Journal of Computer and System Sciences" CiteSeer_Volume="41" Title="On Uniformity within {NC},">

<identifier Org="ISBN:0387986006" Paper_ID="/21971.html" Extracted="0387986006" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:0780342674" Paper_ID="/21971.html" Extracted="0780342674" DDC="511" Normalized_DDC="511" Normalized_Weight="0.125" />

<identifier Org="ISBN:0818608668" Paper_ID="/21971.html" Extracted="0818608668" DDC="511" Normalized_DDC="511" Normalized_Weight="0.125" />

<identifier Org="ISBN:081862955X" Paper_ID="/21971.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:0849326494" Paper_ID="/21971.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897916425" Paper_ID="/21971.html" Extracted="0897916425" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897917308" Paper_ID="/21971.html" Extracted="0897917308" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897918886" Paper_ID="/21971.html" Extracted="0897918886" />

<identifier Org="ISBN:1581136706" Paper_ID="/21971.html" Extracted="1581136706" />

<identifier Org="ISBN:3540578870" Paper_ID="/21971.html" Extracted="3540578870" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540699368" Paper_ID="/21971.html" Extracted="3540699368" />

<identifier Org="ISBN:3540742395" Paper_ID="/21971.html" Extracted="3540742395" />

<identifier Org="ISBN:354074455X" Paper_ID="/21971.html" Extracted="354074455X" />

<identifier Org="ISBN:3540792279" Paper_ID="/21971.html" Extracted="3540792279" />

</rec>

<rec ID="/42137.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="Construction of Pseudorandom Generator from any One-Way Function,">

<identifier Org="ISBN:0471222011" Paper_ID="/42137.html" Extracted="0471222011" DDC="004.67/8/03" Normalized_DDC="00467803" Normalized_Weight="0.1" />

<identifier Org="ISBN:0897918886" Paper_ID="/42137.html" Extracted="0897918886" />

<identifier Org="ISBN:0897918916" Paper_ID="/42137.html" Extracted="0897918916" />

<identifier Org="ISBN:1581131844" Paper_ID="/42137.html" Extracted="1581131844" />

<identifier Org="ISBN:1581133499" Paper_ID="/42137.html" Extracted="1581133499" />

<identifier Org="ISBN:1581139608" Paper_ID="/42137.html" Extracted="1581139608" />

<identifier Org="ISBN:1880446189" Paper_ID="/42137.html" Extracted="1880446189" />

<identifier Org="ISBN:3540206434" Paper_ID="/42137.html" Extracted="3540206434" DDC="330/.01/519536" Normalized_DDC="33001519536" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540210008" Paper_ID="/42137.html" Extracted="3540210008" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540406743" Paper_ID="/42137.html" Extracted="3540406743" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540632484" Paper_ID="/42137.html" Extracted="3540632484" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.1" />

<identifier Org="ISBN:354064766X" Paper_ID="/42137.html" Extracted="354064766X" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540647813" Paper_ID="/42137.html" Extracted="3540647813" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540648925" Paper_ID="/42137.html" Extracted="3540648925" DDC="005.82" Normalized_DDC="00582" Normalized_Weight="0.1" />

<identifier Org="ISBN:354065013X" Paper_ID="/42137.html" Extracted="354065013X" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540725393" Paper_ID="/42137.html" Extracted="3540725393" />

<identifier Org="ISBN:3540858547" Paper_ID="/42137.html" Extracted="3540858547" />

<identifier Org="ISBN:3642010008" Paper_ID="/42137.html" Extracted="3642010008" />

<identifier Org="ISBN:4431708642" Paper_ID="/42137.html" Extracted="4431708642" />

<identifier Org="ISBN:9812709991" Paper_ID="/42137.html" Extracted="9812709991" DDC="515/.2433" Normalized_DDC="5152433" Normalized_Weight="0.1" />

</rec>

<rec ID="/153087.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="How to Recycle Random Bits,">

<identifier Org="ISBN:0818619821" Paper_ID="/153087.html" Extracted="0818619821" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:081862082X" Paper_ID="/153087.html" Extracted="081862082X" />

<identifier Org="ISBN:0897918002" Paper_ID="/153087.html" Extracted="0897918002" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897918886" Paper_ID="/153087.html" Extracted="0897918886" />

<identifier Org="ISBN:0897919521" Paper_ID="/153087.html" Extracted="0897919521" />

<identifier Org="ISBN:1581139608" Paper_ID="/153087.html" Extracted="1581139608" />

<identifier Org="ISBN:3540282394" Paper_ID="/153087.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540441476" Paper_ID="/153087.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540587152" Paper_ID="/153087.html" Extracted="3540587152" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540600841" Paper_ID="/153087.html" Extracted="3540600841" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540601767" Paper_ID="/153087.html" Extracted="3540601767" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540609229" Paper_ID="/153087.html" Extracted="3540609229" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540653856" Paper_ID="/153087.html" Extracted="3540653856" DDC="004.015118" Normalized_DDC="004015118" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540662243" Paper_ID="/153087.html" Extracted="3540662243" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540671412" Paper_ID="/153087.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:354078439X" Paper_ID="/153087.html" Extracted="354078439X" />

<identifier Org="ISBN:9810218761" Paper_ID="/153087.html" Extracted="9810218761" DDC="516.2/0285" Normalized_DDC="51620285" Normalized_Weight="0.08333333333333333" />

</rec>

<rec ID="/696884.html" Type="inproceedings" CiteSeer_Book="Structure in Complexity Theory Conference" CiteSeer_Volume="" Title="Circuit Size Relative to Pseudorandom Oracles,">

<identifier Org="ISBN:0780331214" Paper_ID="/696884.html" Extracted="0780331214" />

<identifier Org="ISBN:0780399528" Paper_ID="/696884.html" Extracted="0780399528" DDC="016.6213" Normalized_DDC="0166213" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:0780399757" Paper_ID="/696884.html" Extracted="0780399757" />

<identifier Org="ISBN:0818620722" Paper_ID="/696884.html" Extracted="0818620722" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:0818622555" Paper_ID="/696884.html" Extracted="0818622555" />

<identifier Org="ISBN:081862955X" Paper_ID="/696884.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:0818640707" Paper_ID="/696884.html" Extracted="0818640707" />

<identifier Org="ISBN:2881249612" Paper_ID="/696884.html" Extracted="2881249612" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540565035" Paper_ID="/696884.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540609229" Paper_ID="/696884.html" Extracted="3540609229" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.14285714285714285" />

<identifier Org="ISBN:3540638768" Paper_ID="/696884.html" Extracted="3540638768" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.14285714285714285" />

</rec>

<rec ID="/699583.html" Type="inproceedings" CiteSeer_Book="Structure in Complexity Theory Conference" CiteSeer_Volume="" Title="Almost Everywhere High Nonuniform Complexity,">

<identifier Org="ISBN:0387949739" Paper_ID="/699583.html" Extracted="0387949739" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0521557364" Paper_ID="/699583.html" Extracted="0521557364" DDC="511.3/5" Normalized_DDC="51135" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0792343964" Paper_ID="/699583.html" Extracted="0792343964" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0818619589" Paper_ID="/699583.html" Extracted="0818619589" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0824700260" Paper_ID="/699583.html" Extracted="0824700260" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540228233" Paper_ID="/699583.html" Extracted="3540228233" DDC="004.1" Normalized_DDC="0041" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540240586" Paper_ID="/699583.html" Extracted="3540240586" DDC="005.3" Normalized_DDC="0053" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540430024" Paper_ID="/699583.html" Extracted="3540430024" DDC="005" Normalized_DDC="005" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540575685" Paper_ID="/699583.html" Extracted="3540575685" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540583254" Paper_ID="/699583.html" Extracted="3540583254" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540590420" Paper_ID="/699583.html" Extracted="3540590420" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540602496" Paper_ID="/699583.html" Extracted="3540602496" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540609229" Paper_ID="/699583.html" Extracted="3540609229" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540638768" Paper_ID="/699583.html" Extracted="3540638768" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540642307" Paper_ID="/699583.html" Extracted="3540642307" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540671412" Paper_ID="/699583.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540679014" Paper_ID="/699583.html" Extracted="3540679014" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540735445" Paper_ID="/699583.html" Extracted="3540735445" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />

</rec>

<rec ID="/38025.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="New Algorithms for Finding Irreducible Polynomials over Finite Fields,">

<identifier Org="ISBN:0387949739" Paper_ID="/38025.html" Extracted="0387949739" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.125" />

<identifier Org="ISBN:0521398770" Paper_ID="/38025.html" Extracted="0521398770" DDC="512/.7" Normalized_DDC="5127" Normalized_Weight="0.125" />

<identifier Org="ISBN:0521516447" Paper_ID="/38025.html" Extracted="0521516447" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.125" />

<identifier Org="ISBN:0769514685" Paper_ID="/38025.html" Extracted="0769514685" />

<identifier Org="ISBN:0769518796" Paper_ID="/38025.html" Extracted="0769518796" />

<identifier Org="ISBN:0818665823" Paper_ID="/38025.html" Extracted="0818665823" />

<identifier Org="ISBN:0821808176" Paper_ID="/38025.html" Extracted="0821808176" DDC="512/.3" Normalized_DDC="5123" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897913612" Paper_ID="/38025.html" Extracted="0897913612" />

<identifier Org="ISBN:0897918886" Paper_ID="/38025.html" Extracted="0897918886" />

<identifier Org="ISBN:0898713137" Paper_ID="/38025.html" Extracted="0898713137" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540206434" Paper_ID="/38025.html" Extracted="3540206434" DDC="330/.01/519536" Normalized_DDC="33001519536" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540527680" Paper_ID="/38025.html" Extracted="3540527680" DDC="510 s" Normalized_DDC="51" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540705740" Paper_ID="/38025.html" Extracted="3540705740" />

<identifier Org="ISBN:9812385703" Paper_ID="/38025.html" Extracted="9812385703" DDC="512/.3" Normalized_DDC="5123" Normalized_Weight="0.125" />

</rec>

<rec ID="/19779.html" Type="inproceedings" CiteSeer_Book="SODA ACMSIAM Symposium on Discrete Algorithms A Conference on Theoretical and Experimental Analysis of Discrete Algorithms" CiteSeer_Volume="" Title="Chernoff-Hoeffding Bounds for Applications with Limited Independence,">

<identifier Org="ISBN:0792352858" Paper_ID="/19779.html" Extracted="0792352858" DDC="519.7/6" Normalized_DDC="51976" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0792369572" Paper_ID="/19779.html" Extracted="0792369572" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0898713137" Paper_ID="/19779.html" Extracted="0898713137" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0898713668" Paper_ID="/19779.html" Extracted="0898713668" />

<identifier Org="ISBN:1584883014" Paper_ID="/19779.html" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:1883276519" Paper_ID="/19779.html" Extracted="1883276519" />

<identifier Org="ISBN:3540220577" Paper_ID="/19779.html" Extracted="3540220577" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540228942" Paper_ID="/19779.html" Extracted="3540228942" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:354024252X" Paper_ID="/19779.html" Extracted="354024252X" DDC="004.65" Normalized_DDC="00465" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540571558" Paper_ID="/19779.html" Extracted="3540571558" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540603131" Paper_ID="/19779.html" Extracted="3540603131" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540609229" Paper_ID="/19779.html" Extracted="3540609229" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540638768" Paper_ID="/19779.html" Extracted="3540638768" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540646221" Paper_ID="/19779.html" Extracted="3540646221" DDC="511/.6" Normalized_DDC="5116" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:354066694X" Paper_ID="/19779.html" Extracted="354066694X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540679960" Paper_ID="/19779.html" Extracted="3540679960" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.07142857142857142" />

</rec>

<rec ID="/171710.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="On the Size of Classes with Weak Membership Properties,">

<identifier Org="ISBN:0444828419" Paper_ID="/171710.html" Extracted="0444828419" DDC="511.352" Normalized_DDC="511352" Normalized_Weight="0.5" />

<identifier Org="ISBN:3540674195" Paper_ID="/171710.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.5" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="How to Privatize Random Bits" />

</references_metadata>