Source: http://www.freepatentsonline.com/8010782.html
Timestamp: 2018-03-22 23:47:23
Document Index: 289042822

Matched Legal Cases: ['Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593', 'Application No. 09000593']

Method and system for mediated secure computation - SAP AG
United States Patent 8010782
12/016686
380/46, 380/278, 705/50, 705/80, 713/169, 713/170, 713/171, 713/189
H04L29/06; H04L9/00; H04L9/08; H04L9/32; G06F21/00; G06Q20/00
Download PDF 8010782 PDF help
7711616 Anonymous transactions between an entity and a provider 2010-05-04 Knapp 705/35
7697693 Quantum cryptography with multi-party randomness 2010-04-13 Elliott 380/278
20090187978 SECURITY AND AUTHENTICATIONS IN PEER-TO-PEER NETWORKS 2009-07-23 Upendran et al. 726/5
20090140767 Universal circuit for secure function evaluation 2009-06-04 Kolesnikov et al. 326/38
7386878 Authenticating peer-to-peer connections 2008-06-10 Fernando et al. 726/3
7346160 Randomization-based encryption apparatus and method 2008-03-18 Michaelsen 380/28
20070294432 DEVICE, METHOD AND PROGRAM FOR PROVIDING MATCHING SERVICE 2007-12-20 Takase et al.
20070245403 Systems and methods for secure transaction management and electronic rights protection 2007-10-18 Ginter et al.
7240198 Honesty preserving negotiation and computation 2007-07-03 Pinkas et al. 713/168
6957341 Method and system for secure computational outsourcing and disguise 2005-10-18 Rice et al. 713/190
20050201555 System, method and apparatus for secure computation on encrypted data 2005-09-15 Yen et al. 380/30
20030074330 Efficient electronic auction schemes with privacy protection 2003-04-17 Asokan et al.
20030046198 Anonymous recommendation technique 2003-03-06 Knapp et al. 705/35
6115471 Member-exclusive service system and method through internet 2000-09-05 Oki et al. 380/242
5799090 pad encryption method and software 1998-08-25 Angert 380/43
Satoshi Koga, et al. “Enhancing Security of Security-Mediated PKI by One-time ID”, 4th Annual PKI R&D Workshop: Multiple Paths to Trust, Apr. 19-21, 2005, NIST, Gaithersburg MD.
Dahlia Malkhi, et al., “Fairplay—A Secure Two-Party Computation System”, Usenix Security Symposium, San Diego, CA, Aug. 2004.
M. Atallah, et al. “Private Collaborative Forecasting and Benchmarking”, In Proceedings of 3rd ACM Workshop on Privacy in the Electronic Society (WPES), pp. 103-114, Washington D.C., Oct. 2004.
D. Beaver, et al., “The Round Complexity of Secure Protocols”, Proceedings of the 22nd ACM Symposium on Theory of Computing, 1990.
P. Bogetoft, et al., “A Practical Implementation of Secure Auctions Based on Multiparty Integer Computation”, Proceedings of Financial Cryptography, 2006.
C. Cachin, “Efficient Private Bidding and Auctions with an Oblivious Third Party”, Proceedings of the 6th ACM Conference on Computer and Communications Security, 1999.
G. Di Crescenzo, “Private Selective Payment Protocols”, Proceedings of Financial Cryptography, 2000.
G. Di Crescenzo, “Privacy for the Stock Market”, Proceedings of Financial Cryptography, 2001.
J. Feigenbaum, et al., “Sharing the Cost of Multicast Transmissions”, Journal of Computer and System Sciences 63 (2001), pp. 21-41.
J. Feigenbaum, et al. “Secure Computation of Surveys”, Proceedings of the EU Workshop on Secure Multiparty Protocols, 2004.
J. Feigenbaum, et al. “Distributed Algorithmic Mechanism Design: Recent Results and Future Directions”, Bulletin of the EATCS 79, 2003.
O. Goldreich, “Secure Multi-party Computation” www.wisdom.weizmann.ac.il˜oded/pp.html, 2002.
J. Halpern, et al. “Rational Secret Sharing and Multiparty Computation: Extended Abstract”, Proceedings of the 36th ACM Symposium on Theory of Computing, 2004.
M. Harkavy, et al., “Electronic Auctions with Private Bids”, Proceedings of 3rd USENIX Workshop on Electronic Commerce, 1998.
M. Hirt, et al., “Efficient Secure Multi-Party Computation” (Extended Abstract), Proceedings of Asiacrypt, 2000.
S. Izmalkov, et al., “Rational Secure Computation and Ideal Mechanism Design”, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005.
A. Juels, et al., “A two-server, sealed-bid auction protocol”, Proceedings of the 6th Conference on Financial Cryptography, 2002.
Y. Lindell, et al., “A Proof of Yao's Protocol for Secure Two-Party Computation”, Electronic Colloquium on Computational Complexity 11, 2004.
M. Naor, et al., “Privacy Preserving Auctions and Mechanism Design”, Proceedings of the 1st ACM Conference on Electronic Commerce, 1999.
S. Pohlig, et al., “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance”, IEEE Transactions on Information Theory 24, 1978.
Y. Shoham, et al., “Non-Cooperative Computation: boolean functions with correctness and exclusivity”, Theoretical Computer Science 343(1-2), 2005.
A. Yao, “Protocols for Secure Computations” Proceedings of the annual IEEE Symposium on Foundations of Computer Science 23, 1982.
Naor, M. et al., “Privacy Preserving Auctions and Mechanism Design”, Proceedings of the 1st ACM conference on Electronic commerce, Denver, Colorado, U.S., Jan. 1, 1999, pp. 129-139.
Brandt, F., “How to obtain full privacy in auctions”, International Journal of information Security, vol. 5, No. 4, Mar. 31, 2006, pp. 201-216.
Yao, A. C., “Protocols for secure computations”, Annual symposium on Foundations of Computer science, Jan. 1, 1982, pp. 160-164.
European Search Report Received for EP Patent Application No. 09000593.5-2415, mailed on Jun. 5, 2009, 5 pages.
Communication Pursuant to Rule 69 EPC for European Patent Application No. 09000593.5, mailed on Jul. 24, 2009, 2 pages.
Office Action Response for European Patent Application No. 09000593.5, filed on Jul. 27, 2009, 15 pages.
Office Action for European Patent Application No. 09000593.5, mailed on Apr. 6, 2010, 2 pages.
Office Action Response for European Patent Application No. 09000593.5, filed on Apr. 30, 2010, 14 pages.
Communication under Rule 71(3) EPC for European Patent Application No. 09000593.5, mailed on Jun. 25, 2010, 72 pages.
Notice of Decision to Grant European Patent for European Patent Application No. 09000593.5, mailed on Sep. 30, 2010, 2 pages.
Response to Communication under Rule 71(3) EPC for European Patent Application No. 09000593.5, filed on Sep. 17, 2010, 25 pages.
1. A system comprising: a mediated secure computation manager including: a unique identifier manager configured to assign a unique identifier value to each one of a plurality of nodes included in a network; a node input receiving manager configured to receive, at a server, an encrypted portion of a logical circuit and a set of keys corresponding to the node's input on respective logical wires from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server; a portion combining engine configured to combine the encrypted portions of the logical circuit received at the server; and a logical circuit execution manager configured to obtain a result based on executing the logical circuit, based on one or more operations of the portion combining engine and based on the sets of keys received from each of the nodes.
2. The system of claim 1 wherein: the unique identifier manager is further configured to assign the unique identifier value to each one of the plurality of nodes included in the network, based on counting values associated with a number of the plurality of nodes, the node input receiving manager is further configured to receive, at the server, from each one of the nodes, the encrypted portions, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the one or more representations of remaining encrypted portions encrypted based on a hash function, wherein the mediated secure computation manager further comprises: a challenge manager configured to receive, from each one of the nodes, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node; and a verification manager configured to verify the representations associated with the one or more gates based on comparing the representations of the remaining encrypted portions received from the nodes.
3. The system of claim 1, wherein the mediated secure computation manager further comprises: an execution result handler configured to send the result to each of the nodes.
4. The system of claim 1, wherein the mediated secure computation manager further comprises: a logical circuit determination manager configured to obtain the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values.
5. The system of claim 1, wherein the mediated secure computation manager further comprises: a logical circuit determination manager configured to obtain the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values associated with one or more of an auction, a fraud detection system, a game, a credit card clearing house system, or a competitive transaction system.
6. The system of claim 1, wherein the mediated secure computation manager further comprises: a logical circuit determination manager configured to obtain the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values, wherein the logical circuit includes one or more binary gates, each binary gate configured to receive binary input values.
8. A system comprising: a network node processing engine including: a node identifier manager configured to receive, at a node included in a plurality of nodes associated with a network, a unique identifier value assigned to the node by a server; a portion encryption manager configured to encrypt a portion of a logical circuit, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server; a node portion manager configured to send, to the server, the encrypted portion of the logical circuit and a set of keys corresponding to the node's input on respective logical wires; and a result receiving manager configured to receive a result from the server based on execution of the logical circuit, based on combining the encrypted portion with one or more other encrypted portions of the logical circuit received at the server from one or more other nodes of the plurality of nodes associated with the network and based on the sets of keys received from each of the nodes.
9. The system of claim 8 wherein: the node identifier manager is configured to receive, at the node included in the plurality of nodes associated with the network, the unique identifier value assigned to the node by the server, wherein the unique identifier is assigned based on counting values associated with a number of the plurality of nodes, and the node portion manager is configured to send, to the server, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the one or more representations of remaining encrypted portions encrypted based on a hash function, and the network node processing engine further includes: a node challenge manager configured to send, to the server, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node.
10. The system of claim 8 wherein the network node processing engine further includes: a node logical circuit determination manager configured to obtain the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values.
11. The system of claim 8 wherein: the node portion manager is configured to send, to the server, the encrypted portion of a logical circuit, the logical circuit including one or more gates, each gate associated with the one or more logical input wires and the one or more logical output wires, each gate represented by one or more truth tables associated with the encrypted portion of the logical circuit, wherein the logical circuit is associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server.
12. A method comprising: assigning a unique identifier value to each one of a plurality of nodes included in a network; receiving, at a server, an encrypted portion of a logical circuit and a set of keys corresponding to the node's input on respective logical wires from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server; and obtaining a result based on executing the logical circuit, based on combining the encrypted portions of the logical circuit received at the server and based on the sets of keys received from each of the nodes.
13. The method of claim 12 wherein: assigning a unique identifier value includes assigning the unique identifier value to each one of the plurality of nodes included in the network, based on counting values associated with a number of the plurality of nodes, the method further comprising receiving, from each one of the nodes, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node, and wherein receiving, at a server, an encrypted portion of a logical circuit includes receiving, at the server, from each one of the nodes, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the representations of remaining encrypted portions encrypted based on a hash function, wherein the method further includes verifying the representations associated with the one or more gates based on comparing the representations of the remaining encrypted portions received from the nodes.
14. The method of claim 12 further comprising: sending the result to each of the nodes.
15. The method of claim 12 further comprising: obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values.
16. The method of claim 12 further comprising: obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values associated with one or more of an auction, a fraud detection system, a game, a credit card clearing house system, or a competitive transaction system.
17. The method of claim 12 further comprising: obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values, wherein the logical circuit includes one or more binary gates, each binary gate configured to receive binary input values.
18. The method of claim 12 wherein: obtaining a result includes obtaining the result based on verifying a correctness of each encrypted portion of the logical circuit and executing the logical circuit, based on combining input values associated with the logical input wires associated with each one of the gates, based on truth tables associated with the encrypted portion of the logical circuit received at the server.
19. A method comprising: receiving, at a node included in a plurality of nodes associated with a network, a unique identifier value assigned to the node by a server; sending, to the server, an encrypted portion of a logical circuit and a set of keys corresponding to the node's input on respective logical wires, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server; and receiving a result from the server based on execution of the logical circuit, based on combining the encrypted portion with one or more other encrypted portions of the logical circuit received at the server from one or more other nodes included in the plurality of nodes associated with the network and based on the sets of keys received from each of the nodes.
20. The method of claim 19 wherein: receiving, at a node included in a plurality of nodes associated with a network, a unique identifier value includes receiving, at the node included in the plurality of nodes associated with the network, the unique identifier value assigned to the node by the server, wherein the unique identifier value is assigned based on counting values associated with a number of the plurality of nodes, the method further comprising sending, to the server, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node, and wherein sending, to the server, an encrypted portion of a logical circuit includes sending, to the server, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the one or more representations of remaining encrypted portions encrypted based on a hash function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server.
FIG. 1 is a block diagram of a system 100 for mediated secure computation. In the example of FIG. 1, a mediated secure computation manager 102 includes various processing engines that obtain and process logical circuits and inputs from a plurality of nodes such as network nodes 104a, 104b. According to an example embodiment, the mediated secure computation manager 102 may include a server 106 for receiving inputs from the plurality of nodes, and may process the inputs based on a logical circuit 108, to provide a result 110 that has been requested by the network nodes 104a, 104b. For example, the server 106 may include a service provider, and the network nodes 104a, 104b may include clients of the service provider, who may communicate with the server 106 via a network such as the Internet. Although not explicitly shown in FIG. 1, there may be a large number of such nodes, for example, communicating with the server 106 via a network such as a local area network (LAN) or a wide area network such as the Internet.
The mediated secure computation manager 102 may include a unique identifier manager 112 configured to assign a unique identifier value 114a, 114b to each one of a plurality of nodes included in a network. For example, if there are n network nodes included in the network, the unique identifier manager 112 may assign the integers 1, 2, 3, . . . , n uniquely to each of the network nodes. For example, each of the network nodes may be informed of its unique identifier value 114a, 114b, and may not be informed of other network nodes' unique identifier values; however, each network node may be informed of the total number of network nodes included in the network, or the total number of network nodes that may be included in a computation of a logical circuit such as the logical circuit 108. According to an example embodiment, the server 106 may not collude with any one or more of the nodes, such as network nodes 104a, 104b.
According to an example embodiment, the unique identifier manager 112 may be configured to assign a unique identifier value 114a, 114b to each one of the plurality of nodes included in the network, based on counting values associated with a number of the plurality of nodes. For example, the unique identifier manager 112 may assign the unique identifier value 114a of 1 to the network node 104a, and the unique identifier value 114b of 2 to the network node 104b. For example, if there are n nodes included in the network, then the unique identifier manager 112 may assign a unique identifier value 114a, 114b, . . . of 1, 2, . . . , n individually to each of the n nodes.
For example, the node input receiving manager 116 may receive an encrypted portion 118a of the logical circuit 108 from the network node 104a, and may receive encrypted portion 118b of the logical circuit 108 from the network node 104b. For example, the node input receiving manager 116 may receive an encrypted portion of the logical circuit 108 from the each one of n network nodes included in the network. All of the network nodes may agree on a value of the random number value 120, and the random number value 120 may be unknown at the server 106 (e.g., may be kept as a secret from the server 106), as discussed further below.
According to an example embodiment, the node input receiving manager 116 may be configured to receive, at the server 106, from each one of the nodes, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit 108, and one or more representations of remaining encrypted portions 122a, 122b of the logical circuit 108, the one or more representations of remaining encrypted portions encrypted based on a hash function. For example, at each one of the nodes included in the network, the hash function may be applied to encrypt the one or more remaining portions 122a, 122b of the logical circuit 108 via hash function logic 124, wherein the one or more remaining portions 122a, 122b may include one or more portions of the logical circuit 108 other than the encrypted portion of the logical circuit 108 associated with the individual node, as discussed further below.
According to an example embodiment, the system 100 may include the node 104a that may include a network node processing engine 138 that may be in communication with the server 106. For example, the connection may be via a local area network (LAN) or a wide area network (WAN) such as the Internet. Although not explicitly shown in FIG. 1, the network node 104b may also include a network node processing engine 138 that may include components similar to those discussed herein with regard to the network node 104a. Similarly, the system 100 may include a large number of network nodes configured similarly to the network node 104a discussed herein.
According to an example embodiment, the network node processing engine 138 may include a node portion manager 144 configured to send, to the server 106, the encrypted portion 118a, 118b of the logical circuit 108. For example, a node portion manager 144 included in the node 104a may send the encrypted portion 118a to the server 106, and a node portion manager 144 (not shown in FIG. 1) included in the node 104b may send the encrypted portion 118b to the server 106.
FIG. 2 is a flowchart illustrating an example operation of the system of FIG. 1. At 202, a unique identifier value may be assigned to each one of a plurality of nodes included in a network. For example, the unique identifier value 114a, 114b may be assigned to the network nodes 104a, 104b by the unique identifier manager 112, as discussed previously.
FIG. 3 is a flowchart illustrating an example operation of the system of FIG. 1. For example, FIG. 3 may illustrate operation of the network node 104a or 104b. At 302, a unique identifier value assigned to a node by a server may be received at the node included in a plurality of nodes associated with a network. For example, the node identifier manager 140 may receive the unique identifier value 114a assigned to the node 104a by the server 106.
According to an example embodiment, a protocol for generating an encrypted version of a desired logical circuit may include generating component gates associated with the logical circuit, and encrypting portions of the gates as discussed below. For example, a binary circuit C may include gates G={g1, . . . , gα} and wires W={w1, . . . ,wβ}. For example, logical input wires associated with the gates may be denoted as I={i1, . . . ,iγ} ⊂ W and logical output wires may be denoted as O={o1, . . . ,oδ} ⊂ W. For example, if the gates are binary gates (i.e., the gates have inputs that may only have one of two possible values) having two inputs, then the two input wires of each binary gate gi may be denoted as ini1 and ini2 and an output wire may be denoted as outi.
According to an example embodiment, for each wire wi a random bit rwi may be selected, as well as two random keys kwi,0 and kwi,1, such that the last bit of a binary representation of kwi,0 has a value of 0 and the last bit of a binary representation of kwi,1 has a value of 1. According to an example embodiment, each gate gi may be represented as a truth table. For example, opi,a,b may denote a result of the gate gi's operation on example inputs a and b, as shown in the encrypted truth table of FIG. 4, which depicts example encrypted results of an based on an example gate gi. One skilled in the art of data processing may appreciate that there may exist many representations of the gates other than truth tables, any of which may be utilized without departing from the spirit of the techniques discussed herein.
According to an example embodiment, the collaborative coin-flipping protocol may include selecting random numbers for garbling or encrypting the circuit for use in the collaborative computation. For example, as discussed with regard to FIG. 1, the portion encryption manager 142, included in a network node, may encrypt a portion of the logical circuit 108, wherein the encrypted portion 118a, 118b may be encrypted based on a random number value 120 that is common to the plurality of nodes and unknown at the server 106. For example, the node portion manager 144 may send, to the server 106, the encrypted portion 118a, 118b, based on one or more representations associated with one or more gates included in the logical circuit 108, and one or more representations of remaining encrypted portions 122a, 122b of the logical circuit 108, the one or more representations of remaining encrypted portions 122a, 122b encrypted based on a hash function.
r=⊕i=1n xi.
r1er2e=(r1r2)e
cj′=∏i=1j-1⁢ci⁢∏i=j+1n⁢ci⁢⁢mod⁢⁢p
r=(ci′)d⁢xi∏j=1i-1⁢PRNGj⁡(s)⁢∏j=i+1n⁢PRNGj⁡(s)⁢⁢mod⁢⁢p=∏j=1n⁢xj⁢⁢mod⁢⁢p
Gi={gα⁡(i-1)n+1,K,gα⁢⁢in}
denote client Ci's fraction, or portion, of the logical circuit C, and xi,j denotes the bit of Ci's input on wire j(j ∈ Ii ⊂ I), then each client Ci may send Gi, H(G\ Gi) and kj,rj⊕xi,j for j ∈ Ii ⊂ I to the server S (e.g., similarly as shown in the example truth table representing an example gate gi of FIG. 4).
O⁡(αn)
t<n2
σ′i:Ui({right arrow over (σ)}−i, σi)≧Ui({right arrow over (σ)}−i,σ′i).
S1. uS(r)>uS(r′) if Σi=1n compute(r)^inf o(r)>Σi=1n compute(r′)^inf o(r′)
S2. uS(r)<uS(r′) if Σi=1n compute(r)^inf o(r)>Σi=1n compute(r′)^inf o(r′)
1. Client Ci may submit commit(kj,xi,j⊕rj), and commit(rj) for each j ∈ Ii ⊂ I of its input wires Ii.
2. The server S may send a timestamp timestamp and signature DS(timestamp.commit(kj,xi,j⊕rj).commit(rj)) of the commitments to the client Ci. For example, in the case of auctions, the server S may also include an auction identifier and a (static) identity of the client Ci.
Upon starting the example collaborative computation protocols after the client Ci has opened the commitment to kj,xi,j⊕rj (e.g., between steps 2 and 3 shown above), the server may perform a verification of the commitment.
2a. The server may verify the commitment commit(kj,xi,j⊕rj) of each client Ci. On a false commitment, the server S may exclude the client from the computation similarly as discussed previously.
In case of a dispute, the client Ci may claim its bid to a trusted third party. The clients Ci may show the two commitments (for the client's input and for the random garble bits) commit(kj,xi,j⊕rj) and commit(rj), the timestamp timestamp and their signature by the server S (DS(timestamp.commit(kj,xi,j⊕rj). commit(rj))). This may convince the trusted third party that the commitments have been made to the server S.
1. Client Ci may send its public key ECi(·) and the token, i.e., ECA(ECi(·), ECA(Ci, timestamp, DS(Ci, timestamp))) to the CA.
2. The CA may verify the freshness and signature of the token and the identity information (e.g., a supplied e-mail address). It may then issue a certificate to the client Ci for its public key: CertCA(Ci)=(Ci, ECi(·), DCA(Ci, ECi(·))). According to an example embodiment, the CA may return the certificate CertCA(Ci), and the secret keys of the protocol ECi(s, e) to Ci.
<- Previous Patent (Method and system to...) | Next Patent (Service provider inv...) ->