Patent ID: 8090956

Claim:
A program conversion device comprising: a program storage unit operable to store therein an original program that includes a secret operation instruction to perform a secret operation, using a secret key, on operand information; a split secret key generation unit operable to generate split secret keys based on the secret key and a predetermined combining operation, such that the secret key is acquired by performing the predetermined combining operation on the split secret keys; a split secret operation instruction generation unit operable to generate a split secret operation instruction for each of the split secret keys, each of the split secret operation instructions performing a split secret operation using a corresponding one of the split secret keys and the operand information; a combining instruction generation unit operable to generate a combining instruction to combine results of the split secret operation using the predetermined combining operation, such that a result that is the same as a result of the secret operation is acquired; and a replacement unit operable to replace the secret operation instruction included in the original program with the split secret operation instructions and the combining instruction, wherein the predetermined combining operation is a bitwise operation f using a self-dual function, the bitwise operation f satisfying the following conditions: (i) ˜f(x 1 , x 2 , . . . , xn)=f(˜x 1 , ˜x 2 , . . . , ˜xn); (ii) f(0, 0, . . . , 0)=0; and (iii) f(1, 1, . . . , 1)=1, where values x 1 to xn are each a bitwise value, and a sign “˜” is a logical operation that represents negation; wherein the split secret operation is performed between each bit value of the operand information and a corresponding bit value of a different piece of the split secret information that is in the same bit position as the bit value of the operand information.