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>

www.000webhost.com