Five methods for the hidden number problem

'''
This code is used to recover the hidden number problem.
Suppose that the modulus, alpha and the middle bits of beta are given, we need to recover the hidden number.
The software used is the Sagemath.
This code gives five methods: the "continued fraction + lattice" method, the lattice method for finding lambda, the lattice method given in inscrypt21, a new lattice-based method and an improved data-saving method.
'''

import time

# Randomly divide m into n segments, the sum of the even segments is K
def distribution(n, m, K):
    d = vector(ZZ, n)
    known = vector(ZZ, int((n - 1)/2))
    unknown = vector(ZZ, int((n + 1)/2))

    known[0] = randint(1, K - 1)
    known[len(known) - 1] = K
    i = 1
    while i < (n - 1)/2 - 1:
        k = randint(1, K - 1)
        jud = 0
        flag = 0
        for j in range(0, i):
            if k == known[j]:
                flag = 1
                break
            if k < known[j]:
                for ii in range(j, i):
                    known[i + j - ii] = known[i + j - ii - 1]
                known[j] = k
                break
            if k > known[j]:
                jud = jud + 1
        if jud == i:
            known[i] = k
        if flag == 0:
            i = i + 1

    unknown[0] = randint(1, m - K - 1)
    unknown[len(unknown) - 1] = m - K
    i = 1
    while i < (n + 1)/2 - 1:
        k = randint(1, m - K - 1)
        jud = 0
        flag = 0
        for j in range(0, i):
            if k == unknown[j]:
                flag = 1
                break
            if k < unknown[j]:
                for ii in range(j, i):
                    unknown[i + j - ii] = unknown[i + j - ii - 1]
                unknown[j] = k
                break
            if k > unknown[j]:
                jud = jud + 1
        if jud == i:
            unknown[i] = k
        if flag == 0:
            i = i + 1

    d[0] = unknown[0]
    d[1] = known[0]
    for i in range(1, len(unknown)):
        d[2 * i] = unknown[i] - unknown[i - 1]
    for i in range(1, len(known)):
        d[2 * i + 1] = known[i] - known[i - 1]

    return d

# The "continued fraction + lattice" method
def continued_fractions_method(n, q, A, R, d):
    m = ceil(q.log() / 2.log())
    a = 2^(d[0] + d[1])
    b = q / 2^(d[0] + d[1] / 2)
    PQ = convergents(a/q)
    for i in range(0, len(PQ) - 1):
        if PQ[i].denominator() < RDF(b) and RDF(b) <= PQ[i + 1].denominator():
            lamda = PQ[i].denominator()
            break

    L = Matrix(ZZ, n + 2, n + 2)
    x = vector(ZZ, n + 2)
    for i in range(0, n):
        L[i, i] = q * 2^(ceil(d[1] / 2) - 1)
        L[n, i] = ((lamda * A[0, i]) % q) * 2^(ceil(d[1] / 2) - 1)
        L[n + 1, i] = ((lamda * R[0, i] * 2^d[0]) % q) * 2^(ceil(d[1] / 2) - 1)
    L[n, n] = 1
    L[n + 1, n + 1] = 2^(ceil(d[1] / 2) - 1)

    reduced_L = L.BKZ(block_size = 20)

    j = 0
    for i in range(0, n + 2):
        if reduced_L[i, n + 1].abs() == L[n + 1, n + 1]:
            x[j] = reduced_L[i, n].abs()
            j = j + 1

    return x

# The lattice method for finding lambda
def balanced_lattice_method(n, q, A, R, d):
    l = len(d)
    m = 256
    L = Matrix(ZZ, (l + 1) / 2, (l + 1) / 2)
    for i in range(0, (l - 1) / 2):
        L[i, i] = q * 2^(d[2 * (i + 1)])
        L[(l - 1) / 2, i] = 1
        for j in range(0, 2 * (i + 1) + 1):
            L[(l - 1) / 2, i] = L[(l - 1) / 2, i] * 2^(d[j])
    L[(l - 1) / 2, (l - 1) / 2] = 2^d[0]

    reduced_L = L.BKZ(block_size = 20)

    sum_unknown = 0
    for i in range(0, (l + 1) / 2):
        sum_unknown = sum_unknown + reduced_L[0, i].abs()
    len_unknown = ceil(sum_unknown.log()/2.log())
    lamda = reduced_L[0, (l - 1) / 2].abs() / 2^d[0]

    LL = Matrix(ZZ, n + 2, n + 2)
    x = vector(ZZ, n + 2)
    for i in range(0, n):
        LL[i, i] = q * 2^(m - len_unknown)
        LL[n, i] = ((lamda * A[0, i]) % q) * 2^(m - len_unknown)
        LL[n + 1, i] = 0
        for j in range(0, (l - 1) / 2):
            known = 0
            for k in range(0, 2 * j + 1):
                known = known + d[k]
            LL[n + 1, i] = LL[n + 1, i] + 2^known * R[j, i]
        LL[n + 1, i] = ((lamda * LL[n + 1, i] + 2^(len_unknown - 1)) % q) * 2^(m - len_unknown)
    LL[n, n] = 1
    LL[n + 1, n] = 2^(len_unknown - 1) * 2^(m - len_unknown)
    LL[n + 1, n + 1] = 2^(len_unknown - 1) * 2^(m - len_unknown)

    reduced_LL = LL.BKZ(block_size = 20)

    j = 0
    for i in range(0, n + 2):
        if reduced_LL[i, n + 1] == -LL[n + 1, n + 1]:
            x[j] = LL[n + 1, n] + reduced_LL[i, n]
            j = j + 1
        if reduced_LL[i, n + 1] == LL[n + 1, n + 1]:
            x[j] = LL[n + 1, n] - reduced_LL[i, n]
            j = j + 1

    return x

# The lattice method given in inscrypt21
def lattice21_method(n, q, A, R, d):
    L = Matrix(ZZ, 2 * n + 1, 2 * n + 1)
    a_inv = (A[0, 0]^(-1)) % q
    for i in range(0, n - 1):
        L[i, i] = q
        L[n - 1, i] = (A[0, i + 1] * a_inv) % q
        L[n, i] = (A[0, i + 1] * a_inv * 2^(d[0] + d[1])) % q
        L[n + 1 + i, i] = 2^(d[0] + d[1])
        L[2 * n, i] = ((R[0, i + 1] * 2^d[0] - A[0, i + 1] * a_inv * 2^d[0] * R[0, 0]) % q) + 2^(d[0] - 1)

    L[n - 1, n - 1] = 1
    L[2 * n, n - 1] = 2^(d[0] - 1)
    L[2 * n, n] = 2^(d[0] - 1)
    L[2 * n, 2 * n] = 2^(d[0] - 1)
    for i in range(n + 1, 2 * n):
        L[2 * n, i] = -2^(d[0] - 1)
    if d[0] >= d[2]:
        for i in range(n, 2 * n):
            L[i, i] = 2^(d[0] - d[2])
    else:
        for i in range(0, 2 * n + 1):
            for j in range(0, 2 * n + 1):
                L[i, j] = L[i, j] * 2^(d[2] - d[0])
        for i in range(n, 2 * n):
            L[i, i] = 1

    reduced_L = L.BKZ(block_size = 20)
    x = vector(ZZ, 2 * n + 1)
    j = 0
    for i in range(0, 2 * n + 1):
        if reduced_L[i, 2 * n] == -L[2 * n, 2 * n]:
            b1 = (L[2 * n, n - 1] + reduced_L[i, n - 1]) / L[n - 1, n - 1]
            b3 = (L[2 * n, n] + reduced_L[i, n]) / L[n, n]
            b = b1 + R[0, 0] * 2^d[0] + b3 * 2^(d[0] + d[1])
            x[j] = (a_inv * b) % q
            j = j + 1
        if reduced_L[i, 2 * n] == L[2 * n, 2 * n]:
            b1 = (L[2 * n, n - 1] - reduced_L[i, n - 1]) / L[n - 1, n - 1]
            b3 = (L[2 * n, n] - reduced_L[i, n]) / L[n, n]
            b = b1 + R[0, 0] * 2^d[0] + b3 * 2^(d[0] + d[1])
            x[j] = (a_inv * b) % q
            j = j + 1

    return x

# Our new lattice-based method
def new_lattice_method(n, q, A, R, d):
    m = 256
    L = Matrix(ZZ, 2 * n + 2, 2 * n + 2)
    for i in range(0, n):
        L[i, i] = q * 2^(m - d[0])
        L[n, i] = A[0, i] * 2^(m - d[0])
        L[n + 1, i] = R[0, i] * 2^m + 2^(m - 1)
    L[n, n] = 1
    L[n + 1, n] = 2^(m - 1)
    L[n + 1, n + 1] = 2^(m - 1)
    for i in range(n + 2, 2 * n + 2):
        L[n + 1, i] = -2^(m - 1)
    for i in range(n + 2, 2 * n + 2):
        L[i, i - n - 2] = 2^(m + d[1])
        L[i, i] = 2^(m - d[2])

    reduced_L = L.BKZ(block_size = 20)

    x = vector(ZZ, 2 * n + 2)
    j = 0
    for i in range(0, 2 * n + 2):
        if reduced_L[i, n + 1] == -L[n + 1, n + 1]:
            x[j] = L[n + 1, n] + reduced_L[i, n]
            j = j + 1
        if reduced_L[i, n + 1] == L[n + 1, n + 1]:
            x[j] = L[n + 1, n] - reduced_L[i, n]
            j = j + 1

    return x

# An improved data-saving method
def improved_lattice_method(n, q, A, R, d, gamma, X):
    m = 256
    L = Matrix(ZZ, 2 * n + 2, 2 * n + 2)
    for i in range(0, n):
        L[i, i] = q * 2^(m - d[0] - gamma)
        L[n, i] = A[0, i] * 2^(m - d[0] - gamma)
        L[n + 1, i] = R[0, i] * 2^(m - gamma) + 2^(m - gamma - 1)
    L[n, n] = 1
    L[n + 1, n] = 2^(m - gamma) * (X >> (m - gamma)) + 2^(m - gamma - 1)
    L[n + 1, n + 1] = 2^(m - gamma - 1)
    for i in range(n + 2, 2 * n + 2):
        L[n + 1, i] = -2^(m - gamma - 1)
    for i in range(n + 2, 2 * n + 2):
        L[i, i - n - 2] = 2^(m + d[1] - gamma)
        L[i, i] = 2^(m - d[2] - gamma)

    reduced_L = L.BKZ(block_size = 20)

    x = vector(ZZ, 2 * n + 2)
    j = 0
    for i in range(0, 2 * n + 2):
        if reduced_L[i, n + 1] == -L[n + 1, n + 1]:
            x[j] = L[n + 1, n] + reduced_L[i, n]
            j = j + 1
        if reduced_L[i, n + 1] == L[n + 1, n + 1]:
            x[j] = L[n + 1, n] - reduced_L[i, n]
            j = j + 1

    return x

# Judge whether x is the hidden number
def judgement_x(X, x):
    jud = 0
    for i in range(0, len(x)):
        if X == x[i]:
            jud = 1
            break

    return jud


m = 256
q = 115792089237316195423570985008687907853269984665640564039457584007913129639747
K = 8    # The number of unknown bits
N = 500
gamma = 6
Tn = 40
start = time.time()
for n_i in range(0, Tn):
    n = Tn - n_i
    print(n)
    success_x = vector(ZZ, 5)
    for count in range(0, 10):
        A = random_matrix(ZZ, 1, N, x = 0, y = q)
        X = randint(0, q - 1)
        R = Matrix(ZZ, 1, N)
        d = distribution(3, m, K)
        for i in range(0, N):
            R[0, i] = (((A[0, i] * X) % q) >> d[0]) % (2^d[1])

        x1 = continued_fractions_method(n, q, A, R, d)
        jx1 = judgement_x(X, x1)
        success_x[0] = success_x[0] + jx1

        x2 = balanced_lattice_method(n, q, A, R, d)
        jx2 = judgement_x(X, x2)
        success_x[1] = success_x[1] + jx2

        x3 = lattice21_method(n, q, A, R, d)
        jx3 = judgement_x(X, x3)
        success_x[2] = success_x[2] + jx3

        x4 = new_lattice_method(n, q, A, R, d)
        jx4 = judgement_x(X, x4)
        success_x[3] = success_x[3] + jx4

        x5 = improved_lattice_method(n, q, A, R, d, gamma, X)
        jx5 = judgement_x(X, x5)
        success_x[4] = success_x[4] + jx5
    print(success_x,'\n')
end = time.time()
print('time:',end-start,'s')