Commons license.

Your support will help MIT OpenCourseWare

continue to offer high-quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

TADGE DRYJA: Today, I'm going to talk

about signatures and all sorts of different signature

kind of things.

In the problem set, you're working with signatures,

but you're working with hash-based signatures, which

are not actually used in bitcoin at all.

But we'll talk about those.

OK.

So if you've gotten through the homework,

there's lamport signatures, right?

These are hash-based signatures.

And they use hash functions.

So it's fairly straightforward.

You can understand them.

There's nothing super crazy going on.

The code is fairly compact.

So that's cool.

What are some disadvantages of these lamport signatures?

Does anyone-- yeah?

AUDIENCE: You can only use it once.

TADGE DRYJA: Yeah.

OK.

So plus.

This is hashes.

That's cool.

One-time use.

Other possible disadvantages of them relative to other systems,

if you're aware.

Another is they're kind of huge, kind of big, right?

You can deal with it.

But if you were looking in the forge,

or that file with the signatures,

it's like, what, 8K for a signature--

8 kilobytes-- kind of big.

Keys are 16 kilobytes--

kind of annoying.

Private keys are also 16 kilobytes.

So yes, sig 8K, 16K priv/pub key.

So that's some disadvantages.

So since I don't have slides, I'm

gonna make this more fun and interactive.

What are some solutions for these problems?

So we can actually mitigate/solve

both of these things to a pretty good extent.

So how about the first one, one-time use?

What would be a fairly obvious way

to mitigate the one-time use problem?

And don't think the answer is too stupid.

It may be a fairly stupid answer, and it might work.

So yeah?

AUDIENCE: Not actually revealing pieces of your private key?

Instead, reveal something else.

TADGE DRYJA: There's probably some clever way.

But that might be too clever.

Something really simple for, OK, I can only use a key once.

How can I use a "key," quote unquote, more than once?

Yeah?

AUDIENCE: Make another one.

TADGE DRYJA: Yeah.

You can make another key.

So you could say, well, I've got this 16 kilobyte public key.

Well, I'm going to make a 32 kilobyte public key.

And it's just two public keys stuck together.

And now, when I make a signature,

I just put an extra bit in the front.

And I say, well, this signature is using key 0

or this signature is using key 1,

and it's got the whole signature after.

And then you look through this 32 kilobyte public key,

and you say, OK, well, it starts with a zero,

so that means it's using the first key, the first subkey

in this 32 byte public key block.

And in this case, it's using one,

so that means it's using the latter subkey.

So that would work.

That would let you use your public key twice,

at the cost of doubling your public key size, which

is not really great, right?

And it's not very efficient.

But it does sort of work.

OK.

Any clever ways to do it more efficiently?

Or wait.

So OK, also, I'll give you sort of a hint.

In this case, let's say this is pub sub 0 and pub sub 1, right?

And then, your 32 byte pubkey is just them

concatenated together, right--

pub0, pub1.

What would happen to the private keys in this case, right?

How would private keys work here?

Same expansion of size, I guess.

Can anyone think of a way to mitigate the expansion of size

of private keys in this case?

So the private keys are the preimages here, right?

They lead into these public key blocks.

So you could just say, OK, well, I

have twice the size private key leading into twice the size

public key.

Could you do that more efficiently?

Yeah?

AUDIENCE: Could you just hash the private key

so that you have two hashes instead of one?

TADGE DRYJA: Yes.

So let's say you have this 16k block,

and you want this to turn into two public key.

So that's the basic good way to do it.

And it sort of turns in like that.

How exactly-- what's the way you do that?

AUDIENCE: You can keep the same private key as before

and just add something like zero or one to indicate--

TADGE DRYJA: Yeah.

So this is a hash function, right?

And so before, we just said, OK, hash of this is block 0,

this is block 1, this is block 2.

So the idea of pub--

let's see.

Is this visible?

This might be too small, right?

AUDIENCE: Yes.

TADGE DRYJA: Yes, OK.

Let me make this bigger.

Sorry.

OK.

So in these diagrams, you've got your private key right now.

And it's in these big blocks.

And there's 256 of them, but let's keep it small.

And the idea is these are 32 byte blocks with random numbers

in it.

And then you hash it to get your public key.

So we say, OK, pub2--

and this is public, this is private, and, let's say,

secret--

pub2 is just the hash of secret2, right?

But yeah.

What we could do is we could sort of have two different hash

functions.

And then a real simple way to make

a whole bunch of different hash functions

is we define, OK, well hash0 is defined

as the hash function of whatever your input x is concatenated

with the number 0.

And then hash1, we define as just x comma 1 and so on.

And this is actually secure.

You could do this.

Any questions or possible objections?

AUDIENCE: I was thinking that if someone knew the hash function

you're using, wouldn't they only define

x because they know that it won't help with [INAUDIBLE] x.

[INAUDIBLE]

TADGE DRYJA: Yes.

Yes.

So there's no real entropy or secrets in this 0 and 1.

But it's purely riding on x, right?

But the idea is, well, if I do this,

and I say, OK, well pub2 is the hash

of secret2 concatenated with 0, yeah, if you know secret2,

you can go back.

Because 0 is obvious.

But the idea is if you don't know secret2, the fact that you

know the last byte of the hash input doesn't really help you.

Because there's all this data that you don't know.

And so you're not going to be able to find a preimage.

You're like, OK, I know the preimage

to public2 ends with a 0 byte.

What are the other 32 bytes that come before that?

You still can't go back to make a preimage.

AUDIENCE: But it feels like there's some sort of--