## Abstract

Deciding “greater-than” relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable. We construct the first implementable encryption system supporting greater-than comparisons on encrypted data that provides the “bestpossible” semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing k-bit values requires only a (k/2+1)-way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size. Beyond comparisons, our results give an implementable secret-key multi-input functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for k-bit inputs the branching program is of length k + 1 and width 4.

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings |

Editors | Marc Fischlin, Elisabeth Oswald |

Publisher | Springer Verlag |

Pages | 563-594 |

Number of pages | 32 |

ISBN (Print) | 9783662468029 |

DOIs | |

State | Published - Jan 1 2015 |

Externally published | Yes |

Event | 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 - Sofia, Bulgaria Duration: Apr 26 2015 → Apr 30 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9057 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 |
---|---|

Country | Bulgaria |

City | Sofia |

Period | 4/26/15 → 4/30/15 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)