Granted Patent B2

US 12,388,801 · App. 18/572,069 · Granted Aug 12, 2025

Inventor: Hoeteck Wee (San Francisco, CA)

Assignee: NTT Research, Inc.

H04L63/0428H04L9/0618H04L9/30

Abstract

Claims (97)

1. A method for encrypting a message for transmitting over a broadcast network to multiple recipients as a ciphertext, the method comprising:

receiving an authorized recipient set S at a broadcast module, wherein the authorized recipient set identifies a set of recipients with permission to recover a broadcast message, wherein S is a subset of {1, 2, . . . , N}, wherein n is an integer such that n 3 ≥N, and wherein N is the total number of possible recipients of the message;

generating a public key mpk at an authority, the public key mpk comprising:

a) a pairing group, the pairing group further comprising a first source group, a second source group, and a target group,

b) vectors [v] 1 , [w 1 ] 1 and [w 2 ] 1 as n random group elements from the first source group,

c) a random group element [ν 0 ] 1 from the first source group, and

d) a random group element a [α] T from the target group;

receiving the public key mpk at the broadcast module from the authority;

receiving or creating a message M for encryption;

encoding the authorized recipient set S as a degree 3 polynomial,

wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the recipient set S, and wherein the vector f has a length n 3 ;

cryptographically compressing the vector f using the vector [w 2 ] 1 of n group elements from the public key mpk and by sampling a random vector w 3 of n integers modulo p resulting in a digest of n group elements;

generating a ciphertext of message M by:

(a) sampling a random scalar s;

(b) multiplying the random scalar s with the digest, the vector w 3 and the public key mpk;

(c) concatenating the output of the multiplying to form the ciphertext;

(d) multiplying the random scalar s by [α] T to derive [αs] T ;

(e) masking message M with [αs] T ; and

transmitting the masked message as a ciphertext and the authorized recipient set S to recipients on the broadcast network.

2. The method of claim 1 , wherein generating the ciphertext is performed by executing:

parsing mpk=([w 1 ] 1 , [w 2 ] 1 , [ν 0 ] 1 , [v] 1 , [α] T );

sampling s← p , w 3 ← p n ;

and outputting ciphertext

ct=[s] 1 ,[(( I n ⊗w 2 ⊗w 3 ) f T +w 1 T ) s] 1 ,[w 3 s] 1 ,[(ν 0 w 3 +v ) s] 1 ,[αs] T ·M.

3. The method of claim 1 , further comprising executing instructions for decrypting the ciphertext by a recipient to recover a broadcast message, the instructions configured for:

receiving the ciphertext and the authorized recipient set S at a receiver module from the remote broadcast module over the broadcast network, wherein the ciphertext further comprises a digest, and the digest further comprises information about the polynomial;

receiving a secret key from a remote authority module, the secret key comprising group elements from the second source group;

checking whether the recipient is in a set of authorized recipients;

computing the degree 3 polynomial that has a coefficient vector f equal to a characteristic vector of the authorized recipient set S;

wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the authorized recipient set S, and wherein the vector f has a length n 3 ;

recovering the broadcast message by evaluating the polynomial with the digest using the group elements in a pairing algorithm; and

storing the recovered broadcast message for further processing at the receiver module.

4. A system for encrypting a message for transmitting over a broadcast network to multiple recipients as a ciphertext, comprising:

a network communication interface configured to communicate over a wired or wireless network;

a set of processing circuits coupled to the network communication interface, the processing circuits comprising modules configured for:

receiving an authorized recipient set S, wherein the authorized recipient set identifies a set of recipients with permission to recover a broadcast message, wherein S is a subset of {1, 2, . . . , N}, wherein n is an integer such that n 3 ≥N, and wherein N is the total number of possible recipients of the message;

generating a public key mpk at an authority, the public key mpk comprising:

a) a pairing group, the pairing group further comprising a first source group, a second source group, and a target group,

b) vectors [v] 1 , [w 1 ] 1 and [w 2 ] 1 as n random group elements from the first source group,

c) a random group element [ν 0 ] 1 from the first source group, and

d) a random group element [α] T from the target group;

receiving the public key mpk from the authority;

receiving or creating a message M for encryption;

encoding the authorized recipient set S as a degree 3 polynomial, wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the recipient set S, and wherein the vector f has a length n 3 ;

cryptographically compressing the vector f using the vector [w 2 ] 1 of n group elements from the public key mpk and by sampling a random vector w 3 of n integers modulo p resulting in a digest of n group elements;

generating a ciphertext of message M by:

(a) sampling a random scalar s;

(b) multiplying the random scalar s with the digest, the vector w 3 and the public key mpk;

(c) concatenating the output of the multiplying to form the ciphertext

(d) multiplying the random scalar s by [α] T to derive [αs] T ;

(e) masking message M with [αs] T ; and

transmitting the masked message as a ciphertext and the authorized recipient set S to recipients on the broadcast network S.

5. The system of claim 4 , wherein generating the ciphertext is performed by executing:

parsing mpk=([w 1 ] 1 , [w 2 ] 1 , [ν 0 ] 1 , [v] 1 , [α] T );

sampling s← p , w 3 ← p n ;

and outputting ciphertext

ct=[s] 1 ,[(( I n ⊗w 2 ⊗w 3 ) f T +w 1 T ) s] 1 ,[w 3 s] 1 ,[(ν 0 w 3 +v ) s] 1 ,[αs] T ·M.

6. The system of claim 4 , further configured for decrypting a ciphertext by a recipient to recover a broadcast message, including:

receiving the ciphertext and the authorized recipient set S at a receiver module from a remote broadcast module over the broadcast network, wherein the ciphertext further comprises a digest, and the digest further comprises information about the polynomial;

receiving a secret key, the secret key comprising group elements from the second source group;

checking whether the recipient is in a set of authorized recipients;

computing the degree 3 polynomial that has a coefficient vector f equal to a characteristic vector of the authorized recipient set S;

wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the authorized recipient set S, and wherein the vector f has a length n 3 ;

recovering the broadcast message by evaluating the polynomial with the digest using the group elements in a pairing algorithm; and

storing the recovered broadcast message for further processing at the receiver module.

7. A non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by one or more processors of a computing device, configure the one or more processors to perform instructions for encrypting a message for transmitting over a broadcast network to multiple recipients as a ciphertext, the instructions comprising:

receiving an authorized recipient set S at a broadcast module, wherein the authorized recipient set identifies a set of recipients with permission to recover a broadcast message, wherein S is a subset of {1, 2, . . . , N}, wherein n is an integer such that n 3 ≥N, and wherein N is the total number of possible recipients of the message;

generating a public key mpk at an authority, the public key mpk comprising:

a) a pairing group, the pairing group further comprising a first source group, a second source group, and a target group,

b) vectors [v] 1 , [w 1 ] 1 and [w 2 ] 1 as n random group elements from the first source group,

c) a random group element [ν 0 ] 1 from the first source group, and

d) a random group element [α] T from the target group;

receiving the public key mpk at the broadcast module from the authority;

receiving or creating a message M for encryption;

encoding the authorized recipient set S as a degree 3 polynomial,

wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the recipient set S, and wherein the vector f has a length n 3 ;

cryptographically compressing the vector f using the vector [w 2 ] 1 of n group elements from the public key mpk and by sampling a random vector w 3 of n integers modulo p resulting in a digest of n group elements;

generating a ciphertext of message M by:

(a) sampling a random scalar s;

(b) multiplying the random scalar s with the digest, the vector w 3 and the public key mpk;

(c) concatenating the output of the multiplying to form the ciphertext;

(d) multiplying the random scalar s by [α] T to derive [αs] T ;

(e) masking message M with [αs] T ; and

transmitting the masked message as a ciphertext and the authorized recipient set S to recipients on the broadcast network.

8. The non-transitory computer-readable storage medium of claim 7 , wherein generating the ciphertext is performed by executing:

parsing mpk=([w 1 ] 1 , [w 2 ] 1 , [ν 0 ] 1 , [v] 1 , [α] T );

sampling s← p ; w 3 ← p n ;

and outputting ciphertext

ct=[s] 1 ,[(( I n ⊗w 2 ⊗w 3 ) f T +w 1 T ) s] 1 ,[w 3 s] 1 ,[(ν 0 w 3 +v ) s] 1 ,[αs] T ·M.

9. The non-transitory computer-readable storage medium of claim 7 , further comprising executing instructions for decrypting the ciphertext by a recipient to recover a broadcast message, the instructions configured for:

receiving the ciphertext and the authorized recipient set S at a receiver module from a remote broadcast module over the broadcast network, wherein the ciphertext further comprises a digest, and the digest further comprises information about the polynomial;

receiving a secret key from a remote authority module, the secret key comprising group elements from the second source group;

checking whether the recipient is in a set of authorized recipients;

computing the degree 3 polynomial that has a coefficient vector f equal to a characteristic vector of the authorized recipient set S;

wherein the degree 3 polynomial has a coefficient vector f equal to a characteristic vector of the authorized recipient set S, and wherein the vector f has a length n 3 ;

recovering the broadcast message by evaluating the polynomial with the digest using the group elements in a pairing algorithm; and

storing the recovered broadcast message for further processing at the receiver module.

Assignments (1)

Continuity (2)

References Cited (13)