Computation using lattice-based cryptography

A method for performing a multi-party electronic computation using a plurality of evaluating computer systems, wherein cryptographic security of the multi-party computation is implemented using lattice-based cryptography, the method comprising by each of the evaluating computer systems:

• receiving from each user of a plurality of users participating in the electronic computation an individual input share of an input chosen by the respective user using a user computer system, wherein the input is split into a plurality of input shares,
• receiving from each user a commitment to the received individual input share of the respective user and an opening information assigned to the respective commitment, proving that the commitment commits to the received individual input share of the respective user,
• checking for each user that the commitment received from the respective user commits to the individual input share received from the same user using the received opening information assigned to the respective commitment,
• generating a first lattice-based zero-knowledge proof that all the commitments received from users are valid commitments to input shares,
• publishing the first lattice-based zero-knowledge proof in order to enable a verifier using a verifying computer system to verify that all commitments are valid commitments to input shares,
• generating a combination of input shares comprising the individual input shares received by the respective evaluating computer system from the plurality of users,
• publishing the combination of input shares in order to enable a verifier using a verifying computer system to generate a computation result by combining the combinations of input shares published by the plurality of evaluating computer systems,
• wherein the commitments to the individual input shares received by the evaluating computer systems are homomorphic commitments and the method further comprises by each of the evaluating computer systems:
• generating a combined opening information using the opening information received by the respective evaluating computer system from each of the users,
• publishing the combined opening information in order to further enable the verifier to check for each of the evaluating computer systems that a first combined commitment generated using the commitments to the individual input shares received by the respective evaluating computer system commits to the combination of input shares published by the respective evaluating computer system using the combined opening information published by the same evaluating computer system, and
• wherein the generation of the combined opening information in order to prevent an accumulation of values of the received opening information further comprises by each evaluating computer system:
• selecting a first subset of individual input shares received by the respective evaluating computer system,
• combining the input shares of the first subset to a first sub-combination of input shares,
• generating a first additional commitment to the first sub-combination of input shares and a first additional opening information assigned to the first additional commitment with a value of the size of the values of opening information assigned to the commitments to individual input shares of the first sub-combination,
• generating a second lattice-based zero-knowledge proof that the first additional commitment commits to the same quantity as a combination of the received commitments to the input shares of the first sub-combination,
• using the first additional opening information for generating the combined opening information,
• publishing the second lattice-based zero-knowledge proof.

A method for performing a multi-party electronic computation using a plurality of evaluating computer systems, wherein cryptographic security of the multi-party computation is implemented using lattice-based cryptography, the method comprising by each of the evaluating computer systems:

• receiving from each user of a plurality of users participating in the electronic computation an individual input share of an input chosen by the respective user using a user computer system, wherein the input is split into a plurality of input shares,
• receiving from each user a commitment to the received individual input share of the respective user and an opening information assigned to the respective commitment, proving that the commitment commits to the received individual input share of the respective user,
• checking for each user that the commitment received from the respective user commits to the individual input share received from the same user using the received opening information assigned to the respective commitment,
• generating a first lattice-based zero-knowledge proof that all the commitments received from users are valid commitments to input shares, and
• publishing the first lattice-based zero-knowledge proof in order to enable a verifier using a verifying computer system to verify that all commitments are valid commitments to input shares, wherein for each of the inputs a lattice-based approximate zero-knowledge proof is provided by the user of the respective input using all the input shares of the input, the approximate zero-knowledge proof proving that an approximation of a second combined commitment combining the commitments to the individual input shares of the respective input commits to a correct input for an approximation of the respective input.

A computer program product comprising a non-volatile computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code being configured to implement the following steps of performing a multi-party electronic computation using a plurality of evaluating computer systems, when being executed by one of the evaluating computer systems, wherein cryptographic security of the multi-party electronic computation is implemented using lattice-based cryptography:

• receiving from each user of a user device of a plurality of user devices participating in the electronic computation an individual input share of an input chosen by the respective user using a user computer system, wherein the input is split into a plurality of input shares,
• receiving from each user a commitment to the received individual input share of the respective user and an opening information assigned to the respective commitment, proving that the commitment commits to the received individual input share of the respective user,
• checking for each user that the commitment received from the respective user commits to the individual input share received from the same user using the received opening information assigned to the respective commitment,
• generating a first lattice-based zero-knowledge proof that all the commitments received from users are valid commitments to input shares,
• publishing the first lattice-based zero-knowledge proof in order to enable a verifier using a verifying computer system to verify that all commitments are valid commitments to input shares.

An evaluating computer system of a plurality of evaluating computer systems for contributing to a multi-party electronic computation using the plurality of evaluating computer systems, each evaluating computer system comprising a memory and at least one processor, coupled to said memory, wherein cryptographic security of the multi-party electronic computation is implemented using lattice-based cryptography, the at least one processor of the evaluating computer system being configured to perform operations comprising:

• receiving from each user of a user device of a plurality of user devices participating in the electronic computation an individual input share of an input chosen by the respective user using a user computer system, wherein the input is split into a plurality of input shares,
• receiving from each user a commitment to the received individual input share of the respective user and an opening information assigned to the respective commitment, proving that the commitment commits to the received individual input share of the respective user,
• checking for each user that the commitment received from the respective user commits to the individual input share received from the same user using the received opening information assigned to the respective commitment,
• generating a first lattice-based zero-knowledge proof that all the commitments received from users are valid commitments to input shares,
• publishing the first lattice-based zero-knowledge proof in order to enable a verifier using a verifying computer system to verify that all commitments are valid commitments to input shares.