Peter's Reading List
From NSAC @ Stony Brook
To read:
- Elliptic Curves. Princeton Mathematical Notes, vol. 40, Princeton University Press, Princeton, New Jersey, 1992.
- P. Lin and K. S. Candan. Hiding traversal of tree structured data from untrusted data stores (http://aria.asu.edu/candan/papers/isi2003.pdf)
- Database privacy: http://research.microsoft.com/research/sv/DatabasePrivacy/
- http://www.csie.ntu.edu.tw/~lyuu/theses/thesis_r89032.pdf
- http://www.cs.umass.edu/~miklau/pubs/jcss06MS/miklau06disclosure.pdf
- http://www.pdl.cmu.edu/Secure/S4.html
- http://www.cs.brown.edu/people/nikos/papers/cbhdp.pdf
- Benny Chor. Niv Gilboa. Moni Naor. Private Information Retrieval by Keywords.
- Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. Public Key Encryption with Keyword Search. In C. Cachin, editor, Proceedings of Eurocrypt 2004.
- http://www.zurich.ibm.com/~cca/talks/ccstut.pdf
- J. Bethencourt, H. Chan, A. Perrig, E. Shi, and D. Song. Anonymous multi-attribute encryption with range query and conditional decryption. Technical report, C.M.U, 2006. CMU-CS- 06-135.
- John Bethencourt, Dawn Song, and Brent Waters. New constructions and practical applications for private stream searching. In Proceeding of 2006 IEEE Symposium on Security and Privacy, 2006.
- Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-dnf formulas on ciphertexts. In Joe Kilian, editor, Proceedings of Theory of Cryptography Conference 2005, volume 3378 of LNCS, pages 325. Springer, 2006
- Dan Boneh, Amit Sahai, and Brent Waters. Fully collusion resistant traitor tracing with short ciphertexts and private keys. In Eurocrypt '06, 2006.
- Dan Boneh and Brent Waters. A fully collusion resistant broadcast trace and revoke system with public traceability. 2006.
- Xavier Boyen and Brent Waters. Anonymous hierarchical identity-based encryption (without random oracles). 2006.
- Rafail Ostrovsky and William Skeith. Private searching on streaming data. In Proceedings of Crypto 2005, LNCS. Springer, 2005. Design and Implementation of the AEGIS Single-Chip Secure Processor Using Physical Random Functions
Read:
- Sean smith -- parallelizing PIR . "practical server privacy with secure coprocessors" http://www.cs.dartmouth.edu/~sws/pubs/ss01.pdf
- Improving the Robustness of Private Information Retrieval (http://www.cypherpunks.ca/~iang/pubs/robustpir.pdf)
- Shuhong Wang and Xuhua Ding and Robert Deng and Feng Bao. Private Information Retrieval Using Trusted Hardware. ESORICS 2006.
- 1/28/2007, Alexander Iliev and Sean W. Smith. Faerieplay on Tiny Trusted Third Parties (Work in Progress). Not yet in print. 2006.
- 1/20/2007, Alina Oprea, Michael K. Reiter, Ke Yang. Space-Efficient Block Storage Integrity. In Proceedings of the 12th Annual Network and Distributed System Security Symposium (NDSS 2005). Instead of using cryptographic hashes to verify storage integrity, use the low entropy of the data to serve as self-validation. In their small sample (author's desktop usage for a month), they found that 98% of 1024-byte block accesses had sufficient lack of entropy to distinguish them from random blocks, which are all that an adversary would be able to produce. Client stores checksum for remainder of blocks.
- Oded Goldreich. Foundations of Cryptography.
- Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. Searchable encryption revisited: Consistency properties, relation to anonymous ibe, and extensions. In CRYPTO, pages 205-222, 2005.
- Eu-Jin Goh. Secure Indexes. Cryptology ePrint Archive, Report 2003/216. 2003.
- D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data
- Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill. Efficiently-searchable and deterministic asymmetric encryption. 2006
- Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. Cryptology ePrint Archive, Report 2006/210. 2006.
Outsourced encrypted data, searchable in constant time. Reveals access patterns/ search outcomes. Also offer a scheme that is robust under adaptive use, i.e., doesn't reveal information even when queries depend on the results of previous queries. - Oct 23: Alexander Illiev and Sean Smith. Private Information Storage with Logarithmic-space Secure Hardware. I-NetSec04: 3rd Working Conference on Privacy and Anonymity in Networked and Distributed Systems, Kluwer. Aug 2004.
Applying oblivious RAM to retrieval and update to untrusted storage via a secure CPU. O(nlogn) initial scramble via Batchers. Maintain an unsecured "accessed list" for sqrt(n) accesses after that point, as in oblivious RAM or Asonov's Almost optimal PIR. Then use a more sophisticated scrambling algorithm in future scrambles, that only shuffles secretly the accessed items and requires O(lgn) secure space / O(nlgn) time. Performance: seconds to perform a request, hours to asynchronously shuffle a 4000-record DB. - Oded Goldreich, Rafail Ostrovsky. Software Protection and Simulation on Oblivious RAMs.
In sqrt solution, access are somewhat reasonable at O(sqrt(N)), but the dominating overhead is the reshuffling required every sqrt(N) accesses, costing O(N lg(N) lg(N)) accesses. Amortizes to the barely sub-linear O(sqrt(N)*lg(N)*lg(N)). In the hierarchical solution they manage to delay the amount of time until reshuffling. Non-shuffle accesses reasonable at cost O(lg(N)*lg(N)). Amortized to O(lg(N)*lg(N)*lg(N)). Questions. 1) What mechanism to hide the values of memory. 2) How does Dmitry's PIR differ from the sqrt soln.
~~
- @inproceedings{ black02ciphers, author = "John Black and Phillip Rogaway", title = "Ciphers with Arbitrary Finite Domains", booktitle = "{CT}-{RSA}", pages = "114-130", year = "2002"}
- Christophe Layer and Hans-Jörg Pfleiderer A Reconfigurable Recurrent Bitonic Sorting Network for Concurrently Accessible Data. Springer Berlin, 2004.
- An Adaptive Packed-Memory Array: (M. Bender,Haodong Hu) PODS 2006 http://www.inf.uni-konstanz.de/disy/teaching/ws0607/filesystems/download/adaptivepackedmemoryarray.pdf
- Hiding Location Information from Location-Based Services http://www.cs.uwaterloo.ca/~uhengart/publications/palms07.pdf