Proofs of Plaintext Knowledge and Group Signatures Incorporating Same

Patent metadata

Field	Value
Publication number	US-2017366349-A1
Application number	US-201615184352-A
Country	US
Kind code	A1
Filing date	Jun 16, 2016
Priority date	Jun 16, 2016
Publication date	Dec 21, 2017
Grant date	—

Abstract

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 , i=1 to l, dependent on the ciphertext u. For each challenge c i , the user computer generates a cryptographic proof Π 2 i comprising that challenge c i and 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 Π 2 i to the verifier computer. Each challenge c i is constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element c i ″ such that the message m can be obtained via a decryption operation using the ciphertext u, the element c i ″, and a decryption key of said encryption scheme.

First claim

What is claimed is:

1 . A method for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer, the method comprising, at a user computer:
encrypting the message m via a predetermined encryption scheme to produce a ciphertext u; generating a plurality l of challenges c i , i=1 to l, dependent on the ciphertext u; for each challenge c i , generating a cryptographic proof Π 2 i comprising that challenge c i and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u; and sending the ciphertext u and the l proofs Π 2 i to the verifier computer; wherein each challenge c i is constrained to a predetermined challenge space C permitting identification, by searching the challenge space C, of an element c i ″ such that the message m can be obtained via a decryption operation using the ciphertext u, the element c i ″, and a decryption key of said encryption scheme.

2 . A method as claimed in claim 1 wherein:
said encryption scheme applies a predetermined linear function A Π 2 to a function S Π 2 which is dependent on the message m and a set of random elements;
each proof Π 2 i comprises a zero-knowledge proof of knowledge of a first element c i =γ(c i , c i ′), dependent on the challenge c i , a second element c i ′ and a predetermined function γ, and of a function S Π 2 i , dependent on the first element c i and said function S Π 2 , such that A Π 2 S Π 2 i = c i u; and
each second element c i ′ is constrained to said challenge space C permitting identification, by searching the challenge space C, of said element c i ″ such that γ(c i , c i ″)u decrypts to γ(c i , c i ″)m using said decryption key of the encryption scheme, thereby revealing the message m.

3 . A method as claimed in claim 2 wherein γ(c i , c i ′)=(c i −c i ′) and S Π 2 i = S Π 2 c i , whereby (c i −c i ″)u decrypts to (c i −c i ″)m using said decryption key of the encryption scheme.

4 . A method as claimed in claim 3 wherein said linear function A Π 2 is dependent on-a public key of the encryption scheme.

5 . A method as claimed in claim 4 wherein said encryption scheme comprises a Ring-LWE encryption scheme, said set of random elements comprises elements r, e 1 and e 2 , and wherein said ciphertext u comprises a vector

[

v

w

]

such that

[

v

w

]

=

A

Π
2



S

Π
2

,

where:
A Π 2 is the matrix

[

pa
|
p
|
0
|
0

pt
|
0
|
p
|
1

]

,

S Π 2 is the vector

[

r

e
1

e
2

m

]

,

and a, t and p are public components of said encryption scheme.

6 . A method as claimed in claim 5 including, at the user computer
for each proof Π 2 i , selecting a masking vector Y i ; and
generating the challenge c i for each proof Π 2 i as a function of the ciphertext

[

v

w

]

,

a vector U i =A Π 2 Y i , and said public key of the encryption scheme;
wherein each proof Π 2 i comprises the challenge c i and a vector Z i =S Π 2 c i +Y i .

7 . A method as claimed in claim 6 wherein a predetermined combination of said elements r, e 1 and e 2 has a norm of less than a predetermined magnitude.

8 . A method as claimed in claim 7 wherein the message m, said first element c i , and said elements r, e 1 and e 2 satisfy



p


(

r
_

i



s
2

+

e
_

2
i

-

Assignees

• IBM

Inventors

• Lyubashevsky Vadim
• Neven Gregory

Classifications

• H04L9/3006

  underlying computational problems or public-key parameters · CPC title

• H04L9/321

  involving a third party or a trusted authority · CPC title

• H04L9/3221 Primary

  interactive zero-knowledge proofs · CPC title

• H04L9/3255 Primary

  using group based signatures, e.g. ring or threshold signatures · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title