Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2011-07-26
2011-07-26
Woo, Isaac M (Department: 2155)
Data processing: database and file management or data structures
Database design
Data structure types
C707S802000, C707S822000, C707S828000
Reexamination Certificate
active
07987201
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: 7191333 (2007-03-01), Maddury et al.
patent: 2004/0250100 (2004-12-01), Agrawal 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(nimg id="CUSTOM-CHARACTER-00001" he="3.13mm" wi="1.78mm" file="US07987201-20110726-P00001.TIF" alt="custom character" img-content="character" img-format="tif" ?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 Appln No. US 2005/017618, mailed Nov. 30, 2006 (6 pages).
US Office Action for U.S. Appl. No. 12/365,833, Oct. 15, 2010, 8 pgs.
Japanese Office Action for corresponding Japanese Patent Application No. 2007-527450, Apr. 5, 2011, 15 pgs.
Cachin et al., “Computationally Private Information Retieval with Polylogarithimic Communication”, International Conference on the Theory and Application of Cryptographic Techniques, May 1999, pp. 402-414, Prague, Czech Republic.
US Office Action for related U.S. Appl. No. 12/365,840, May 3, 2011, 7 pgs.
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-2645165