Proofs of plaintext knowledge and group signatures incorporating same

1. A method for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer, the method comprising:

encrypting, by a user computer, the message m via a predetermined encryption scheme to produce a ciphertext u;

generating, by the user computer, a plurality l of challenges c i , i=1 to l, dependent on the ciphertext u;

generating, by the user computer, a composition of proofs in parallel for the plurality l of challenges c i to reduce soundness error, wherein generating the composition of proofs comprises, for each respective challenge c i , generating a cryptographic proof Π 2 i comprising the respective challenge c i and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u; and

sending, by the user computer, 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 is obtainable 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 ē 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 cipertext 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

-

e

_

1

i

⁢

s

1

)

+

m

_

i



∞

<

q

2

⁢

⁢

C

⁢

⁢

where

C

=

max

c

_

i

∈

C

_

⁢



c

_

i



1

=

max

c

i

,

c

i

⁢

⁢

′

∈

C

⁢



c

i

-

c

i

⁢

⁢

′



1

,

and where:

q is a predetermined prime number;

r i =r c i , ē 1 i =e 1 i c i , ē 2 i =e 2 i c i and m i =m c i ; and

s 1 and s 2 are components of a secret key of the encryption scheme, s 1 being said decryption key.

9. A method for authenticating a message μ, at a user computer of a group signature scheme, to a verifier computer, the method comprising at the user computer:

storing a user identity id for the user computer and a user signing key which comprises a signature on the user identity id under a secret key of a signature scheme;

proving plaintext knowledge of the user identity id by a method as claimed in claim 1 , wherein said ciphertext u is produced by encrypting the user id m via said encryption scheme;

generating a first cryptographic proof Π 1 comprising a zero-knowledge proof of knowledge of said user signing key, in which the user identity id is that encrypted in the user identity id, and including the message μ in said proof of knowledge;

sending the message μ and a group signature, comprising the ciphertext u, the first proof Π 1 and said plurality l of proofs Π 2 i , to the verifier computer.

10. A method as claimed in claim 9 wherein said signature scheme comprises a selectively-secure signature scheme, and wherein the user identity id is an element of a predetermined subring, isomorphic to q [x]/(g(x)), of a ring R= q [x]/(f(x)), where f(x) and g(x) are polynomials of degree deg(f) and deg(g) respectively such that deg(f)>deg(g)>1.

11. A method as claimed in claim 10 wherein each of the challenge c i and the second element c i ′ for each proof Π 2 i , is an element of said predetermined subring of the ring R.

12. A method as claimed in claim 11 wherein:

said encryption scheme comprises a Ring-LWE encryption scheme, said set of random elements comprises elements r, e 1 and e 2 being elements of the ring R, and 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

i

d

]

,

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

said function S Π 2 i is the vector S Π 2 c i ; and

each of the vectors S Π 2 and S Π 2 i have polynomial coefficients of less than a predetermined magnitude.

13. A method as claimed in claim 10 wherein said ring R= q [x]/(x n +1) where n is a predetermined integer power of 2.

14. A computer program product for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer, said computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therein, the program instructions being executable by a user computer to cause the user computer to:

encrypt the message m via a predetermined encryption scheme to produce a ciphertext u;

generate a plurality l of challenges c i , i=1 to l, dependent on the ciphertext u;

generate, by the user computer, a composition of proofs in parallel for the plurality l of challenges c i to reduce soundness error, wherein generating the composition of proofs comprises, generate, for each respective challenge c i , a cryptographic proof Π 2 i comprising the respective challenge c i and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u; and

send 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 is obtained via a decryption operation using the ciphertext u, the element c i ″, and a decryption key of said encryption scheme.

15. A computer program product as claimed in claim 14 , said program instructions being executable such that:

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.

16. A computer program product as claimed in claim 15 , said program instructions being executable such that γ(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.

17. A system for proving plaintext knowledge of a message m, encrypted in a ciphertext, to a verifier computer, wherein the system comprises:

at least one processor; and at least one non-transitory memory including computer program code;

the at least one memory and the computer program code configured to, with the at least one processor, cause the system to:

encrypt the message m via a predetermined encryption scheme to produce a ciphertext u;

generate a plurality l of challenges c i , i=1 to l, dependent on the ciphertext u;

generate, by the user computer, a composition of proofs in parallel for the plurality l of challenges c i to reduce soundness error, wherein generation of the composition of proofs comprises, generation of, for each respective challenge c i , a cryptographic proof Π 2 i comprising the respective challenge c i and a zero-knowledge proof of plaintext knowledge of the message m encrypted in the ciphertext u; and

send 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 is obtained via a decryption operation using the ciphertext u, the element c i ″, and a decryption key of said encryption scheme; and

wherein each proof Π 2 i is verifiable by the verifier computer using a public key of said encryption scheme.

18. A system as claimed in claim 17 , wherein said challenge space C is searchable by an opener computer storing said decryption key of the encryption scheme to identify said element c i ″, and the message m is obtainable via a decryption operation using the ciphertext u, the element c i ″, and a decryption key of said encryption scheme by the opener computer.

19. A system as claimed in claim 17 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.

20. A system as claimed in claim 19 said challenge space C is searchable by an opener computer to identify said element c i ″, and to decrypt γ(c i , c i ″)u using said decryption key to obtain γ(c i , c i ″)m, thereby revealing the message m.