Microsoft Technology Licensing, LLC

Kim Laine

Kristin E Lauter

Hao Chen

Ran Gilad-Bachrach

Michael Naehrig

John Wernsing

Nathan Dowlin

Peter Byerley Rindal

Zhicong Huang

Madanlal S Musuvathi

Todd Douglas Mytkowicz

Nicolo Fusi

Saeed Maleki

Srinath T V Setty

Sebastian G Angel

Olli Ilari Saarikivi

Roshan Dathathri

Rachel Louise Player

Olli Llari Saarikivi

Systems and methods for computing a private set intersection are disclosed. A method includes storing, at a sender device, a first set of values. The method includes receiving, from a receiver device, a homomorphic encryption of a receiver device value. The method includes computing a homomorphically encrypted number based on a difference between the homomorphic encryption of the receiver device value and each value in the first set of values, and based on a hash function of the encryption of the receiver device value. The method includes transmitting the homomorphically encrypted number to the receiver device for determination, at the receiver device, whether the receiver device value is in the first set of values.

Computing a private set intersection

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

Systems, methods, and computer-executable instructions for reducing amortized computational costs for a query that includes receiving at least two indexes for elements stored in an n-element database. The n-element database is encoded into at least three buckets. Each element is stored within at least two buckets. Each bucket stores a proper subset of the n-elements. For each of the two indexes, a bucket is determined to retrieve the element at the index. The determined buckets are queried to retrieve the elements. The elements at the indexes are retrieved based on the querying the determined buckets.

Private information retrieval with probabilistic batch codes

The disclosure herein relates to private set intersection techniques. The described private set intersection techniques enable entities to determine common data strings in their respective data sets. The private set intersection techniques described herein allow those common data strings to be shareable between the entities, while maintaining the secrecy of other data strings stored in their respective data sets.

Private set intersection encryption techniques

Homomorphic encryption systems encode plaintext represented as rational numbers based on modular products of the rational numbers and a power of an integer basis with respect to a modulus defined by the integer basis. Decrypted ciphertexts are decoded based on modular products of the decrypted ciphertexts and an integer power of the integer basis. Typically, the integer power is one-half the number of available digits if the integer basis is odd; if the integer basis is even, the integer power is one-half the number of available digits plus one.

Rational number arithmetic in homomorphic encryption

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

Growing community of inventors

Seattle, WA, United States of America

Kim Laine