# US 2024/0267213 A1 · System and Method for Security Against Bounded-Storage Mass Surveillance

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0267213 A1
- Document ID: US20240267213A1
- Status: Published application
- Kind: A1
- Application number: 18/437,215
- Filed: 2024-02-08
- Published: 2024-08-08
- Earliest claimed: 2023-02-08
- Assignees: NTT Research, Inc.
- Applicants: NTT Research, Inc.
- Inventors: Jiaxin Guan; Daniel Wichs; Mark Zhandry
- Web page: https://patentgrep.com/patent/US20240267213A1

## CPC

- H04L 9/0869: {involving random numbers or seeds}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

The method of claim 2, wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R1, . . . , Rt whose total joint min-entropy rate is α, for random and independent seeds S1, . . . , St, close to an α-fraction of the extracted outputs Ext(Ri; Si) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds.

### Claim 4 (depends on 3)

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 F2w such that n=w·(l+gg);
the seed s=(s1, s2) consists of s1∈2wl and s2∈w/m2m; and
the output of the extractor is set to r(s1), s2, wherein the polynomial evaluation y=r(s1) is performed over the field F2w and the dot product y, s2 is performed over the first 2m.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 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.

### Claim 8 (depends on 7)

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 cti,w using the ski,w and storing the output as the plaintext message.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 9)

The method of claim 9, wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R1, . . . , Rt whose total joint min-entropy rate is α, for random and independent seeds S1, . . . , St, close to an α-fraction of the extracted outputs Ext(Ri; Si) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds.

### Claim 11 (depends on 10)

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 F2w such that n=w·(l+gg);
the seed s=(s1, s2) consists of s1∈2wl and s2∈2mw/m; and
the output of the extractor is set to r(s1), s2, wherein the polynomial evaluation y=r(s1) is performed over the field F2w and the dot product y, s2 is performed over the first 2m.

### Claim 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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 13)

The system of claim 13, wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R1, . . . , Rt whose total joint min-entropy rate is α, for random and independent seeds S1, . . . , St, close to an α-fraction of the extracted outputs Ext(Ri; Si) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds.

### Claim 15 (depends on 14)

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 F2w such that n=w·(l+gg);
the seed s=(s1, s2) consists of s1∈2wl and s2∈2mw/m; and
the output of the extractor is set to r(s1), s2, wherein the polynomial evaluation y=r(s1) is performed over the field F2w and the dot product y, s2 is performed over the first 2m.

### Claim 16 (depends on 12)

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.

### Claim 17 (depends on 12)

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.

### Claim 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.

### Claim 19 (depends on 18)

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 cti,w using the ski,w and storing the output as the plaintext message.

### Claim 20 (depends on 18)

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.

### Claim 21 (depends on 20)

The system of claim 20, wherein the extractor Ext is somewhere randomness extracting, wherein somewhere randomness extracting further comprises: for any random variables R1, . . . , Rt whose total joint min-entropy rate is α, for random and independent seeds S1, . . . , St, close to an α-fraction of the extracted outputs Ext(R2; Si) is guaranteed to be jointly statistically indistinguishable from uniform, even given all the remaining extracted outputs and all the seeds.

### Claim 21 (depends on 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 F2w such that n=w·(l+gg);
the seed s=(s1, s2) consists of s1∈2wl and s2∈2mw/w; and
the output of the extractor is set to r(s1), s2, wherein the polynomial evaluation y=r(s1) is performed over the field F2w and the dot product y, s2 is performed over the first 2m.
