补充说明：侧信道攻击之电磁侧信道攻击出题指南

4.5lwe

这道题参考了2024Crypto的顶会论文，全称“Crypto Conference”，是密码学领域最重要的国际会议之一。Crypto Conference由国际密码学研究协会（IACR）组织，是每年举办的三大顶级密码学会议之一，另外两个分别是欧洲密码学会议（Eurocrypt）和亚洲密码学会议（Asiacrypt）Crypto Conference自1981年开始举办，至今已有40多年的历史。会议通常在每年的八月下旬至九月初于美国加州圣巴巴拉的加州大学圣巴巴拉分校（UCSB）举行。

@inproceedings{crypto-2024-34347,
  title={Adaptively Sound Zero Knowledge SNARKs for UP},
  publisher={Springer-Verlag},
  author={Surya Mathialagan and Spencer Peters and Vinod Vaikuntanathan},
  year=2024
}

因文章篇幅原因，在此仅对题目所涉及的内容进行简单介绍，论文详情我附在了引用里，感兴趣的可以下载论文进行学习。

这篇论文的主要内容是研究UP类问题的自适应安全零知识SNARK（succinct non-interactive arguments of knowledge）。UP（Unambiguous Polynomial time）是NP问题的一个子类，其中每个实例最多只有一个见证。

1. 从次指数级的学习错误（subexponential Learning With Errors，LWE）和一种新的LWE变种（evasive LWE）构建出一种可重复使用且自适应安全的零知识指定验证者SNARG（dvSNARG），其证明长度为比特，声音错误率为。

2. 提出了一种通用的转换方法，可以将任何“Sahai-Waters-like”的zk-SNARG提升为在指定验证者设置下的自适应安全zk-SNARG。

3. 提出了一种通用转换方法，将任何自适应安全的zk-SNARG for UP提升为自适应安全的zk-SNARK for UP，同时保持零知识属性。

学习错误（LWE）假设

LWE假设：给定参数 和，次指数级LWE假设

其中，

Puncturable PRF（可戳伪随机函数）

• 定义：一个可戳伪随机函数族在密钥空间 、域 、输出空间 和多项式 上是一个包含以下算法的PPT算法组：
• ：生成密钥 。
• ：输入密钥 和集合 ，输出新的密钥 。
• ：输入密钥 和 ，输出值 。

混淆（Obfuscation）

• σ-matrix PRFs：一种使用矩阵分支程序计算的带有噪声的伪随机函数族，满足特定的平均情况下的混淆属性。具体的混淆方案基于evasive LWE构建，具有以下形式：
• 矩阵编码（GGH编码）：使用随机矩阵 和噪声矩阵 进行编码。
• 安全性证明依赖于LWE和evasive LWE假设，使用逐步混淆的方法来逐层移除矩阵，同时保持伪随机性。

证明构造

• SNARK证明：基于自适应安全的SNARG，通过引入全同态加密（FHE）和公钥加密（PKE）来构建SNARK。
• 生成过程包括生成全同态加密密钥对和公钥加密密钥对，并使用这些密钥对将关系转换为新的UP关系。
• 证明者使用全同态加密和公钥加密生成证明，而验证者使用原始SNARG系统验证。

这篇论文通过详细的理论推导和构造，展示了如何在次指数级可证伪假设下构建自适应安全的零知识SNARK，从而推进了SNARK在密码学中的应用。

4.5.2.出题思路

题目有3个文件，包含flag信息的数据文件，题目有3个文件，包含flag信息的数据文件，格基矩阵文件，显示嵌入flag信息的格基信息图。

这道题目通过处理和分析嵌入有特定标志信息的LWE样本信号数据，考察对信号处理、统计特征分析以及LWE理论的理解和应用。

1. 加载和显示信号数据

提供包含嵌入flag信息的LWE信号数据文件和对应的格基矩阵文件。

要求使用数据可视化工具对信号数据和格基矩阵进行可视化展示，以便直观地观察和理解数据特征。

2. 信号数据降噪

提供一个常见的信号处理技术（如Savitzky-Golay滤波器）。

要求对原始信号数据进行降噪处理，并展示处理后的信号数据，以观察降噪效果。

3. 分析信号数据的统计特征

通过分析信号数据的统计特征，推导出LWE问题的相关参数（如安全参数、模数、噪声参数）计算信号数据的长度、最大值、标准差等统计特征。

根据这些统计特征估计LWE问题中的相关参数，例如，利用信号数据的最大值估计模数，利用标准差估计噪声参数。

4. 解码嵌入的flag信息

通过LWE理论对信号数据进行解码，提取嵌入的信息（flag），主要对LWE解码过程的理解和实现能力。

4.5.3.解题思路

学习错误（LWE）假设

学习错误（LWE）假设是基于格的加密算法的基础，其基本形式可以表示为：

其中：

• 是一个随机生成的矩阵。
• 是秘密向量。
• 是误差向量，其元素通常从某个离散高斯分布中采样。
• 是一个模数。

信号数据处理和参数估计

• 模数的估计：

其中，max_value是信号数据的最大绝对值。

• 噪声参数的估计：

其中，std(signals) 是信号数据的标准差。

• 信号数据降噪 使用Savitzky-Golay滤波器对信号数据进行降噪处理，公式如下：Savitzky-Golay滤波器：

其中，窗口大小为101，多项式阶数为3。

统计特征分析和参数估计

代码中分析信号数据的统计特征，并估计LWE参数：

• 信号长度 signal_length 和最大值 max_value 的计算：

• 模数的估计：

• 噪声参数的估计：

从LWE样本中提取flag信息

代码通过解码LWE样本中的flag信息：

• 将信号数据转换为二进制字符串：

• 查找二进制字符串中的特征模式：

• 提取flag：

import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import savgol_filter
def extract_flag_from_lwe_sample(signals, q, n):
    binary_str = ''.join([str(val & 1) for val in signals])
    patterns = ["01100110011011000110000101100111"]
    for pattern in patterns:
        flag_start_index = binary_str.find(pattern)
        if flag_start_index != -1:
            break
    else:
        return "Flag not found"
    flag_length_bits = len(''.join(format(ord(char), '08b') for char in "flag{To_be_both_a_speaker_of_words_and_a_doer_of_deeds_xuruihan_is_the_author}"))
    flag_binary_str = binary_str[flag_start_index:flag_start_index + flag_length_bits]
    flag_chars = [chr(int(flag_binary_str[i:i+8], 2)) for i in range(0, flag_length_bits, 8)]
    return ''.join(flag_chars)
b_with_flag = np.load('lwe_with_flag.npy')
A = np.load('lwe_with_flag_A.npy')
extracted_flag = extract_flag_from_lwe_sample(b_with_flag, q, n)
print(f"Extracted Flag: {extracted_flag}")
plt.figure(figsize=(10, 6))
plt.plot(b_with_flag)
plt.title('LWE Sample with Embedded Flag')
plt.xlabel('Sample Index')
plt.ylabel('Value')
plt.show()
plt.figure(figsize=(10, 6))
plt.imshow(A, cmap='viridis', aspect='auto') 
plt.title('Lattice Basis with Embedded Flag Information')
plt.xlabel('Column Index')
plt.ylabel('Row Index')
plt.colorbar(label='Value')
plt.show()
denoised_signals = savgol_filter(b_with_flag, 101, 3)  # window size 101, polynomial order 3
plt.figure(figsize=(10, 6))
plt.plot(denoised_signals)
plt.title('Denoised LWE Sample with Embedded Flag')
plt.xlabel('Sample Index')
plt.ylabel('Value')
plt.show()
def estimate_lwe_parameters(signals, lattice_basis):
    signal_length = len(signals)
    n = 1 if signal_length < 1024 else 64
    max_value = np.max(np.abs(signals))
    q = int(2**np.ceil(np.log2(max_value))) 
    sigma = np.std(signals) / 3  
    return n, q, sigma
n, q, sigma = estimate_lwe_parameters(denoised_signals, A)
print(f"Estimated LWE Parameters: n={n}, q={q}, sigma={sigma}")

Estimated LWE Parameters: n=64, q=1024, sigma=98.47414168241636
Extracted Flag: flag{To_be_both_a_speaker_of_words_and_a_doer_of_deeds_xuruihan_is_the_author}

4.5.3.代码分析

篇幅限制，只对关键代码进行分析，加载数据文件和频谱图代码已在上述相关环节进行过解释，不再进行详细说明。

import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import savgol_filter

导入必要的库：numpy用于处理数组，matplotlib.pyplot用于绘图，scipy.signal.savgol_filter用于信号降噪。

def extract_flag_from_lwe_sample(signals, q, n):
    binary_str = ''.join([str(val & 1) for val in signals])
    patterns = ["01100110011011000110000101100111"]
    for pattern in patterns:
        flag_start_index = binary_str.find(pattern)
        if flag_start_index != -1:
            break
    else:
        return "Flag not found", -1

    flag_length_bits = len(''.join(format(ord(char), '08b') for char in "flag{To_be_both_a_speaker_of_words_and_a_doer_of_deeds_xuruihan_is_the_author}"))
    flag_binary_str = binary_str[flag_start_index:flag_start_index + flag_length_bits]
    flag_chars = [chr(int(flag_binary_str[i:i+8], 2)) for i in range(0, flag_length_bits, 8)]
    
    return ''.join(flag_chars), flag_start_index, flag_length_bits

定义了一个函数extract_flag_from_lwe_sample，用于从信号数据中提取嵌入的flag信息。首先，将信号数据转换为二进制字符串，然后查找特定的二进制模式（'flag'的二进制表示）。找到模式后，提取对应长度的二进制字符串并转换为字符，返回提取的flag信息、起始索引和长度。

b_with_flag = np.load('lwe_with_flag.npy')
A = np.load('lwe_with_flag_A.npy')

加载LWE样本信号数据b_with_flag和对应的格基矩阵A。

def estimate_lwe_parameters(signals, lattice_basis):
    signal_length = len(signals)
    n = 1 if signal_length < 1024 else 64
    max_value = np.max(np.abs(signals))
    q = int(2**np.ceil(np.log2(max_value)))
    sigma = np.std(signals) / 3
    return n, q, sigma

定义了一个函数estimate_lwe_parameters，用于估计LWE参数。计算信号数据的长度、最大值、模数q和噪声参数sigma，并根据信号长度估计安全参数n。

n, q, sigma = estimate_lwe_parameters(b_with_flag, A)
print(f"Estimated LWE Parameters: n={n}, q={q}, sigma={sigma}")

调用estimate_lwe_parameters函数估计LWE参数，并打印估计的参数值。

extracted_flag, flag_start_index, flag_length_bits = extract_flag_from_lwe_sample(b_with_flag, q, n)
print(f"Extracted Flag: {extracted_flag}")

调用extract_flag_from_lwe_sample函数从信号数据中提取flag信息，并打印提取的flag。

denoised_signals = savgol_filter(b_with_flag, 101, 3)

使用Savitzky-Golay滤波器对信号进行降噪处理。

plt.figure(figsize=(10, 6))
plt.plot(denoised_signals)
if flag_start_index != -1:
    plt.axvline(x=flag_start_index, color='r', linestyle='--')
    plt.axvline(x=flag_start_index + flag_length_bits, color='r', linestyle='--')
    plt.title('Denoised LWE Sample with Embedded Flag (Flag Region Highlighted)')
else:
    plt.title('Denoised LWE Sample with Embedded Flag')
plt.xlabel('Sample Index')
plt.ylabel('Value')
plt.show()

显示降噪后的频谱图，并在图中用红色虚线标记包含flag信息的区域。如果未找到flag信息，则只显示降噪后的频谱图标题。

1.Timing Attacks on Implementations of Die-Hellman, RSA, DSS, and Other Systems https://paulkocher.com/doc/TimingAttacks.pdf

2.The ChaCha family of stream ciphers https://cr.yp.to/chacha.html

3.Adaptively Sound Zero-Knowledge SNARKs for UP https://eprint.iacr.org/2024/227.pdf