Secure execution of workflow tasks are executed according to a given execution pattern in a decentralized workflow system with a central workflow engine and multiple task execution agents. The method starts at an i'th execution agent which is selected by at least one preceding execution agent in accord with the execution pattern to perform an i'th task of the workflow. The method includes receiving, from the at least one preceding execution agent via a secure channel, a task-based private key generated by the at least one preceding execution agent, signing workflow information of the workflow for at least one subsequent execution agent with a workflow signature, selecting at least one appropriate subsequent execution agent, computing a task-based private key for the at least one subsequent execution agent, and forwarding to the at least one subsequent execution agent the workflow information with its associated workflow signature.