Karl Gluck karlgluck

Keybase proof

I hereby claim:

I am karlgluck on github.
I am karlgluck (https://keybase.io/karlgluck) on keybase.
I have a public key whose fingerprint is 6797 F0BC 1431 E8CB 5E34 D924 B4F7 4EB0 FF8B 9035

To claim this, I am signing this object:

Extensible Merkle Trees

I present a simple algorithm that lets one use an undetermined number of OTS's for the same public key at the expense of a larger signature. My scheme would allow at least 4.2 billion one-time signatures to be used with a single public key using today's technology.

Background

The Merkle signature scheme (MSS) is a well-known way to use a one-time signature (OTS) like the Lamport-Diffie OTS to create a public key cryptosystem. Briefly, one creates a hash tree of height h from 2^h OTS public keys leading to a root public key. To sign a message, one then simply creates a signature from one of the leaf OTS's as usual and provides evidence of its presence in the tree by giving the sequence of hashes that lead from it to the root public key of the MSS.

What's this all about?

Digital cryptography! This is a subject I've been interested in since taking a class with Prof. Fred Schneider back in college. Articles pop up on Hacker News fairly often that pique my interest and this technique is the result of one of them.

Specifically, this is about Lamport signatures. There are many signature algorithms (ECDSA and RSA are the most commonly used) but Lamport signatures are unique because they are formed using a hash function. Many cryptographers believe that this makes them resistant to attacks made possible by quantum computers.

How does a Lamport Signature work?


	// this lets you write bits to a buffer and scan them back:
	//
	// char buffer[3];
	// bitfield writer(buffer);
	// writer.write(2,6); // write "2" as a 6-bit uint
	// writer.write(9,4); // write "9" as a 4-bit uint
	// writer.write(0,1); // etc
	// writer.write(1,2);
	// size_t bytes = writer.bytes(buffer); // bytes == 2

	void demoExtractBackBufferPixels(LPDIRECT3DDEVICE9 d3d_device) {

	// TODO: In your app, add FAILED() macros to check the HRESULTs passed back
	// by each of the API calls. I leave these out for clarity.

	// Grab the backbuffer from the Direct3D device
	LPDIRECT3DSURFACE9 back_buffer = NULL;
	d3d_device->GetBackBuffer(0, 0, D3DBACKBUFFER_TYPE_MONO, &back_buffer);

	// Get the buffer's description and make an offscreen surface in system memory.