JP5727353B2 - Information collection system, communication apparatus, and program - Google Patents

Description

  The present invention relates to a technique for collecting information from a plurality of communication devices.

  Grid computing, which is a mechanism for distributing and executing a single calculation process to many computers, has been put into practical use. In grid computing, the server device monitors the status of the grid, that is, each computer, appropriately divides the calculation process, requests execution of the divided calculation process to each computer, and obtains the result. Here, Non-Patent Document 1 proposes a mechanism for requesting calculation processing to an apparatus such as each computer.

  Non-Patent Documents 2 to 4 disclose Secure Multi-party Computation (SMC), which is a mechanism for performing calculation by distributing a certain process in a plurality of nodes. Here, in the SMC, each communication device that performs each calculation process needs to be able to directly communicate with each other.

Dianji Huang, et al. , “MobilCloud: Building Secure Cloud Framework for Mobile Computing and Communication,” In Proc. Of the 2010 Fifth IE International Symposium. Goldreich, O., "Foundations of Cryptography," Volume 2, Basic Applications. Cambridge University Press, 2004 Goldreich, O., et al. , “How to play any mental game,” In Proceedings of the nine-annual annual ACM symposium on Theory of computing (1987), ACM, pp. 218-229. Ben-Or, M.M. Goldwasher, S .; , And Wigderson, A .; , “Completeness theorem for non-cryptographic fault-tolerant distributed computation,” In Proceedings of the twenty-annual ACM symposium. 1-10

  Currently, a large number of people have mobile phones. For example, by using these mobile phones to answer questionnaires, a large amount of information can be quickly collected. Specifically, for example, information related to products that are of interest by age group, or information related to the number of patients by region and age group, etc., in the event of an influenza outbreak, etc. can do. In addition, since recent mobile phones are equipped with various sensors such as temperature sensors and GPS receivers, for example, use the functions of mobile phones that do not rely on questionnaires, such as the temperatures at various locations acquired by the temperature sensor. It is also possible to collect information acquired by the mobile phone.

  Here, the collector wants to collect some information (hereinafter referred to as the collector) and the one that provides the information required by the collector (hereinafter referred to as the provider) so that the collector can efficiently perform the information. Consider realizing an information collection system that can collect information. In the following description, a communication device used by a collector is called a collection device, and a communication device used by a provider is called a providing device. Note that the collector is not the information itself provided by each provider, but statistical information such as information provided by each provider such as total, average, variance, etc. Suppose you need it.

  First, in order to realize the above information collection system, a mechanism for mediating the collection device and the providing device is required. From the viewpoint of protecting personal information, it is also desirable to provide a mechanism that allows a provider to keep secret the information provided by a provider using not only other providers but also the collector. In other words, for example, if you want to examine the age distribution of whether or not the collector has had a disease, the collector can obtain the total number of people who have had the disease by age group. It is only a value, and it is desirable that even the collectors can be kept secret as to whether or not individual donors have been ill.

  The present invention provides the above mechanism, so that the information provided by each providing device is kept secret, and the collecting device can collect the statistical information, and the communication device used in the information collecting system. A program for operating a computer as the communication device is provided.

An information collection system according to the present invention includes a collection device, a plurality of providing devices each having a different identifier, and providing information requested by the collection device, and the collection device and the plurality of provision devices. A relay device that relays transmission / reception of information between the two devices, wherein the collection device communicates with each of the plurality of providing devices via the relay device. Means for generating an encryption key shared by the collection device and the plurality of providing devices, and a first function and a second function for calculating statistical information of information provided by each of the plurality of providing devices. Means for determining and notifying each providing device of the second function, and each of the plurality of providing devices can be used for restoring the provided information from the provided information. Means for generating a plurality of shared information respectively corresponding to the identifiers of the providing devices, encrypting each generated shared information to the corresponding identifier providing device with the encryption key, and transmitting the information via the relay device; Of the distributed information corresponding to the identifier assigned to the own device and the shared information corresponding to the identifier assigned to the own device received from another providing device of the plurality of providing devices. Means for obtaining an output value as an input of the function, and encrypting the output value with the encryption key to the collection device and transmitting it via the relay device, and the collection device receives from each providing device an output value to calculate the statistical information as an input of the first function, each of the plurality of providing apparatuses generates a random number, said generated random number is encrypted with the public key of the collection device Transmitted to the collection device via a relay device, the collection device decrypts the encrypted random number received from each providing device with a secret key for the public key, and obtains all of the random numbers received from each providing device. The first number is obtained by multiplication, and the remainder obtained by multiplying the predetermined number by the first number is a predetermined prime number, and is received from other than the first providing device of the plurality of providing devices. A second number is obtained by multiplying all the random numbers, and a remainder obtained by multiplying the predetermined number by the second number is obtained from the first providing apparatus and the encryption key. In order to share, it transmits to said 1st provision apparatus via the said relay apparatus, It is characterized by the above-mentioned.

The communication device according to the present invention is a communication device of an information collection system including a plurality of communication devices each assigned an identifier, and communicates with the collection device of the information collection system via a relay device, whereby the collection device And means for generating an encryption key shared by the plurality of communication devices, means for acquiring information, and restoration of the acquired information from the acquired information, each corresponding to an identifier of the plurality of communication devices Means for generating a plurality of shared information to be generated, encrypting each generated shared information to a communication device having a corresponding identifier with the encryption key, and transmitting the same via the relay device, and the own device of the generated shared information The distributed information corresponding to the identifier assigned to the communication device and the distributed information corresponding to the identifier assigned to the own device received from another communication device are notified from the collection device. Obtains the output value as an input, and means for transmitting the output value to the collection device via the relay device encrypted with the encryption key comprises a means for generating the encryption key, generates a random number Then, the generated random number is encrypted with the public key of the collection device, transmitted to the collection device via the relay device, and the encryption key is based on the value received from the collection device by the relay device and the generated random number The value received by the relay device from the collection device is multiplied by all the random numbers received by the collection device from communication devices different from the communication device of the plurality of communication devices. The number of 1 is obtained, and the remainder is obtained by multiplying the predetermined number by the first number by a predetermined prime number .

  An information collecting system that can obtain statistical information of information provided by each provider without knowing the contents of the information provided by each provider from an unspecified provider becomes possible.

The system block diagram in one Embodiment. The block diagram of the provision apparatus in one Embodiment. The figure which shows the preservation | save state of the shared information in one Embodiment. The figure which shows the information which the collection apparatus in one Embodiment collects.

  FIG. 1 is a schematic configuration diagram of a system in the present embodiment. In FIG. 1, the collection device 3 is a communication device used by an information collector, and the providing device 1 is a communication device used by an information provider. The server device 2 is a device for connecting the collection device 3 and the providing device 1. The collection device 3 and the providing device 1 are each a personal computer, a mobile phone, or the like, for example. In the figure, only three providing devices are shown, but this is an example, and any number of providing devices 1 can be used. Furthermore, although the collection device 3 and the providing device 1 are displayed as different devices, these may be devices having the same function. That is, the collection device 3 can also operate as the providing device 1 that provides information requested by other collectors, and the providing device 1 operates as the collection device 3 that requests information from other providers. Can do.

  The collection device 3, the server device 2, and the provision device 1 can be connected to the network 4, the collection device 3 can communicate with the server device 2, and each provision device 1 can communicate with the server device 2. In the present embodiment, in order to keep each other's identity secret, transmission / reception of information between the collection device 3 and the providing device 1 and between each providing device 1 is always performed via the server device 2. That is, the server device 2 functions as a relay device for transmitting and receiving information between the collection device 3 and two of the providing devices 1.

  The server device 2 mediates the collector and the provider, and information on the collector and the provider, and the collection device 3 and the provider 1 used by the collector and the provider is stored in the database of the server device 2 in advance. It is registered in. Specifically, for example, the server device 2 is a collector of the provider's age, sex, attributes (fixed terminal or portable terminal) and functions (sensor type, etc.) of the communication device possessed by the provider. Holds arbitrary information used as a criterion for selecting a provider when requesting provision of information. Such information can include, for example, the provider's residential area, the current position of the providing device 1 that the providing device 1 periodically notifies the server device 2, and the like. Furthermore, information such as the provider's occupation and hobbies can be included.

  When it is desired to collect some information, the collection device 3 transmits to the server device 2 a request message indicating the contents of the information to be collected and the conditions of the provider, and the server device 2 provides the information. The provider who requests information provision is selected from the providers registered in the database based on the conditions of the provider. And the server apparatus 2 transmits the request message which shows the information which the collection apparatus 3 wants to collect to the provision apparatus 1 of the selected provider. If the information to be collected is an answer to a certain questionnaire, the request message includes information indicating the question items and options. Further, when it is desired to collect information measured by a sensor or the like provided in the providing apparatus 1, a program for measuring necessary information by the sensor or the like can be included in the request message.

  When receiving the request message, the providing device 1 displays a screen that allows the provider to select whether or not to cooperate with information provision. When the provider responds to the information provision, the providing device 1 transmits an acceptance message to the server device 2, and the server device 2 transmits the total number of accepted providers to the collection device 3.

Collecting apparatus 3 number of provider is determined, the collecting device 3, to start the process of sharing the encryption key K _c to be used between the providing apparatus 1 Accepted provider. In the following description, the providing device 1 of the accepted provider is simply referred to as the providing device 1. That is, for example, “all the providing devices 1” means “all the providing devices 1 of the accepted providers”. In the following, it is assumed that the number of accepted providers is N. In this case, the collection device 3 assigns 1 to N different numbers k to each providing device 1.

First, the collection device 3 transmits the public key K _p in a public key cryptosystem, and prime p, the primitive element g, the providing apparatus 1 via the server apparatus 2. At this time, the collection device 3 also notifies the number assigned to each providing device 1. Incidentally, the public key K _p, and prime p, for primitive element g, and form collecting device 3 is what was published to any device on the network 4, it obtains the providing apparatus 1 accesses to the device You can also

Subsequently, the providing device 1 to which the number k is assigned generates a random number X _k in the range of 0 to (p−1), and encrypts the generated random number X _k with the public key K _p of the collection device 3. And transmitted to the collection device 3 via the server device 2. The collection device 3 decrypts the encrypted random number X _k received from each providing device 1 with the secret key K _s for the public key K _p . After that, the collection device 3, the encryption key _{K c,}
K _c = g ^X mod p
Ask for. X is a number obtained by multiplying the random numbers X ₁ to X _N of all the providing devices 1.

Further, the collection device 3 transmits the following value Z _i via the server device 2 to the providing device 1 with the number i (i is a natural number from 1 to N).
Z _i = g ^Yi mod p
Here, Yi is a number _obtained by multiplying the random numbers Xk received from the providing devices 1 other than the providing device 1 with the number i.

The providing device 1 with the number _i generates the encryption key K _c from the received Z _i and the random number X _i generated by itself. With the above configuration, the server apparatus 2 which relays information can be shared between the cipher key K _c of a secret, and the collection device 3 and each providing apparatus 1. The above processing is executed by the encryption key sharing unit 14 of the collection device 3 shown in FIG.

  In addition to the encryption key sharing process, the collection device 3 determines a function F1 and a function F2 for calculation processing, stores the function F1, and transmits the function F2 to each providing device 1. The functions F1 and F2 are determined in accordance with statistical information desired to be collected by the collection apparatus 3, that is, for example, according to a known SMC according to the total, variance, and the like. Note that the functions F1 and F2 do not need to be kept secret from the server apparatus 2, and may be notified to the providing apparatus 1 before the function calculation process in the providing apparatus 1 described later.

After sharing the encryption key K _c, information acquisition unit 11 of the providing apparatus 1 number k (k is a natural number of from 1 N) obtains information along with a request collectors. For example, if the information to be collected is a response to a questionnaire, the information acquisition unit 11 displays the questionnaire on the screen of the providing device 1 to prompt the provider to input information and acquires information. Also, for example, when the information to be collected is information that the providing device 1 has and a program for obtaining the information is provided from the collecting device 3 together with the request message, the information acquisition unit 11 executes the program. To get information. When the information acquisition unit 11 acquires information, the distributed execution unit 12 generates N pieces of information I _{k1 to} I _kN (hereinafter, generated by the threshold secret sharing method) from the acquired information I _k by a known threshold secret sharing method. Information is called distributed information). For example, the providing device 1 with the number k uses the Shamir secret sharing method to obtain a (t−1) -order polynomial with respect to the threshold t.
A (x) = a _t−1 x ^t−1 +... A ₁ x + a
First ask for. Here, the coefficients a _{t−1 to} a ₁ are values individually designated by the collection device 3 for each providing device together with the threshold value t, and the constant term a is determined by the information acquisition unit 11 of the providing device 1. It is the acquired information. In this case, the providing device 1 with the number k substitutes each distribution information by substituting the number of the providing device 1 into the obtained polynomial as I _k1 = A (1),..., I _kN = A (N). Ask. In addition, regarding the values of the coefficients other than the constant term, the collection device 3 designates the coefficient in each providing device 1 so that at least each providing device 1 cannot recognize the coefficient used in the other providing device 1. In other words, the collection device 3 individually designates a coefficient for each providing device 1. At this time, for example, the collection device 3 can set different sets of coefficients for each providing device, or can specify the same set of coefficients for a part or all of the providing device 1.

After that, the providing device 1 with the number k stores I _kk out of the N pieces of shared information in its own _shared information storage unit 13, and the other _shared information I _ki (k ≠ i) is numbered via the server device 2. to the i providing device 1. At this time, the distributed information I _ki is encrypted with the previously shared encryption key K _c . Similarly, the providing device 1 with the number k acquires the _shared information I _ik (k ≠ i) from all the other providing devices 1 via the server device 2 and stores the acquired shared information in the shared information storage unit 13. To do. In the present embodiment, the number of each providing device 1 is also notified to the server device 2, and each providing device 1 notifies the server device 2 of the destination of the encrypted distributed information with the number of the providing device. To do. FIG. 3 is a diagram illustrating a relationship between information acquired by each providing device 1, N pieces of shared information generated from the acquired information, and the providing device 1 in which the shared information is stored. In FIG. 3, each row indicates shared information generated from the acquired information, and each column indicates shared information stored in each providing device 1. For example, providing device 1 of the numbers # 1 obtains the information _{I 1,} the threshold secret sharing scheme _to generate N dispersed information I 11 _{~I 1N.} On the other hand, the providing apparatus 1 with the number # 1 stores the shared information I _{21 to} I _N1 received from the other providing apparatus 1 in the shared information storage unit 13 in addition to the shared information I ₁₁ generated by itself. .

When the function processing execution unit 15 of the providing device 1 with the number k acquires all of the _shared information I _1k , I _2k ,..., I _Nk , the value R _k = F 2 ( I _1k , I _2k ,..., I _Nk ), and the calculated value R _k is encrypted with the encryption key K _c and transmitted to the collection device 3 via the server device 2. The collection device 3 calculates F1 (R ₁ ,..., R _N ) from the values R _{1 to} R _N acquired from each providing device 1 and the function F1, thereby obtaining information acquired by each providing device 1. Statistical information such as a total value of I _k and a variance value can be calculated. Since the information is distributed by the threshold secret sharing method, if the threshold is t, the collection device 3 can obtain each value from the _N values R _{1 to} R _N by providing each providing device. 1 is the total value and the information I _k obtained, it is possible to calculate information such as variance.

  For example, it is assumed that there are five providers, the information provided by the provider is Yes or No, and the collector wants to know the number of people who answered Yes. Note that Yes is a value “1”, and No is a value “0”. Further, the threshold value in each providing device 1 is set to 2, and the coefficient of the distribution information generation polynomial A (x) is set to 1 in each providing device for the sake of simplicity. That is, the generator polynomial is A (x) = x + a. Note that a is a value corresponding to the information acquired by the information acquisition unit 11 and is 1 or 0 in this example. In this case, in the case of No, each providing device 1 assigns the value “1” to the providing device of number # 1, the value “2” to the providing device of number # 2, and the value “2” to the providing device of number # 3. 3 ”, the value“ 4 ”is stored in the providing apparatus of number # 4, and the value“ 5 ”is stored in the providing apparatus of number # 5. In the case of Yes, the value “2” is assigned to the providing device of number # 1, the value “3” is assigned to the providing device of number # 2, the value “4” is assigned to the providing device of number # 3, and the number # 4. The value “5” is stored in the providing device and the value “6” is stored in the providing device of number # 5.

  In this case, each providing device 1 is notified from the collection device 3 of a function for obtaining the total value of the shared information as the function F2. Therefore, the relationship between the number of people of Yes and the value output by each providing device 1 is as shown in FIG. The collecting device 3 can obtain the number of people who answered Yes by obtaining B (y) as a first-order polynomial according to the value received from each providing device 1 and obtaining the value of B (0). In other words, for example, when the number of Yes in FIG. 4 is two, the first-order polynomial B (y) = 5y + 2 is obtained from the received value, and the number of Yes is known from B (0) = 2. In the above example, since each providing device 1 obtains the dispersion information using the same polynomial, if each providing device 1 recognizes that each providing device 1 uses the same coefficient, each providing device 1 receives from another providing device. By acquiring the distributed information, it is possible to know the information content acquired by the other providing device. That is, when the providing device 1 with the number 1 receives the value 2 from the providing device 1 with the number 3, it can be seen that the information in the providing device 1 with the number 3 is Yes. However, in a situation where the providing device 1 has no knowledge of the generating polynomials of the other providing devices 1 due to the collection device 3 specifying the distributed information generating polynomial, etc., each providing device 1 has another providing device 1. I can't know the information. However, for example, when the collection device 3 specifies a set of coefficients of at least two types of generator polynomials to the providing device 1, each providing device 1 knows the contents of the information acquired by the other providing devices. Can be prevented.

  As described above, by using the server device 2, the collection device and the providing device can be linked. In addition, by sending and receiving information between the collection device and the providing device via the server device 2, the identity of the provider can be concealed from the collector. Furthermore, the information acquired by each providing device is converted into a plurality of pieces of shared information for restoring the acquired information by a threshold secret sharing method, and each shared information is distributed to each providing device. Here, in the threshold secret sharing method, the original information can be restored when the shared information equal to or higher than the threshold is acquired. In the present embodiment, shared information is transmitted and received between providing devices via the server device 2, thereby preventing collusion between the providing devices and restoring information of other providing devices.

  For the above reasons, all information is sent and received via the server device 2. When the server device 2 acquires information from each providing device, the server device 2 uses the information obtained by each providing device. It can be restored. For this reason, each distributed information is concealed with respect to the server apparatus 2 by performing the encryption communication by the encryption key shared previously.

  With the above configuration, the information provider can collect necessary information while concealing the content of the information provided to others. In the above embodiment, the collection device 3 assigns a number to the providing device 1. However, the number may be an arbitrary character string or the like as long as it can be finally converted into a number. For example, a value that does not overlap with each providing device, such as an identifier assigned to the providing device 1, can be used as the number of the providing device 1.

  The collection device 3, the server device 2, and the providing device 1 can be realized by a program that causes a computer to operate as the server device described above. These computer programs can be stored in a computer-readable storage medium or distributed via a network.

Claims (7)

A collecting device;
A plurality of providing devices each provided with a different identifier and providing information requested from the collection device;
A relay device that relays transmission / reception of information between two of the collection device and the plurality of providing devices;
An information collection system comprising:
The collection device communicates with each of the plurality of providing devices via the relay device to generate an encryption key shared by the collection device and the plurality of providing devices, and each of the plurality of providing devices Means for determining a first function and a second function for calculating statistical information of information provided by the device, and notifying each providing device of the second function,
Each of the plurality of providing devices can be used for restoring the provided information from the information to be provided, and generates a plurality of pieces of shared information corresponding to the identifiers of the plurality of providing devices, Means for encrypting with the encryption key to the corresponding identifier providing device and transmitting via the relay device, shared information corresponding to the identifier assigned to the own device among the generated shared information, and the plurality of provisions An output value is obtained by using, as an input to the second function, shared information corresponding to an identifier assigned to the device received from another providing device of the device, and the output value is encrypted in the collection device with the encryption key Means for transmitting via the relay device,
The collection device calculates the statistical information using an output value received from each providing device as an input of the first function ,
Each of the plurality of providing devices generates a random number, encrypts the generated random number with the public key of the collection device, and transmits the random number to the collection device via the relay device,
The collection device decrypts an encrypted random number received from each providing device with a secret key corresponding to the public key, obtains a first number by multiplying all the random numbers received from each providing device, and The remainder obtained by multiplying the first number by the predetermined prime number is used as the encryption key, and all the random numbers received from the plurality of providing devices other than the first providing device are multiplied by the second number. In order to share the encryption key with the first providing device, the first providing device shares the remainder of the predetermined prime number obtained by multiplying the predetermined number by the second number. To send via the relay device,
An information collection system characterized by that. Each of the plurality of providing devices generates shared information by a threshold secret sharing method.
The system according to claim 1. Each of the plurality of providing devices corresponds to a value obtained by substituting the identifier of the providing device for a polynomial of a predetermined order whose constant term is a value corresponding to the information to be provided. Distributed information
The part other than the constant term of the polynomial is designated by the collection device.
The system according to claim 1 or 2, characterized by the above. A communication device of an information collection system including a plurality of communication devices each assigned an identifier,
Means for generating an encryption key shared by the collection device and the plurality of communication devices by communicating with the collection device of the information collection system via a relay device;
Means for obtaining information;
From the acquired information, it can be used to restore the acquired information, generate a plurality of shared information respectively corresponding to the identifiers of the plurality of communication devices, and generate each of the generated distributed information to the communication device with the corresponding identifier. Means for encrypting with an encryption key and transmitting via the relay device;
Among the generated shared information, the collection device is notified of the shared information corresponding to the identifier assigned to the own device, and the shared information corresponding to the identifier assigned to the own device received from another communication device. Means for obtaining an output value as an input of a function, encrypting the output value with the encryption key, and transmitting to the collection device via the relay device;
Equipped with a,
The means for generating the encryption key generates a random number, encrypts the generated random number with the public key of the collection device, transmits the random number to the collection device via the relay device, and receives from the collection device by the relay device And generating the encryption key based on the value to be generated and the generated random number,
The value received by the relay device from the collection device is multiplied by all the random numbers received by the collection device from communication devices different from the communication device among the plurality of communication devices, and is multiplied by the first number. A communication apparatus characterized by being a remainder of a predetermined prime number obtained by multiplying the predetermined number by the first number . A communication device that communicates with a plurality of providing devices each assigned an identifier via a relay device,
Means for generating an encryption key shared by the communication device and the plurality of providing devices by communicating with the plurality of providing devices via the relay device;
Means for determining a first function and a second function for calculating statistical information of information provided by each of the plurality of providing devices, and notifying each providing device of the second function;
Means for calculating the statistical information using output values received from the plurality of providing devices as inputs of the first function, wherein the providing device corresponds to an identifier of each of the plurality of providing devices; Generating a plurality of pieces of shared information that can be used to restore the provided information from the information provided by the providing device, encrypting each generated shared information with a corresponding identifier providing device with the encryption key, and via the relay device Of the shared information generated by the providing device and the shared information corresponding to the identifier assigned to the providing device and the shared information received by the providing measure from the other providing device. The means that was sought as input,
With
The means for generating the encryption key includes:
Means for receiving a random number encrypted with the public key of the communication device from each of the plurality of providing devices;
The encrypted random number received from each of the plurality of providing devices is decrypted with a secret key corresponding to the public key, and the first number is obtained by multiplying all the random numbers received from the plurality of providing devices, and a predetermined number Means for multiplying the first prime number by a predetermined prime number remainder as the encryption key;
The predetermined prime number is a number obtained by multiplying all the random numbers received from the plurality of providing apparatuses other than the first providing apparatus to obtain a second number and multiplying the predetermined number by the second number. Means for transmitting the remainder from the first providing device via the relay device in order to share the encryption key with the first providing device;
A communication apparatus comprising: A program causing a computer to function as the communication device according to claim 4 . A program that causes a computer to function as the communication device according to claim 5.

Images