To provide a program conversion device capable of executing a program that includes a secret operation using secret information without exposure of the secret information in a memory. In an execution program generation device, with respect to an original program that includes the secret operation, a combining function generation unit generates combining function processing for applying a bitwise self-dual function to an input value, a split secret information generation unit generates pieces of split secret information by performing an inverse operation of the self-dual function, a program conversion unit generates pieces of split secret operation processing each for performing the operation between each bit value of the operand information and a corresponding bit value of a different piece of the split secret information, and replaces the secret operation processing with the pieces of the split secret operation processing and the combining function processing.