notes

Crytography - Digital Signature and Secure Multi-Party Computation

Digital Signature

The authenticity of a message is a more critical issue in a public-key encryption setting than in a private-key setting, since in public-key encryption, anyone can encrypt a message and send it to the receiver. Analogous to Message Authentication Codes in symmetric cryptography, we use digital signatures for message authentication in asymmetric cryptography. The definition is as follows:

A digital signature scheme is a triplet $(\text{Gen}, \text{Sign}, \text{Vrfy})$: Given input $n$, $\text{Gen}(n)$ outputs a public key $k_p$ and a private key $k_s$ (not for encryption but for authentication); the signing algorithm $\text{Sign}$ takes a message $m$ and a private key $k_s$, generating a signature $\sigma = \text{Sign}_{k_s}(m)$; the verification algorithm $\text{Vrfy}$ takes a message $m$, a signature $\sigma$, and a public key $k_p$ as input, and outputs 1 if the verification succeeds, or 0 if it fails.

From the above definition, it is clear that only the holder of the private key can generate a signature, while anyone with the public key can verify it. In other words, a digital signature scheme allows only the private key holder to produce a signature, but anyone in the world can verify its legitimacy.

Security Definition

Similarly to private-key cryptography, we can define the security of a digital signature scheme:

Consider the following experiment $SigForge_{\mathcal{A}, \Pi}(n)$: Given input $n$, $\text{Gen}(n)$ generates $(k_p, k_s)$; adversary $\mathcal{A}$ receives $k_p$ and queries the $\text{Sign}$-oracle polynomial times, obtaining pairs $(m, \sigma)$; the adversary eventually outputs a message $m_0$ and a corresponding signature $\sigma_0$ that were not queried before. If $\text{Vrfy}_{p_k}(m_0, \sigma_0) = 1$, the we call the adversary successful. If the probability of any adversary's success is bounded by $\Pr[SigForge_{\mathcal{A}, \Pi}(n) = 1] \leq \text{negl}$, the scheme is considered secure.

The Schnorr Signature Scheme

We now construct a secure digital signature scheme based on the Diffie-Hellman assumption, called the Schnorr Signature Scheme.

Gen: Given input $n$, $\text{Gen}(n)$ outputs parameters $G, q, g$ that are secure under the Diffie-Hellman assumption; randomly select $x \in \Z_q$, set $h = g^x$, and output the public key $(G, q, g, h)$, with the private key being $x$. $\text{Gen}$ also outputs a hash function $H: \{0,1\}^\ast \to \Z_q$, which is assumed to be collision-resistant.

Sign: Given the private key $x$ and message $m$, uniformly at random select $y \in \Z_q$, set $r := H(g^y \| m)$, compute $s = (rx + y) \mod q$, and outputs the signature $\sigma = (r, s)$.

Vrfy: Given the message $m$ and signature $(r, s)$, compute $z = g^s \cdot h^{-r}$, check if $H(z \| m) = r$, and output 1 if true, otherwise 0.

We verify the correctness of this scheme. For the signature generated by Sign, we have $z = g^{rx + y} \cdot g^{-xr} = g^y$, thus $H(z \| m) = H(g^y \| m) = r$, which holds.

Next, we verify the security of this scheme. Proof Sketch: If an adversary can forge a message-signature pair $(m^*, (r^*, s^*))$ with a probability greater than $\text{negl}$, then we can assume $r^* = H(g^y \| m)$ (since we assumed the hash function is collision-resistant, the probability that $r^* \neq H(g^y \| m)$ is negligible). Based on $s^* = r^* x + y \mod q$, we can derive $x = (s^* - y) (r^*)^{-1} \mod q$, thus obtaining a relationship between $x$ and $y$. This can lead to a break of the Diffie-Hellman assumption. A rigorous proof can be found in Introduction to Modern Cryptography 13.5, ' The underlying intuition for the Schnorr signature scheme is best explained by taking a slight detour to discuss (public-key) identification schemes. We then describe the Fiat–Shamir transform that can be used to convert identification schemes to signature schemes in the random-oracle model. Finally,we present the Schnorr identification scheme—and corresponding signature scheme—based on the discrete-logarithm problem '.

A Summary For the Public Key Setting

We have constructed the Diffie-Hellman assumption based on the discrete logarithm problem, which allows us to achieve key exchange, general public key encryption, and digital signature algorithms. In fact, in public-key encryption, besides the Diffie-Hellman assumption based on the discrete logarithm, there is also the RSA assumption based on integer factorization, which also enables us to build public key encryption and digital signature algorithms. Due to the lack of time, in this course we won't discuss the RSA-based algorithms.

It is worth to mention that both the discrete logarithm assumption and the integer factorization assumption are insecure against quantum computers. In other words, if quantum computers are eventually realized, schemes based on these assumptions will be broken (since quantum computers can no longer be considered as PPT adversaries). Therefore, cryptographers are also looking for new assumptions (e.g., Learning With Errors) to construct cryptographic schemes that are secure against quantum computers, known as Post-Quantum algorithms.

Secure Computation

So far, we have discussed algorithms ensuring the security of communication and message authenticity in both private-key and public-key contexts. Next, we will discuss algorithms ensuring the security of computations.

Secure 2-Party Computation

As a motivating example, consider Yao's Millionaire's Problem, proposed by Qizhi Yao in 1986. Two millionaires, $A$ and $B$, have \x$and$$y$ in assets, respectively. They want to compare who has more assets without revealing the exact amounts.

This problem can be understood as a problem of Secure Computation. The parties want to compute the function $f(x, y) = \mathbb{1}[x > y]$ while preserving the privacy of $x$ and $y$. Intuitively, a secure algorithm for the Millionaire's Problem should ensure that both parties can correctly compute $f(x, y)$ without revealing any information other than $f(x, y)$ (which is only 1 bit information). For example, both parties revealing their assets and then comparing is an absolutely terrible algorithm since it exposes all the information.

Another similar problem is Private Set Intersection(PSI), where each party holds a private set $X$ and $Y$, respectively, and they want to securely share the intersection $S = X \cap Y$ without revealing any information outside the intersection. This is a problem of securely computing $f(X, Y) = X \cap Y$.

Generally, we can formalize these problems into the "Secure 2-Party Computation" problem: Two parties $A$ and $B$ each hold binary strings $x$ and $y$, and for a public function $f$, they want to interact and eventually output $f(x, y)$ on their devices without revealing any additional information. (Note that in the definition, we consider $f$ to be public. In fact, $f$ can also be private, e.g., provided by one of the computing parties. To achieve this, simply define $f(x, y)$ as $F(f, x, y)$ on a universal Turing machine $F$, so the party providing $f$ inputs this parameter to the universal Turing machine, thus privatizing $f$.)

Secure Multi-Party Computation

The above problem can be extended to the multi-party setting. Suppose $n$ parties $A_1, \cdots, A_n$ each hold their own information $x_i$, and for a public function $f$, they want to compute $f(x_1, \cdots, x_n)$ without revealing any additional information.

There are two ways to define this problem. One way is that after multiple rounds of interaction, each party outputs $z = f(x_1, \cdots, x_n)$; the other way is that each party outputs a different result $z_i = f_i(x_1, \cdots, x_n)$. Clearly, the latter definition includes the former, but in fact, we can implement the latter using the former: Assume each user $A_i$ holds information $x_i$ and a random string $r_i$. Define $f((x_1, r_1), \cdots, (x_n, r_n)) = (f_1(x_1, \cdots, x_n) \oplus r_1, \cdots, f_n(x_1, \cdots, x_n) \oplus r_n)$. If each user outputs $z = f((x_1, r_1), \cdots, (x_n, r_n))$, then $A_i$ can only recover $f_i(x_1, \cdots, x_n)$ using their random string $r_i$, without being able to recover any other information (with a probability greater than negligible), which is equivalent to each user outputting a different result $z_i$.

In the next class, we will present a specific secure multi-party computation protocol.

About Adversaries

An important question is, what capabilities should we assume the adversary has in secure multi-party computation? In traditional encryption and authentication contexts, we assume the communicating parties are honest, and the adversary tries to eavesdrop or tamper with their communication. However, in secure computation, the other participants in the computation might not be honest and may try to steal our information during the interaction and computation process. Therefore, the strongest assumption about the adversary is that they collude with all other participants except us. Based on this assumption, we can provide the strongest security for multi-party computation. But such schemes are usually inefficient. Therefore, sometimes we weaken the assumption, such as "there are no more than $t$ adversaries among the $n$ participants," etc.