A method for signing a digital message (m), comprising: computing a password sequence ( z 1,..., z i) comprising a plurality of passwords such that each respective password corresponds to an index unit ( t, i); receiving the message; from a client, submitting a current request (x) to a signature server, said current request being computed as a first function of the message and a current one of the passwords; and if the request is approved, receiving, by the client, from the signature server a current time-stamp for the current request and, by the client, forming and storing a signature (Σ) for the message to include at least the current time-stamp; further comprising: computing each of the plurality of passwords as a second function of a respective subsequent password (z t+1, z i+1), said sequence terminating with an initial password ( z 0) that forms a first public key parameter for the password sequence, wherein the second function is a cryptographic function such as pseudorandom function, a hash function or an encryption function having, as at least one input parameter, a respective one of the index units; computing for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key parameter for the password sequence. computing a password sequence ( z 1,..., z i) comprising a plurality of passwords such that each respective password corresponds to an index unit ( t, i); receiving the message; from a client, submitting a current request (x) to a signature server, said current request being computed as a first function of the message and a current one of the passwords; and if the request is approved, receiving, by the client, from the signature server a current time-stamp for the current request and, by the client, forming and storing a signature (Σ) for the message to include at least the current time-stamp; further comprising: computing each of the plurality of passwords as a second function of a respective subsequent password (z t+1, z i+1), said sequence terminating with an initial password ( z 0) that forms a first public key parameter for the password sequence, wherein the second function is a cryptographic function such as pseudorandom function, a hash function or an encryption function having, as at least one input parameter, a respective one of the index units; computing for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key parameter for the password sequence. computing each of the plurality of passwords as a second function of a respective subsequent password (z t+1, z i+1), said sequence terminating with an initial password ( z 0) that forms a first public key parameter for the password sequence, wherein the second function is a cryptographic function such as pseudorandom function, a hash function or an encryption function having, as at least one input parameter, a respective one of the index units; computing for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key parameter for the password sequence.