# US 2015/0149773 A1 · Average-complexity ideal-security order-preserving encryption

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0149773 A1
- Document ID: US20150149773A1
- Status: Published application
- Kind: A1
- Application number: 14/088,123
- Filed: 2013-11-22
- Published: 2015-05-28
- Earliest claimed: 2013-11-22
- Assignees: Sap SE
- Inventors: FLORIAN KERSCHBAUM; AXEL SCHROEPFER; PATRICK GROFIG; ISABELLE HANG; MARTIN HAERTERICH; MATHIAS KOHLER; ANDREAS SCHAAD; WALTER TIGHZERT
- Web page: https://patentgrep.com/patent/US20150149773A1

## CPC

- H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload}
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0637: {Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]}
- H04L 2209/76: Proxy, i.e. using intermediary entity to perform cryptographic operations
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

A computer-implemented method comprising:
causing an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
causing the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
causing the engine to update the data stored in the database according to an update probability;
causing the engine to create further encrypted data from the encrypted data;
causing the engine to send the further encrypted data to the server; and
causing the engine to send a cryptographic key to allow decryption of the further encrypted data.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 wherein the algorithm comprises constructing a binary search tree comprising n nodes.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1 wherein the database is in the structured query language (SQL).

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 wherein the database comprises a column-store in-memory database.

### Claim 8

A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising:
causing an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
causing the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
causing the engine to update the data stored in the database according to an update probability;
causing the engine to create further encrypted data from the encrypted data;
causing the engine to send the further encrypted data to the server; and
causing the engine to send a cryptographic key to allow decryption of the further encrypted data.

### Claim 9 (depends on 8)

A non-transitory computer readable storage medium as in claim 8 wherein the algorithm comprises constructing a binary search tree comprising n nodes.

### Claim 10 (depends on 9)

A non-transitory computer readable storage medium as in claim 9 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.

### Claim 11 (depends on 8)

A non-transitory computer readable storage medium as in claim 8 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.

### Claim 12 (depends on 8)

A non-transitory computer readable storage medium as in claim 8 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.

### Claim 13 (depends on 8)

A non-transitory computer readable storage medium as in claim 8 wherein the database is in the structured query language (SQL).

### Claim 14 (depends on 8)

A non-transitory computer readable storage medium as in claim 8 wherein the database comprises a column-store in-memory database.

### Claim 15

A computer system comprising:
one or more processors;
a software program, executable on said computer system, the software program configured to:
cause an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
cause the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
cause the engine to update the data stored in the database according to an update probability;
cause the engine to create further encrypted data from the encrypted data;
cause the engine to send the further encrypted data to the server; and
cause the engine to send a cryptographic key to allow decryption of the further encrypted data.

### Claim 16 (depends on 15)

A computer system as in claim 15 wherein the algorithm comprises constructing a binary search tree comprising n nodes.

### Claim 17 (depends on 16)

A computer system as in claim 16 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.

### Claim 18 (depends on 15)

A computer system as in claim 15 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.

### Claim 19 (depends on 15)

A computer system as in claim 15 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.

### Claim 20 (depends on 15)

A computer system as in claim 15 wherein the database comprises a column-store in-memory database.
