Secure electronic device with mechanism to provide unlinkable attribute assertion verifiable by a service provider

1. A method for operating an attribute assertion device having a processor and memory to create an unlinkable digital signature-equivalent of an assertion message that is verifiable, by a service provider receiving the unlinkable digital signature-equivalent on a service provider device having a processor and memory, as being generated from a digital signature (S) of a known attribute provider having a public key PK AP , wherein the digital signature is in a group G having a generator g, and wherein the unlinkable digital signature-equivalent is created by the attribute assertion device and verifiable by the service provider device without the sharing of a secret cryptographic key between the attribute assertion device and the service provider device, the method comprising:

operating the processor of the attribute assertion device to transform a digital signature of the attribute message into an unlinkable digital signature-equivalent using a one-way transformation of the digital signature using a first random number generated by the attribute assertion device, and a challenge provided by the service provider device, the first random number held as a secret by the attribute assertion device by:

generating a secret random number (r) and a shared random number (k) in Zp;

receiving the challenge from the service provider;

on each of the attribute assertion device and the service provider device, computing a value w that is a function of the shared random number and the challenge provided by the service provider;

generating the unlinkable signature-equivalent (S′) that is a pairing of a first product (S 1 ′) and a second product (S 2 ′), wherein the first product (S 1 ′) is the product of the digital signature (S) and the value w to the power of the generated random number (r) (S 1 ′=Sw r ) and the second product (S 2 ′) is the generator g to the power of the generated random number (r) (S 2 ′=g r ); and

transmitting the unlinkable signature-equivalent S′ and the shared random secret k to the service provider; and

on the service provider, verifying the unlinkable signature-equivalent S′ using the challenge, the public key of the known attribute provider, and the shared secret.

2. The method for operating an attribute assertion device having a processor and memory to create an unlinkable digital signature-equivalent of an assertion message according to claim 1 , further comprises:

wherein the verifying of the unlinkable signature-equivalent comprises using a bilinear map e to map the unlinkable signature-equivalent, a hash of the attribute message H(M) and known quantities including the public key of the attribute provider, the computed value w into quantities that may be compared to confirm that the unlinkable signature-equivalent proves that the attribute asserter knows the signature produced by the attribute provider.

3. The method for operating an attribute assertion device having a processor and memory to create a digital signature-equivalent of an assertion message according to claim 2 , wherein the challenge C is equal to g c in G, and

wherein the attribute assertion device computes w as (g c ) k in G, the signature equivalent being the pair S′=(s 1 ′, s 2 ′)={Sw r , g r ) wherein the s is the digital signature of the attribute message M, w is (g c ) k in G, and r is the first random number;

the service provider device verifies S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by:

computing w as (g c ) k in G;

performing the bilinear mappings v1=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′,g), and v=e (s1′,g); and

verifying that v=v1*v2 which proves that s′ is derived from s.

4. The method for operating an attribute assertion device to create a digital signature-equivalent of an assertion message M according to claim 2 ,

wherein the attribute assertion device computes w as H(k∥c) wherein c is the challenge from the service provider device, the signature equivalent being the pair S′=(s 1 ′, s 2 ′)={Sw r , g r ) wherein the s is the digital signature of the attribute message M, w is H(k∥c), and r is the first random number;

the service provider device verifies S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by:

compute w as H(k∥c) wherein c is the challenge from the service provider device;

performing the bilinear mappings v1=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′,g), and v=e (s 1 ′,g); and

verifying that v=v 1 *v 2 which proves that S′ is derived from S.

5. The method for operating an attribute assertion device to create a digital signature-equivalent of an assertion message M according to claim 1 , wherein the service provider device is a server.

6. The method for operating an attribute assertion device to create an unlinkable digital signature-equivalent of an assertion message according to claim 1 , wherein the method comprising:

wherein the challenge received from the service provider is a challenge C, wherein C is g c in G, c being a random value in Zp, g being a group generator for the group G;

wherein the value w has the value w=g kc of the shared random number and the challenge provided by the service provider; and

on the service provider, verifying the unlinkable signature-equivalent S′ using the challenge, the public key of the known attribute provider, and the shared secret is performed by:

computing a hash (H(M)) of the attribute message M,

computing v 1 =e (H(M), PK APi )

computing v 2 =e (S2′, w)

computing v=e (S 1 ′, g), and

verifying that v=v1*v2 as a proof that the attribute asserter device has knowledge of the signature S without revealing S.

7. The method for operating an attribute assertion device to create an unlinkable digital signature-equivalent of an assertion message according to claim 1 , wherein the method comprising:

wherein the challenge received from the service provider is a challenge c in Zp;

wherein the value w has the value w=H(k∥c) where H(k∥c) is a hash of the shared random number k concatenated with the challenge C provided by the service provider; and

wherein on the service provider, verifying the unlinkable signature-equivalent s′ using the challenge, the public key of the known attribute provider, and the shared secret is performed by:

computing a hash (H(M)) of the attribute message M,

computing V 1 =e (H(M), PK APi )

computing v 2 =e (s 2 ′, w)

computing v=e (s 1 ′, g), and

verifying that v=v 1 *v 2 as a proof that the attribute asserter device has knowledge of the signature S without revealing S.

8. An attribute assertion device having a processor, memory, and instruction storage, the instruction storage comprising instructions to cause the attribute assertion device processor to perform a method to create an unlinkable digital signature-equivalent of an assertion message that is verifiable, operating the processor of the attribute assertion device to transform a digital signature of the attribute message into an unlinkable digital signature-equivalent using a one-way transformation of the digital signature using a first random number generated by the attribute assertion device, and a challenge provided by the service provider device, the first random number held as a secret by the attribute assertion device, wherein the instructions comprise instructions to cause the processor to compute the unlinkable digital signature by:

generating a secret random number (r) and a shared random number (k) in Zp;

receiving a challenge from the service provider;

on each of the attribute assertion device and the service provider device, computing a value w that is a function of the shared random number and the challenge provided by the service provider;

generating the unlinkable signature-equivalent (S′) that is a pairing of a first product (S 1 ′) and a second product (S 2 ′), wherein the first product (S 1 ′) is the product of the digital signature (S) and the value w to the power of the generated random number (r) (S 1 ′=Sw r ) and the second product (S 2 ′) is the generator g to the power of the generated random number (r) (S 2 ′=g r ); and

transmitting the unlinkable signature-equivalent S′ and the shared random secret k to the service provider.

9. The attribute assertion device of claim 8 wherein the digital signature is in a group G having a generator g, the signature-equivalent is a pair wherein the first member of the pair computed from the first random number the challenge (c or g c ), and the digital signature, and the second member of the digital signature-equivalent pair is an exponentiation the group generator g to the power of the first random number.

10. The attribute assertion device of claim 8 wherein the challenge C is equal to g c in G, and

wherein the attribute assertion device computes w as (g c ) in G, the signature equivalent being the pair S′=(s 1 ′, s 2 ′)={Sw r , g r ) wherein the s is the digital signature of the attribute message M, w is (g c ) k in G, and r is the first random number;

thereby enabling the service provider device to verify S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by:

computing w as (g c ) k in G;

performing the bilinear mappings v1=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′,g), and v=e (s1′,g); and

verifying that v=v1*v2 which proves that s′ is derived from s.

11. The attribute assertion device of claim 8 wherein the attribute assertion device computes w as H(k∥c) wherein c is the challenge from the service provider device, the signature equivalent being the pair S′=(si′, s2)={Sw r , g′) wherein the s is the digital signature of the attribute message M, w is H(k∥c), and r is the first random number; thereby enabling the service provider to verify S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by: compute w as H(k∥c) wherein c is the challenge from the service provider device; performing the bilinear mappings v=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′, g), and v=e (si′,g); and verifying that v=vi*v 2 which proves that S′ is derived from S.

12. The attribute assertion device of claim 8 the method performed by the attribute assertion device comprising:

wherein the challenge received from the service provider is a challenge C wherein C is g c in G, c being a random value in Zp, g being a group generator for the group G;

wherein the value w, also computed by the service provider device and has the value w=g kc of the shared random number and the challenge provided by the service provider; and

thereby enabling the service provider to verify the unlinkable signature-equivalent S′ using the challenge, the public key of the known attribute provider, and the shared secret, by:

computing a hash (H(M)) of the attribute message M,

computing v 1 =e (H(M), PK APi )

computing v 2 =e (S2′, w)

computing v=e (S 1 ′, g), and

verifying that v=v1*v2 as a proof that the attribute asserter device has knowledge of the signature S without revealing S.

13. The attribute assertion device of claim 8 the method performed by the attribute assertion device comprising:

wherein the challenge received from the service provider is a challenge c in Zp;

wherein the value w, which is also computed on the service provider device and has the value w=H(k∥c) where H(k∥c) is a hash of the shared random number k concatenated with the challenge provided by the service provider; and

thereby enabling the service provider to verify the unlinkable signature-equivalent s′ using the challenge, the public key of the known attribute provider, and the shared secret, by:

computing a hash (H(M)) of the attribute message M,

computing V 1 =e (H(M), PK APi )

computing v 2 =e (s 2 ′, w)

computing v=e (s 1 ′, g), and

verifying that v=v 1 *v 2 as a proof that the attribute asserter device has knowledge of the signature S without revealing S.

14. A service provider device comprising:

a processor,

memory, and

instruction storage storing instructions to cause the service provider device processor to perform a method to verify an unlinkable digital signature-equivalent provided by an attribute assertion device receiving the unlinkable digital signature-equivalent on a service provider device having a processor and memory, as being generated from a digital signature of a known attribute provider having a public key PK AP wherein the unlinkable digital signature-equivalent is created by the attribute assertion device and verifiable by the service provider device without the sharing of a secret cryptographic key between the attribute assertion device and the service provider device, including instructions to cause the processor to provide a challenge to the attribute assertion device, and verify the unlinkable signature-equivalent using the challenge, the public key of the known attribute provider, and a shared secret received from the attribute assertion device; wherein the unlinkable signature-equivalent is produced by the attribute assertion device by generating on the attribute assertion device a first random number (k or g k ), computing a value w that is a function of the shared random number and the challenge provided by the service provider; generating the unlinkable signature-equivalent (S′) that is a pairing of a first product (S 1 ′) and a second product (S 2 ′), wherein the first product (S 1 ′) is the product of the digital signature (S) and the value w to the power of the generated random number (r) (S 1 ′=Sw r ) and the second product (S 2 ′) is the generator g to the power of the generated random number (r) (S 2 ′=g r ).

15. The service provider device of claim 14 , the instructions to cause the service provider device processor to perform a method comprising instruction to cause the processor to:

provide a challenge c to the attribute assertion device; and

wherein the verifying of the unlinkable signature-equivalent comprises using a bilinear map e to map the unlinkable signature-equivalent, a hash of the attribute message H(M) and known quantities including the public key of the attribute provider, the computed value w into quantities that may be compared to confirm that the unlinkable signature-equivalent proves that the attribute asserter knows the signature produced by the attribute provider.

16. The service provider device of claim 15 wherein the challenge C is equal to g c in G, and

wherein the attribute assertion device computes w as (g c ) k in G, the signature equivalent being the pair S′=(s 1 ′, s 2 ′)={Sw r , g r ) wherein the s is the digital signature of the attribute message M, w is (g c ) k in G, and r is the first random number;

thereby enabling the service provider device to verify S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by:

computing w as (g c ) k in G;

performing the bilinear mappings v1=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′,g), and v=e (s1′,g); and

verifying that v=v1*v2 which proves that s′ is derived from s.

17. The service provider device of claim 15 wherein the attribute assertion device computes w as H(k∥c) wherein c is the challenge from the service provider device, the signature equivalent being the pair S′=(s 1 ′, s 2 ′)={Sw r , g r ) wherein the s is the digital signature of the attribute message M, w is H(k∥c), and r is the first random number;

thereby enabling the service provider to verify S′ as being an unlinkable signature-equivalent derived from S (the digital signature of the message M) by:

compute w as H(k∥c) wherein c is the challenge from the service provider device;

performing the bilinear mappings v1=e (H(M), PK AP ) where H(M) is a hash of the message M and PK AP is the public key of the attribute provider, v2=e (s2′,g), and v=e (s 1 ′,g); and

verifying that v=v 1 *v 2 which proves that S′ is derived from S.