§17 Hard-Core Predicates

Hard-Core Predicates

• Definition. A function $hc : \{0,1\}^* \rightarrow \{0,1\}$ is a hard-core predicate of a function $f$ if $hc$ can be computed in polynomial time, and for every probabilistic polynomial-time
  algorithm $\mathscr{A}$ there is a negligible function $\epsilon$ such that

  $$\operatorname{Pr}_{x\leftarrow\{0,1\}^n}\left[\mathscr{A}\left(1^n,f(x)\right)=hc(x)\right]\le\frac{1}{2}+\epsilon(n)$$

  Here the probability is taken over the uniform choice of $x$ in $\{0,1\}^n$ and the randomness of $\mathscr A$.

A Hard-Core Predicate for the RSA problem: $lsb(x)$

• We define the RSA hard-core predicate experiment $\operatorname{RSA-lsb}_{\mathscr{A}, GenRSA}(1^n)$ as follows :

  1. Run $GenRSA(1^n)$ to obtain $(N, e, d)$.
  2. Choose uniform $x \in \mathbb{Z}^*_N$ and compute $y := [x^e \bmod N]$.
  3. $\mathscr A$ is given $N, e, y$ and outputs a bit $b$.
  4. $\mathscr A$ succeeds and the output of the experiment is $1$ if and only if $lsb(x) = b$.

• Theorem. If the RSA problem is hard relative to $GenRSA$, then for all probabilistic polynomial-time algorithms $\mathscr A$, there is a negligible function $\epsilon$ such that

  $$\Pr \left[\operatorname{RSA-lsb}_{\mathscr{A}, GenRSA}(n) = 1\right] \le \frac {1} {2} + \epsilon(n)$$

Single-bit Encryption scheme $\Pi$ using the Hard-core Predicate for RSA

• Define the single-bit public-key encryption scheme $\Pi$ as follows:

  • $Gen$: On input $1^n$, run $GenRSA(1^n)$ to get $(N, e, d)$.

    Output the public-private key pair $pk = \langle N, e \rangle$, $sk = \langle N, d \rangle$.

  • $Enc$: Given as inputs a public key $pk = \langle N, e \rangle$, and message $m \in \{0,1\}$,

    choose a uniform $r \in \mathbb{Z}^*_N$ satisfying $lsb(r) = m$. Output the ciphertext $c := [r^e \bmod N]$.

  • $Dec$: Given as inputs a private key $sk = \langle N, d \rangle$, and a ciphertext $c$,

    compute $r := [c^d \bmod N]$. Output $\bar{m} := lsb(r)$.

Security of the single-bit Encryption Scheme $\Pi$

• Theorem: If the RSA problem is hard relative to $GenRSA$, then $\Pi$ is a CPA-secure encryption scheme.

— Apr 5, 2023

§17 Hard-Core Predicates by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.