System and Method for Security Against Bounded-Storage Mass Surveillance

Abstract

The present disclosure relates to a computerized method and system for message encryption in a multi-user setting. The method involves receiving a message of arbitrary length for each user, storing the message in a computerized data store, and executing a setup to generate a master secret and public keys. A random variable is generated, and a function is defined based on this variable. A second secret is derived using a functional encryption scheme, resulting in a derived secret. The message is encrypted by generating a first random string, a second partially random string, and a ciphertext. The system also includes a method for decrypting the encrypted message, processing the derived secret and ciphertext to derive a string, and deriving a plaintext message from this string.

1 . A computerized method for message encryption in a multi-user setting, the method comprising:
 for each of multiple users:   receiving a message m of arbitrary length and storing the message m on a computerized data store;   storing a predetermined target ciphertext length;   executing a setup comprising:   instantiating a functional encryption scheme to generate a master secret key msk and master public key mpk;   generating a random variable v;   defining a function fv based on v;   deriving a second secret key by executing a key generation algorithm of the functional encryption scheme based on fv and the master secret key msk, resulting in a derived secret key skv;   encrypting the message m by:   generating a first random string r having a length based on the predetermined target ciphertext length;   generating an at least partially random second string u;   encrypting u under the functional encryption scheme using mpk to generate ciphertext c;   deriving z from r and u and m; and   outputting z, r and ciphertext c and storing ciphertext c in the computerized data store.   
     
     
         2 . The method of  claim 1 , wherein:
 u is based on two random strings and has a last bit set to be 0; and   the derivation of z from r and u and m is performed by:   applying a randomness extractor Ext to r and s, where s is a component of string u; and   generating z by xoring the results of the randomness extractor Ext with m and t, where t is a part of string u.   
     
     
         3 . The method of  claim 2 , wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R 1 , . . . , R t  whose total joint min-entropy rate is α, for random and independent seeds S 1 , . . . , S t , close to an α-fraction of the extracted outputs Ext(R i ; S i ) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds. 
     
     
         4 . The method of  claim 3 , wherein the somewhere randomness extractor Ext(r; s) is constructed as:
 the input r∈{0, 1} n  is interpreted as an l-variate polynomial of total degree g over some field F 2     w    such that n=w·(l+gg);   the seed s=(s 1 , s 2 ) consists of s 1 ∈   2     w     l  and s 2 ∈   w/m   2     m   ; and   the output of the extractor is set to  r(s 1 ), s 2   , wherein the polynomial evaluation y=r(s 1 ) is performed over the field F 2     w    and the dot product  y, s 2    is performed over the first    2     m   .   
     
     
         5 . The method of  claim 1 , wherein the generated first random string has a length that closely approximates but is smaller than the length of the specified target ciphertext length. 
     
     
         6 . The method of  claim 1 , wherein defining a function fv based on v further comprises:
 receiving an input string;   based on the last bit of u, if the last bit is 0, then outputting s and t; and   if the last bit is 1, then outputting (s and t) xor v.   
     
     
         7 . A method for decrypting an encrypted message, the decryption method comprising:
 for each sender-receiver pair:   processing a derived secret key sky and a ciphertext c by a functional encryption decryption algorithm to derive a string s′;   deriving a plaintext message from s′, r and z;   wherein, the plaintext message was previously encrypted by:
 generating a first random string r having a length based on a specified target ciphertext length; 
 generating an at least partially random second string u; 
 encrypting u under a functional encryption scheme to generate c; and 
 deriving z from r and u and m; and 
 outputting z, r, and ciphertext c. 
   
     
     
         8 . The method of  claim 7 , further comprising executing the decryption method by:
 for i in the range of 1 to n, executing a public key decryption on the ciphertext ct i,w  using the sk i,w  and storing the output as the plaintext message.   
     
     
         9 . The method of  claim 7 , where deriving plaintext message from s′, r and z further comprises:
 decomposing s′ into s and t; and 
 applying a randomness extractor to r and s, and xoring the result with t. 
 
     
     
         10 . The method of  claim 9 , wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R 1 , . . . , R t  whose total joint min-entropy rate is α, for random and independent seeds S 1 , . . . , S t , close to an α-fraction of the extracted outputs Ext(R i ; S i ) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds. 
     
     
         11 . The method of  claim 10 , wherein the somewhere randomness extractor Ext(r; s) is constructed as:
 the input r∈{0, 1} n  is interpreted as an l-variate polynomial of total degree g over some field F 2     w    such that n=w·(l+gg);   the seed s=(s 1 , s 2 ) consists of s 1 ∈   2     w     l  and s 2 ∈   2     m     w/m ; and   the output of the extractor is set to  r(s 1 ), s 2   , wherein the polynomial evaluation y=r(s 1 ) is performed over the field F 2     w    and the dot product  y, s 2    is performed over the first    2     m   .   
     
     
         12 . A computerized system for message encryption in a multi-user setting, the system comprising:
 a computerized processor configured for executing instructions for:   for each of multiple users:   receiving a message m of arbitrary length and storing the message m on a computerized data store;   storing a predetermined target ciphertext length;   executing a setup comprising:   instantiating a functional encryption scheme to generate a master secret key msk and master public key mpk;   generating a random variable v;   defining a function fv based on v;   deriving a second secret key by executing a key generation algorithm of the functional encryption scheme based on fv and the master secret key msk, resulting in a derived secret key skv;   encrypting the message m by:   generating a first random string r having a length based on the predetermined target ciphertext length;   generating an at least partially random second string u;   encrypting u under the functional encryption scheme using mpk to generate ciphertext c;   deriving z from r and u and m; and   outputting z, r and ciphertext c and storing ciphertext c in the computerized data store.   
     
     
         13 . The system of  claim 12 , wherein:
 u is based on two random strings and has a last bit set to be 0; and   the derivation of z from r and u and m is performed by:   applying a randomness extractor Ext to r and s, where s is a component of string u; and   generating z by xoring the results of the randomness extractor Ext with m and t, where t is a part of string u.   
     
     
         14 . The system of  claim 13 , wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R 1 , . . . , R t  whose total joint min-entropy rate is α, for random and independent seeds S 1 , . . . , S t , close to an α-fraction of the extracted outputs Ext(R i ; S i ) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds. 
     
     
         15 . The system of  claim 14 , wherein the somewhere randomness extractor Ext(r; s) is constructed as:
 the input r∈{0, 1} n  is interpreted as an l-variate polynomial of total degree g over some field F 2     w    such that n=w·(l+gg);   the seed s=(s 1 , s 2 ) consists of s 1 ∈   2     w     l  and s 2 ∈   2     m     w/m ; and   the output of the extractor is set to  r(s 1 ), s 2   , wherein the polynomial evaluation y=r(s 1 ) is performed over the field F 2     w    and the dot product  y, s 2    is performed over the first    2     m   .   
     
     
         16 . The system of  claim 12 , wherein the generated first random string has a length that closely approximates but is smaller than the length of the specified target ciphertext length. 
     
     
         17 . The system of  claim 12 , wherein defining a function fv based on v further comprises:
 receiving an input string;   based on the last bit of u, if the last bit is 0, then outputting s and t; and   if the last bit is 1, then outputting (s and t) xor v.   
     
     
         18 . A system for decrypting an encrypted message, the decryption system comprising:
 a computerized processor configured for executing instructions:   for each sender-receiver pair:   processing a derived secret key sky and a ciphertext c by a functional encryption decryption algorithm to derive a string s′;   deriving a plaintext message from s′, r and z;   wherein, the plaintext message was previously encrypted by:
 generating a first random string r having a length based on a specified target ciphertext length; 
 generating an at least partially random second string u; 
 encrypting u under a functional encryption scheme to generate c; and 
 deriving z from r and u and m; and 
 outputting z, r, and ciphertext c. 
   
     
     
         19 . The system of  claim 18 , further comprising executing the decryption by:
 for i in the range of 1 to n, executing a public key decryption on the ciphertext ct i,w  using the sk i,w  and storing the output as the plaintext message.   
     
     
         20 . The system of  claim 18 , where deriving plaintext message from s′, r and z further comprises:
 decomposing s′ into s and t; and 
 applying a randomness extractor to r and s, and xoring the result with t. 
 
     
     
         21 . The system of  claim 20 , wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R 1 , . . . , R t  whose total joint min-entropy rate is α, for random and independent seeds S 1 , . . . , S t , close to an α-fraction of the extracted outputs Ext(R 2 ; S i ) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds. 
     
     
         21 . The system of claim  21 , wherein the somewhere randomness extractor Ext(r; s) is constructed as:
 the input r∈{0, 1} n  is interpreted as an l-variate polynomial of total degree g over some field F 2     w    such that n=w·(l+gg);   the seed s=(s 1 , s 2 ) consists of s 1 ∈   2     w     l  and s 2 ∈   2     m     w/w ; and   the output of the extractor is set to  r(s 1 ), s 2   , wherein the polynomial evaluation y=r(s 1 ) is performed over the field F 2     w    and the dot product  y, s 2    is performed over the first    2     m   .