Hidden Number Problem

Posted on Nov 18, 2022
Updated on Oct 28, 2024

Table of contents:

在最近的很多比赛都遇到了这个Hidden Number Problem(HNP)，所以抽个时间来仔细学习一下，然后马上要HGAME2023了，正好准备一下题目给新生写。

Introduce

HNP问题第一次被提出是在这篇论文中 “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan。HNP问题本来是用来研究Diffie-Hellman共享密钥中的最高有效位是否与整个秘密一样难以计算？并且D. Boneh和R. Venkatesan还展示了一种有效的算法，用于在有足够大的位泄漏的情况下恢复密钥。

这个方法用到了格和格基规约的算法，一开始学习格密码时把重点放在了基于格的密钥系统的学习上，但格终究是数学上的东西，数学说白了就是一个工具，那么格自然也是一个工具，只不过我们把格这个有力的工具用在了密码分析上而已。

How is the HNP defined

论文中首先提出了most significant bits（MSB）的定义。首先令$p$是一个素数，$n$是$p$的二进制位数，即$n=log_2(p)$，用$x\ mod\ p$来表示一个定义在有限域的数$a \in GF(p)$，即$x \equiv a \pmod{p}$。定义$MSB_k(x)$的值为$t$并且 $(t-1)\cdot p/2^k\leq x <t \cdot p/2^k$，或者更简单的定义 $$ MSB_k(x)=z,\quad |x-z|< p/2^k $$

About the $MSB_k(x)$

一看到most signficant bits可能很多人都会想当然的认为是$x$的最高$k$位。其实不然，根据定义，可以写一个小demo

from random import randint
from sage.all import *
from Crypto.Util.number import getPrime
# Some parameters of the game, chosen for simplicity.

# p - A prime number for our field.
p = getPrime(128)

# n - The number of bits in `p`.
n = ceil(log(p, 2))

# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))
print(f"The number of significant bits = {k}")

def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2**(k+1):
            break
    return z

x = randint(1, p-1)
print(f"x = {x}")
print(f"MSB's output = {msb(x)}")
print(f"most k bit of x = {x >> (n - k)}")

'''
The number of significant bits = 19
x = 54914319491231438995398843041850226262
MSB's output = 54914493779494223381640832877194242316
|MSB(x) - x| = 124182961411716441204715130169529
most k bit of x = 84608
'''

如何去理解这个$MSB_k(x)$呢，不难得出以下几点：

根据$MSB_k(x)$的定义，有$u=x$是一定满足$|x-u|\leq\frac{p}{2^{k+1}}$的，那么$u=x$一定是$MSB$的一个输出，为什么是一个呢，因为这个不等式肯定是多解的。
当$k$增大时，不等式的右边$\frac{p}{2^{k+1}}$和会快速的缩减，意味着不等式左边的$z$也就是$MSB$的输出要接近$x$。$k$越大，$MSB_k(x)$越接近$x$。

由于$k$越大，$MSB_k(x)$越接近$x$，也就是说，对于越大的$k$，我们得到的数就泄漏了越多的$x$的有效位。

然后定义Hidden Number Problem（HNP）：确定$p$和$k$，已知$MSB_k(\alpha g^x\ mod \ p)$求$\alpha$。

论文中提到如果可以请求到正确的$MSB_k(\alpha\cdot t\ mod\ p)$，这里$t=g^x$，那么恢复$\alpha$是一件简单的事情。

Main Results

这一节主要讲的是多大的k可以来解决HNP问题。直接上定理。

Theorem 1

令$\alpha$是定义在有限域$GF(p)$的一个数， $k=\lceil\sqrt{n}\rceil+\lceil\log n\rceil$，$\mathcal{O}(t)=\operatorname{MSB}_{k}(\alpha t \bmod p)$。存在一种算法A可以在多项式时间内解决HNP。

$$ \underset{t_{1}, \ldots, t_{d}}{\operatorname{Pr}}\left[A\left(t_{1}, \ldots, t_{d}, \mathcal{O}\left(t_{1}\right), \ldots, \mathcal{O}\left(t_{d}\right)\right)=\alpha\right] \geq \frac{1}{2} $$

其中$d=2\sqrt{n}$，$t_1,\cdots,t_d$是均匀的，独立的随机从$\mathbb{Z}_{p}^{*}$中选择。

这里均匀的，独立的随机选择应该是为了保证数据的不相关性。

Theorem 2

设$k=\lceil\sqrt{n}\rceil+\lceil\log{n}\rceil$ ，给出一个有效的算法从$g^a, g^b$计算$MSB_k(g^{ab})$，存在一个算法可以在多项式时间内计算$g^{ab}$。也就是已知$MSB_k(g^{ab})$求$g^{ab}$。

Proof

首先回顾一下格这个东西。格可以这个样子定义

$$ L=\left{y: y=\sum_{i=1}^{d} t_{i} b_{i}, t_{i} \in \mathbb{Z}\right} $$

$d$是格$L$的阶，${b_i}={b_1,\cdots,c_d}$是$L$的一组线性无关向量，被称为$L$的基，$\sum^{d}_{i=1}t_ib_i$是这个基的一个线性组合。利用LLL格基规约算法可以从一个给定的格$L$和一个点$v$（不必要是格上的点），找到一个最靠近$v$的格点。

接下来证明Theorem 1。

$d=2\lceil\sqrt{n}\rceil$，$k=k=\lceil\sqrt{n}\rceil+\lceil\log n\rceil$，然后假设我们已经获得了$d$个正确的MSB oracle $a_1, \cdots, a_d$，对应的输入为$t_1,\cdots,t_d$。根据MSB的定义，我们有对于所有的a和t

$$ |\alpha t_i\ mod\ p-a_i|\leq p/2^k $$

构造格$L$

$$ \left(\begin{array}{cccccc} p & 0 & 0 & \ldots & 0 & 0 \\ 0 & p & 0 & \ldots & 0 & 0 \\ & \vdots & & & & \vdots \\ 0 & 0 & 0 & \ldots & p & 0 \\ t_{1} & t_{2} & t_{3} & \ldots & t_{d} & 1 / p \end{array}\right) $$

注意对于最后一行乘$\alpha$后模$p$可以得到这样一个向量

$$ v_{\alpha}=(r_1,\cdots,r_d,\alpha/p) $$

说明$v_{\alpha}$确实存在与格$L$中，其中 $r_i=\alpha t_i\ mod\ p$，于是

$$ |r_i - a_i|<p/2^k\quad i\in[1,d] $$

定义向量$u=(a_1,\cdots,a_d,0)$，那么向量$u$和$v_{\alpha}$的距离，即$||u-v_{\alpha}||$

$$ ||u-v_{\alpha}||<\sqrt{\sum^{d-1}_{i=1}(a_i-r_i)^2+(\frac{\alpha}{p})^2} \le \sqrt{d+1}p/2^k $$

那么我们就可以用LLL和Babai算法来寻找到$v_{\alpha}$，对$v_{\alpha}$的最后一个元素乘$p$就求出了$\alpha$。

Example & Demo

demo from kel.

from random import randint
from sage.all import *
from Crypto.Util.number import getPrime
# Some parameters of the game, chosen for simplicity.

# p - A prime number for our field.
p = getPrime(128)

# n - The number of bits in `p`.
n = ceil(log(p, 2))

# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))
print(f"The number of significant bits = {k}")
d = 2*ceil(sqrt(n))

def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2**(k+1):
            break
    return z

def create_oracle(alpha):
    """Returns a randomized MSB oracle using the specified alpha value.
    """
    alpha = alpha
    def oracle():
        random_t = randint(1, p-1)
        return random_t, msb((alpha * random_t) % p)
    return oracle

def build_basis(oracle_inputs):
    """Returns a basis using the HNP game parameters and inputs to our oracle
    """
    basis_vectors = []
    for i in range(d):
        p_vector = [0] * (d+1)
        p_vector[i] = p
        basis_vectors.append(p_vector)
    basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])
    return Matrix(QQ, basis_vectors)

def approximate_closest_vector(basis, v):
    """Returns an approximate CVP solution using Babai's nearest plane algorithm.
    """
    BL = basis.LLL()
    G, _ = BL.gram_schmidt()
    _, n = BL.dimensions()
    small = vector(ZZ, v)
    for i in reversed(range(n)):
        c = QQ(small * G[i]) / QQ(G[i] * G[i])
        c = c.round()
        small -= BL[i] * c
    return (v - small).coefficients()

# Hidden alpha scalar
alpha = randint(1, p-1)

# Create a MSB oracle using the secret alpha scalar
oracle = create_oracle(alpha)

# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = zip(*[ oracle() for _ in range(d) ])

# Build a basis using our oracle inputs
lattice = build_basis(inputs)
print("Solving CVP using lattice with basis:\n%s\n" % str(lattice))

# The non-lattice vector based on the oracle's answers
u = vector(ZZ, list(answers) + [0])
print("Vector of MSB oracle answers:\n%s\n" % str(u))

# Solve an approximate CVP to find a vector v which is likely to reveal alpha.
v = approximate_closest_vector(lattice, u)
print("Closest lattice vector:\n%s\n" % str(v))

# Confirm the recovered value of alpha matches the expected value of alpha.
recovered_alpha = (v[-1] * p) % p
assert recovered_alpha == alpha
print("Recovered alpha! Alpha is %d" % recovered_alpha)

Refer to

The Hidden Number Problem
Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan