Cryptography in $NC^0$ TeX Export

@article{citeulike:3441187, abstract = {We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing instances of these primitives by \$NC^0\$ functions, namely, by functions in which each output bit depends on a constant number of input bits. Despite previous efforts in this direction, there has been no convincing theoretical evidence supporting this possibility, which was posed as an open question in several previous works.}, address = {Philadelphia, PA, USA}, author = {Applebaum, Benny and Ishai, Yuval and Kushilevitz, Eyal}, citeulike-article-id = {3441187}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1328015}, citeulike-linkout-1 = {http://dx.doi.org/10.1137/S0097539705446950}, doi = {10.1137/S0097539705446950}, issn = {0097-5397}, journal = {SIAM J. Comput.}, keywords = {nc, one-way}, number = {4}, pages = {845--888}, posted-at = {2008-10-22 20:44:25}, priority = {2}, publisher = {Society for Industrial and Applied Mathematics}, title = {Cryptography in \$NC^0\$}, url = {http://dx.doi.org/10.1137/S0097539705446950}, volume = {36}, year = {2006} }

TY - JOUR ID - citeulike:3441187 L3 - citeulike-article-id:3441187 N2 - We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing instances of these primitives by $NC^0$ functions, namely, by functions in which each output bit depends on a constant number of input bits. Despite previous efforts in this direction, there has been no convincing theoretical evidence supporting this possibility, which was posed as an open question in several previous works. IS - 4 JF - SIAM J. Comput. SN - 0097-5397 AD - Philadelphia, PA, USA EP - 888 TI - Cryptography in $NC^0$ PB - Society for Industrial and Applied Mathematics VL - 36 SP - 845 KW - nc KW - one-way AU - Applebaum, Benny AU - Ishai, Yuval AU - Kushilevitz, Eyal PY - 2006/// UR - http://dx.doi.org/10.1137/S0097539705446950 ER -