Granted Patent B2

US 9,672,564 · App. 13/802,801 · Granted Jun 6, 2017

Inventor: Philippe Jean-Paul Golle (San Francisco, CA)

Assignee: Palo Alto Research Center Incorporated

G06Q40/04G06F21/602G06Q50/10

Abstract

Claims (122)

1. A computer-implemented system for providing private stable matchings through a re-encryption mix network, comprising:

a storage to maintain encrypted preferences, comprising encrypted preferences for a set of active participants comprising one unique preference for each participant in a set of passive participants, encrypted preferences for a set of pseudo participants comprising one unique preference for each participant in the set of passive participants, and encrypted preferences for a set of passive participants comprising one unique preference for each participant in the set of active participants and one unique preference for each participant in the set of pseudo participants, such that each pseudo participant preference is less preferred than each matcher preference; and

one or more matching authorities, each associated with a public and private key pair and comprising memory, a central processing unit, an input port to receive the encrypted preferences from the storage, and an output port, wherein the central processing unit is configured to:

create bids, comprising a set of unmatched bids initially comprising the encrypted preferences for each participant in the set of active participants, and a set of matched bids initially comprising the encrypted preferences and the preference of the passive participant identified in one of the encrypted preferences for each participant in the set of pseudo participants;

perform an initial mixing, comprising externally mixing the set of unmatched bids and the set of matched bids independently, and internally mixing a union of the set of unmatched bids and the set of matched bids;

permute, during the internal mixing, each unmatched bid as π(W i )=[E(i), π(a i ), π(v i ), π(q i ), E(p)], where the unmatched bid is denoted as W i =[E(i), a i , v i , q i , E(p)] and the permuted vectors π(a i ), π(v i ), and π(q i ) are defined as π(a i )=(p′ i,π(1) , . . . , p′ i,π(n) ), π(v i )=(E′ π(1) , . . . , E′ π(n) ), π(q i )=(q′ i,π(1) , . . . , q′ i,π(n) ), which each include re-encryption of ciphertext;

determine, for the number of participants in the set of active participants, a stable match for one of the passive participants, while the set of unmatched bids remains non-empty by maintaining-encrypted rankings for each internal mixing of the encrypted preferences in the set of unmatched bids, selecting one unmatched bid from the set of unmatched bids and learning the encrypted preference and the preference of the passive participant identified in the encrypted preference in the selected unmatched bid based on the encrypted rankings, resolving a conflict between the selected unmatched bid and one matched bid in the set of matched bids that comprises the encrypted preference that identifies the same passive participant that is identified in the encrypted preference, wherein one of the unmatched bid and the matched bid is assigned to the set of matched bids and the other bid is assigned to the set of unmatched bids for a next stable match, and the set of matched bids is designated as the set of matched bids for the next stable match, performing an interim mixing, comprising externally mixing the set of matched bids, and internally mixing a union of the set of matched bids, the set of unmatched bids for the current stable match, and the set of unmatched bids for the next stable match and performing a final mixing when the set of unmatched bids becomes empty, comprising externally mixing the set of matched bids for the next stable match and the set of unmatched bids for the next stable match independently, and internally mixing a union of the set of matched bids for the next stable match and the set of unmatched bids for the next stable match; and

externally mix the set of matched bids for the last stable match and to decrypt the preferences in the set of matched bids via the private key to identify the passive participants stably matched to the active participants without disclosing preferences of the active and passive participants.

2. A system according to claim 1 , wherein each unmatched bid comprises an encryption of the index of the participant, a vector comprising the encrypted preferences, a vector comprising the rankings, a vector comprising an initial ranking given to the participant, and a count of a number of times that the unmatched bid has been rejected.

3. A system according to claim 1 , wherein the preferences are encrypted as vectors of Paillier ciphertexts and the external mixing is performed by re-encrypting each of the Paillier ciphertexts in the vectors of preferences.

4. A system according to claim 1 , wherein the bids are encrypted as vectors of Paillier ciphertexts and the internal mixing is performed by internally permuting the bids as re-encryptions of the Paillier ciphertexts in the vectors of bids.

5. A system according to claim 1 , wherein the preferences are encrypted as vectors of Paillier ciphertexts and only the Paillier ciphertexts in the preferences in the set of matched bids is retained prior to the decrypting.

6. A system according to claim 1 , further comprising:

a matched bid permuter to permute each matched bid as (π(W i ), E(j), q j,i ), where the matched bid is denoted as (W i , E(j), q j,i ).

7. A system according to claim 1 , further comprising:

a passive adversaries accommodator to accommodate passive adversaries comprising proofs of correctness by matching authorities, comprising:

a conflict resolving performer to perform one re-encryption network for the conflict resolving;

an external mixing performer to perform one re-encryption network for the external mixing; and

an internal mixing performer to perform one re-encryption network for the internal mixing.

8. A system according to claim 1 , further comprising:

an active adversaries accommodator to accommodate active adversaries comprising proofs of correct protocol execution by the participants and matching authorities;

a preference vector matcher to match each preference vector of each participant, wherein the preference is encrypted as vectors of Paillier ciphertexts, with the preferences of that participant; and

a verifier to confirm verification of the preference vector by the matching authorities.

9. A computer-implemented method for providing private stable matchings through a re-encryption mix network, comprising the steps of:

encrypting preferences maintained in storage, comprising:

encrypting preferences for a set of active participants comprising one unique preference for each participant in a set of passive participants;

encrypting preferences for a set of pseudo participants comprising one unique preference for each participant in the set of passive participants; and

encrypting preferences for a set of passive participants comprising one unique preference for each participant in the set of active participants and one unique preference for each participant in the set of pseudo participants, such that each pseudo participant preference is less preferred than each matcher preference;

creating bids via one or more matching authorities, each matching authority associated with a public and private key pair and comprising memory, a central processing unit, an input port to receive the encrypted preferences from the storage, and an output port, comprising:

forming a set of unmatched bids initially comprising the encrypted preferences for each participant in the set of active participants; and

forming a set of matched bids initially comprising the encrypted preferences and the preference of the passive participant identified in one of the encrypted preferences for each participant in the set of pseudo participants;

performing an initial mixing, comprising externally mixing the set of unmatched bids and the set of matched bids independently, and internally mixing a union of the set of unmatched bids and the set of matched bids;

determining via the matching authorities, for the number of participants in the set of active participants, a stable match for one of the passive participants, while the set of unmatched bids remains non-empty, comprising:

maintaining encrypted rankings for each internal mixing of the encrypted preferences in the set of unmatched bids;

selecting one unmatched bid from the set of unmatched bids and learning the encrypted preference and the preference of the passive participant identified in the encrypted preference in the selected unmatched bid based on the encrypted rankings;

resolving a conflict between the selected unmatched bid and one matched bid in the set of matched bids that comprises the encrypted preference that identifies the same passive participant that is identified in the encrypted preference;

assigning one of the unmatched bid and the matched bid to the set of matched bids and assigning the other bid to the set of unmatched bids for a next stable match, and designating the set of matched bids as the set of matched bids for the next stable match;

performing an interim mixing, comprising externally mixing the set of matched bids, and internally mixing a union of the set of matched bids, the set of unmatched bids for the current stable match, and the set of unmatched bids for the next stable match;

permuting, during the internal mixing, each unmatched bid as π(W i )=[E(i), π(a i ), π(v i ), π(q i ), E(p)], where the unmatched bid is denoted as W i =[E(i), a i , v i , q i , E(p)] and the permuted vectors π(a i ), π(v i ), and π(q i ) are defined as π(a i )=(p′ i,π(1) , . . . , p′ i,π(n) ), π(v i )=(E′ π(1) , . . . , E′ π(n) ), π(q i )=(q′ i,π(1) , . . . , q′ i,π(n) ), which each include re-encryption of ciphertext; and

performing a final mixing when the set of unmatched bids becomes empty, comprising externally mixing the set of matched bids for the next stable match and the set of unmatched bids for the next stable match independently, and internally mixing a union of the set of matched bids for the next stable match and the set of unmatched bids for the next stable match; and

externally mixing the set of matched bids for the last stable match and decrypting the preferences in the set of matched bids via the private key to identify the passive participants stably matched to the active participants without disclosing preferences of the active and passive participants.

10. A method according to claim 9 , wherein each unmatched bid comprises an encryption of the index of the participant, a vector comprising the encrypted preferences, a vector comprising the rankings, a vector comprising an initial ranking given to the participant, and a count of a number of times that the unmatched bid has been rejected.

11. A method according to claim 9 , wherein the preferences are encrypted as vectors of Paillier ciphertexts and the external mixing is performed by re-encrypting each of the Paillier ciphertexts in the vectors of preferences.

12. A method according to claim 9 , wherein the bids are encrypted as vectors of Paillier ciphertexts and the internal mixing is performed by internally permuting the bids as re-encryptions of the Paillier ciphertexts in the vectors of bids.

13. A method according to claim 9 , wherein the preferences are encrypted as vectors of Paillier ciphertexts and only the Paillier ciphertexts in the preferences in the set of matched bids is retained prior to the decrypting.

14. A method according to claim 9 , further comprising:

permuting each matched bid as (π(W i ) E(j), q j,i ), where the matched bid is denoted as (W i , E(j), q j,i ).

15. A method according to claim 9 , further comprising:

accommodating passive adversaries comprising proofs of correctness by matching authorities, comprising:

performing one re-encryption network for the conflict resolving;

performing one re-encryption network for the external mixing; and

performing one re-encryption network for the internal mixing.

16. A method according to claim 9 , further comprising:

accommodating active adversaries comprising proofs of correct protocol execution by the participants and matching authorities;

matching each preference vector of each participant, wherein the preference is encrypted as vectors of Paillier ciphertexts, with the preferences of that participant; and

confirming verification of the preference vector by the matching authorities.

17. A method according to claim 16 , further comprising:

performing the proofs of correct protocol execution of each participant's preference vector as

⋀

j

∈

{

0

,

…

⁢

,

n

-

1

}

⁢

(

⋁

i

∈

{

0

,

…

⁢

,

n

}

⁢

(

E

-

1

⁡

(

E

⁡

(

r

i

)

)

=

j

)

)

.

18. A method according to claim 9 , wherein the steps are executed via a computer system and stored in a computer-readable persistent storage medium.

19. A computer-implemented method for providing private stable matchings through a re-encryption mix network, comprising:

encrypting preferences maintained in storage, comprising:

encrypting preferences for a set of active participants comprising one unique preference for each participant in a set of passive participants;

encrypting preferences for a set of pseudo participants comprising one unique preference for each participant in the set of passive participants; and

encrypting preferences for a set of passive participants comprising one unique preference for each participant in the set of active participants and one unique preference for each participant in the set of pseudo participants, such that each pseudo participant preference is less preferred than each matcher preference;

creating bids via one or more matching authorities, each matching authority associated with a public and private key pair and comprising memory, a central processing unit, an input port to receive the encrypted preferences from the storage, and an output port, comprising:

forming a set of unmatched bids initially comprising the encrypted preferences for each participant in the set of active participants; and

forming a set of matched bids initially comprising the encrypted preferences and the preference of the passive participant identified in one of the encrypted preferences for each participant in the set of pseudo participants;

performing an initial mixing, comprising externally mixing the set of unmatched bids and the set of matched bids independently, and internally mixing a union of the set of unmatched bids and the set of matched bids;

determining via the matching authorities, for the number of participants in the set of active participants, a stable match for one of the passive participants, while the set of unmatched bids remains non-empty, comprising:

maintaining encrypted rankings for each internal mixing of the encrypted preferences in the set of unmatched bids;

selecting one unmatched bid from the set of unmatched bids and learning the encrypted preference and the preference of the passive participant identified in the encrypted preference in the selected unmatched bid based on the encrypted rankings;

resolving a conflict between the selected unmatched bid and one matched bid in the set of matched bids that comprises the encrypted preference that identifies the same passive participant that is identified in the encrypted preference;

assigning one of the unmatched bid and the matched bid to the set of matched bids and assigning the other bid to the set of unmatched bids for a next stable match, and designating the set of matched bids as the set of matched bids for the next stable match;

performing an interim mixing, comprising externally mixing the set of matched bids, and internally mixing a union of the set of matched bids, the set of unmatched bids for the current stable match, and the set of unmatched bids for the next stable match;

permuting, during the internal mixing, each matched bid as (π(W i ), E(j), q j,i ), where the matched bid is denoted as (W i , E(j), q j,i ); and

performing a final mixing when the set of unmatched bids becomes empty, comprising externally mixing the set of matched bids for the next stable match and the set of unmatched bids for the next stable match independently, and internally mixing a union of the set of matched bids for the next stable match and the set of unmatched bids for the next stable match; and

externally mixing the set of matched bids for the last stable match and decrypting the preferences in the set of matched bids via the private key to identify the passive participants stably matched to the active participants without disclosing preferences of the active and passive participants.

Assignments (8)

Continuity (3)