Network system, server and information terminal for list matching
AssigneeInternational Business Machines Corporation
InventorsMasayuki Numao, Yuji Watanabe
Life of this patent
Estimating the term…
Abstract
A method, apparatus and system to ensure the security in the information exchange and to provide list matching with higher efficiency and practicality. In a particular embodiment, each of lists to be subject to list matching is represented as a polynomial having roots equivalent to the items of the list. Then, polynomials generated for the lists to be subject to list matching are added according to a distributed secret computation. A list containing an item equivalent to a root of a polynomial resulting from the addition is created and output as the list of a common item.
Claims25
A list matching method for extracting a common item among a plurality of lists using a computer, the method comprising:
- reading from memory the lists to be processed;
- generating for each list read a list polynomial having roots equivalent to items of the list;
- generating an addition polynomial by adding the list polynomials;
- and
- generating an addition result containing an addition item constituted by a root of the addition polynomial.
A list matching method for extracting a common item among a plurality of lists held by a plurality of information terminals within a network, the method comprising:
- generating a terminal polynomial for each of the information terminals holding a terminal list, the terminal polynomial having roots equivalent to items of the terminal list;
- for each terminal, generating a resulting polynomial by adding the information terminal's respective terminal polynomial to a preceding polynomial, the preceding polynomial being received from a preceding information terminal specified in a set order, the resulting polynomial being passed to a subsequent information terminal specified in the set order;
- and
- generating a final list containing an item equivalent to a root of a final polynomial, the final polynomial being generated by a last information terminal specified in the set order.
A list matching method for extracting a common item among a plurality of lists held by a plurality of information terminals within a network, the method comprising:
- generating a terminal polynomial for each of the information terminals holding a terminal list, the terminal polynomial having roots equivalent to items of the terminal list;
- adding the terminal polynomials through a distributed secret computation involving a plurality of servers in the network, the servers being arranged to be commonly used by the information terminals;
- and
- restoring by the information terminals a restored polynomial resulting from the addition of the terminal polynomials;
- and
- generating a result list containing an item equivalent to a root of the restored polynomial.
A list matching method for extracting a common item among a plurality of lists held by a plurality of information terminals interconnected via network, the method comprising:
- generating a bivariate polynomial for each of the information terminals holding a terminal list, the bivariate polynomial based on a first polynomial having roots equivalent to items of the terminal list and a second polynomial with an order corresponding to a predetermined number of servers on the network;
- distributing the bivariate polynomial to the servers according to the second polynomial;
- adding the bivariate polynomials distributed to the servers into a resulting polynomial;
- sending the resulting polynomial to the information terminals;
- generating a restored polynomial from the resulting polynomial, the restored polynomial describing the lists held by the information terminals;
- and
- generating a final list containing an item equivalent to a root of the restored polynomial.
A list matching method for extracting a common item among a plurality of lists held by a plurality of information terminals within a network, the method comprising:
- obtaining, by a predetermined information terminal, open information generated based on a polynomial having roots equivalent to the items of a first list held by another terminal;
- verifying, by the predetermined information terminal, the open information obtained from the another terminal;
- and
- determining, by the predetermined information terminal, a common item among the first list and a second list held by the information terminal, wherein the common item is based on the open information of the another terminal having the verified open information and a polynomial having roots equivalent to items of the second list.
A network system comprising a server and a plurality of client terminals interconnected via a network, the system comprising:
- a first client terminal configured to add a first polynomial to a second polynomial and to generate a resulting polynomial, the first polynomial describing a list to be matched, the second polynomial received from a second terminal via the network, the first client terminal further configured to transmit the resulting polynomial to a third client terminal;
- and
- a server configured to receive a total polynomial resulting from the addition of all the polynomials generated from the plurality of client terminals, the server configured to generate a list containing an item equivalent to a root of the total polynomial.
A network system comprising a plurality of information terminals and a plurality of interconnected via a network, the system comprising:
- a server configured to perform a distributed secret computation on data transmitted from the information terminals and to send back the computation result to the information terminals;
- and
- an information terminal configured to transmit a polynomial describing a list to be matched to the servers in a distributive manner, receive the computation result from the server, restore a polynomial resulting from an addition of polynomials generated by the plurality of information terminals based on the computation result, and generate a list containing an item equivalent to a root of the restored polynomial.
A network system comprising a plurality of information terminals that exchange information via a network, the system comprising:
- a first information terminal configured to generate a polynomial having a root equivalent to an item of a list held by the terminal itself, generates and opens first information based on the polynomial and generates second information based on the polynomial;
- and
- a second information terminal that obtains and verifies said first information of said first information terminal, and if the verification is passed, obtains said second information from the first information terminal, and based on the first and second information and said polynomial generated from a list held by the terminal itself, determines a common item among the list used to generate the open information and the list held by the terminal itself.
A server for extracting a common item among a plurality of lists held by a plurality of information terminals interconnected via a network, the server comprising:
- a communication unit for obtaining from the information terminals via the network a resulting polynomial from an addition of a plurality of polynomials describing the lists held by the plurality of information terminals;
- and
- a processing unit for generating a list containing an item equivalent to a root of the resulting polynomial.
A first information terminal connected to a second information terminal via a network, the first information terminal comprising:
- a communication unit for exchanging data with the second information terminal via the network;
- a storage unit for storing a predetermined list;
- a processing unit for generating a polynomial having roots equivalent to items of the predetermined list and for processing the polynomial;
- and
- an output unit for outputting information on a resulting list containing an item equivalent to a root of a resulting polynomial from an addition of a plurality of polynomials.
A first information terminal connected to a second information terminal via a network, the first information comprising:
- a storage unit for storing a predetermined list;
- a processing unit for generating a bivariate polynomial based on a first polynomial having roots equivalent to items of the predetermined list and a second polynomial having an order corresponding to a number of predetermined servers on the network;
- a communication unit for transmitting the bivariate polynomial to the predetermined servers based on the second polynomial in a distribution manner, and for receiving an addition result of the distributed polynomials from the servers;
- and
- an output unit for outputting information on a list containing an item equivalent to a root of a polynomial restored from the addition result received via the communication unit.
An information terminal connected to a network, the information terminal comprising:
- a storage section for storing a predetermined list;
- a verification section for obtaining open information based on a terminal list held by another terminal via the network, and for verifying the open information;
- and
- a matching result output section for, based on the open information having passed the verification by the verification section and a polynomial having roots equivalent to the items of the predetermined list, determining a common item among the terminal list and the predetermined list.
A computer program product embodied in a tangible media comprising:
- computer readable program codes coupled to the tangible media, the computer readable program codes configured to cause the program to:
- input a predetermined list from a memory and generate a bivariate polynomial based on a first polynomial describing the predetermined list and a second polynomial having an order corresponding to a number of predetermined servers;
- transmit the bivariate polynomial to the predetermined servers via a network interface in a distribution manner based on the second polynomial;
- and
- restore a resulting polynomial from a distribution secret computation result received from the servers and generate a resulting list containing an item equivalent to a root of the resulting polynomial.
A computer program embodied in a tangible media for controlling a computer connected to a network, the computer program comprising:
- a communication unit for obtaining open information based on a list held by an information terminal via the network;
- a verification unit for verifying the open information obtained via the communication unit;
- and
- a matching result output unit for, based on the open information having passed the verification by the verification unit and a polynomial having roots equivalent to the items of the list stored in a predetermined storage device, determining a common item among a list used to generate the open information and the list stored in the storage device.
A computer program product embodied in a tangible media comprising:
- computer readable program codes coupled to the tangible media, the computer readable program codes configured to cause the program to:
- input a predetermined list from a memory and generate a bivariate polynomial based on a fist polynomial describing the list and a second polynomial having an order corresponding to a number of predetermined servers;
- transmit the bivariate polynomial to the predetermined servers via a network interface in a distribution manner based on the second polynomial;
- and
- restore a resulting polynomial from a distribution secret computation result received from the servers via the network interface and generate a list containing an item equivalent to a root of the resulting polynomial.
A computer program embodied in a tangible media for controlling a computer connected to a network, the computer program comprising:
- a communication unit for obtaining open information based on a list held by another information terminal via the network;
- a verification unit for verifying the open information obtained via the communication unit;
- and
- a matching result output unit for, based on the open information having passed the verification by the verification unit and a polynomial having roots equivalent to the items of the list stored in a predetermined storage device, determining a common item among a list used to generate the open information and the list stored in the storage device.
Dependencies are inferred from the claim text.