1. Method to prove authenticity of execution of program instructions, comprising the steps of: (i) executing program instructions under control of a security program on a security device comprising a random function, the random function being accessible only from the security program through a controlled interface, the controlled interface comprising at least one primitive function accessing the random function that returns output that depends on at least part of a representation of at least those parts of the security program that call the primitive function, (ii) using the random function, computing proof results during execution of the security program operating in a first mode by accessing the random function through the controlled interface, and (iii) using the random function, verifying the proof results during execution of the same security program operating in a second mode by accessing the random function through the controlled interface, wherein the security program, if operating in the first mode, performs the steps of: executing an application program with application program input generating application program output, using the random function through the controlled interface to obtain a result by encrypting, and generating a message authentication code for, at least one of at least part of the application program input, at least part of the application program output, and at least part of the application program, and generating proof results comprising the encrypted and message-authenticated result, and wherein the security program, if operating in the second mode, performs the steps of: receiving proof results to be verified, and at least partially verifying the message authenticity of the encrypted and message-authenticated result in the proof results.