Average-complexity ideal-security order-preserving encryption

US9037860B1 · kind B1 · utility

Assignee

• SAP SE · DE

Inventors

• Florian Kerschbaum · Walldorf, DE
• Axel Schroepfer · Heidenau, DE
• Patrick Grofig · Karlsruhe, DE
• Isabelle Hang · Darmstadt, DE
• Martin Haerterich · Wiesloch, DE
• Mathias Kohler · Blankenloch, DE
• Andreas Schaad · Bruchsal, DE
• Walter Tighzert · Heidelberg, DE

Key dates

• Filing date: Nov 22, 2013
• Grant date: May 19, 2015
• Expiry date: Nov 22, 2033

Classification

• Technology area (CPC H): Electricity
• CPC primary: H04L2209/76
• WIPO field: Digital communication
• WIPO sector: Electrical engineering

Abstract

Embodiments provide ideal security, order-preserving encryption (OPE) of data of average complexity, thereby allowing processing of the encrypted data (e.g. at a database server in response to received queries). Particular embodiments achieve high encryption efficiency by processing plaintext in the order preserved by an existing compression dictionary already available to a database. Encryption is based upon use of a binary search tree of n nodes, to construct an order-preserving encryption scheme having Ω(n) complexity and even O(n), in the average case. A probability of computationally intensive updating (which renders conventional OPE impractical for ideal security) is substantially reduced by leveraging the demonstrated tendency of a height of the binary search tree to be tightly centered around O(log n). An embodiment utilizing such an encryption scheme is described in the context of a column-store, in-memory database architecture comprising n elements. OPE according to embodiments is compatible with adjustable encryption approaches.