Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2011-05-10
2011-05-10
Woo, Isaac M (Department: 2166)
Data processing: database and file management or data structures
Database and file access
Query optimization
C707S722000, C707S736000, C707S758000, C707S781000, C707S791000
Reexamination Certificate
active
07941422
ABSTRACT:
A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database.
REFERENCES:
patent: 6438554 (2002-08-01), Di-Crescenzo et al.
patent: 2005/0097063 (2005-05-01), Benaloh
Office Action dated Feb. 24, 2009 for parent U.S. Appl. No. 11/133,836, filed May 19, 2005, 6 pages.
Cachin, et al., “Computationally private information retrieval with polylogarithmic communication”, Proceeding of Eurocrypt, Online 1999, accessed at http://www.springerlink.com, pp. 402-414.
Beimel, et al., “Breaking the 0(nΛ1/(2k-1)) barrier for information-theoretic private information retrieval”, 43rd Annual Symposium on Foundations of Computer Science, Vancouver, Canada, Nov. 2002, pp. 261-270.
PCT Written Opinion for PCT Appl. No. US 2005/017618, mailed Nov. 30, 2006 (6 pages).
PCT Search Report for PCT Appl. No. PCT/US2005/017618, mailed Oct. 10, 2005 (3 pages).
Chor et al., “Private Information Retrieval,” Journal of the ACM, 45, 1998 (earlier version in FOCS 95).
Ambainis “Upper Bound on the Communication Complexity of Private Information Retrieval,” Proceedings of the 24thICALP, 1997.
Chor and Gilboa “Computationally Private Information Retrieval,” Proceedings of 29thSTOC, pp. 304-313, 1997 (extended abstract only).
Kushilevitz, E. and Ostrovsky, R. “Replication is Not Needed: Single Database, Computationally Private Information Retrieval,” Proceedings of FOC '97, pp. 364-373.
Chang “Single-Database Private Information Retrieval with Logarithmic Communication,” Proceedings of 9thAustralasian Conference on Information Security and Privacy (ACISP 2004), Sydney, Australia, Lecture Notes in Computer Science, Springer Verlag.
Gentry Craig B.
Ramzan Zulfikar Amin
Blakely , Sokoloff, Taylor & Zafman LLP
NTT Docomo Inc.
Woo Isaac M
LandOfFree
Method and apparatus for communication efficient private... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for communication efficient private..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for communication efficient private... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2650648