System and method for order-preserving encryption for numeric data

Patent 7426752 Issued on September 16, 2008. Estimated Expiration Date:

January 5, 2024. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Residue number encryption and decryption system
Patent #: 5077793
Issued on: 12/31/1991
Inventor: Falk, et al.

Creation and distribution of cryptographic envelope
Patent #: 5673316
Issued on: 09/30/1997
Inventor: Auerbach, et al.

Method for changing passwords on a remote computer
Patent #: 5719941
Issued on: 02/17/1998
Inventor: Swift, et al.

Bilateral authentication and encryption system
Patent #: 6105133
Issued on: 08/15/2000
Inventor: Fielder, et al.

Cryptographic technique that provides fast encryption and decryption and assures integrity of a ciphertext message through use of a message authentication code formed through cipher block chaining of the plaintext message
Patent #: 6226742
Issued on: 05/01/2001
Inventor: Jakubowski, et al.

Sequence numbering mechanism to ensure execution order integrity of inter-dependent smart card applications Patent #: 6490720
Issued on: 12/03/2002
Inventor: Carlsen, et al.

Inventors

Assignee

International Business Machines Corporation

Application

No. 10752154 filed on 01/05/2004

US Classes:

726/26, PREVENTION OF UNAUTHORIZED USE OF DATA INCLUDING PREVENTION OF PIRACY, PRIVACY VIOLATIONS, OR UNAUTHORIZED DATA MODIFICATION726/27, Access control726/30By authorizing data

Examiners

Primary: Jung, David

Attorney, Agent or Firm

McSwain; Marc D.

International Class

G06F 17/30

Abstract

A system, method, and computer program product to automatically eliminate the distribution information available for reconstruction from a disguised dataset. The invention flattens input numerical values into a substantially uniformly distributed dataset, then maps the uniformly distributed dataset into equivalent data in a target distribution. The invention allows the incremental encryption of new values in an encrypted database while leaving existing encrypted values unchanged. The flattening comprises (1) partitioning, (2) mapping, and (3) saving auxiliary information about the data processing, which is encrypted and not updated. The partitioning is MDL based, and includes a growth phase for dividing a space into fine partitions and a prune phase for merging some partitions together.

Other References

Schneier. Applied Cryptography. John Wiley, second edition, 1996.
[27] D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In IEEE Symp. on Security and Privacy, Oakland, California, 2000.
R. Rivest. The MD5 message digest algorithm. RFC 1320, Apr. 1992.
National Institute of Standards and Technology, U.S. Department of Commerce. Digital Signature Standard, May 1994.
R. Vingralek. Gnatdb: A small-footprint, secure database system. In Proc. of the VLDB Conference, p. 884-893,Hong Kong, China, Aug. 2002.
D. R. Stinson. Cryptography: Theory and Practice. CRC Press, 2nd edition, 2002.
R. L. Rivest, L.Adelman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, p. 169-178, 1978.
J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific Publ. Co., 1989.
W. H. Press, S. A. Teukolsky,W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, second edition, 1992.
Oracle Corporation. Database Encryption in Oracle 8i, Aug. 2000.
T. M. Mitchell. Machine Learning, chapter 6. McGraw-Hill, 1997.
M. Mehta, R. Agrawal, and J. Rissanen. SLIQ: A fast scalable classifier for data mining. In Proc. of the Fifth Int'l Conference on Extending Database Technology (EDBT), Avignon, France, Mar. 1996.
A. Konig and G. Weikum. Combining histograms and parametric curve fitting for feedback-driven query result-size estimation. In Proc. of the 25th Int'l Conference on Very Large Databases (VLDB '99), 1999.
Y. E. Ioannidis. The history of histograms (abridged). In Proc. of 29th Int'l Conf. on Very Large Data Bases (VLDB), Berlin, Germany, Sep. 2003.
T. Hamilton. Error sends bank files to eBay. The Toronto Star, Sep. 15, 2003.
H. Hacigumus, B. R. Iyer, and S. Mehrotra. Providing database as a service. In Proc. of the Int'l Conf. on Data Engineering, San Jose, California, Mar. 2002.
H. Hacigumus, B. R. Iyer, C. Li, and S. Mehrotra. Executing SQL over encrypted data in the database-service-provider model. In Proc. of the ACM SIGMOD Conf. on Management of Data, Madison,Wisconsin, Jun. 2002.
S. C. Gultekin Ozsoyoglu, David Singer. Anti-tamper databases: Querying encrypted databases. In Proc. of the 17th Annual IFIP WG 11.3 Working Conference on Database and Applications Security, Estes Park, Colorado, Aug. 2003.
E. A. Fox, Q. F. Chen, A. M. Daoud, and L. S. Heath. Order preserving minimal perfect hash functions and information retrieval. ACM Transactions on Information Systems (TOIS), 9:281-308, 1991.
J. Feigenbaum, M. Y. Liberman, and R. N. Wright. Cryptographic protection of databases and software. In Proc. of the DIMACS Workshop on Distributed Computing and Cryptography, 1990.
J. Domingo i Ferror. A new privacy homomorphism and applications. Information Processing Letters, 60(5):277-282, 1996.
J. Domingo-Ferrer and J. Herrera-Joancomarti. A privacy homomorphism allowing field operations on encrypted data, 1998.
D. Denning. Cryptography and Data Security. Addison-Wesley, 1982.
E. Damiani, S. D. C. di Vimercati, S. Jajodia, S. Paraboschi, and P. Samarati. Balancing confidentiality and efficiency in untrusted relational DBMSs. In Proc. of the 10th ACM Conf. on Computer and Communications Security (CCS), Oct. 2003.
Z. J. Czech, G. Havas, and B. S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43(5):257-264, 1992.
C. Boyens and O. Gunther. Trust is not enough: Privacy and security in ASP and web service environments. In 6th East-European Conference on Advances in Databases and Information Systems, Bratislava, Slovakia, Sep. 2002.
L. Bouganimand, P. Pucheral. Chip-secured data access: Confidential data on untrusted servers. In Proc. of the VLDB Conference, p. 131-142,Hong Kong, China, Aug. 2002.
G. Bebek. Anti-tamper database research: Inference control techniques. Technical Report EECS 433 Final Report, Case Western Reserve University, Nov. 2002.
N. Ahituv, Y. Lapid, and S. Neumann. Processing encrypted data. Communications of the ACM, 30(9):777-780, 1987.
R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Hippocratic databases. In Proc. of the 28th Int'l Conference on Very Large Databases,Hong Kong, China, Aug. 2002.
A survey of data protection technologies Chung-Yen Chang; Electro Information Technology, 2005 IEEE International Conference on May 22-25, 2005 p. 6.
Rights protection for discrete numeric streams Sion, R.; Atallah, M.; Prabhaka, S.; Knowledge and Data Engineering, IEEE Transactions on vol. 18, Issue 5, May 2006 pp. 699-714.
Rights protection for categorical data Sion, R.; Atallah, M.; Prabhakar, S.; Knowledge and Data Engineering, IEEE Transactions on vol. 17, Issue 7, Jul. 2005 pp. 912-926.