Generate local signatures with additional randomness