Device and method for certifying reliability of public key, and program therefor

A program for causing a first computer to perform a method for proving a reliability of a second public key which is part of a second key pair generated in association with a first key pair comprising a first secret key and a first public key, wherein the first secret key is a, a generator of a cyclic group G1 is g1, the first public key is a·g1, the second secret key is ax where x is an integer, the second public key is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, the method comprising steps of:

• receiving a proof request for a proof of a reliability of the second public key ax·g1 from a second computer which can communicate with the first computer via a computer network,
• calculating a verification formula expressed in equation (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H (n1, n2, . . . nN) in response to the proof request, and
• transmitting a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which n1 is ax·g1.

A first computer for proving a reliability of a second public key which is part of a second key pair generated in association with a first key pair comprising a first secret key and a first public key, wherein the first secret key is a, a generator of a cyclic group G1 is g1, the first public key is a·g1, the second secret key is ax where x is an integer, the second public key is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, configured to:

• receive a proof request for a proof of a reliability of the second public key ax·g1 from a second computer which can communicate with the first computer via a computer network,
• calculate a verification formula expressed in equation (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H (n1, n2, . . . nN) in response to the proof request, and
• send a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which n1 is ax·g1.

A method for proving a reliability of a second identifier generated in association with a first identifier, wherein a first constant is a, a generator of a cyclic group G1 is g1, a first identifier is a·g1, a second constant is ax where x is an integer, a second identifier is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, comprising steps of:

• a first computer receiving a proof request for a proof of a reliability of the second identifier ax·g1 from a second computer which can communicate with the first computer via a computer network,
• the first computer calculating a verification formula expressed in formula (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H(n1, n2, . . . nN) in response to said proof request, and
• the first computer transmitting a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which n1 is ax·g1.

A first computer comprising a non-transitory computer readable medium and a processor for proving a reliability of a second identifier generated in association with a first identifier, wherein a first constant is a, a generator of a cyclic group G1 is g1, a first identifier is a·g1, a second constant is ax where x is an integer, a second identifier is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, the first computer configured to:

• receive a proof request for a proof of a reliability of the second identifier ax·g1 from a second computer which can communicate with the first computer via a computer network,
• calculate a verification formula expressed in formula (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H(n1, n2, . . . nN) in response to said proof request, and
• transmit a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which n1 is ax·g1.

A program, stored in a non-transitory computer readable medium of a first computer comprising the medium and a processor, including instructions that, when executed, causes the first computer to perform a method for proving a reliability of a second identifier generated in association with a first identifier, wherein a first constant is a, a generator of a cyclic group G1 is g1, a first identifier is a·g1, a second constant is ax where x is an integer, a second identifier is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, the method comprising steps of:

• receiving a proof request for a proof of a reliability of the second identifier ax·gi from a second computer which can communicate with the first computer via a computer network,
• calculating a verification formula expressed in formula (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H(n1, n2, . . . nN) in response to said proof request, and transmitting a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which ni is ax·g1.

A non-transitory computer readable medium storing a program including instructions that, when executed, causes a first computer comprising the medium and a processor to perform a method for proving a reliability of a second identifier generated in association with a first identifier, wherein a first constant is a, a generator of a cyclic group G1 is g1, a first identifier is a·g1, a second constant is ax where x is an integer, a second identifier is ax·g1, and H(n1, n2, . . . nN) (N is an integer greater than or equal to 1) is a hash function, the method comprising steps of:

• receiving a proof request for a proof of a reliability of the second identifier ax·g1 from a second computer which can communicate with the first computer via a computer network,
• calculating a verification formula expressed in formula (1)
• e(ax·g1,H)=e(a·g1,x·H)=e(g1,ax·H) (1)
• to verify proof data including x·H(n1, n2, . . . nN) and ax·H(n1, n2, . . . nN) in response to said proof request, and transmitting a result of the verification as a response to the proof request to the second computer,
• wherein G2 is a cyclic group with g2 as a generator, GT is a cyclic group with gT as a generator, and a bilinear map e can be defined from G1×G2 to GT, and
• wherein a hash function H(n1, n2, . . . nN) can be defined as a map from an arbitrary combination of first to Nth data to the cyclic group G2 in which n1 is ax·g1.