# US 9,521,124 B2 · Secure computation using a server module > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,521,124 B2 - Document ID: US9521124B2 - Status: Granted - Kind: B2 - Application number: 14/887,130 - Filed: 2015-10-19 - Published: 2016-02-11 - Granted: 2016-12-13 - Earliest claimed: 2010-02-26 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Mariana Raykova; Seny F. Kamara - Web page: https://patentgrep.com/patent/US9521124B2 ## CPC - H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload} - H04L 9/008: {involving homomorphic encryption} - H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords} - H04L 9/0869: {involving random numbers or seeds} - H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs} - H04L 2209/50: Oblivious transfer - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A server module evaluates a circuit based on concealed inputs provided by respective participant modules, to provide a concealed output. By virtue of this approach, no party to the transaction (including the sever module) discovers any other party's non-concealed inputs. In a first implementation, the server module evaluates a garbled Boolean circuit. This implementation also uses a three-way oblivious transfer technique to provide a concealed input from one of the participant modules to the serer module. In a second implementation, the server module evaluates an arithmetic circuit based on ciphertexts that have been produced using a fully homomorphic encryption technique. This implementation modifies multiplication operations that are performed in the evaluation of the arithmetic circuit by a modifier factor; this removes bounds placed on the number of the multiplication operations that can be performed. ## Claims ### Claim 1 A computing device comprising: one or more processing devices; and one or more computer-readable memories or storage devices storing instructions which, when executed by the one or more processing devices, configure the one or more processing devices to: generate a key using a fully homomorphic encryption technique; generate a modifier factor; encrypt a first input using the key to obtain a first ciphertext; send the first ciphertext and the modifier factor to a server that performs a multi-party computation using the first ciphertext, the modifier factor, and a second ciphertext provided by a second computing device to obtain an encrypted output, the use of the modifier factor not revealing the key to the server; receive the encrypted output from the server; and decrypt the encrypted output, the use of the modifier factor in the multi-party computation influencing a degree of an underlying polynomial function used to decrypt the encrypted output. ### Claim 2 (depends on 1) The computing device of claim 1, wherein the key includes a first component that identifies values for evaluation using the underlying polynomial function and a second component that identifies locations of noise information. ### Claim 3 (depends on 1) The computing device of claim 1, wherein the modifier factor reveals no information regarding the key to the server. ### Claim 4 (depends on 1) The computing device of claim 1, wherein the instructions, when executed by the one or more processing devices, configure the one or more processing devices to: decrypt the encrypted output by interpolating the underlying polynomial function to recover an unencrypted output of the multi-party computation. ### Claim 5 (depends on 4) The computing device of claim 4, wherein the use of the modifier factor in the multi-party computation prevents the degree of the underlying polynomial function from growing in linear proportion to a number of operations performed in the multi-party computation. ### Claim 6 A computing device comprising: one or more processing devices; and one or more computer-readable memories or storage devices storing instructions which, when executed by the one or more processing devices, configure the one or more processing devices to: generate a key and a modifier factor; encrypt a first input using the key to obtain a first ciphertext; send the first ciphertext and the modifier factor to a server module configured to perform a multi-party computation, the multi-party computation involving an evaluation of an arithmetic circuit on the first ciphertext and a second ciphertext provided by a second computing device, the server module using the modifier factor to perform the multi-party computation without the key being revealed to the server module; receive an encrypted output from the server module; and decrypt the encrypted output using the key to derive a polynomial function and use the polynomial function to obtain a result of the evaluation of the arithmetic circuit, the use of the modifier factor in the multi-party computation affecting a corresponding degree of the polynomial function used to obtain the result. ### Claim 7 (depends on 6) The computing device of claim 6, wherein the instructions further configure the one or more processing devices to: generate the key using a distributed coin tossing protocol in concert with the second computing device, wherein the second computing device is configured to generate the key, use the key to generate the second ciphertext, and send the second ciphertext to the server module. ### Claim 8 (depends on 7) The computing device of claim 7, wherein the distributed coin tossing protocol results in a random string. ### Claim 9 (depends on 8) The computing device of claim 8, wherein the instructions further configure the one or more processing devices to: use the random string and a security parameter to generate the key and the modifier factor. ### Claim 10 (depends on 6) The computing device of claim 6, wherein, to encrypt the first input, the instructions further configure the one or more processing devices to: provide a plurality of location values corresponding to locations along an axis of another polynomial function; and encrypt the first input by evaluating the another polynomial function at the location values to produce a plurality of polynomial values. ### Claim 11 (depends on 10) The computing device of claim 10, wherein, to encrypt the first input, the instructions further configure the one or more processing devices to: provide a set of noise indices; and form the key based at least on a combination of the plurality of location values and the set of noise indices. ### Claim 12 (depends on 11) The computing device of claim 11, wherein the first ciphertext includes noise elements corresponding to noise locations identified by the noise indices and non-noise elements corresponding to the polynomial values. ### Claim 13 (depends on 10) The computing device of claim 10, wherein, to decrypt the encrypted output, the instructions further configure the one or more processing devices to: generate the another polynomial function such that the first input is obtained by evaluating the another polynomial function at the zero location value on the axis. ### Claim 14 A method performed by a computing device, the method comprising: generating a key and a modifier factor; concealing a first input using the key to obtain a first ciphertext; sending the first ciphertext and the modifier factor to another computing device that performs a multi-party computation by evaluating an arithmetic circuit using the first ciphertext, a second ciphertext provided by a second computing device, and the modifier factor, the modifier factor not revealing the key to the another computing device; receiving a concealed output from the another computing device; and performing interpolation using the concealed output to derive a polynomial function; and evaluating the polynomial function to obtain a result of the evaluation of the arithmetic circuit, the use of the modifier factor in the multi-party computation influencing a number of samples involved in the interpolation used to derive the polynomial function. ### Claim 15 (depends on 14) The method of claim 14, wherein the multi-party computation involves a multiplication operation. ### Claim 16 (depends on 14) The method of claim 14, further comprising: determining a plurality of noise indices; determining a plurality of α values; and combining the plurality of noise indices and the plurality of α values to obtain the key. ### Claim 17 (depends on 16) The method of claim 16, wherein the plurality of a values identify corresponding locations on an axis of the polynomial function. ### Claim 18 (depends on 17) The method of claim 17, wherein the polynomial function is a univariate polynomial. ### Claim 19 (depends on 18) The method of claim 18, wherein the arithmetic circuit is a multiplication circuit. ### Claim 20 (depends on 19) The method of claim 19, wherein the interpolation is performed at the plurality of α values on the axis and the result is obtained by evaluating the polynomial function at zero on the axis.