Microsoft Technology Licensing, LLC

Yaacov Nissim Kobliner

Cynthia Dwork

Frank David McSherry

Anton Mityagin

Ilya Mironov

Avrim L Blum

A database has a plurality of entries and a plurality of attributes common to each entry, where each entry corresponds to an individual. A query is received from a querying entity query and is passed to the database, and an answer is received in response. An amount of noise is generated and added to the answer to result in an obscured answer, and the obscured answer is returned to the querying entity. The noise is normally distributed around zero with a particular variance. The variance R may be determined in accordance with R&#x3e;8 T log(T/&#x3b4;)/&#x3b5;, where T is the permitted number of queries T, &#x3b4; is the utter failure probability, and &#x3b5; is the largest admissible increase in confidence. Thus, a level of protection of privacy is provided to each individual represented within the database. Example noise generation techniques, systems, and methods may be used for privacy preservation in such areas as k means, principal component analysis, statistical query learning models, and perceptron algorithms.

Private clustering and statistical queries while analyzing a large database

An addition chain is first generated, and then an integer x is derived from it. Doubling and star steps may be implemented in the addition chain. This approach eliminates the computationally expensive step of generating the addition chain from an exponent, and therefore can greatly reduce the computation time of the modular exponentiation.

Systems and methods for generating random addition chains

A database has a plurality of entries and a plurality of attributes common to each entry, where each entry corresponds to an individual. A query q is received from a querying entity query q and is passed to the database, and an answer a is received in response. An amount of noise e is generated and added to the answer a to result in an obscured answer o, and the obscured answer o is returned to the querying entity. Thus, a level of protection of privacy is provided to each individual represented within the database.

Growing community of inventors

Beer-Sheva, Israel

Yaacov Nissim Kobliner