# US 2018/0019866 A1 · Leakage-Free 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 2018/0019866 A1
- Document ID: US20180019866A1
- Status: Published application
- Kind: A1
- Application number: 15/209,003
- Filed: 2016-07-13
- Published: 2018-01-18
- Earliest claimed: 2016-07-13
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Florian Kerschbaum
- Web page: https://patentgrep.com/patent/US20180019866A1

## CPC

- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation}
- H04L 2209/12: Details relating to cryptographic hardware or logic circuitry
- H04L 2209/30: Compression, e.g. Merkle-Damgard construction
- 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 implement leakage-free order-preserving encryption by assigning a distinct ciphertext for each plaintext, including repeated plaintext whose ciphertext is randomly inserted. In order to conceal insertion order, the randomized ciphertexts are compressed to minimal ciphertext space. A uniform distribution is achieved by rotating about a modulus on the ciphertexts rather than the plaintexts. The resulting ciphertext distribution has no leakage from the ciphertexts—even if an adversary has perfect background knowledge on the distribution of plaintexts. The encryption may be further secured even against passive query monitoring attacks by hiding the access pattern using ε, δ-differential privacy, such that the adversary observing a sequence of queries will not learn the frequency of plaintext. The leakage-free order-preserving encryption may be converted into an adjustable encryption scheme to allow querying (e.g., on a remote server).

## Claims

### Claim 1

A computer-implemented method comprising:
encrypting plaintext into randomized ciphertext by inserting repeated plaintext elements at random locations;
converting the randomized ciphertext into a compressed ciphertext space according to a probabilistic encryption scheme;
performing a rotation of the compressed ciphertext space about a modulus to create distributed ciphertext;
communicating the distributed ciphertext for storage in a server database;
communicating a query to the server; and
decrypting a query result received from the server in response to the query.

### Claim 2 (depends on 1)

A method as in claim 1 further comprising encrypting the distributed ciphertext to a high strength according an adjustable encryption scheme for communication to the server, wherein the query result is decrypted from a lower strength of the adjustable encryption scheme.

### Claim 3 (depends on 2)

A method as in claim 2 wherein the adjustable encryption scheme stores a binary tree.

### Claim 4 (depends on 3)

A method as in claim 3 wherein the binary tree is self-balancing.

### Claim 5 (depends on 2)

A method as in claim 2 wherein the lower strength comprises deterministic encryption or order preserving encryption.

### Claim 6 (depends on 1)

A method as in claim 1 wherein decrypting the query result comprises updating the modulus based upon a further rotation performed at the server.

### Claim 7 (depends on 1)

A method as in claim 1 further comprising applying a differential privacy procedure to generate the query as a private query.

### Claim 8 (depends on 7)

A method as in claim 7 wherein the private query includes positive noise added by the differential privacy procedure.

### Claim 9 (depends on 7)

A method as in claim 7 further comprising the client engine communicating a fake query to the server.

### Claim 10

A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising:
encrypting plaintext, into randomized ciphertext by inserting repeated plaintext elements at random locations;
converting the randomized ciphertext into a compressed ciphertext space according to a probabilistic encryption scheme;
performing a rotation of the compressed ciphertext space about a modulus to create distributed ciphertext;
encrypting the distributed ciphertext to a high strength according an adjustable encryption scheme for communication to the server;
communicating the encrypted distributed ciphertext at the high strength to a server for storage in a database;
communicating a query to the server; and
decrypting a query result received from the server in response to the query, the query result being in a lower strength of the adjustable encryption scheme.

### Claim 11 (depends on 10)

A non-transitory computer readable storage medium as in claim 10 wherein the adjustable encryption scheme stores a binary tree.

### Claim 12 (depends on 11)

A non-transitory computer readable storage medium as in claim 11 wherein the binary tree is self-balancing.

### Claim 13 (depends on 10)

A non-transitory computer readable storage medium as in claim 10 wherein decrypting the query result comprises updating the modulus based upon a further rotation performed at the server.

### Claim 14 (depends on 10)

A non-transitory computer readable storage medium as in claim 10 wherein the method further comprises applying a differential privacy procedure to generate the query as a private query.

### Claim 15 (depends on 10)

A non-transitory computer readable storage medium as in claim 10 wherein the private query includes noise computed from a pseudo-random function.

### Claim 16

A computer system comprising:
one or more processors;
a software program, executable on said computer system, the software program configured to cause an in-memory database engine to:
receive distributed ciphertext achieved by rotation about a modulus and adjustably encrypted at a high strength;
store the distributed ciphertext at the high strength in a database;
receive a query;
decrypt the distributed ciphertext to a lower strength;
apply the query to the distributed ciphertext at the lower strength to produce a query result encrypted at the lower strength; and
communicate the query result to a client.

### Claim 17 (depends on 16)

A computer system as in claim 16 wherein the high strength comprises probabilistic encryption and the lower strength comprises deterministic encryption or order preserving encryption.

### Claim 18 (depends on 16)

A computer system as in claim 16 wherein the in-memory database engine is configured to,
further rotate the distributed ciphertext prior to storage in the database, and
communicate to the client an updated modulus.

### Claim 19 (depends on 16)

A computer system as in claim 16 wherein the in-memory database engine is configured to receive the query as a private query including positive noise.

### Claim 20 (depends on 16)

A computer system as in claim 16 wherein the in-memory database engine is configured to distinguish the query from a fake query also received from the client.
