Asymmetric Encryption Scheme

cryptography

Definition

Asymmetric Encryption Scheme

An asymmetric encryption scheme with a public key space $\mathcal{P}\mathcal{K}$, a private key space $\mathcal{S}\mathcal{K}$, a message space $\mathcal{M}$, and a ciphertext space $\mathcal{C}$ is a triple of algorithms:

$$⟨\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}⟩$$

where:

• The key generation algorithm $\mathsf{Gen}$ takes no input (arity 0) and returns a randomly selected key pair $(pk,sk)\in \mathcal{P}\mathcal{K}\times \mathcal{S}\mathcal{K}$.
• The encryption algorithm $\mathsf{Enc}$ takes a public key $pk\in \mathcal{P}\mathcal{K}$ and a message $m\in \mathcal{M}$, and produces a ciphertext $c\in \mathcal{C}$:

$$\mathsf{Enc}:\mathcal{P}\mathcal{K}\times \mathcal{M}\to \mathcal{C}$$

• The decryption algorithm $\mathsf{Dec}$ takes a private key $sk\in \mathcal{S}\mathcal{K}$ and a ciphertext $c\in \mathcal{C}$, and produces a plaintext $m\in \mathcal{M}$, or an error:

$$\mathsf{Dec}:\mathcal{S}\mathcal{K}\times \mathcal{C}\to \mathcal{M}$$

One-Way Function

Integer Factorisation

Definition

Integer Factorisation

The integer factorisation problem is the problem of decomposing a positive integer into a product of prime numbers. Given a composite integer $n$, find primes $p_1,p_2,\dots ,p_k$ and positive integers $e_1,e_2,\dots ,e_k$ such that

$$n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$$

Link to original

Discrete Logarithm

Definition

Discrete Logarithm

Let $G$ be a finite cyclic group of order $q$ with generator $g$. For an element $h\in G$, the discrete logarithm of $h$ with respect to base $g$ is the unique integer $x\in \{0,1,\dots ,q-1\}$ such that

$$g^x=h$$

The discrete logarithm problem is to find $x$ given $g$ and $h$.

Link to original