Lamport signature for multiple messages

27 views
Skip to first unread message

Leo

unread,
Nov 13, 2021, 6:11:11 PM11/13/21
to
Hi sci.crypt,

I had a question while reading about Lamport signatures [1], but a
quick internet search didn't reveal any answers.

Lamport signatures are one-time signatures, using them to sign
multiple messages massively reduces their security / unforgeability.
But if you include a new public key at the end of each message, and
the recipient receives every message you send without missing any,
would you be able to have authenticated communications using only
lamport signatures?

My intuition tells me this should work without security problems.
After all, if an adversary could modify the public keys we sent
without breaking the signature, they could just change message
contents even if we always used a fresh signature that we exchanged
beforehand.

I'm asking for opinions here in case I missed something while
researching this online, or if anyone knows that this is broken and
not the right thing to do.

[1]: https://en.wikipedia.org/wiki/Lamport_signature

--
Leo

Max

unread,
Nov 13, 2021, 8:59:18 PM11/13/21
to
On 14.11.21 00:10, Leo wrote:
[...]

> After all, if an adversary could modify the public keys we sent
> without breaking the signature, they could just change message
> contents even if we always used a fresh signature that we exchanged
> beforehand.

I agree. As long as the new private key is completely random and
independent from the ones before there is no way to break this system
other than breaking the hash function itself.

[...]

Cheers,

Max

Max

unread,
Nov 14, 2021, 1:33:58 PM11/14/21
to
On 14.11.21 00:10, Leo wrote:
How about instead of including the new public key in the message, you
generate 2 public keys as your initial public key. When you sign a
message, you sign it with the first key, generate two new keys, sign
those with the second key and write them in some public ledger/PKI? This
way, it wouldn't matter if your recipient misses a message. You could
even use this technique to use a single root key for communication with
different recipients.

711 Spooky Mart

unread,
Nov 15, 2021, 1:51:18 AM11/15/21
to
You can generate a large tree of public keys to start and sign the batch
hashes with a parent key that is disposed, and publish and dispose of
each key in succession with each new message.

There is also another method for Lamport signatures in which you walk a
merkle tree of these keys and prune them off as you use them, signing
the remainder until you run out of key.

In the latter methods you don't need to publish all the keys up front,
just a signed hash table or signed merkle tree of hashes. If the hash of
a signing key is in the signed hash table, it is assumed to be valid.

Whatever your assumptions are for the security of aprioroi hash
permutations, will also hold true for chaining Lamport signatures. Like
Max said, it hinges on the security of the hash algorithm and
punctilious insurance against key re-use.

--
──┏━━━━┓──┏━━┓───┏━━┓── ┌────────────────────────┐ ┌────────┐
──┗━━┓─┃──┗┓─┃───┗┓─┃── │ Spooky Mart [chan] 711 │ │ always │
─────┃─┃──┏┛─┗┓──┏┛─┗┓─ │ https://bitmessage.org │ │ open │
─────┗━┛──┗━━━┛──┗━━━┛─ └────────────────────────┘ └────────┘

Max

unread,
Nov 15, 2021, 8:57:55 AM11/15/21
to
On 15.11.21 07:53, 711 Spooky Mart wrote:
> On 11/14/21 12:33 PM, Max wrote:
>> On 14.11.21 00:10, Leo wrote:
>>> Hi sci.crypt,
>>>
[...]

>
> You can generate a large tree of public keys to start and sign the batch
> hashes with a parent key that is disposed, and publish and dispose of
> each key in succession with each new message.
>
> There is also another method for Lamport signatures in which you walk a
> merkle tree of these keys and prune them off as you use them, signing
> the remainder until you run out of key.
>
> In the latter methods you don't need to publish all the keys up front,
> just a signed hash table or signed merkle tree of hashes. If the hash of
> a signing key is in the signed hash table, it is assumed to be valid.

Yes, but that makes the already large signature even larger and/or the
public key huge, doesn't it? Also, you have to keep track of the keys
you already used. There are some cool schemes with hypertrees, where
each leaf of a top tree signs the root of a subtree. Yet, afaik, you end
up with signatures around 50 kB instead of the 1-2k for a single signature.

Jakob Bohm

unread,
Nov 16, 2021, 8:14:20 AM11/16/21
to
The Merkle tree of Lamport public keys only requires publishing the
single hash at the top of the tree, plus the algorithm paramaters (hash
alg, weierstrass factor, tree depth). There are actually two competing
RFC standard formats for this now, and NIST is very close to
standardizing one set of parameters.


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

Max

unread,
Nov 16, 2021, 5:25:54 PM11/16/21
to
Thanks for the hint. The problem is, you have to make a trade off
between public key size, private key size, signature size and
computation time (signing and verification).

You can use the root of a single Merkle tree as the public key. But this
means, you have to calculate the whole Merkle tree in advance which gets
infeasible for larger amounts of signatures. Also, you have to store the
resulting hashes if you don't intend to repeat this calculation for each
signature. For just 1,000,000 signatures you run into about
16,000,000,000 hash operations and 32 MB of storage space for generating
the private key. In addition, you have to include the hashes required
for calculating the public key/root hash with each signature, which is
like 640 extra bytes. Those extra bytes are not to bad to add to the
2048 bytes signature, but the time and storage requirements for the
Merkle tree are annoying.

If you go with hypertrees, where each leaf signs the root of another
Merkle tree with the public one-time-keys being the leafs of the
bottom-most trees, you can circumvent the need for calculating all
public one-time-keys in advance but at the cost of much bigger
signatures (one public key and one signature for each tree plus some
change).

I really like the simplicity and don't mind its quantum resistance, yet,
the statefulness (yes, I know there are stateless approaches, but there
signatures become really big) and the memory/bandwidth requirements
aren't nothing.
Reply all
Reply to author
Forward
0 new messages