Microsoft Technology Licensing, LLC

University of California

The University of Texas System

Kristin E Lauter

Denis X Charles

Peter L Montgomery

Michael Naehrig

Anton Mityagin

Ran Gilad-Bachrach

Kim Laine

Anne Kirsten Eisentraeger

Hao Chen

Melissa Erin Chase

Kim Henry Martin Laine

John Wernsing

Eyal Zvi Goren

Nathan Dowlin

Ramarathnam R Venkatesan

Kamal Jain

Brian LaMacchia

David Junzi Wu

Vinod Vaikuntanathan

Yuhou Xia

Peter Byerley Rindal

Reinier M Broker

Joppe Willem Bos

Tony Feng

Jacob J Loftus

Gizem Selcan Cetin

Samuel James McKelvie

Chris Demetrios Karkanias

Josh D Benaloh

David A Nichols

Krysta Marie Svore

Mihir M Bellare

John D Mehr

Madanlal S Musuvathi

Martin Henri Roetteler

Elissa E S Murphy

Todd Douglas Mytkowicz

Vadym Kliuchnikov

Mathew James Dickson

Nishanth Chandran

Nicolo Fusi

Saeed Maleki

Adam Edward Paetznick

David Freeman

Olli Ilari Saarikivi

Erik J Horvitz

Elisabeth Malmskog

Ning Shang

Tonghai Yang

David Gruenewald

Dimitar Petkov Jetchev

Xiaoqian Jiang

Miran Kim

Yongsoo Song

Roshan Dathathri

Adriana Lopez-Alt

Olli Llari Saarikivi

A low-cost solution for performing a quantum operation provides for defining a target unitary that rotates a single qubit by a target rotation to place the qubit in a target state. The method further provides for identifying multiple projective rotation circuits that each implement an approximation of the target rotation upon successful measurement and assigning a selection probability to each of the multiple identified projective rotation circuits, the selection probability being defined by a metric that increases in value in proportion to a proximity between a qubit state resulting from the approximation and the target qubit state. The method further provides for probabilistically selecting one of the multiple projective rotation circuits according to the assigned selection probabilities and outputting a circuit definition that includes the selected projective rotation circuit.

Mixing techniques for probabilistic quantum circuits with fallback

A method, system and computer program product for performing computations on sensitive data while guaranteeing privacy. A service provider receives a first and a second ciphertext from a medical provider that homomorphically encrypts matrices A and B, respectively, using an encryption key, where the matrices A and B include medical data encoded as vectors. The service provider performs a homomorphic matrix multiplication on the first and second ciphertexts without decrypting the first and second ciphertexts. An encrypted result from the performed homomorphic matrix multiplication on the first and second ciphertexts is generated and transmitted to the medical provider to decrypt which matches a result of performing a matrix multiplication on unencrypted matrices A and B thereby enabling computations to be performed on the medical data in a secure manner.

Performing computations on sensitive data while guaranteeing privacy

In aspects of multiplication operations on homomorphic encrypted data, a computing device stores homomorphic encrypted data as a dataset, and implements an encryption application that can perform multiplication operations on ciphertexts in the homomorphic encrypted data, where the ciphertexts include polynomial variables of the ciphertexts. The encryption application can compute and store intermediate polynomial variables that are computed as the multiplication operations are performed. The encryption application can then utilize one or more of the intermediate polynomial variables rather than recomputing the intermediate polynomial variables as the multiplication operations are performed on the ciphertexts.

Multiplication operations on homomorphic encrypted data

Embodiments of the present invention provide systems, methods, and computer storage media directed to optimizing the generation, evaluation, and selection of tensor circuit specifications for a tensor circuit to perform homomorphic encryption operations on encrypted data. A computing device having an improved compiler and runtime configuration can obtain a tensor circuit and associated schema. The computing device can map the obtained tensor circuit to an equivalent tensor circuit, adapted to perform fully homomorphic encryption (FHE) operations, and instantiated based on the obtained associated scheme. The computing device can then monitor a flow of data through the equivalent FHE-adapted tensor circuit utilizing various tensor circuit specifications determined therefor. A cost of each tensor circuit specification can be determined by the computing device based on the monitored flow of data, so as to identify an optimal set of optimal tensor circuit specifications that can be employed by the obtained tensor circuit, to efficiently perform homomorphic encryption operations on encrypted data.

Homomorphic evaluation of tensor programs

Techniques for using different data sources for a predictive model are described. According to various implementations, techniques described herein enable different data sets to be used to generate a predictive model, while minimizing the risk that individual data points of the data sets will be exposed by the predictive model. This aids in protecting individual privacy (e.g., protecting personally identifying information for individuals), while enabling robust predictive models to be generated using data sets from a variety of different sources.

Using different data sources for a predictive model

In aspects of string matching in encrypted data, a computing device stores homomorphic encrypted data as a dataset, and implements a string matching application that receives an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset. The string matching application can compute, for each row of the dataset, a sum of some function of dataset bits and query bits for a row result, and multiply the row results of the computed rows to determine matching strings. Alternatively, the string matching application can compute, for each row of the dataset, a product over some function of the dataset bits and the query bits for a row result, and add the row results of the computed rows to determine matching strings.

String matching in encrypted data

In this application, example methods for performing quantum Montgomery arithmetic are disclosed. Additionally, circuit implementations are disclosed for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. This application also shows that elliptic curve discrete logarithms on an elliptic curve defined over an n-bit prime field can be computed on a quantum computer with at most 9n+2&#x250c;log(n)&#x2510;+10 qubits using a quantum circuit of at most 512nlog(n)+3572nToffoli gates.

Quantum resource estimates for computing elliptic curve discrete logarithms

The techniques and/or systems described herein are directed to improvements in genomic prediction using homomorphic encryption. For example, a genomic model can be generated by a prediction service provider to predict a risk of a disease or a presence of genetic traits. Genomic data corresponding to a genetic profile of an individual can be batch encoded into a plurality of polynomials, homomorphically encrypted, and provided to a service provider for evaluation. The genomic model can be batch encoded as well, and the genetic prediction may be determined by evaluating a dot product of the genomic model data the genomic data. A genomic prediction result value can be provided to a computing device associated with a user for subsequent decrypting and decoding. Homomorphic encoding and encryption can be used such that the genomic data may be applied to the prediction model and a result can be obtained without revealing any information about the model, the genomic data, or any genomic prediction.

Privacy-preserving genomic prediction

The subject disclosure is directed towards secure computations of encrypted data over a network. In response to user desired security settings with respect to the encrypted data, software/hardware library components automatically select parameter data for configuring a fully homomorphic encryption scheme to secure the encrypted data items while executing a set of computational operations. A client initiates the set of computational operations via the library components and if requested, receives secure computation results in return.

Managed secure computations on encrypted data

The techniques and/or systems described herein are directed to improvements in homomorphic encryption to improve processing speed and storage requirements. For example, the techniques and/or systems can be used on a client device to encode data to be sent to a remote server, to be operated on while maintaining confidentiality of data. For example, data including a real number can be encoded as a polynomial, with the fractional part of the real number encoded as high-order coefficients in the polynomial. Further, real numbers can be approximated and encoded in a polynomial using a fractional base, and/or the encoding can include slot encoding. Thus, the optimized encodings disclosed herein provide an optimized homomorphic encryption scheme.

Homomorphic encryption with optimized encoding

The techniques and/or systems described herein are directed to improvements in homomorphic encryption to improve processing speed and storage requirements. For example, the techniques and/or systems can be used on a client device to encode data to be sent to a remote server, to be operated on while maintaining confidentiality of data. The encoding scheme can be optimized by automatically selecting one or more parameters using an error growth simulator based on an actual program that operates on the encoded data. For example, the simulator can be used iteratively to determine an optimized parameter set which allows for improved homomorphic operations while maintaining security and confidentiality of a user's data.

Homomorphic encryption with optimized parameter selection

The techniques and/or systems described herein are directed to improvements in homomorphic operations within a homomorphic encryption scheme. The homomorphic operations may be performed on encrypted data received from a client device without decrypting the data at a remote computing device, thereby maintaining the confidentiality of the data. In addition to the operations of addition, subtraction, and multiplication, the homomorphic operations may include an approximate division, a sign testing, a comparison testing, and an equality testing. By combining these operations, a user may perform optimized operations with improved processor and memory requirements.

Homomorphic encryption with optimized homomorphic operations

A user device and one or more server computers securely evaluate a k-nearest neighbor model, with reasonable computation speed and bandwidth utilization, using a combination of techniques. The user device encrypts input vectors using a client's public key to keep client information private. The server computer homomorphically computes a distance between the encrypted input vector and vectors stored in the k-nearest neighbor model. The server computer then engages in a minimization process which results in the user device receiving classification vectors corresponding to the k-nearest neighbors.

Secure computer evaluation of k-nearest neighbor models

Decision trees can be securely evaluated with reasonable computation speed and bandwidth utilization. A user device encrypts input vectors using a client's public key in an additively homomorphic encryption system. A server computer effectively randomizes the decision tree for each use, such that a value indicative of a path resulting from applying an input vector to the decision tree is different each time the decision tree is used. The server computer homomorphically computes the evaluations of each decision node. The server computer provides the value indicative of the path through the decision tree as one part accessible by the client, and another part accessible by the server. The server computer uses the parts to look up a corresponding output value from a database of output values for each path. In this operation, only the output value corresponding to the combined parts can be retrieved, and only by the intended recipient.

Secure computer evaluation of decision trees

Genomic data encryption embodiments are presented which generally maintain the privacy of genomic data via an encryption scheme which allows computations to be performed on the encrypted data without the need for decryption. The genomic data is encrypted using a homomorphic polynomial encryption scheme to produce a vector of ciphertexts, where each ciphertext represents a different sample of the genomic data and takes the form of a polynomial and its associated coefficients. Computations on the encrypted genomic data are then performed on the vector or vectors of ciphertexts without decrypting the data. The results of the computations are then provided to an end user who decrypts them.

Encrypting genomic data for storage and genomic computations

Growing community of inventors

La Jolla, CA, United States of America

Kristin E Lauter