WO2006103608A2 - Negociation privee - Google Patents

Negociation privee Download PDF

Info

Publication number
WO2006103608A2
WO2006103608A2 PCT/IB2006/050909 IB2006050909W WO2006103608A2 WO 2006103608 A2 WO2006103608 A2 WO 2006103608A2 IB 2006050909 W IB2006050909 W IB 2006050909W WO 2006103608 A2 WO2006103608 A2 WO 2006103608A2
Authority
WO
WIPO (PCT)
Prior art keywords
attributes
station
acceptable
agreed
sets
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IB2006/050909
Other languages
English (en)
Other versions
WO2006103608A3 (fr
Inventor
Pim T. Tuyls
Klaus Kursawe
Gregory K. R. Neven
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Koninklijke Philips NV
Original Assignee
Koninklijke Philips Electronics NV
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Koninklijke Philips Electronics NV filed Critical Koninklijke Philips Electronics NV
Publication of WO2006103608A2 publication Critical patent/WO2006103608A2/fr
Publication of WO2006103608A3 publication Critical patent/WO2006103608A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/12—Details relating to cryptographic hardware or logic circuitry
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/46—Secure multiparty computation, e.g. millionaire problem

Definitions

  • the invention relates to a method of automatic agreeing on a set of attributes between a plurality of stations in a computer network.
  • the invention further relates to a computer program product for causing a processor to execute such method.
  • the invention also relates to a system for agreeing on a set of attributes between a plurality of stations in a computer network.
  • the invention further relates to a station for automatic agreeing on a set of attributes with at least one other station.
  • P3P Platform for Privacy Preferences Project
  • P3P Platform for Privacy Preferences Project
  • a user can thus define his personal privacy policy, and automatically get a warning if the policy of an organization he interacts with does not match (assuming the organization does provide a P3P policy).
  • P3P is a standardized set of multiple- choice questions, covering all the major aspects of a Web site's privacy policies. Taken together, they present a snapshot of how a site handles personal information about its users. P3P-enabled Web sites present their data-collection practices in a standardized, machine- readable, easy-to-locate manner. P3P-enabled browsers can "read” this snapshot automatically and compare it to the consumer's own set of privacy preferences. P3P enables Web users to understand what data will be collected by sites they visit, how that data will be used, and what data/uses they may "opt-out" of or "opt-in” to.
  • a P3P enabled browser may automatically fetch the P3P policy for a home page specified by the user.
  • the policy might state that the only data the site collects on its home page is the data found in standard HTTP access logs.
  • the browser then checks this policy against the preferences of the user. For example, is this policy acceptable, or should the user be notified? If the user has selected a checkout page of an on-line shop then some additional information is required, such as the user's name, address, credit card number, and telephone number. For that page another P3P policy is available that describes the data that is collected here and states that this data will be used only for completing the current transaction. The browser examines this P3P policy.
  • the user may have specified in the browser that the user wants to be warned whenever a site asks for the telephone number. In this case, the browser will pop up a message saying that this Web site is asking for the telephone number, and explaining the contents of the P3P statement. The user can then decide if this is acceptable and continue with the on-line order; otherwise the user can cancel the transaction. More complex criteria may also have been given to the browser. For example, the user may have indicated to be warned only if a site is asking for the telephone number and was going to give it to third parties and/or use it for uses other than completing the current transaction.
  • the current version of P3P does not deal with negotiation on a policy to be used. Rather, the server simply reveals its policy, and the client then proceeds with the interaction, or not. This works as long there is only one option that must be accepted or rejected by the user. In more complex situations where in principle one or more of the parties involved would be willing to interact with the other party under one of several possible options it is required to negotiate such an option, i.e. find a policy that is acceptable to all parties involved.
  • the negotiated policy can be seen as a set of values for a given set of attributes (such as a users' telephone number).
  • the method of agreeing on a set of attributes between a plurality of stations in a computer network includes: in each station determining at least one respective set of attributes that is acceptable for the station to be agreed with the other station by for each set of attributes selected the attributes from a predetermined list of attributes and arranging the sets of attributes in a predetermined order; using a predetermined multi-party computation protocol to evaluate in each station the respective ordered lists of acceptable sets without revealing to the other station any information other than a willingness to accept the agreed set, and to determine the agreed set based on the evaluation.
  • the client's privacy is protected as the client does not reveal any data outside the ones automatically revealed in contacting the server. If negotiations are introduced, however, the problem of privacy is not that simple, especially if there is reason to protect the privacy of the server as well. Usually, it is assumed that both sides somehow agree on a common policy specifying what data will be transmitted and how sensitive data should be handled. In very privacy-sensitive settings, this negotiation is complicated by the additional effect that a person's privacy preferences may already give away information about that person. Since the vast majority of the population is still willing to reveal seemingly innocent data (e.g. their monthly consumption of alcohol), a person that considers this piece of data as sensitive might quickly raise suspicion and consequently be treated with a worst-case assumption (e.g.
  • the method according to the invention enables automatic agreement on a set of attributes by applying a secure multi-party computation protocol for negotiating the set of attributes.
  • a secure multi-party computation protocol for negotiating the set of attributes.
  • an agreed set can be determined (if that exists) without revealing to the other party information other than a willingness to accept the agreed set.
  • a server can thus not detect the privacy preferences of a client station whereas still an agreed set can be negotiated.
  • privacy settings are themselves considered as private data. It will be appreciated that the scope of the invention is much broader than negotiating a policy between a client station and a server.
  • the invention covers automatic negotiation between at least two computing devices where each device has at least one acceptable set of attributes from a predetermined list of attributes.
  • the sets that are not agreed are not revealed.
  • the multi-party computation protocol is based on a homomorphic encryption system. Using such an encryption system makes the evaluation fast.
  • the homomorphic encryption system is an El Gamal or Paillier type of encryption. Both are established suitable encryption systems where El Gamal has the additional advantage of an efficient generation of the encryption keys being used.
  • the method includes the step of representing for each stations the acceptable sets of attributes using respective truth tables including a preference column that for each possible set of attributes of the predetermined list of attributes includes information on a level of acceptability of the set.
  • the method includes selecting for a first one of the stations a generating subset of acceptable sets of attributes where an acceptable set of attributes of the first one of the stations is a generating subset if there is no other acceptable set of attributes that fully includes the acceptable set of attributes; and selecting for a second one of the station a generating subset of acceptable sets of attributes where an acceptable set of attributes of the second one of the stations is a generating subset if there is no other acceptable set of attributes that includes not at least one of the attributes of the acceptable set of attributes. Selecting the so-called generating subsets can significantly reduce the number of sets that need to be evaluated, increasing speed.
  • the first station plays in the negotiation a 'client' role.
  • the client station is willing to accept set A (e.g. to reveal the attributes on set A to the other station) then automatically the client station is also willing to accept a related set B with less of those attributes (B cz A) .
  • B is not a generating subset.
  • a candidate acceptable set for the first station is thus a 'generating subset' if it is not itself a subset of a larger acceptable set, where larger means that that set includes all attributes of the candidate set and at least one more.
  • the second station plays in the negotiation a 'server' role. If the server station is willing to accept set A (e.g.
  • a candidate acceptable set for the second station is thus not a 'generating subset' if there is smaller acceptable set, where 'smaller' means that all the attributes of the smaller set are also member of the candidate set. If this is not the case, then the acceptable set is a generating subset.
  • a Boolean circuit implementing a process of matching the generating subsets, where the generating subsets the respective preference columns for the generating subsets are used as input and an index representing a mutually acceptable set of attributes is generated as output.
  • a Boolean circuit is a representation that can easily be evaluated by a secure multi-party computation protocol.
  • the predetermined multiparty computation protocol is used to evaluate the Boolean circuit. This is an effective way of achieving a secure multi-party agreement.
  • the method includes using a predetermined selection criterion to select the agreed set among a plurality of mutually acceptable sets of attributes. In this way a choice can be made between multiple mutually acceptable candidate sets. Any suitable selection criterion may be used, such as the first acceptable set on the list, assigning weights to preferred sets, etc.
  • the method further includes agreeing on a set of obligations between the stations; each of the stations being associated with at least one respective set of obligations selected from a predetermined list of obligations; the method including using the multi-party computation protocol to determine the agreed set of obligations without revealing other information than a willingness to accept the agreed set of obligations.
  • the method including using the multi-party computation protocol to determine the agreed set of obligations without revealing other information than a willingness to accept the agreed set of obligations.
  • a computer program product for causing a processor to execute the method as claimed in claim 1.
  • a system for automatic agreeing on a set of attributes includes a plurality of stations arranged to communicate through a computer network, where each station includes: respective means for determining at least one respective set of attributes that is acceptable for the station to be agreed with the other station by for each set of attributes selecting the attributes from a predetermined list of attributes and arranging the sets of attributes in a predetermined order; and respective means for executing a predetermined multi-party computation protocol to evaluate in each station the respective ordered lists of acceptable sets without revealing to the other station any information other than a willingness to accept the agreed set, and to determine the agreed set based on the evaluation.
  • a station for automatic agreeing on a set of attributes with at least one other station and arranged to communicate through a computer network with the at least one other station includes means for determining at least one set of attributes that is acceptable for the station to be agreed with the at least one other station by for each set of attributes selecting the attributes from a predetermined list of attributes and arranging the sets of attributes in a predetermined order; and means for participating in a predetermined multi-party computation protocol to evaluate the ordered list of acceptable sets without revealing to the at least one other station any information other than a willingness to accept the agreed set, and to determine the agreed set based on the evaluation.
  • Fig. 1 shows a block diagram of a system in which the invention may be employed
  • Fig. 2 shows a flow diagram of the method according to the invention
  • Fig. 3 shows a Boolean circuit representing the acceptable sets to be securely evaluated
  • Fig. 4 illustrates an extension to the Boolean circuit incorporating conditions.
  • the method and system according to the invention deal with multiple parties in a computer network agreeing on a set of attributes to be used.
  • the invention will be described for two parties. Persons skilled in the art can easily extent the principle to more than two parties using the multi-party computational protocol for more than two parties.
  • the negotiation (agreement) is performed automatically. As such the parties can be seen as 'computing devices', or 'stations'. Since such a device is usually controlled by a human, it is assumed that the negotiating is performed on behalf of the human. In the description, the term 'party' will thus sometimes be used as referring to a user on which behalf the station operates.
  • Fig. 1 shows a block diagram of an exemplary system in which the invention may be used.
  • the system 100 includes at least a first station 110 and a second station 120.
  • the stations (parties) can communicate via a computer network 130, such as Internet.
  • a computer network 130 such as Internet.
  • the stations are equipped with suitable hardware and/or software, shown as block 116 and 126, respectively.
  • Such hardware/software is well-known and will not be described here any further.
  • the stations are equipped with a respective user interface 112, 122 for interaction with a user or human operator. Any suitable user interface may be used, such as display and keyboard/mouse.
  • the core of the processing defined by the invention is performed by a digital processor, such as a general purpose microprocessor or signal processor.
  • a secure module which in itself is well-known.
  • a secure module may but need not include a specialized cryptographic processor which is optimized for fast execution of cryptographic operations.
  • the stations itself may be based on conventional computer platforms such as a desktop PC, a server computer, or even mobile computing platforms, such as PDAs or advanced mobile phones. It will be appreciated that the stations may further be equipped with conventional means such as a main memory (RAM-type), permanent memory (e.g. ROM, hard disk, flash, etc.), internal buses, etc.
  • the memory may be used to store, for example, the attribute sets.
  • Fig. 2 shows an exemplary structure of steps that can be performed by the processors 114, 124. Each of those steps may be implemented in a separate software procedure, but may also be combined in less software modules. Each of the stations in principle performs the same operations.
  • step 210 of all possible sets of attributes the subset of attributes is determined that is acceptable to the station. Typically, a human user/operator indicates this to the station via the user interface 112, 122, respectively.
  • the number of acceptable sets is reduced to those sets that can be regarded as the generating subsets. This reduces the number of sets that need to be evaluated.
  • Step 230 shows a further optional step wherein additional conditions are determined for each of the stations as will be described in more detail below.
  • the secure multi-party computation protocol is executed to evaluate the agreeable attribute sets and optional conditions in order to find a set on which the stations agree.
  • a Boolean circuit is built representing the attribute sets (and optional conditions) to be evaluated.
  • the Boolean circuit is a 'virtual' circuit in the sense that the gates of the circuit need not be implemented using actual electronic gates.
  • known secure multi-party computation protocols may be used to evaluate the logical circuit in a known way. Notations
  • N ⁇ 0,l,2,... ⁇ be the set of natural numbers.
  • Z ⁇ ...,-2,-l,0,l,2,... ⁇ be the set of integers. If k& N , then 0* is the Ar-bit string of k zeros, and ⁇ is the Ar-bit string of k ones. The individual bits of a Ar-bit string x are indicated as X 0 , ... , x k _ ⁇ .
  • 'server' one of the parties that is offering a service
  • 'client' or 'user' The 'client' and 'server' may be formed by a client station and server station, respectively, as for example known from Internet.
  • the two parties may be involved in a peer-to-peer (P2P) interaction through the Internet.
  • P2P peer-to-peer
  • one of the stations requests a 'service' from the other station.
  • the agreement could result in a transfer of data (e.g. audio/video) from a server station to a client station, it could result in the sale of a product or delivery of a service by the owner of the server to the user of the client, etc..
  • data e.g. audio/video
  • the server itself provides a service to the client.
  • the agreement could be seen as part of a contract between two parties which, according to the invention, is established using electronic means and in a secure way so that no third party can see the negotiation and not even the parties involved can see what the other party would be willing to accept other than the final outcome of the process. So, the parties can keep all their cards on the table and only need to reveal the card that they known the other party will accept.
  • preferences of a user is meant a strategy defining which attributes (e.g. credit card number, address, ...) the user is willing to reveal in turn for getting a certain service.
  • a server's preferences defines the set of attributes required from a user in turn for offering a certain service.
  • the negotiation according to the invention refers to the process of finding out whether the attributes that the user wants to reveal correspond to the set of attributes that the server requires.
  • a combination of attributes is a matching subset if it is acceptable to both the client and the server. More formally, the problem of subset matching is defined as follows: Let A be a predetermined set of attributes, and let S be a totally ordered set of scores with least element 0.
  • Preferences over the set of attributes A are described by a function f:2 A ⁇ S that assigns to each subset of attributes A c A a score SG S , indicating the client's willingness to reveal the combination of attributes A (in the case of client preferences), or indicating the server's inclination to accept that combination of attributes as sufficient to access the service (in the case of server preferences).
  • a matching function M:2 A x Sx S ⁇ S assigns to A ⁇ A a matching score based on A, the client's willingness f(A) and the server's acceptance g(A) .
  • a combination of attributes A c A is said to be a matching subset with respect to client preferences / , server preferences g and matching function M if M(A,f(A),g(A)) > 0 .
  • a best matching subset is a subset A ⁇ A for which M(A,f(A),g(A)) is maximal.
  • S ⁇ 0,1 ⁇ , meaning that a client is either willing to reveal a combination of attributes (e.g. indicated using a binary 1) or not (e.g. indicated using a binary 0).
  • private subset negotiation is meant a matching process between the client and the server where during the process they learn nothing about each other's preferences (i.e. agreeable subsets) except whether a matching subset exists, and possibly what that matching subset is.
  • the functions f(x) and g(x) are preferably represented through their truth tables, as illustrated in the following tables.
  • the top row shows the possible attributes.
  • Each other row represents an attribute subset.
  • the matching process is performed using a Boolean circuit with as input the client's input in the form of the bit string
  • this is used by determining the so-called generating subsets for both the client and the server respectively.
  • generating subsets are expressed as follows.
  • These generating subsets are a very compact representation of the client's and server's preferences. Preferably, they are generated automatically by analyzing the preferences given by a user (i.e. the agreeable subsets). Alternatively, via a user interface the user of the clients station or server, respectively, may be requested to specify this set of generating subsets.
  • a human user normally has a good idea of the "minimal"' combinations of attributes he doesn't want to reveal, independent of whether additionally even more attributes being revealed. For example, he may be reluctant to simultaneously show his credit card number and his mother's maiden name (the latter is sometimes used as a backup secret to reactivate lost cards), and having to add his favorite color will not make him change his mind.
  • the server knows the minimal information that he needs from users (e.g. name and either email address or phone number), but he won't mind extra attributes being given. The same principle holds for any form of contract negotiations.
  • finding a match is equivalent to finding a set of attributes A ⁇ A such that VF 1 G F .F 1 isnotcz ⁇ , and ⁇ G J G G .G ⁇ A .
  • the matching subset is one of the server's generating subsets, if a match exists. This is the match with the smallest number of shown attributes). Therefore, the condition for the matching subset A can be written more compactly as the set of attributes AG G . such that VF 1 G F .F 1 is not c A .
  • the client's input consists of the generating subsets F 1 ,..., F a encoded as n - bit strings, where the j -th bit of F 1 is 1 iff attribute a 7 e F 1 .
  • the server's input consists of the subsets G 1 ,... , G b in the same encoding. It is noted that the values of a and b may leak information about the complexity of the respective client's and server's preferences. To avoid such leaking it is preferred that the circuit is designed for some predetermined maximum values of a and b .
  • the client and server assign then arbitrary values to unused F 1 and G 7 entries, but distinguish "real" subsets from “dummy" subsets, for example by setting the additional input bits f t and g j to 1 or 0, respectively.
  • M takes the value 0,...,0.
  • Gates with multiple fan- in in Fig. 3 can be implemented as a cascade of binary gates, or as a balanced tree of binary gates. Both options are equivalent in the total number of gates, but the latter option gives a better efficiency in terms of communication rounds.
  • the thick lines in Fig. 3 represent buses, which are essentially collections of parallel wires to carry words, rather than individual bits. Thick gates represent bitwise operations on words, e.g. the bitwise AND of n -bit words x,y e ⁇ 0,1 ⁇ " is the n -bit word
  • the wire labeled C 7 in Fig. 3 carries a one if G 1 is a candidate set, and a zero if not.
  • the output word of the bitwise AND gates in Layer 1 contains a one-bit for each such attribute. OR-ing the n bits of this word together gives 1 iff at least one such attribute exists.
  • the output of the OR-gate is forced to 1 for dummy input sets F 1 , representing the fact that subset G 1 should never be rejected because of a conflict with a dummy set.
  • a second layer L2 of the circuit finds the candidate subset with the lowest index and outputs it as the matching set.
  • the circuit uses intermediate variables e y that are 1 iff a matching set exists among G 1 , ... , G 7 .
  • AND-ing c y with -Ig 7-1 ensures that the only non-zero bit coming out of any of the leftmost AND gates in Layer 2 is on the wire corresponding to the first match.
  • the final gates of the circuit encode a matching set onto the output bus M .
  • layer 2 can be replaced by another selection mechanism than selecting the commonly acceptable subset with the lowest index.
  • the stations may assign weights to subsets acceptable to the stations. Layer 2 would then need to be redesigned to select the candidate with maximum weight. Designing this lies well within the skills of a person skilled in the art. Subset Matching with Obligations
  • the method and system according to the invention are extended to allow the client to express demands concerning certain attributes, such as to delete the data after a certain time, not to forward it to third parties, ....
  • the server expresses which promises he's willing to make for which attributes.
  • a matching subset is then defined as a combination of attributes such that (1) they suffice to access the service, (2) the client is willing to reveal them, and (3) the server is willing to comply with the client's demands related to the revealed attributes.
  • This extension is described for the preferred embodiment with ordered sets but can equally well be applied to the unordered set scenario.
  • the client's demand function d:A ⁇ 2° associates to each attribute a set of obligations that the client demands from the server when revealing that attribute.
  • the server's willingness function w:A ⁇ 2° maps an attribute to the set of obligations that the server is willing to respect for that attribute.
  • a combination of attributes A c A is now said to be a matching subset with respect to client preferences / , server preferences g and matching function M , demand function d and willingness function w if M(A,f(A),g(A)) > 0 and Va G A : d(A) c w(A) .
  • a best matching subset is a subset A c ⁇ for which
  • Fig. 4 illustrates the modification that this extension gives to the circuit of Fig. 3.
  • the circuit now also outputs the obligations O 0 ,..., O n _ ⁇ c O that the server has to adhere to for attributes a 0 , ... , a n _ ⁇ .
  • the circuit in Fig. 4A is inserted between Layers 1 and 2 in Fig.
  • this subcircuit computes a bit c y , indicating whether the server is also willing to make all promises that the client requires for attributes in G 7 .
  • the second circuit in Fig. 4B is to be attached to the right of the circuit in Fig. 3. If attribute ⁇ ( e M , then the bitwise AND gate encodes the client's demands D 1 onto the output promises O 1 , or it encodes the all-zeroes string if ⁇ ( £ M .
  • Encrypted inputs are inputs containing a message unknown to both players. Often they are the result from a previous (intermediate) computation whose result should remain unknown to both users. Clearly, the execution of the protocol should not reveal anything more on the message hidden by the encryption than what is revealed by the result of the protocol.
  • the remainder first background on preferred encryption protocols is given, followed by a description how the gates of the circuit can be securely evaluated. The remainder will focus on using a homomorphic crypto-systems for the evaluation. However other suitable techniques, such as garbled circuit approach or oblivious transfer, may be used and fall within the knowledge of a person skilled in multi-part computation protocols. Homomorphic Encryption
  • E an encryption iunction E
  • E p (m) the encryption of m with the public key p
  • Well-known examples of homomorphic cryptosystems are the El Gamal cryptosystem and the Paillier cryptosystem. In this description, the El Gamal cryptosystem is used, but the Paillier system may also be used. The El Gamal system has the advantage that key generation can be done very efficiently.
  • this DL-problem which we assumed to be infeasible
  • [m] is used to denote an encryption of the message m
  • an (n,t) threshold cryptosystem the private key is distributed over n parties such that only coalitions of size at least t parties can decrypt the message hidden inside a ciphertext.
  • decryption is performed as follows.
  • it is checked whether m e ⁇ 0, 1 ⁇ . If this does not hold decryption fails.
  • DKG Distributed Key Generation
  • Any suitable protocol may be used.
  • a more light-weight one-round protocol may also be used.
  • Domain ⁇ 0,1 ⁇ or any other domain ⁇ a,b ⁇ ,a ⁇ b , can be used instead, as these domains can be transformed into each other by linear transformations: x ⁇ a y + ⁇ b y -a y ) ⁇ x -a)l ⁇ b -a) maps ⁇ a,b ⁇ to ⁇ a ',£' ⁇ .
  • These transformations can be applied directly to homomorphic encryptions, transforming [x] with xe ⁇ a,b ⁇ into [V] with jc'e ⁇ a ⁇ b ⁇ ⁇ .
  • [*],[ ⁇ >] denote encryptions, with xe ⁇ -1,1 ⁇ cZ ? and je Z ? .
  • the following protocol enables players P 1 and P 2 , to compute an encryption [xy] securely.
  • Player P 1 broadcasts an encryption « S 1 » , with S 1 G n ⁇ -1,1 ⁇ .
  • P 1 applies the private-multiplier multiplication protocol to multiplier S 1 and multiplicands [x] and [y] , yielding random encryptions [s ⁇ x] and ⁇ y] .
  • player P 2 broadcasts an encryption « s 2 » , with s 2 e R ⁇ -1,1 ⁇ .
  • P 2 applies the private-multiplier multiplication protocol to multiplier s 2 and multiplicands [s ⁇ x] and [s ⁇ y] , yielding random encryptions [S 1 S 2 X] and [S 1 S 2 ⁇ ] .
  • this protocol takes only one threshold decryption, has a communication complexity of 26& bits (in total) and round complexity of two rounds.
  • the evaluation of this gate requires 15 exponentiations per party while the private multiplier gate requires only 6 exponentiations. Evaluation of the gates
  • the players run a conditional gate on the inputs [x] and [y] and obtain the result [xy] .
  • the described protocol is suitable for negotiation in general and more specifically for negotiating privacy preferences. It can be used in various settings where it is not sufficient to simply match attributes, but to allow users to negotiate a match based on more complicated preferences. Some examples are: Non-humiliating dating.
  • the protocol may further be used for classical negotiation deals, i.e., for buying goods or services.
  • Classical private negotiation systems are one-dimensional, i.e., both parties define an amount of money they are willing to spent or want to get, respectively, and the system tells them if a deal can happen (and potentially, for how much).
  • Most negotiations today have more facets.
  • the seller may offer some discount if paid in cash, or if several items are bought, and the buyer may pay more if home delivery is ensured, or the warranty is extended. Assuming the number of options is not exceedingly high, the protocol according to the invention delivers a practical way to privately negotiate the proper conditions.
  • Patients privacy A pharmacist can test whether any conditions for a patient not to take a certain drug apply, without learning anything about the patients state.
  • the conditions in this case can be rather complex - for example, a drug may not be prescribed to patients with a weak heart, or an HIV infection and a certain allergy, or under various sets of other medications.
  • the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice.
  • the program may be in the form of source code, object code, a code intermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention.
  • the carrier be any entity or device capable of carrying the program.
  • the carrier may include a storage medium, such as a ROM, for example a CD ROM or a semiconductor ROM, or a magnetic recording medium, for example a floppy disc or hard disk.
  • the carrier may be a transmissible carrier such as an electrical or optical signal, which may be conveyed via electrical or optical cable or by radio or other means.
  • the carrier may be constituted by such cable or other device or means.
  • the carrier may be an integrated circuit in which the program is embedded, the integrated circuit being adapted for performing, or for use in the performance of, the relevant method.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer And Data Communications (AREA)
  • Communication Control (AREA)

Abstract

Procédé de passage d'accord automatique sur un ensemble d'attributs entre une pluralité de stations dans un réseau informatique. Le procédé consiste, dans chaque station, à déterminer au moins un ensemble respectif d'attributs acceptable pour la station devant passer un accord avec l'autre station. Les attributs des ensembles sont sélectionnés dans une liste prédéterminée d'attributs. Le procédé utilise un protocole de calcul multipartite pour déterminer l'ensemble agréé sur la base des ensembles acceptables déterminés respectifs sans révéler d'autres informations que la volonté d'accepter l'ensemble convenu.
PCT/IB2006/050909 2005-04-01 2006-03-24 Negociation privee Ceased WO2006103608A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP05102580.7 2005-04-01
EP05102580 2005-04-01

Publications (2)

Publication Number Publication Date
WO2006103608A2 true WO2006103608A2 (fr) 2006-10-05
WO2006103608A3 WO2006103608A3 (fr) 2007-03-15

Family

ID=37053757

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IB2006/050909 Ceased WO2006103608A2 (fr) 2005-04-01 2006-03-24 Negociation privee

Country Status (1)

Country Link
WO (1) WO2006103608A2 (fr)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8539220B2 (en) 2010-02-26 2013-09-17 Microsoft Corporation Secure computation using a server module
US9077539B2 (en) 2011-03-09 2015-07-07 Microsoft Technology Licensing, Llc Server-aided multi-party protocols
US11436671B2 (en) * 2020-06-05 2022-09-06 Capital One Services, Llc Secure multi-party computation for sensitive credit score computation
US11496309B2 (en) 2018-06-27 2022-11-08 International Business Machines Corporation Method for performing a disjunctive proof for two relations
US20240176822A1 (en) * 2022-06-13 2024-05-30 Snowflake Inc. Projection constraint policies in a database system

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6834272B1 (en) * 1999-08-10 2004-12-21 Yeda Research And Development Company Ltd. Privacy preserving negotiation and computation

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8539220B2 (en) 2010-02-26 2013-09-17 Microsoft Corporation Secure computation using a server module
US9191196B2 (en) 2010-02-26 2015-11-17 Microsoft Technology Licensing, Llc Secure computation using a server module
US9521124B2 (en) 2010-02-26 2016-12-13 Microsoft Technology Licensing, Llc Secure computation using a server module
US10033708B2 (en) 2010-02-26 2018-07-24 Microsoft Technology Licensing, Llc Secure computation using a server module
US9077539B2 (en) 2011-03-09 2015-07-07 Microsoft Technology Licensing, Llc Server-aided multi-party protocols
US11496309B2 (en) 2018-06-27 2022-11-08 International Business Machines Corporation Method for performing a disjunctive proof for two relations
US11436671B2 (en) * 2020-06-05 2022-09-06 Capital One Services, Llc Secure multi-party computation for sensitive credit score computation
US12112370B2 (en) 2020-06-05 2024-10-08 Capital One Services, Llc Secure multi-party computation for sensitive credit score computation
US20240176822A1 (en) * 2022-06-13 2024-05-30 Snowflake Inc. Projection constraint policies in a database system
US12314319B2 (en) * 2022-06-13 2025-05-27 Snowflake Inc. Projection constraint policies in a database system

Also Published As

Publication number Publication date
WO2006103608A3 (fr) 2007-03-15

Similar Documents

Publication Publication Date Title
US20190386814A1 (en) Systems and Methods for Implementing an Efficient, Scalable Homomorphic Transformation of Encrypted Data with Minimal Data Expansion and Improved Processing Efficiency
US20190036678A1 (en) Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
Liu et al. Oblivious neural network predictions via minionn transformations
JP7152909B2 (ja) データを共有する有用性の安全な２パーティ評価のためのシステム及び方法
CN112465627B (zh) 基于区块链和机器学习的金融借贷审核方法及系统
US11811934B2 (en) Distributed machine learning via secure multi-party computation and ensemble learning
WO2019094303A1 (fr) Systèmes et procédés pour mettre en œuvre une transformation homomorphique évolutive et efficace de données chiffrées avec une expansion de données minimale et une efficacité de traitement améliorée
US12155754B2 (en) Secure integer comparison using binary trees
CN114175028A (zh) 密码假名映射方法、计算机系统、计算机程序和计算机可读介质
Nakayama et al. Federated Learning with Python
Tripathi et al. A blockchain enabled reversible data hiding based on image smoothing and interpolation
Fan et al. Differential cryptanalysis of full-round ANU-II ultra-lightweight block cipher
CN114144783A (zh) 密码假名映射方法、计算机系统、计算机程序和计算机可读介质
WO2006103608A2 (fr) Negociation privee
CN116414875A (zh) 数据处理装置和数据处理方法
Rao Paras-a private nft protocol
US20220321358A1 (en) Apparatus and method for first value device verification
Kumar et al. Data confidentiality and integrity preserving outsourcing algorithm for matrix chain multiplication over malicious cloud server
Slayton Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman
US20160232553A1 (en) Apparatus and method for secure digital coupon verification
Jeno Federated Learning with Python: Design and implement a federated learning system and develop applications using existing frameworks
CN113902443A (zh) 数据处理方法、装置和服务器
Kursawe et al. Private policy negotiation
CN111339275A (zh) 答题信息的匹配方法、装置、服务器和存储介质
FR3103922A3 (fr) Stockage de tokens sécurisé

Legal Events

Date Code Title Description
NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

NENP Non-entry into the national phase

Ref country code: RU

WWW Wipo information: withdrawn in national office

Country of ref document: RU

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 06727731

Country of ref document: EP

Kind code of ref document: A2

122 Ep: pct application non-entry in european phase

Ref document number: 06727731

Country of ref document: EP

Kind code of ref document: A2

WWW Wipo information: withdrawn in national office

Ref document number: 6727731

Country of ref document: EP