Created
January 1, 2026 18:12
-
-
Save kelbyludwig/dc4dfd904761dc94177c2f69b16c4696 to your computer and use it in GitHub Desktop.
Notebook version of https://kel.bz/post/hnp/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# The Hidden Number Problem\n", | |
| "\n", | |
| "The Hidden Number Problem (HNP) is a problem that poses the question: Are the most signficant bits of a Diffie-Hellman shared key as hard to compute as the entire secret? The original problem was defined in the paper [\"Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes\" by Dan Boneh and Ramarathnam Venkatesan](https://crypto.stanford.edu/~dabo/pubs/abstracts/dhmsb.html).\n", | |
| "\n", | |
| "In this paper Boneh and Venkatesan demonstrate that a bounded number of most signifcant bits of a shared secret are as hard to compute as the entire secret itself. They also demonstrate an efficient algorithm for recovering secrets given a significant enough bit leakage. This notebook walks through some of the paper and demonstrates some of the results.\n", | |
| "\n", | |
| "## How is the HNP defined?\n", | |
| "\n", | |
| "Like many \"hard problems\" in cryptography the HNP is defined as a game with an \"oracle\". When the oracle is queried with a specific number, it returns a value that approximately reveals the most significant bits of the input.\n", | |
| "\n", | |
| "To be concrete, the oracle depends on a $n$-bit prime number $p$ and a $k$-bit significant bit leak. The output of $MSB_{k}(x)$ defined as some value $z$ such that:\n", | |
| "\n", | |
| "$$ |x - z| \\lt \\frac{p}{2^{k+1}}$$\n", | |
| "\n", | |
| "The Hidden Number Problem oralce reveals $g^x$ and $MSB_{k}(\\alpha g^{x} \\pmod{p})$ for randomized values of $g^x$ and asks if you can reveal the hidden $\\alpha$ value. \n", | |
| "\n", | |
| "There are a few variations on this problem described in the paper, however, this \"randomized\" version of the HNP is the only version of the problem we'll focus on.\n", | |
| "\n", | |
| "An implementation of the $MSB$ function can be found below." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 1, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# Some parameters of the game, chosen for simplicity.\n", | |
| "\n", | |
| "# p - A prime number for our field.\n", | |
| "p = next_prime(2^16)\n", | |
| "\n", | |
| "# n - The number of bits in `p`.\n", | |
| "n = ceil(log(p, 2))\n", | |
| "\n", | |
| "# k - The number of significant bits revealed by the oracle.\n", | |
| "# Using parameters from Thereom 1.\n", | |
| "k = ceil(sqrt(n)) + ceil(log(n, 2))\n", | |
| "\n", | |
| "def msb(query):\n", | |
| " \"\"\"Returns the MSB of query based on the global paramters p, k.\n", | |
| " \"\"\"\n", | |
| " while True:\n", | |
| " z = randint(1, p-1)\n", | |
| " answer = abs(query - z)\n", | |
| " if answer < p / 2^(k+1):\n", | |
| " break\n", | |
| " return z\n", | |
| "\n", | |
| "def create_oracle(alpha):\n", | |
| " \"\"\"Returns a randomized MSB oracle using the specified alpha value.\n", | |
| " \"\"\"\n", | |
| " alpha = alpha\n", | |
| " def oracle():\n", | |
| " random_t = randint(1, p-1)\n", | |
| " return random_t, msb((alpha * random_t) % p)\n", | |
| " return oracle" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## What is the MSB function revealing?\n", | |
| "\n", | |
| "Something worth noting about this paper is their defintion of most signficant bits. The definition of $MSB_k$ tripped me up at first as I defaulted to thinking $MSB_{k}(x)$ was intended to reveal exactly the $k$ most significant bits of $x$. If you think the same you may discover: \n", | |
| "\n", | |
| "* This definition is defined for \"some value of $z$\" which means $MSB_{k}(x)$ can have multiple correct outputs!\n", | |
| "\n", | |
| "* This definition depends on a prime value $p$ which shouldn't affect $x$'s most significant bits!\n", | |
| "\n", | |
| "These properties of $MSB$ are very unlike the properties I would expect from the most natural definition of most significant bits. This is why earlier I specified that the value revealed by the oracle *approximately* reveals the most signficant bits of the input.\n", | |
| "\n", | |
| "So how do you make sense of the $MSB$ function? I found the following observations helped me grok what it was doing.\n", | |
| "\n", | |
| "* $u = x$ will always be one valid solution satsifying the inequality $| x - u | \\leq \\frac{p}{2^{k+1}}$. Note that if $u = x$ the oracle's output would be $x$.\n", | |
| "\n", | |
| "* Other solutions to the inequality will \"hover\" around $x$. Plotting the function `f(u) = | x - u |` for some fixed $x$ values should convince you of this.\n", | |
| "\n", | |
| "* As $k$ increases, the right hand side of the inequality greatly shrinks. This reduces the set of valid $u$ solutions. This also means the set of valid $u$ values are also closer to $x$.\n", | |
| "\n", | |
| "* The $k$ value isn't exactly the number of bits of $x$ revealed. Instead, as $k$ increase, the possible values of $u$s become closer to $x$. The closer $u$ solutions are to $x$, the more likely $x - u$ will accurately reveal $x$'s most significant bits.\n", | |
| "\n", | |
| "Another way to say it: As $k$ grows closer to the number of bits in $p$, the closer $MSB_k(x)$ will be to $x$. The closer the possible answers of $MSB_k(x)$ are to $x$ the more accurate the leaked bits are." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## When is the HNP solvable?\n", | |
| "\n", | |
| "In Section 3 Theorem 1 the paper shows that an adversary has an advantage in solving an instance of the randomized HNP given a $k$ value that is approximately $\\sqrt{\\log{p}}$ using $d = 2\\sqrt{n}$ oracle queries. For this demonstration, I used a more significant $k$ value: $\\sqrt{\\log{p}} + \\log{\\log{p}} = \\sqrt{n} + \\log{n}$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# d - The number of oracle queries.\n", | |
| "# Using parameters from Thereom 1.\n", | |
| "d = 2 * ceil(sqrt(n))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Given a useful oracle, how do I solve the HNP?\n", | |
| "\n", | |
| "I'm trying to summarize an otherwise dense paper, so I likely have some of this wrong. With that being said...\n", | |
| "\n", | |
| "Given $d$ oracle queries and answers, solving the HNP can be done by viewing the solution as a specific case of the [Closest Vector Problem](https://en.wikipedia.org/wiki/Lattice_problem). This case of CVP is easy to solve given an useful enough $MSB$ oracle and a specially selected basis.\n", | |
| "\n", | |
| "This special case CVP uses a lattice with the basis vectors:\n", | |
| "\n", | |
| "```\n", | |
| "[ p, 0, ... , 0, 0 ]\n", | |
| "[ 0, p, ... , 0, 0 ]\n", | |
| "[ ... ]\n", | |
| "[ 0, 0, ... , p, 0 ]\n", | |
| "[ t1, t2, ... , td, 1/p ]\n", | |
| "```\n", | |
| "\n", | |
| "Where $t_N$ values are randomized inputs for the $MSB$ oracle. The lattice is spanned by the rows of this matrix. \n", | |
| "\n", | |
| "The vector $u$ = `[a1, a2, ..., ad, 0]` is the vector that we want to find a close lattice point to. The $a_N$ values are the outputs of the $MSB$ oracle for the respective $t_N$ values.\n", | |
| "\n", | |
| "A vector with the first coefficient $\\alpha t_1 \\pmod{p}$ (for example) can be a valid lattice point as $\\alpha$ is an integer scalar of the last row, and $\\pmod{p}$ is equivalent to subtracting some integer multiple of the first row. \n", | |
| "\n", | |
| "The vector $v$ is a lattice vector such that each element of $v$ is $\\alpha t_n \\pmod{p}$ except for the $d+1$th coefficient which is $\\frac{\\alpha}{p}$. Given the vector $v$, we can recover $\\alpha$ easily by scaling the vector by $p$.\n", | |
| "\n", | |
| "By the definition of the $MSB$ oracle, the vector $u$ is likely to be close to $v$. The paper proves this. The paper also proves that $v$ is a likely to be the only vector close to $u$.\n", | |
| "\n", | |
| "Given all of this, we can use a efficient algorithm that solves approximate CVP (e.g. [Babai's Nearest Plane Algorithm](https://www.isical.ac.in/~shashank_r/lattice.pdf)) for $u$. This is likely to find our friend $v$ which reveals $\\alpha$. This means we solved a case of the HNP!" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 3, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Solving CVP using lattice with basis:\n", | |
| "[ 65537 0 0 0 0 0 0 0 0 0 0]\n", | |
| "[ 0 65537 0 0 0 0 0 0 0 0 0]\n", | |
| "[ 0 0 65537 0 0 0 0 0 0 0 0]\n", | |
| "[ 0 0 0 65537 0 0 0 0 0 0 0]\n", | |
| "[ 0 0 0 0 65537 0 0 0 0 0 0]\n", | |
| "[ 0 0 0 0 0 65537 0 0 0 0 0]\n", | |
| "[ 0 0 0 0 0 0 65537 0 0 0 0]\n", | |
| "[ 0 0 0 0 0 0 0 65537 0 0 0]\n", | |
| "[ 0 0 0 0 0 0 0 0 65537 0 0]\n", | |
| "[ 0 0 0 0 0 0 0 0 0 65537 0]\n", | |
| "[ 48551 1628 14964 48927 50148 53570 35147 30246 38191 58907 1/65537]\n", | |
| "\n", | |
| "Vector of MSB oracle answers:\n", | |
| "(18059, 60122, 7350, 9904, 22254, 10999, 28418, 1197, 4772, 55857, 0)\n", | |
| "\n", | |
| "Closest lattice vector:\n", | |
| "[18088, 60138, 7377, 9917, 22252, 10984, 28403, 1220, 4782, 55883, 10262/65537]\n", | |
| "\n", | |
| "Recovered alpha! Alpha is 10262\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "def build_basis(oracle_inputs):\n", | |
| " \"\"\"Returns a basis using the HNP game parameters and inputs to our oracle\n", | |
| " \"\"\"\n", | |
| " basis_vectors = []\n", | |
| " for i in range(d):\n", | |
| " p_vector = [0] * (d+1)\n", | |
| " p_vector[i] = p\n", | |
| " basis_vectors.append(p_vector)\n", | |
| " basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])\n", | |
| " return Matrix(QQ, basis_vectors)\n", | |
| "\n", | |
| "def approximate_closest_vector(basis, v):\n", | |
| " \"\"\"Returns an approximate CVP solution using Babai's nearest plane algorithm.\n", | |
| " \"\"\"\n", | |
| " BL = basis.LLL()\n", | |
| " G, _ = BL.gram_schmidt()\n", | |
| " _, n = BL.dimensions()\n", | |
| " small = vector(ZZ, v)\n", | |
| " for i in reversed(range(n)):\n", | |
| " c = QQ(small * G[i]) / QQ(G[i] * G[i])\n", | |
| " c = c.round()\n", | |
| " small -= BL[i] * c\n", | |
| " return (v - small).coefficients()\n", | |
| "\n", | |
| "# Hidden alpha scalar\n", | |
| "alpha = randint(1, p-1)\n", | |
| "\n", | |
| "# Create a MSB oracle using the secret alpha scalar\n", | |
| "oracle = create_oracle(alpha)\n", | |
| "\n", | |
| "# Using terminology from the paper: inputs = `t` values, answers = `a` values\n", | |
| "inputs, answers = zip(*[ oracle() for _ in range(d) ])\n", | |
| "\n", | |
| "# Build a basis using our oracle inputs\n", | |
| "lattice = build_basis(inputs)\n", | |
| "print(\"Solving CVP using lattice with basis:\\n%s\\n\" % str(lattice))\n", | |
| "\n", | |
| "# The non-lattice vector based on the oracle's answers\n", | |
| "u = vector(ZZ, list(answers) + [0])\n", | |
| "print(\"Vector of MSB oracle answers:\\n%s\\n\" % str(u))\n", | |
| "\n", | |
| "# Solve an approximate CVP to find a vector v which is likely to reveal alpha.\n", | |
| "v = approximate_closest_vector(lattice, u)\n", | |
| "print(\"Closest lattice vector:\\n%s\\n\" % str(v))\n", | |
| "\n", | |
| "# Confirm the recovered value of alpha matches the expected value of alpha.\n", | |
| "recovered_alpha = (v[-1] * p) % p\n", | |
| "assert recovered_alpha == alpha\n", | |
| "print(\"Recovered alpha! Alpha is %d\" % recovered_alpha)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## A solution using Sage's IntegerLattice\n", | |
| "\n", | |
| "I also wrote this originally using Sage's `IntegerLattice` module which has a `closest_vector` method. However this was non-ideal because:\n", | |
| "\n", | |
| "* `IntegerLattice` requires integer coefficient basis vectors but the HNP uses $\\frac{1}{p}$ as one of the coefficients. This was addressable, as I just scaled the basis and the CVP vectors by a value of $p$.\n", | |
| "\n", | |
| "* `IntegerLattice.closest_vector` is slow, as it solves a more general problem then approximate CVP.\n", | |
| "\n", | |
| "Because I may want to borrow ideas from this code in the future, I'll keep the old and slow solution around." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 4, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "from sage.modules.free_module_integer import IntegerLattice\n", | |
| "\n", | |
| "def build_integer_lattice(oracle_inputs):\n", | |
| " basis_vectors = []\n", | |
| " for i in range(d):\n", | |
| " p_vector = [0] * (d+1)\n", | |
| " p_vector[i] = p*p\n", | |
| " basis_vectors.append(p_vector)\n", | |
| " scaled_answers = list(map(lambda oi: oi*p, oracle_inputs))\n", | |
| " basis_vectors.append(scaled_answers + [1])\n", | |
| " return IntegerLattice(basis_vectors)\n", | |
| "\n", | |
| "oracle = create_oracle(alpha)\n", | |
| "inputs, answers = zip(*[ oracle() for _ in range(d) ])\n", | |
| " \n", | |
| "basis = build_integer_lattice(inputs)\n", | |
| "v = vector(ZZ, list(answers) + [0])*p\n", | |
| "\n", | |
| "# This general closest_vector method is pretty slow so I'm leaving it commented out.\n", | |
| "# cv = lat.closest_vector(v)\n", | |
| "# assert cv[-1] % p == alpha\n", | |
| "# print(\"Found!\")" | |
| ] | |
| } | |
| ], | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "SageMath 8.1", | |
| "language": "", | |
| "name": "sagemath" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 2 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython2", | |
| "version": "2.7.14" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment