US 2009/0276325 A1 · SYSTEM AND METHOD FOR QUANTITATIVE COMPETITION AND RECORDING MEDIUM HAVING RECORDED THEREON PROGRAM FOR IMPLEMENTING THE METHOD

A quantitative competition method for a system in which a plurality of participant devices send their secret aimed values to a server device and said server device determines which of said plurality of participant devices has offered the maximum or minimum one of said aimed values received, and in which there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, and m=1, 2, . . . , M, M being an integer equal to or greater than 2;

said method comprising the steps wherein:
(a) each of said participant devices processes, with a predetermined one-way function h and through the use of said conversion table, information k(+)bm(k)(+)Rm(k), which contains each index k equal to or larger than an index km corresponding to said aimed value, select information bm(k) indicating whether said index k corresponds to said aimed value, and a random number Rm(k), to generate at least K−km+1 pieces of aimed value information h(k(+)bm(k)(+)Rm(k)), and sends these pieces of aimed value information to said server device, A(+)B representing a predetermined arbitrary operation;
(b) said server device publishes its received aimed value information on a bulletin board accessible from all of said participant devices;
(c) said server device obtains said random number Rm corresponding to each of said sequence of indexes k;
(d) letting a be a predetermined value with which said select information bm(k) indicates said aimed value, said server device calculates h(k(+)a(+)Rm(k));
(e) said server device checks said aimed values on said bulletin board for matching with said calculated h(k(+)a(+)Rm(k));
and
(f) if a match is detected in said step (e), said server device decides that the aimed value of the aimed value information of a participant device having sent said random number Rm(k) at that time is the maximum or minimum value.

5 more elements

A participant device for a system in which M participant devices send their aimed values to a server device and said server device determines which of said M participant devices has offered the maximum or minimum one of said aimed values received, said participant device comprising:

aimed value generating means;
aimed value transforming means which processes said aimed value with a predetermined one-way function by the number of times corresponding to said aimed value to obtain aimed value information;
and
sending means for sending to said server device said aimed value information and an identifier specifying said participant device.

1 more element

A server device for a system in which M participant devices send their aimed values to said server device and said server device determines which of said M participant devices has offered the maximum or minimum one of said aimed values received, said device comprising:

a conversion table memory which has stored therein a conversion table which defines the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, for converting said aimed value PRm to the corresponding index km;
a bulletin board on which said server device writes said aimed value information an identifier received from each of said participant devices;
updated initial value generating means which generates an updated initial value by processing said initial value with a one-way function repeatedly in correspondence with values of an index k which is a predetermined consecutive positive integers;
a counter which updates said index k one by one;
and
control means which, upon each updating of said index k, compares said updated initial value with said aimed value information on said bulletin board to check whether they match, and determines m and k at the time of first detection of a match.

3 more elements

A recording medium on which there is recorded as a program the procedure which is followed by an m-th one of M participant devices, where m=1, 2, . . . , M, in a quantitative competition method for a system in which said M participant devices send their aimed values to a server device and said server device determines which of said M participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps of:

(a-1) processing an initial value inherent to said participant device m with a predetermined one-way function by the number of times corresponding to said aimed value to generate aimed value information
γm=g(hkm(IVm))
where g is a one-way function, IVm is said initial value, km is an index corresponding to the aimed value of said participant device m and hkm(IVm) indicates processing of said initial value IVm with a one-way function h by km times;
(a-2) generating verification information Cm=hK+1(IVm) and sending said verification information to said server device together with said aimed value information γm;
(b) generating said initial value updated by the number of times requested by said server device and sending said updated initial value to said server device;
and
(c) sending said aimed value information γm=g(hkm(IVm)) to said server device.

4 more elements

A recording medium on which there is recorded as a program the procedure which is followed by an m-th one of M participant devices, where m=1, 2, . . . , M, in a quantitative competition method for a system in which said M participant devices send their aimed values to a server device and said server device determines which of said M participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps of:

(a-1) computing aimed value information by
γm=g(hkm(IVm))
where g is a one-way function, IVm is said initial value, km is an index corresponding to the aimed value PRm of said participant device m and hkm(IVm) indicates processing of said initial value IVm with a one-way function h by km times;
(a-2) generating verification information Cm=hK+1(IVm);
(a-3) generating h(PRm(+)Rm) from a random number Rm and said aimed value PRm and sending said h(PRm(+)Rm) to said server device together with said aimed value information γm and said verification information Cm, said (+) indicating a predetermined arbitrary operation;
(b-1) sending said aimed value PRm and said random number Rm to said server device in response to its request;
and
(b-2) generating Dm=hk(IVm) as said updated initial value corresponding to said index k and sending said updated initial value to said server device in response to its request to present said hk(IVm).

5 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps of:

(a) receiving, from each of participant devices, h(Hm(K)) generated as aimed value information of said each participant device by repeating, for each of a sequence of index values k from at least km corresponding to an aimed value of said each participant device to an upper limit index value K, processing of:
combining an initial value of said each participant device with select information to provide combined information and
operating a one-way function h on said combined information to generate an updated value, said select information indicating whether said each index value k is an aimed value or not, and
publishing said aimed value information h(Hm(K)) on a bulletin board accessible from all of said participant devices and any other devices as well;
(b) requesting said each participant device to send an updated initial value {Hm(k−1), bm(k)} corresponding to each value of said index k in descending order from K;
(c) publishing said updated initial value {Hm(k−1), bm(k)} on said bulletin board;
(d) processing said updated initial value {Hm(k−1), bm(k)} with said one-way function h to generate Hm(k)=h(Hm(k−1)∥bm(k));
(e) checking whether said updated initial value Hm(k) matches Hm(k) in {Hm(k), bm(k+1)} received previously;
and
(f) if a match is detected in said step (e), deciding whether said select information bm(k) represents that the corresponding index k is the index km of said aimed value;
and
(g) if the result of decision in said step (f) is true, outputting said index k concerned and the corresponding participant device number m, and if the result of decision is false, said server device returns to said step (b) and repeats processing for the next index value k.

9 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps wherein said server device:

(a) receives Hm(K) as said aimed value information from said each participant device which, upon each processing of said initial value with said one-way function h, generates an updated initial value by adding said processed initial value with select information bm(k) indicating whether said processed initial value is an aimed value for one value of said index k, and generates Hm(K) by repeatedly performing this processing from at least that index km of a sequence of indexes which corresponds to said aimed value to the upper limit value K, and publishes said aimed value information Hm(K) on a bulletin board accessible from all of said participant device;
(b) for each value of said index k in order descending from K, inquires said each participant device about whether it has bid for said index k, said each participant device responding YES or NO to said inquiry;
(c) upon first detection of the response YES, requests said each participant device to send its updated initial value Hm(k−1);
and
(d) receives Hm(k−1)=h(Hm(k−2)∥bm(k−1)) as said updated initial value from said each participant device and publishes said received updated initial value on said bulletin board;
(e) letting a and a represent predetermined values of said select information bm(k) indicating bidding and not bidding, respectively, generates, for said participant device m having bid for the current index k,
Hm=h( . . . h(h(Hm(k−1)∥a)∥a) . . . ∥a)
through the use of said updated initial value Hm(k−1), and for every one of the other participant devices m, generates
Hm=h( . . . h(h(Hm(k−1)∥a)∥a) . . . ∥a)
through the use of said updated initial values Hm(k−1);
(f) checks whether said Hm for said each participant device matches said Hm(k) published on said bulletin board;
and
(g) if a match is detected in said step (f), determines that said participant device having responded YES is the winning bidding device, and publishes the current value of said index k as the index km of the aimed value of said winning bidding device.

10 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps of:

(a) letting the initial value of said each participant device be represented by IVm, receiving from said each participant device Hm(K)=hK−km(gxm(IVm)) generated as said aimed value information using a predetermined positive integer xm, said initial value IVm and one-way functions h and g;
(b) publishing said aimed value information Am on a bulletin board accessible from all of said participant devices;
and
(c) sending said index k to said each participant device to ask for its updated initial value;
(d) processing said updated initial value Hm(k−1) with said one-way function h to generate h(Hm(k−1));
(e) deciding whether said h(Hm(k−1)) is equal to said aimed value information Hm(K);
(f) if it is decided in said step (e) that they are equal, updating said aimed value information Hm(K) with said updated initial value Hm(k−1), then decrementing said index k by one and returning to said step (c);
(g) if it is decided in said step (e) that they are not equal, processing said updated initial value Hm(k−1) with said one-way function g to generate g(Hm(k−1));
and
(h) deciding whether said g(Hm(k−1)) matches said aimed value information Hm(K);
and
(i) deciding that the aimed value of said participant device corresponding to m and k having provided said match is the maximum or minimum, if a match is detected in said step (h).

9 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps wherein said server device:

(a), letting the initial value of said each participant device be represented by IVm, where m=1, 2, . . . , M, M being an integer equal to or greater than 2, receives from each participant device, as said aimed value information, Hm(K)=hK−km(gxm(IVm)) using a predetermined positive integer xm, said initial value IVm and one-way functions h and g, and publishes said received aimed value information on a bulletin board accessible from all of said participant devices;
(b) for each value of said index k in order descending from K, inquires said each participant device about whether it has bid for said index k, said each participant device responding YES or NO to said inquiry;
(c) upon first detection of the response YES, requests said each participant device to send its updated initial value Hm(k−1);
(d) receives from said each participant device Hm(k−1)=gxm−1(IVm) if k=km and Hm(k−1)=hk−km−1(gxm(IVm)) if k≠km;
(e) for said updated initial value Hm(k−1) received from said participant device having responded YES, generates
Hm=hK−kmg(Hm(k−1))
and for said updated initial value received from said each participant device having responded NO, generates
Hm=hK+1−kg(Hm(k−1))
(f) checks whether said Hm for said each participant device matches said Hm(K) published on said bulletin board;
and
(g) if a match is detected in said step (f), determines that said participant device having responded YES is the winning bidding device, and publishes the current value of said index k as the index Km of the aimed value of said winning bidding device.

8 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, said procedure comprising the steps of:

(a) letting the initial value of said each participant device be represented by IVm, receiving from said each participant device Hm(K)=hK−km(gxm(IVm)) generated as said aimed value information using a predetermined positive integer xm, said initial value IVm and one-way functions h and g;
(b) publishing said aimed value information Hm(K) on a bulletin board accessible from all of said participant devices;
and
(c) sending said index k to said each participant device to ask for its updated initial value;
(d) checking whether its received updated initial value Hk,m is added with said flag;
(e) if it is decided in said step (d) that said flag is added, processing said updated initial value Hm(k−1) with said one-way function g to generate g(Hm(k−1));
(f) deciding whether said g(Hm(k−1)) matches said aimed value information Hm(K);
(g) if it is decided in said step (d) that no flag is added, processing said updated initial value Hm(k−1) with said one-way function h to generate h(Hm(k−1));
(h) deciding whether said h(Hm(k−1)) matches said aimed value information Hm(K);
(i) if it is decided in said step that they are equal, updating said aimed value information Hm(K) with said initial value Hm(k−1), then decrementing said index k by one and returning to said step (c);
and
(j) if it is decided in said step (h), processing said initial value Hm(k−1) with said one-way function g to generate g(Hm(k−1)) and returning to said step (f);
and
(k) if a match is detected in said step (f), deciding that the aimed value of said participant device corresponding to m and k having provided said match is the maximum or minimum.

11 more elements

A recording medium on which there is recorded as a program the procedure which is followed by a server device in a quantitative competition method for a system in which a plurality of participant devices send their aimed values to said server device and said server device determines which of said participant devices has offered the maximum or minimum one of said aimed values received, and there is provided a conversion table showing the relationships between a sequence of values selectable as said aimed values and a sequence of indexes k of integral values respectively corresponding thereto, and m=1, 2, . . . , M, M being an integer equal to or greater than 2;

said procedure comprising the steps of:
(a) receiving from each of said participant devices at least K−km+1 pieces of aimed value information h(k(+)bm(k)(+)Rm(k)) generated by processing, with a predetermined one-way function h and through the use of said conversion table, information k(+)bm(k)(+)Rm(k), which contains each index k equal to or larger than an index km corresponding to said aimed value, select information bm(k) indicating whether said index k corresponds to said aimed value, and a random number Rm(k), A(+)B representing a predetermined arbitrary operation between A and B;
(b) receiving and publishing said aimed value information on a bulletin board accessible from all of said participant devices;
(c) obtaining said random number Rm corresponding to each of said sequence of indexes k;
(d) calculating h(k(+)a(+)Rm(k)), where a is a predetermined value with which said select information bm(k) indicates said aimed value;
(e) checking said aimed values on said bulletin board for matching with said calculated h(k(+)a(+)Rm(k));
and
(f) if a match is detected in said step (e), deciding that the aimed value of the aimed value information of a participant device having sent said random number Rm(k) at that time is the maximum or minimum value.

5 more elements

A quantitative competition system which comprises a server device and M participant devices each connected via a communication channel to said server device and in which said M participant devices send their aimed values to said server device and said server device determines which of said M participant devices has offered the maximum or minimum one of said aimed values received,

each of said participant devices comprising:
aimed value generating means for generating an aimed value PRm;
aimed value transforming means provided with a conversion table memory having stored therein a conversion table which defines the relationships between a sequence of values selectable as said aimed values and a sequence of indexes corresponding thereto, for converting said aimed value PRm to the corresponding index km and which processes said aimed value with a predetermined one-way function by the number of times corresponding to said aimed value to obtain aimed value information;
and
sending means for sending to said server device said aimed value information and an identifier identifying said participant device;
and
said server device comprising:
a conversion table memory which has stored therein a conversion table which is the same as said conversion table;
a bulletin board on which said server device writes said aimed value information an identifier received from said each participant device;
updated initial value acquiring means which acquires an updated initial value obtained by processing said initial value with a one-way function repeatedly in correspondence with values of an index k which is a predetermined consecutive positive integers;
a counter which updates said index k one by one;
and
control means which, upon each updating of said index k, compares said updated initial value with said aimed value information on said bulletin board to check whether they match, and determines m and k at the time of first detection of a match.

10 more elements

System and method for quantitative competition and recording medium having recorded thereon program for implementing the method

Life of this patent

System and method for quantitative competition and recording medium having recorded thereon program for implementing the method

Life of this patent

Abstract

Claims68