单向函数 — Lalande.

One-Way Function.

One-Way Functions are a critical cryptographic primitive, that is both necessary and sufficient for private-key encryption and MACs. Informally speaking, a function $f$ is one-way if it is easy to compute but hard to invert.

We formally define "hard to invert" with the inverting experiment $\mathtt{Invert}_{\mathscr{A}, f}(n)$ .

The Inverting Experiment

Challenger $\mathscr{C}$ choose uniform $x\in\{0,1\}^n$ , and compute $y:=f(x)$ .
Adversary $\mathscr{A}$ is given $1^n$ and $y$ as inputs. $\mathscr{A}$ outputs $x'$ .
$\mathscr{A}$ succeeds and the experiment evaluates to $1$ if and only if $f(x')=y$ .

Note that the preimage $x'$ does NOT neccessarily have to equal $x$ , as long as $f(x')=y$ .

Definition. A function $f:\{0,1\}^{*}\to \{0,1\}^{*}$ is one-way if the following two conditions hold:

(Easy to compute): There is a polynomial-time algorithm that on input $x$ outputs $f(x)$ .
(Hard to invert): For all PPT algorithm $\mathscr{A}$ there is a negligible function $\varepsilon(n)$ such that: $\Pr[\mathtt{Invert}_{\mathscr{A}. f}(n)=1]\leq \varepsilon(n)$ .

One-Way Functions Based on Assumptions

We could construct one-way functions based on the above four assumptions (factoring assumption, RSA assumption, discrete logarithm assumption, Diffie-Hellman assumption).

We illustrate this by using factoring assumption to construct a one-way function.

Given $1^n$ and GenModulus, define the (deterministic) function $f_{Gen}$ as follows:

Input: A random tage: string $x$ of length $n$
Output: Integer $N$ .
Compute $(N,p,q):=GenModulus(1^n;x)$ and return $N$ .

Theorem. If the Factoring problem is hard relative to GenModulus, then $f_{Gen}$ is one-way.

Hard-Core Predicates

For a one-way function $f$ , it does not exist any PPT adversary that could efficiently invert it. However, the partial information of the preimage may be easily revealed.

Consider the function $f:\{0,1\}^{2n}\to \{0,1\}^{2n}$ and one-way function $g:\{0,1\}^n\to \{0,1\}^n$ . We could define $f(x,y)=g(x)||y$ . Since $g$ is one-way, it is trivial that $f$ is also one-way. However, it is easy to know the last $n$ bits of the preimage are exactly the last $n$ bits of $f(x,y)$ .

Though $f$ is one-way, half of the information about the preimage is revealed.

We define hard-core predicate $hc$ of a one-way function as the bit that could NEVER be revealed. Informally speaking, $hc(x)$ is a bit that is efficiently computable given $x$ , but hard to compute given $f(x)$ .

Definition. A function $hc:\{0,1\}^{*}\to\{0,1\}$ is a hard-core predicate of a function $f$ if:

hc can be computed in polynomial time.
For every probabilistic polynomial-time algorithm $\mathscr{A}$ there is a negligible function $\varepsilon(n)$ such that $\Pr_{x\leftarrow \{0,1\}^n}[\mathscr{A}(1^n,f(x))=hc(x)]\leq 1/2+\varepsilon(n)$ .

A hard-core predicate for the RSA problem is the least significant bit. That is to say, compute $lsb(x)$ given $y=[x^e\mod{N}]$ is hard.

Eureka moment!

做了这么长的铺垫，终于来到了单向函数 (one-way function) 的介绍。我觉得单向函数是密码学中最重要的概念之一，它的定义体现了密码学的核心思想—— Easy to compute, hard to invert.

首先来谈谈它的存在性。之前介绍的三个数学难题 (hard problems) 都很符合单向函数的定义；Factoring problem，质数相乘容易，质因数分解难；RSA problem，模意义下幂运算简单，开方运算难；Discrete Logarithm problem，模意义下幂运算简单，对数运算难；因此，由这些难题的猜想 (assumptions) 构造单向函数再自然不过。

最后谈谈它的意义。密码学中，加密方案 (encryption)，消息验证码 (MAC)，数字签名 (digital signature) 等加密学原语 (cryptographic primitives) 本质上是一个单向函数构建的过程。更具体一点说，是一个 单向陷门函数 (trapdoor one-way function) 的构建。所谓陷门 (trapdoor) 是指，存在某个 $z$ 使得计算原像 $x=f^{-1}(y)$ 简单，则该 $z$ 称为函数的陷门。

一个单向陷门函数有以下性质：(1) 单向性 (2) 存在陷门。这是否和某些原语的构造十分相似？以公钥加密 (或是 CPA 安全的私钥加密) 为例，加密消息 $m$ 得到密文 $c$ 很容易： $Enc_{pk}(m)\to c$ (公钥 $pk$ 公开)；而由密文 $c$ 解密得到原文 $m$ 却很困难。此为单向性 (one-way)。而倘若知道私钥 $sk$ ，由密文 $c$ 解密得到原文 $m$ 的过程就非常简单： $Dec_{sk}(c)\to m$ 。因此，私钥 $sk$ 是加密函数 $Enc_{pk}$ 的陷门 (trapdoor)。