Method for querying data in privacy preserving manner using attributes
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsWei Sun, Shantanu Rane
Life of this patent
Estimating the term…
Abstract
A client queries a set of encrypted data instances located at a server with a query attribute of the client. The set of encrypted data instances is associated with a set of ciphertexts, wherein a ciphertext is an encrypted function of a representation of a corresponding data instance and a data instance attribute extracted from the corresponding data instance. The client decrypts the ciphertext from the set of ciphertexts based on a distance function of the query attribute and the data instance attribute to produce the representation, and accesses the corresponding data instance using the representation.
Claims15
A method for privacy-preserving querying of a set of encrypted data instances located at a server with a query attribute of a client, wherein the set of encrypted data instances is associated with a set of ciphertexts, wherein a ciphertext is an encrypted function of a representation of a corresponding data instance and a data instance attribute extracted from the corresponding data instance, comprising:
- decrypting the ciphertext from the set of ciphertexts based on a distance function of the query attribute and the data instance attribute to produce the representation, wherein the ciphertext is
- C
-
- (
- x
- (
- j
- )
- ,
- L
- j
- ,
- W
- )
- =
- (
- A
- 0
- ,
- {
- A
- i
- }
- i
- =
- 1
- n
- ,
- A
- _
- ,
- B
- ,
- H
- j
- )
- ,
-
- wherein
- A
- 0
- =
- (
- g
- q
-
- c
- )
- γ
- ,
-
- A
- i
- =
- (
- g
- q
-
- c
- )
- γ
-
-
- x
- i
- (
- j
- )
-
- s
- i
- ,
-
- A
- _
- =
- s
- 0
-
- (
- g
- q
-
- c
- )
- γ
-
- ∑
- i
- =
- 1
- n
-
-
- (
- x
- i
- (
- j
- )
- )
- 2
- ,
- B=gpδ, Hj=Lj·e(gp, α)δ, wherein p, q, r are primes of cyclic groups G and GT of order N=pqr, Gp, Gq and Gr are cyclic groups with orders p, q and r respectively with generators gp, gq and gr respectively, e:G×G→GT is a non-degenerate bilinear map, a belongs to Gp and c belongs to Gr are randomly chosen parameters, W=(N, gp, gr, gqc, e(gp, α)), and the ciphertext is encrypted with a private master key (p, q, r, gq, α, c);
- and
- accessing the corresponding data instance using the representation, wherein steps of the method are performed by a processor of the client.
A method for privacy-preserving querying a set of encrypted data instances with a query attribute, wherein the set of encrypted data instances is associated with a set of ciphertexts, wherein a ciphertext is an encrypted function of a representation of a corresponding data instance and a data instance attribute extracted from the corresponding data instance, and wherein the querying is based on a distance function of the query attribute, and the data instance attribute, wherein the ciphertext is C(x(j), Lj, W)=(A0,{Ai}i=1n, Ā, B, Hj), wherein
- A
- 0
- =
- (
- g
- g
-
- c
- )
- γ
- ,
- A
- i
- =
- (
- g
- g
-
- c
- )
- γ
-
-
- x
- i
- (
- j
- )
-
- s
- i
- ,
- A
- _
- =
- s
- 0
-
- (
- g
- q
-
- c
- )
- γ
-
- ∑
- i
- =
- 1
- n
-
- (
- x
- i
- (
- j
- )
- )
- 2
- ,
- B=gpδ, Hj=Lj·e(gp, α)δ, wherein p, q, r are primes of cyclic groups G and GT of order N=pqr, Gp, Gq and Gr are cyclic groups with orders p, q and r respectively with generators gp, gq and gr respectively, e:G×G→GT is a non-degenerate bilinear map, α belongs to Gp and c belongs to Gr are randomly chosen parameters W=(N, gp, gr, gqc, e(gp, α)), and the ciphertext is encrypted with a private master key (p, q, r, gq, α, c), the method comprising:
- receiving, in response to transmitting a masked query attribute a pre-decryption key including elements of multiplicative groups wherein a number of the elements and a mathematical form of the elements correspond to a polynomial structure of the distance function and the masked query attribute;
- determining a decryption key based on the pre-decryption key and the masked query attribute;
- determining, using the decryption key, a product of the representation with an expression that evaluates to one when a result the distance function corresponds to a value bound by a threshold;
- and
- accessing the corresponding data instance using the representation, wherein steps of the method are performed by a processor.
A system for privacy-preserving querying a set of encrypted data instances with a query attribute, wherein the set of encrypted data instances is associated with a set of ciphertexts, wherein a ciphertext is an encrypted function of a representation of a corresponding data instance and a data instance attribute extracted from the corresponding data instance, comprising:
- a processor for decrypting the ciphertext from the set of ciphertexts based on a distance function of the query attribute and the data instance attribute to produce the representation, wherein the decrypting is successful if and only if a result of the distance function is less than a threshold, wherein the ciphertext is
- C(x(j), Lj, W)=(A0, {Ai}i=1n, Ā, B, Hj), wherein
- A
- 0
- =
- (
- g
- g
-
- c
- )
- γ
- ,
- A
- i
- =
- (
- g
- g
-
- c
- )
- γ
-
-
- x
- i
- (
- j
- )
-
- s
- i
- ,
- A
- _
- =
- s
- 0
-
- (
- g
- q
-
- c
- )
- γ
-
- ∑
- i
- =
- 1
- n
-
- (
- x
- i
- (
- j
- )
- )
- 2
- ,
- B=gpδ, Hj=Lj·e(gp, α)δ, wherein p, q, r are primes of cyclic groups C and Gr of order N=pqr, Gp, Gq and Gr are cyclic groups with orders p, q and r respectively with generators gp, gq and gr respectively, e:
- G×G→GT is a non-degenerate bilinear man, a belongs to Gp and c belongs to Gr are randomly chosen parameters, W=(N, gp, gr, gqc, e(gp, α)), and the ciphertext is encrypted with a private master key (p, q, r, gp, α, c).
Dependencies are inferred from the claim text.