karlgluck

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.

karlgluck

// 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

karlgluck

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.

karlgluck

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?