Automatically assigned DDC number: 00582

Manually assigned DDC number: 00582

Number of references: 4

Title: Efficient Privatization of Random Bits

Author:

Subject: Marius Zimand Efficient Privatization of 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. This process is called privatization of random bits. We consider the case in which the party privatizing random bits has a small number of private random bits. Using techniques from the theory of pseudo-random generators and finely tailoring them for the specifics of this problem, we show that starting with cn private bits and using a long but public random string, one can produce 2 dn random bits that cannot be distinguished (but with exponentially small bias) from real random bits by any adversary circuits of size 2 0:499n . Keywords: one-way function, pseudo-random generator, random bits. 1 Introduction It is commonly accepted that random bits are a valuable computational resource. Unfortunately, random bits are hard and expensive to produce. Generating them by special-purpose devices such as Geiger counters or...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1999-04-01

Pubyear: 1997

Format: ps

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

Source: ftp://168.18.216.164/~zimand/papers/rand-privat.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

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

<references_metadata>

      <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="/147275.html"   Type="article"   CiteSeer_Book="Journal   of   Cryptology   the   journal   of   the   International   Association   for   Cryptologic   Research"   CiteSeer_Volume="5"   Title="Conditionally-perfect   secrecy   and   a   provably-secure   randomized   cipher,">

            <identifier   Org="ISBN:0809052172"   Paper_ID="/147275.html"   Extracted="0809052172"   />

            <identifier   Org="ISBN:0821865978"   Paper_ID="/147275.html"   Extracted="0821865978"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:1581134959"   Paper_ID="/147275.html"   Extracted="1581134959"   />

            <identifier   Org="ISBN:3540212582"   Paper_ID="/147275.html"   Extracted="3540212582"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540226680"   Paper_ID="/147275.html"   Extracted="3540226680"   DDC="005.82"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540243011"   Paper_ID="/147275.html"   Extracted="3540243011"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540253386"   Paper_ID="/147275.html"   Extracted="3540253386"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540266569"   Paper_ID="/147275.html"   Extracted="3540266569"   DDC="005.8/2"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540290397"   Paper_ID="/147275.html"   Extracted="3540290397"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540327312"   Paper_ID="/147275.html"   Extracted="3540327312"   DDC="005.82"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540401768"   Paper_ID="/147275.html"   Extracted="3540401768"   DDC="511/.8"   Normalized_DDC="5118"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:3540435530"   Paper_ID="/147275.html"   Extracted="3540435530"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540492437"   Paper_ID="/147275.html"   Extracted="3540492437"   DDC="005.8/2"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540606939"   Paper_ID="/147275.html"   Extracted="3540606939"   DDC="003/.54"   Normalized_DDC="00354"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540632476"   Paper_ID="/147275.html"   Extracted="3540632476"   DDC="005.8/2"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540663479"   Paper_ID="/147275.html"   Extracted="3540663479"   DDC="005.82"   Normalized_DDC="00582"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540730915"   Paper_ID="/147275.html"   Extracted="3540730915"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540741429"   Paper_ID="/147275.html"   Extracted="3540741429"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="/192548.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="On   Randomized   Cryptographic   Primitives,"   />

      <rec   ID="/174773.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="How   to   Privatize   Random   Bits,"   />

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Efficient   Privatization   of   Random   Bits"   />

</references_metadata>