Skip to content

Instantly share code, notes, and snippets.

@karlgluck
karlgluck / Extensible-Merkle-Trees.md
Last active November 26, 2018 08:05
I present a simple algorithm that allows billions of one-time signatures to be used for the same public key with today's technology

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.

// 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
karlgluck / How to Access Data in the Backbuffer in Direct3D 9.cpp
Created January 17, 2014 03:35
This is the code for accessing pixel data from the backbuffer in a D3D9 application. Keywords: LPDIRECT3DSURFACE9 read backbuffer copy back buffer directly access back buffer Direct3D device DirectX 9
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
karlgluck / Hash Ladders for Shorter Lamport Signatures.md
Last active March 31, 2024 17:53
I describe a method for making Lamport signatures take up less space. I haven't seen anyone use hash chains this way before, so I think it's pretty cool.

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?