#### ink

• Technical / 技术
• Distributed System / 分布式系统
• Blockchain / 区块链
• Cryptography / 密码学
• Programming Language / 程序设计语言
• Misc / 随笔
• Notes / 笔记
• Programming / 编程
• Cryptography / 密码学
• Blockchain / 区块链

# 搞 MPC 和 ZKP 的基础密码学面试

## 数论

### 群 (group)

• 封闭性：如果 $a,b \in G$，则 $ab \in G$
• 结合律： 如果 $a,b,c \in G$，则 $(ab)c =a(bc)$
• 单位元：集合中存在一个元素 $I$，保证 $aI = Ia = a$，对所有的 $a \in G$ 都成立
• 逆元：对每个集合的元素 $a \in G$，存在对应的 $b = a^{-1}$，保证 $ab = ba = I$

### 环 (ring)

• 加法结合律
• 加法交换律
• 加法单位元
• 加法逆元
• 乘法结合律
• (乘法关于加法满足) 分配律, 即：
• a · (b + c) = (a · b) + (a · c)
• (a + b) · c = (a · c) + (b · c)

#### 理想 (ideal)

• 如果 $B$ 是 $A$ 的一个理想，那么对于任何 $a \in A, b \in B$，存在 $ab \in B$（左理想），并且 $ba \in B$（右理想）。
• 注意环中乘法不一定可交换，所以 $ab$ 和 $ba$ 不同。

• 单个 0 元所生成的环 (因为任何一个元与0元的乘都为0元)
• 这个环本身

### 域 (field)

• 加法和乘法的结合律
• 加法和乘法的交换律
• 加法和乘法的分配律
• 加法和乘法的单位元
• 加法和乘法的逆元

#### 有限域 (finite field)

• 如果域上不要求乘法的交换律，就是除法代数。
• 域上存在逆元。（域上支持除法运算。）
• 环不是域。
• 矩阵环不支持乘法的交换律。
• 域中所有非零元素的集合是关于乘法的阿贝尔群。
• 有限域的乘法群是循环群。
• 有限域中所有非零元素的集合的每个有限子群都是循环群。

## 椭圆曲线

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

$y^2 = x^3 + ax + b,\ 4a^3 + 27b^2 \ne 0$

### 基于椭圆曲线的群定义

• 所有椭圆曲线上的点就是这个群里的元素
• 单位元就是 0
• 点 P 的逆元是点 P 相对 x 坐标的对称点
• 加法：在椭圆曲线上，和一条直线相交的 3 个点 P, Q 和 R，三点相加满足 P + Q + R = 0。也就是说 椭圆曲线上两点相加的结果还在这条椭圆曲线上。

• 封闭性：因为椭圆曲线上的点相加还是椭圆曲线上的点
• 结合律： P + (Q + R) = (P + Q) + R = 0
• 单位元：单位元是 0
• 逆元：一个椭圆曲线上的点 P 的逆元，是相对 x 坐标的对称点
• 交换律：P + Q = Q + P

## The Diffie-Hellman Problem

• probabilistic polynomial time Turing machine
• 概率多项式时间图灵机
• DLP vs ECDLP
• ECDLP is still the discrete logarithm problem, since you have a group with an operation (addition on EC) applied to itself n times, and you're trying to find the value $x$ given $B$ and $Y$, where $xB$ = $Y$. This is the same as in a prime field (which is a group with an operation that is multiplication) trying to find $x$ given $g$ and $y$ were $g^x$ = $y$.
• However, elliptical curves aren't fields, which means the methods that are efficient at solving discrete logarithm on fields aren't accelerated.

## Fiat-Shamir transform

• the Fiat-Shamir heuristic
• a technique for taking an interactive proof of knowledge and creating a digital signature based on it.
• This way, some fact (for example, knowledge of a certain secret number) can be publicly proven without revealing underlying information.
• For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.
• yields a non-interactive zero-knowledge argument in the random oracle model
• only secure in the random oracle model.
• 也就是说
• The Fiat-Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into a non-interactive proof of knowledgel (in random oracle model).
• 怎么做
• The Fiat-Shamir transformation takes an interactive public coin argument and replaces the challenges with the output of a cryptographic hash function.

### Public coin protocol

The verifier must show the prover all the random bits it uses in its computation. The result is that the verifier cannot "hide" anything from the prover, because the prover is powerful enough to simulate everything the verifier does if it knows what random bits it used.

## SNARG ## universal (zk)-S[N/T]ARKS

https://miro.com/app/board/o9J_knthJ3w=/

also see:

## Paillier cryptosystem

Paillier 是一种原生支持加法同态的非对称加密体系。能同时支持 语义安全 (semantically secure) 和 加法同态 (additively homomorphic)；RSA 只能取其一。

• probabilistic public-key encryption
• 概率公钥加密系统
• Assumption:
• The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.
• 基于复合剩余类的困难问题
• partial homomorphic encryption scheme
• 加法和数乘同态

## Semantic Security

Any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message $m$ (taken from any distribution of messages), and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length (and not the ciphertext).

• Perfect Secrecy
• the ciphertext reveals no information at all about the plaintext
• Semantic Security
• implies that any information cannot be feasibly extracted

indistinguishability 则是一个 更简单易用的、等价的 notation。

## 应用题

### Sharding & Randomness Beacon

Sharding 协议中决定将节点分配至哪个 shard 时可能使用 Randomness Beacon，为什么 Randomness Beacon 需要满足:

• unbias
• 无法操纵自己加入哪个shard，否则就可以运行多个节点加入同一个shard，然后51。
• unpredictable
• 无法预测分配至哪个shard，否则就可以等到轮到那个shard时再加入，并提前和也加入那个shard的人串谋。

also see:

## 密码学工程安全性

1. 下面这个检查密码是否相等的代码有什么问题？

1. 下面这个 RSA 快速幂取余算法的代码有什么问题？

1. 下面这个解密代码有什么问题？