International Business Machines Corporation

Vadim Lyubashevsky

Gregory Neven

Rafael Del Pino

Gregor Seiler

The present disclosure relates to a method method for performing a disjunctive proof for two relations Rand R. The relation Ris between an instance set Xand a witness set Wand defines a language L(R) containing those elements x&#x2208;Xfor which there exists a witness wthat is related to xin accordance with R. The relation Ris between an instance set Xand a witness set Wand defining a language L(R) containing those elements x&#x2208;Xfor which there exists a witness wthat is related to xin accordance with R. For proving knowledge of a witness wof at least one of instances xand x, where b is 0 or 1, of the respective relations Rand R, the prover may generate using a bijective function a challenge from a simulated challenge c.

Method for performing a disjunctive proof for two relations

The invention relates to a method for performing a multi-party electronic computation using a plurality of evaluating computer systems. The cryptographic security of the multi-party computation is implemented using lattice-based cryptography. Each evaluating computer system receives from each user of a plurality of users an individual input share of an input chosen by the respective user. Furthermore, each evaluating computer system receives from the user a commitment to the received individual input share and an opening information. Each evaluating computer system checks the commitments received to the individual input shares and generates a first lattice-based zero-knowledge proof that all the commitments received are valid commitments to input shares. Each evaluating computer system publishes the first lattice-based zero-knowledge proof. Thus, a verifier may be enabled to verify that all commitments are valid commitments to input shares.

Computation using lattice-based cryptography

Embodiments of the present invention may provide the capability for performing public-key encryption with proofs of plaintext knowledge using a lattice-based scheme that provides improved efficiency over conventional techniques. For example, in an embodiment, a computer-implemented method of verifying encryption may comprise generating a ciphertext, derived from a plaintext, via an encryption scheme, proving validity of the ciphertext, wherein the proof includes at least one challenge value, and using a decryption procedure that recovers a plaintext by choosing at least one additional challenge value at random from a challenge space.

Flexible verifiable encryption from lattices

Systems and methods are provided for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer. The method includes, at a user computer, encrypting the message m via a predetermined encryption scheme to produce a ciphertext u, and generating a plurality l of challenges c, i=1 to l, dependent on the ciphertext u. For each challenge c, the user computer generates a cryptographic proof &#x3a0;comprising that challenge cand a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u. The user computer sends the ciphertext u and the l proofs &#x3a0;to the verifier computer. Each challenge cis constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element c&#x2033; such that the message m can be obtained via a decryption operation using the ciphertext u, the element c&#x2033;, and a decryption key of said encryption scheme.

Proofs of plaintext knowledge and group signatures incorporating same

Methods and systems are provided for authenticating a message &#x3bc;, at a user computer of a group signature scheme, to a verifier computer. The method includes, at the user computer, storing a user id m for the user computer and a user signing key which comprises a signature on the user id m under a secret key of a selectively-secure signature scheme. The user id m is an element of a predetermined subring, isomorphic to[x]/(g(x)), of a ring R=[x]/(f(x)), where f(x) and g(x) are polynomials of degree deg(f) and deg(g) respectively such that deg(f)&#x3e;deg(g)&#x3e;1. The method includes, at the user computer, generating a first cryptographic proof &#x3a0;comprising a zero-knowledge proof of knowledge of the user signing key and including the message &#x3bc; in this proof of knowledge. The user computer sends the message &#x3bc; and a group signature, comprising the first proof &#x3a0;, to the verifier computer.

Growing community of inventors

Zug, Switzerland

Vadim Lyubashevsky