TCHo: A Code-Based Cryptosystem

Abstract

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz and Vaudenay with non-polynomial (though practical) decryption time. The latest version came in 2007 with more co-authors. It reached competitive (heuristic) polynomial complexity and IND-CPA security. Since then, a key-recovery chosen ciphertext attack was published by Herrmann and Leander in 2009. In this paper we review the state of the art on this cryptosystem, together with some latest improvements regarding implementation and selection of parameters. We provide also more formal results regarding correctness and we update the key generation algorithm.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Public-key cryptography first appeared with the seminal paper of Diffie and Hellman in 1976 [21]. From this work, Rivest, Shamir, and Adleman presented the RSA cryptosystem in 1978 [60], which is still the mostly used one nowadays. Among the popular cryptosystems, there are the Rabin cryptosystem [56], which is very close to RSA, and the ElGamal family of cryptosystems [25].

Every public-key cryptosystem relies on problems that are believed to be computationally infeasible. As far as we know, all cryptosystems which are used in practice rely on two problems: the integer factorization problem [56, 60] and the discrete logarithm problem [25]. However, these two problems can easily be solved in polynomial time on a quantum computer using Shor’s algorithm [62] and its generalizations [32]. Hence, if one can build a quantum computer with sufficiently many qubits to solve these problems, the mostly used public-key cryptographic systems will be broken and will have to be replaced.

To be prepared for this, we need crypto-diversity. Then, if one cryptosystem is broken, another ideally well-studied cryptosystem will be available for use. In particular, some of these systems should be secure on quantum computers as well. Such cryptosystems are referred to post-quantum cryptosystems. Nowadays, this has become a hot topic and dozens of quantum-resistant schemes have been designed.

Several types of post-quantum cryptosystems have been proposed. Some are based on multivariate equations [22, 36, 45, 52–54], whereas some others are code-based [3, 29, 46, 50] or lattice-based [1, 2, 30, 34, 44, 55, 57, 58]. The former are, to the best of our knowledge, used only to design signature schemes. In the following, we focus on code-based and lattice-based cryptosystems.

1.1 Code-Based Cryptosystems

Code-based cryptosystems rely on error correcting codes and the addition of random noise during the encryption.

The most famous code-based cryptosystem is the McEliece cryptosystem [46]. It was introduced by McEliece in 1978 and is still unbroken. In this scheme, the private key is the generator matrix G of a random [k, n]-Goppa code able to correct up to t errors along with two matrices P and S, where P is a random k ×k permutation and S a random n ×n non-singular matrix. The public key is then a scrambled version $\hat{G}$ of G, defined as $\hat{G}:=SGP$. A message is encrypted by first encoding it with the code associated to $\hat{G}$ and by adding a random noise with exactly t ones. The security of the system relies on the hardness of decoding a scrambled Goppa code. This problem is also known as the McEliece problem. Decryption of a ciphertext can be performed efficiently if one is in possession of P, S, and G, since Goppa codes are efficiently decodable.

Niderreiter described a dual variant of the McEliece cryptosystem [50]. Instead of representing the message as a codeword, the encryption is performed with the parity check matrix H of a Goppa code. The security of the two schemes have been shown to be equivalent [39]. A signature scheme [19] was derived from the Niderreiter cryptosystem by Courtois et al.

A code-based symmetric key cipher, LPN-C [29], was introduced by Gilbert et al. This cipher is based on another problem which is believed to be hard: the Learning from Parity with Noise problem (LPN). The LPN problem consists in finding an unknown k-bit vector $\bf{x}$ given access to an oracle that returns $(\bf{a},\bf{a} \cdot \bf{ x} + \nu )$, for some biased noise ν and some random vector $\bf{a}$.

The main drawback of these schemes is that the key length needed to obtain reasonable security is pretty large. For the McEliece cryptosystem, public keys of size 2¹⁶ achieve only 84. 88-bit security [9]. To obtain 266. 94-bit security, 2²⁰-bit keys are needed. Note that, asymptotically, the McEliece cryptosystem has better key sizes than RSA. For a security parameter λ, a McEliece key has size λ^2 + o(1) while RSA keys have size λ^3 + o(1) [8], but this holds only for impractical λ. Another drawback of these schemes is that the ciphertext length has to be bigger than the plaintext. This comes from the use of an error-correcting code and cannot be changed.

TCHo belongs also to the code-based cryptosystem category. However, its security rely on a somewhat different problem: the low weight polynomial multiple problem.

1.2 Lattice-Based Cryptosystems

The other category of post-quantum cryptosystems are lattice-based cryptosystems. One of the strengths of lattice-based cryptography is that its security is often based on the worst-case hardness of problems instead of average-case hardness.

One of the computationally hard problems on which lattice-based systems rely on is the Shortest Vector Problem (SVP). Briefly, this problem consists of finding the shortest non-zero vector in a lattice or an approximation of it within a polynomial factor. Polynomial algorithms like LLL [38] or its improvements [61] can only find subexponential approximations of it.

Lattice-based cryptography was introduced by Ajtai in 1996 [1]. Shortly after, Ajtai and Dwork designed the first lattice-based public-key cryptosystem based on the worst-case hardness of SVP [2]. This scheme was later improved in [30, 57]. However, they suffer from large key sizes and a large expansion factor, and are inefficient in practice. Indeed, for a lattice of dimension n, the keys in this scheme have size $\widetilde{O}\left ({n}^{4}\right )$ and the ciphertexts õ n ² [59].¹

Another class of lattice-based cryptosystems are based on the worst-case complexity of the Learning With Errors (LWE) problem [44, 55, 58]. The LWE problem is the following: given a dimension n, a modulus q and an error distribution χ over ${\mathbb{F}}_{q}$, the goal is to find a secret vector $s \in {\mathbb{F}}_{q}^{n}$ using independent LWE-samples:

$$(a,\langle a,s\rangle + \epsilon ) \in {\mathbb{F}}_{q}^{n} \times {\mathbb{F}}_{ q},\quad a\mathop{\longleftarrow}\limits_{}^{U}{\mathbb{F}}_{q}^{n},\quad \epsilon \mathop{\longleftarrow}\limits_{}^{\chi }{\mathbb{F}}_{ q}.$$

Reference [44] introduces the ring-LWE problem, an algebraic variant of the LWE problem. According to the authors, it is the first truly practical lattice-based cryptosystem based on LWE.

The most famous and efficient lattice-based cryptosystem is NTRU [34] which is based on the work of Goldreich et al. [31]. Its security is based on the hardness of SVP and the Closest Vector Problem (CVP) in convolution modular lattices, a particular class of lattices. Unlike some schemes we named above, NTRU’s security has not been shown equivalent to the hardness of SVP or CVP. Nevertheless, for a security parameter λ, the asymptotic cost for encryption and decryption is Oλ² and the key sizes is Oλ which makes of NTRU one of the most efficient public-key cryptosystems.

1.3 TCHo

It is often the case in stream cipher cryptanalysis that we need to cancel the effect of a linear feedback shift register with noise by using a low weight multiple of its connection polynomial. This happens in fast correlation attacks [47]. For instance, in the cryptanalysis of Bluetooth E0 [40–43], we need to find such a multiple with low weight for a given polynomial coming from the E0 specifications. Actually, the lower the degree and the weight, the more efficient the attack. This happens to be hard in practice. However, the designer of E0 could have selected the polynomial as a factor of some secret low weight multiple. That is, a trapdoor could have been hidden to break the cipher. Refining this idea, in 2006, Finiasz and Vaudenay [26] came up with the notion of trapdoor cipher on which TCHo is based. Indeed, the name “ TCHo” stands for “Trapdoor Cipher, Hardware Oriented”.² This early version of TCHo was using a linear code based on another LFSR.

One drawback of this design was that decryption (using the trapdoor) was not polynomially bounded, although still feasible in practice. Then, Meier suggested using other codes. Finally, in 2007, Aumasson et al. presented the latest version [3] with polynomial complexity using heuristic algorithms. They proved semantic security based on some new complexity assumptions. They further proposed to apply the Fujisaki-Okamoto construction [27] to achieve IND-CCA security.

In 2009, Herrmann and Leander [33] have shown that we can mount a key recovery chosen ciphertext attack, which seemingly proves that the key recovery problem and the decryption problem are somewhat equivalent.

Since then, Duc [23] has shown how to generate better parameter vectors, and Bindschaedler [10] implemented it as a new cipher in TLS for a browser and an HTTP server.

In this paper, we survey known results about TCHo. Additionally, we provide more formal (i.e. non-heuristic) results regarding correctness, with an updated key generation algorithm.

1.4 Structure of This Paper

In Sect. 7.2 we describe our notation and give basic definitions used throughout the paper. In Sect. 7.3 we present the problems on which the security of TCHo relies on and we survey algorithms that solve them. The complexity of these algorithm will be needed to find secure parameters for TCHo. In Sect. 7.4 we present the TCHo cipher and prove that it is a cryptosystem with heuristic key generation. In Sect. 7.5 we discuss the security of TCHo, we prove that TCHo is IND-CPA secure and we show how to achieve IND-CCA security. In Sect. 7.6 we give some practical parameters for TCHo and we discuss some implementation results. We conclude in Sect. 7.7.

2 Notations and Definitions

We denote by “log” the logarithm in base two and by “ln” the natural logarithm. We write $x\mathop{\longleftarrow}\limits_{}^{U}\mathcal{D}$ if an element x is drawn uniformly at random in a domain $\mathcal{D}$. We write $x\mathop{\longleftarrow}\limits_{}^{\chi }\mathcal{D}$ if x is drawn from domain $\mathcal{D}$ using distribution χ. For TCHo, we consider only binary polynomials, i.e., polynomials with coefficients in ${\mathbb{F}}_{2}$. The degree of a polynomial $P \in {\mathbb{F}}_{2}[x]$ is denoted d _P . We use uppercase characters to represent polynomials and the same letter in lowercase to represent its coefficients. Hence, we write $P = {p}_{0} + {p}_{1}X + {p}_{2}{X}^{2} + \cdots + {p}_{{d}_{P}}{X}^{{d}_{P}}$. The number of nonzero coefficients of P is called the weight of the polynomial and is denoted w _P . In other words, ${w}_{P} =\sum\limits_{i=0}^{{d}_{P}}{p}_{i}$, where p _i ’s are considered as elements in $\mathbb{Z}$. A polynomial P with w _P  ≪ d _P is called a sparse polynomial or a low weight polynomial.

The bias γ of a random bit B is the difference between the probability of occurrence of a zero and the probability of occurrence of a one, i.e., $\gamma =\Pr [B = 0] -\Pr [B = 1]$. Hence, a source producing random bits with bias γ outputs a zero with probability $\frac{1} {2}(1 + \gamma )$ and a one with probability $\frac{1} {2}(1 - \gamma )$. We call a finite sequence of bits x a bitstring. We write its length | x | , which denotes its number of bits. As for polynomials, we call the weight of a bitstring its number of ones. The concatenation of two bitstrings x and y is written $x\|y$. The (possibly infinite) output of a bitsource $\mathrm{S}$ is called a bitstream. If we need to specify the input (e.g. the seed) r of a source $\mathrm{S}$, we write $\mathrm{S}(r)$. The bitstring constructed from the first ℓ bits produced by $\mathrm{S}$ is denoted $\mathrm{{S}}^{\mathcal{l}}$. We denote by $\mathrm{{S}}_{\gamma }$ a bitsource producing independent bits with bias γ. Given a bitstring x, we denote by ${\mathsf{trunc}}_{\mathcal{l}}(x)$ the substring of x made by its first ℓ bits.

Given some initial parameters Π and a predicate P, we write

$$\Pr \left [P({v}_{1},\ldots ,{v}_{m};{r}_{p})\;: \quad \begin{array}{cc} & {v}_{1} \leftarrow {f}_{1}(\Pi ;{r}_{1}) \\ & \vdots \\ &{v}_{m} \leftarrow {f}_{m}(\Pi ,{v}_{1},\ldots ,{v}_{m-1};{r}_{m}) \end{array} \right ]$$

to denote

$${\Pr}_{\begin{matrix}\scriptstyle c{r}_{1},\ldots ,{r}_{m} \\ \scriptstyle {r}_{p} \end{matrix}}\left [\vee_{{v}_{1},\ldots ,{v}_{m}}P({v}_{1},\ldots ,{v}_{m};{r}_{p}) \wedge {v}_{1} = {f}_{1}(\Pi ;{r}_{1}) \wedge \cdots \wedge {v}_{m} = {f}_{m}(\Pi ,{v}_{1},\ldots ,{v}_{m};{r}_{m})\right ].$$

A Linear Feedback Shift Register (LFSR) can be described by its feedback polynomial $P =\sum\limits_{i=0}^{{d}_{P}}{p}_{i}{X}^{i}$. It is then denoted ${\mathcal{L}}_{P}$. When given an initial state $s = ({s}_{0},{s}_{1},\ldots ,{s}_{{d}_{P}-1})$, an LFSR ${\mathcal{L}}_{P}$ produces a bitstream denoted $\mathrm{{S}}_{{\mathcal{L}}_{P}}(s)$. Recall that an LFSR with feedback polynomial P and initial state $s = ({s}_{0},{s}_{1},\ldots ,{s}_{{d}_{P}-1})$ produces the bitstream s _i with ${s}_{i+{d}_{P}} = \sum\limits_{k=0}^{{d}_{P}-1}{p}_{k}{s}_{i+k}$ in ${\mathbb{F}}_{2}$.

Finally, we define two operations used in TCHo. The bitwise sum (in ${\mathbb{F}}_{2}$) of two bitstrings x and y of same length is written x + y. The product of a polynomial $K \in {\mathbb{F}}_{2}[X]$ of degree d, $K = \sum\limits_{j=0}^{d}{k}_{j}{X}^{j}$ and a bitstring $\mathrm{{S}}^{d+N} = ({s}_{0},\ldots ,{s}_{N+d-1})$ is denote $K \otimes \mathrm{ {S}}^{d+N}$ and is defined as

$$K \otimes \mathrm{ {S}}^{d+N} = ({s}_{ 0}\prime,\ldots ,{s}_{N-1}\prime),$$

with ${s}_{i}\prime:={s}_{i}{k}_{0} + {s}_{i+1}{k}_{1} + \cdots + {s}_{i+d}{k}_{d}$. We can also associate the polynomial K with an N ×(d + N) matrix M _K ^N defined as

$${ M}_{K}^{N}:=\left [\begin{array}{*{10}c} {k}_{0} & {k}_{1} & \ldots &{k}_{d}& 0 & 0 &\ldots & 0 \\ 0 &{k}_{0} & {k}_{1} & \ldots &{k}_{d}& 0 &\ldots & 0\\ & & \ddots & & & \ddots \\ 0 & 0 & \ldots & 0 &{k}_{0} & {k}_{1} & \ldots &{k}_{d} \end{array} \right ].$$

Then, we have

$${ \left [\begin{array}{*{10}c} {s}_{0}\prime & \ldots &{s}_{N-1}\prime \end{array} \right ]}^{T} = {M}_{ K}{\left [\begin{array}{*{10}c} {s}_{0} & \ldots &{s}_{N+d-1} \end{array} \right ]}^{T}.$$

Note that $P \otimes \mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} =\bf{ 0}$, i.e., when the feedback polynomial is used for the multiplication, we obtain the zero bitstring. This multiplication operator verifies also $(PQ) \otimes \mathrm{ S} = P \otimes (Q \otimes \mathrm{ S})$. Thus, if P divides K, $K \otimes \mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} =\bf{ 0}$.

A function f(λ) is negligible if for all $d \in \mathbb{R}$ we have $f(\lambda ) = O\left ({\lambda }^{-d}\right )$.

Definition 7.1 (Cryptosystem). 

A cryptosystem over a given message space $\mathcal{M}$ and random coin space $\mathcal{R}$ consists of three polynomial-time algorithms:

• A probabilistic key-generation algorithm $\mathsf{Gen}({1}^{\lambda })$ taking as input some security parameter 1^λ in unary representation, and producing a secret key K _s and a public key K _p ;

• A probabilistic encryption algorithm $\mathsf{Enc}({K}_{p},m;r)$ taking as input a public key K _p and a message $m \in \mathcal{M}$ with some random coins $r \in \mathcal{R}$, and producing a ciphertext y in the ciphertext space $\mathcal{C}$;

• A deterministic decryption algorithm $\mathsf{Dec}({K}_{s},c)$ taking as input a secret key K _s and a ciphertext $c \in \mathcal{C}$, and producing a message or an error.

The cryptosystem must satisfy the following correctness property:

$${\max }_{m\in \mathcal{M}}\Pr \left [\mathsf{Dec}({K}_{s},\mathsf{Enc}({K}_{p},m;\rho ))\neq m\;: \quad ({K}_{s},{K}_{p}) \leftarrow \mathsf{Gen}({1}^{\lambda };{\rho }_{ g})\right ]$$

is negligible as λ increases.

We will also use the following security notions and acronyms. Adaptive Chosen Ciphertext Attack is denoted CCA, Chosen Plaintext Attack CPA, Indistinguishability IND, and One-wayness OW.

Definition 7.2 (OW-CCA-security). 

A cryptosystem is (t, ε)-OW-CCA-secure if no adversary $\mathcal{A}$, with access to a decryption oracle ${\mathcal{O}}_{{K}_{s},c}$ and with running time bounded by t, can recover the plaintext from a given ciphertext with a probability higher than ε. More formally, for all $\mathcal{A}$ bounded by t,

$$\Pr \left [{\mathcal{A}}^{{\mathcal{O}}_{{K}_{s},c} }(c;\rho ) = m\; : \quad \begin{array}{c} m\mathop{\longleftarrow}\limits_{}^{U}\mathcal{M};\;r\mathop{\longleftarrow}\limits_{}^{U}\mathcal{R} \\ ({K}_{s},{K}_{p}) \leftarrow \mathsf{Gen}({1}^{\lambda }) \\ c \leftarrow \mathsf{Enc}({K}_{p},m;r) \end{array} \right ] \leq \epsilon ,$$

where ${\mathcal{O}}_{{K}_{s},c}(y) = \mathsf{Dec}({K}_{s},y)$ for y≠c and ${\mathcal{O}}_{{K}_{s},c}(y) = \perp$ otherwise. Asymptotically, a cryptosystem is OW-CCA-secure if for any polynomial t(λ) there exists a negligible function ε(λ) such that it is (t(λ), ε(λ))-OW-CCA-secure.

Definition 7.3 (IND-CPA-security). 

A cryptosystem is said (t, ε)-IND-CPA-secure or (t, ε)-semantically secure against chosen plaintext attacks if no adversary $\mathcal{A} = ({\mathcal{A}}_{1},{\mathcal{A}}_{2})$ with running time bounded by t can distinguish the encryption of two different plaintexts m ₀ and m ₁ with a probability higher than ε. More formally, for all $\mathcal{A}$ bounded by t,

$$\Pr \left [{\mathcal{A}}_{2}({K}_{p},c;\rho ) = b\; : \quad \begin{array}{cc} & ({K}_{s},{K}_{p}) \leftarrow \mathsf{Gen}({1}^{\lambda }) \\ &{m}_{0},{m}_{1} \leftarrow {\mathcal{A}}_{1}({K}_{p};\rho ) \\ & r\mathop{\longleftarrow}\limits_{}^{U}\mathcal{R};\;b\mathop{\longleftarrow}\limits_{}^{U}\{0,1\} \\ & c \leftarrow \mathsf{Enc}({K}_{p},{m}_{b};r) \end{array} \right ] \leq \frac{1} {2}+\epsilon.$$

Asymptotically, a cryptosystem is IND-CPA-secure if for any polynomial t(λ) there exists a negligible function ε(λ) such that it is (t(λ), ε(λ))-IND-CPA-secure.

IND-CPA-security can also be represented in the real-or-random game model [5, 6].

Definition 7.4 (Real-or-random IND-CPA game security). 

A cryptosystem is (t, ε)-IND-CPA-secure in the real-or-random game model if no adversary $\mathcal{A} = ({\mathcal{A}}_{1},{\mathcal{A}}_{2})$ with running time bounded by t can distinguish the encryption of a chosen plaintexts m ₀ to a random one with a probability higher than ε. More formally, for all $\mathcal{A}$ bounded by t,

$$\Pr \left [{\mathcal{A}}_{2}({K}_{p},c;\rho ) = b\; : \quad \begin{array}{cc} & ({K}_{s},{K}_{p}) \leftarrow \mathsf{Gen}({1}^{\lambda }) \\ &{m}_{0} \leftarrow {\mathcal{A}}_{1}({K}_{p};\rho );\;{m}_{1}\mathop{\longleftarrow}\limits_{}^{U}\mathcal{M} \\ & r\mathop{\longleftarrow}\limits_{}^{U}\mathcal{R};\;b\mathop{\longleftarrow}\limits_{}^{U}\{0,1\} \\ & c \leftarrow \mathsf{Enc}({K}_{p},{m}_{b};r) \end{array} \right ] \leq \frac{1} {2}+\epsilon.$$

Asymptotically, a cryptosystem is IND-CPA-secure in the real-or-random game model if for any polynomial t(λ) there exists a negligible function ε(λ) such that it is (t(λ), ε(λ))-IND-CPA-secure in the real-or-random game model.

A (t, ε)-IND-CPA-secure system in the real-or-random game model is (t, 2ε)-IND-CPA-secure in the standard model [5]. Conversely, a $(t,\epsilon )$-IND-CPA-secure system in the standard model is (t, ε)-IND-CPA-secure in the real-or-random game model. Asymptotically, both models are equivalent.

Definition 7.5 (IND-CCA-security). 

A cryptosystem is said (t, ε)-IND-CCA-secure or (t, ε)-secure against adaptive chosen plaintext attacks if no adversary $\mathcal{A} = ({\mathcal{A}}_{1},{\mathcal{A}}_{2})$, with access to a decryption oracle ${\mathcal{O}}_{{K}_{s},c}$ and with running time bounded by t can distinguish the encryption of two different plaintexts m ₀ and m ₁ with a probability higher than ε. More formally, for all $\mathcal{A}$ bounded by t,

$$\begin{array}{rcl} \Pr \left [{\mathcal{A}}_{2}^{{\mathcal{O}}_{{K}_{s},c} }({K}_{p},c;\rho ) = b\; : \quad \begin{array}{cc} & ({K}_{s},{K}_{p}) \leftarrow \mathsf{Gen}({1}^{\lambda }) \\ &{m}_{0},{m}_{1} \leftarrow {\mathcal{A}}_{1}^{{\mathcal{O}}_{{K}_{s}}}({K}_{p};\rho ) \\ & r\mathop{\longleftarrow}\limits_{}^{U}\mathcal{R};\;b\mathop{\longleftarrow}\limits_{}^{U}\{0,1\} \\ & c \leftarrow \mathsf{Enc}({K}_{p},{m}_{b};r) \end{array} \right ] \leq \frac{1} {2} + \epsilon ,& & \\ \end{array}$$

where ${\mathcal{O}}_{{K}_{s},c}(y) = \mathsf{Dec}({K}_{s},y)$, and ${\mathcal{O}}_{{K}_{s},c}(y) = \mathsf{Dec}({K}_{s},y)$ for y≠c and ${\mathcal{O}}_{{K}_{s},c}(c) = \perp$. Asymptotically, a cryptosystem is IND-CCA-secure if for any polynomial t(λ) there exists a negligible function ε(λ) such that it is (t(λ), ε(λ))-IND-CCA-secure.

Definition 7.6.

Given two sources S₀ and S₁, a distinguisher between them is an algorithm $\mathcal{D}$ that takes as input one sample x from either S₀ or S₁ and has to decide which source was used. Its advantage is

$$Adv_{\mathcal{D}}(\mathrm{{S}}_{0},\mathrm{{S}}_{1}) =\Pr \left [\mathcal{D}(x) = 1 : x \leftarrow \mathrm{ {S}}_{1}\right ] -\Pr \left [\mathcal{D}(x) = 1 : x \leftarrow \mathrm{ {S}}_{0}\right ].$$

We say that the two sources are (t, ε)-computationally indistinguishable if for any distinguisher $\mathcal{D}$ with running time bounded by t,

$$\vert Adv_{\mathcal{D}}(\mathrm{{S}}_{0},\mathrm{{S}}_{1})\vert \leq \epsilon.$$

Asymptotically, two sources are computationally indistinguishable if for any polynomial t(λ) there exists a negligible function ε(λ) such that, they are (t(λ), ε(λ))-computationally indistinguishable.

We will be using the following Chernoff bound:

Theorem 7.1 (Chernoff [14]). 

For ${X}_{1},\ldots ,{X}_{n}$ independent identically distributed Bernoulli random variables with $E({X}_{1}) \leq \frac{1} {2}$,

$$\Pr \left [ \frac{1} {n}\sum\limits_{i=1}^{n}{X}_{ i} \geq \frac{1} {2}\right ] \leq \exp \left (-2n{\left (E({X}_{1}) -\frac{1} {2}\right )}^{2}\right ).$$

3 Computational Problems

TCHo ’s security is based on computational problems which are believed to be hard. In this section, we survey the existing algorithms used to solve these problems and we focus on their best complexity to find suitable parameters for TCHo.

3.1 Low Weight Polynomial Multiple Problem

Unlike the integer factorization, efficient algorithms exist to factor polynomials over a finite field [7, 13]. However, finding a multiple of a given polynomial that has a bounded degree and a bounded weight can be hard. TCHo ’s security relies on the Low Weight Polynomial Multiple problem (LWPM).

Problem 7.1 (LWPM). 

Let $w,d,{d}_{P} \in \mathbb{N}$ be three parameters such that 0 < d _P  < d and w < d. Given an instance $P \in {\mathbb{F}}_{2}[x]$ of degree d _P , find a multiple K of P of degree at most d and weight at most w.

In TCHo, P will be the public key and one will be able to recover some information about the plaintext from a ciphertext using such a low weight polynomial K. Note that in TCHo, the private key will be one of the solutions to this problem. Hence, we are ensured that a solution exists. In fact, the public key P is generated as an irreducible factor of a random polynomial K of weight w _K and degree at most d with a nonzero constant factor. In this case, one can heuristically estimate the number of solutions with nonzero constant term as

$${\mathcal{N}}_{\mathrm{sol}} \approx 1 + {2}^{-{d}_{P} }\left({{d}\atop {w - 1}}\right).$$

(7.1)

Note that the additional solution comes from the way we generate our polynomial P. We present now algorithms used to find low weight polynomial multiples. In what follows, we review some existing algorithms to solve the LWPM problem in order to derive heuristically some hard domain parameters.

To support the hardness of the LWPM problem, Giesbrecht et al. showed that finding sparse multiple polynomials with unbounded degree in a finite field is at least as hard as computing orders in an extension of this field [28], a problem which is believed to be hard. Unfortunately, this result is not directly applicable to TCHo because we consider polynomially bounded degrees and we know that a solution exists within this bound.

3.1.1 Exhaustive Search

When d is close to d _P , we can use exhaustive search to find all low weight multiples of P. The exhaustive search is performed by simply checking the weight of all multiples of P. The complexity for finding all multiples is Θ (Poly(d)2^d-dp). _P . However, this method is inefficient in TCHo, since d − d _P is very large.

3.1.2 Birthday Paradox

Following Meier and Staffelbach [47], we build two lists L ₁ and L ₂ in which we store respectively polynomials with weight $\left \lfloor (w - 1)/2\right \rfloor$, degree smaller than d, and zero constant term and polynomials with weight $\left \lceil (w - 1)/2\right \rceil$, degree smaller than d, and constant term equal to one. Once we have these lists, we look for pairs that sum to 0 modulo P. This collision search can be done efficiently using a hash table. Note that when w is odd (as in TCHo ), one can use only the list L ₁ and search for pairs (in L ₁) summing to 1 instead. The list size is $\left({{d}\atop {\lceil (w - 1)/2\rceil }}\right)$. Hence, the memory use is

$$2\left({{d}\atop {\lceil (w - 1)/2\rceil}}\right)(w - 1)\log (d) \approx \Theta \left ({d}^{\lceil (w-1)/2\rceil }\log (d)\right )$$

for small weights w. The time complexity is $\Theta \left (\left({{d}\atop {(w - 1)/2}}\right)\right)$. This strategy is clearly faster than exhaustive search but uses a lot of memory. In the case of TCHo, d is typically greater than 2¹⁵ and w greater than 68. Hence, the lists contains more than Ω2³⁸⁸ elements, which is way too much. An improvement of this method is proposed by Chose, Joux and Mitton to solve this problem using $\Theta \left ({d}^{\lceil (w-1)/4\rceil }\log (d)\right )$ space instead [15]. An alternative solution was also proposed by Didier and Laigle-Chapuy using discrete logarithms [20]. Assuming that in practice the discrete logarithm with base element X has a negligible complexity over ${\mathbb{F}}_{2}[X]/\langle P\rangle$, they achieve a time complexity of $\Theta \left ({d}^{(w-1)/2-1}\right )$ for a memory cost equal to the original birthday paradox method.

3.1.3 Generalized Birthday Paradox

When there is a large number of solutions, one can use Wagner’s generalized birthday paradox [64] to find more efficiently one solution. The idea is to make use of 2^k lists of polynomial of weight $(w - 1)/{2}^{k}$ instead of two lists as in the birthday paradox algorithm. Collisions are then found in pairs of lists until one single list remains containing a wanted solution. This algorithm will not return all possible solutions but can find one of them. However, the lists need to have a size greater than ${2}^{{d}_{P}/(k+1)}$. Hence, we need

$$\left({{d}\atop {(w - 1)/{2}^{k}}}\right) \geq {2}^{{d}_{P}/(k+1)},$$

for a k > 1. In this case, a solution can be found with time and memory complexity

$$\Theta \left ({2}^{k}{2}^{{d}_{P}/(k+1)}\right ).$$

3.1.4 Finding a Low Weight Multiple Using Lattices

El Ailmani and von zur Gathen [24] presented a lattice-based algorithm to solve the LWPM problem. The set of multiples of P with degree lower than d form a lattice L _d . More formally

$${L}_{d}:=\{Q \in \mathbb{Z}[X] : Q \in P\mathbb{Z}[X] + 2\mathbb{Z}[X],\deg (Q) < d\}.$$

This lattice has dimension d. Now, note that a low weight polynomial multiple of P is a short vector in L _d . Such a vector can be found by first finding a basis of L _d , then by reducing this basis using for instance the LLL algorithm [38]. The algorithm uses Od ⁶ time and Od ×d _P memory if we use LLL. However, this method is strongly limited by the lattice dimension. When d is too large, the size of the short vector we find using LLL becomes greater than w. This comes from the fact that this vector is only an approximation of the shortest vector in the lattice. Hence, this technique is inefficient to attack TCHo.

3.1.5 Syndrome Decoding

Syndrome decoding can also solve this problem. First, we compute the matrix H, whose column i is defined by X ⁱ mod P, for 1 ≤ i ≤ d − 1. Once this matrix is computed, we search for a low weight polynomial in the preimages of 1 of this matrix. Following Canteaut and Chabaud [11], one solution can be found in time

$$\Theta \left ( \frac{1} {{\mathcal{N}}_{\mathrm{sol}}}{\left (\frac{d - 1} {{d}_{P}} \right )}^{w-1}\right ).$$

By using (7.1), this approximates to

$$\Theta \left ( \frac{{\left (\frac{d-1} {{d}_{P}} \right )}^{w-1}}{{2}^{-{d}_{P}}}\left({{d}\atop {{w - 1} + 1}}\right)\right ).$$

3.1.6 Hardness of the LWPM Problem

Out of this survey, we deduce the following assumption

Assumption 7.2.

Let w,d,P be an instance of the LWPM problem. Let λ be the security parameter. The LWPM problem is believed to require a super-polynomial complexity if

$$(w - 1)\log \frac{d} {{d}_{p}} \geq \lambda ,$$

(7.2)

and

$$\left({{d}\atop {{w - 1} < {2}^{{d}_{P} }}}\right).$$

(7.3)

Indeed, these inequalities give no complexity better than Θ2^λ with the previous algorithms. Note that (7.3) implies that we shall expect no more solution than the one which was hidden.

3.2 The Noisy LFSR Decoding Problem

TCHo ’s security relies also on the noisy LFSR decoding problem.

Problem 7.2 (Noisy LFSR Decoding). 

Let ℓ > 0 be a length, let P be a polynomial of degree d _P , and let 0 ≤ γ ≤ 1 be a bias. Recover X, the random seed of an LFSR, given $Y :=\mathrm{{S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}(X) +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}\;$, i.e., the bitwise addition between the output of this LFSR with feedback polynomial P and seed X, and some random noise with bias γ.

In TCHo, the plaintext will be hidden by such a Y. Hence, since the noise is strongly biased, if one can easily recover the seed of the LFSR, one can recover the plaintext. We survey now the techniques used to solve the noisy LFSR decoding problem.

3.2.1 Information Set Decoding

Information set decoding is performed as follows. We pick d _P random bits out of the ℓ output bits of Y and we solve the linear system induced by the columns of the generator matrix of the LFSR corresponding to these bits (e.g. by performing Gaussian elimination). X can be recovered if there are no errors among the d _P selected bits. This happens with probability

$${ \left (\frac{1} {2} + \frac{\gamma } {2}\right )}^{{d}_{P} }.$$

Hence, we can recover X with complexity³

$$\Theta {\left (\frac{1} {2} + \frac{\gamma } {2}\right )}^{-{d}_{P} }.$$

(7.4)

This is Ω(2^λ) for

$$\gamma \leq {2}^{1-\lambda /{d}_{P} } - 1.$$

3.2.2 Maximum Likelihood Decoding

Maximum likelihood (ML) decoding is a bruteforce technique that consists in computing S _{ℒ P} ^ℓ(X) for all possible random seeds X and keep the one with smallest distance to Y. This costs $\Theta \left ({2}^{{d}_{P}}\mathcal{l}\right )$ and can be improved to Θ2^d _P d _P by using a fast Walsh transform [42]. More subtle ML algorithms exist that decode only a subcode of the full code. In this case, even though we do not recover completely the seed X, we may recover some bits of information which may threaten TCHo. It can be shown [26] that if we take d _P  ≥ 2λ, these algorithms yield less than 1 bit of information.

3.2.3 Iterative Decoding

Iterative decoding [12] consists in finding low weight multiples of P forming parity check equations. The low-weight parity check code associated to these equations can then be solved. When d _P  ≥ 2λ, decoding is not possible using this technique [26].

3.2.4 Hardness of the Noisy LFSR Decoding Problem

Out of this survey, we deduce the following assumption.

Assumption 7.3.

Let ℓ,P,γ be an instance of the noisy LFSR decoding problem. Let λ be the security parameter. The problem is believed to require a super-polynomial complexity if

$${d}_{P} \geq 2\lambda ,$$

(7.5)

and

$$\gamma \leq {2}^{1-\lambda /{d}_{P} } - 1.$$

(7.6)

Indeed, these inequalities give no complexity better than Θ2^λ with the previous algorithms.

3.3 The Noisy LFSR Distinguishing Problem

The previous problem has a decisional counterpart.

Problem 7.3 (Noisy LFSR Distinguishing). 

Let ℓ > 0 be a length, let P be a polynomial of degree d _P , and let 0 ≤ γ ≤ 1 be a bias. Given an ℓ-bit string Y , decide whether Y was generated by $Y =\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}(X) +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}\;$ or by a uniformly distributed source Y = S₀ ^ℓ.

3.3.1 Linear Noise Cancellation

We can think of two strategies to distinguish $\mathrm{{S}}_{{_\ast}}^{\mathcal{l}} =\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}$ from S_∗ ^ℓ = S₀ ^ℓ. The first one is to apply the solutions we presented to solve the noisy LFSR decoding problem, i.e., to recover the random seed used by ℒ _P . We know that if (7.5) and (7.6) hold, the problem is supposed hard.

Another solution is to multiply S_∗ ^ℓ by P or any of its multiple Q. If S_∗ ^ℓ is not S₀ ^ℓ, we have

$$Q \otimes \mathrm{ {S}}_{{_\ast}}^{\mathcal{l}} \approx \mathrm{ {S}}_{{ \gamma }^{{w}_{Q}}}^{\mathcal{l}-{d}_{Q} }.$$

The best advantage [4] one can get to distinguish N bits of bias γ^w from random ones is $Adv \approx {\gamma }^{w}\sqrt{N/(2\pi )}$. From Sect. 7.3.1, we know that the cost to find a multiple of P with degree bounded by d and weight bounded by w is $Comp ={ \left (d/{d}_{P}\right )}^{w-1}$ if we use syndrome decoding. It works with probability bounded by $Success = {2}^{-{d}_{P}}\left({{d}\atop {{w - 1}}}\right)$.

To identify the range of parameters for which this method does not work, we want

$$\frac{1}{Adv} + \frac{Comp}{Success} \leq {2}^{\lambda }.$$

So, N, w, d _P are polynomially bounded. We have

$$\frac{1}{Adv} + \frac{Comp}{Success} = \frac{{\gamma }^{-w}} {\sqrt{N/2\pi }} + \frac{{(d/{d}_{P})}^{w-1}} {{2}^{-{d}_{P}}}\left({{d}\atop {{w - 1}}}\right) \geq Poly (\lambda )\left ( \frac{{\gamma }^{-w}} {\sqrt{N/2\pi }} +{ \left (\frac{w\mathrm{{e}}^{-1}} {{d}_{P}}\right )}^{w}{2}^{{d}_{P} }\right )$$

Let f(w) be the term under parentheses. The function $w\mapsto {\left (w\mathrm{{e}}^{-1}/{d}_{P}\right )}^{w}$ decreases until w = d _P and then increases. Let τ be the root of $\gamma \mathrm{{e}}^{-1} = \tau {2}^{-\tau }$. Since we will take $\gamma = 1 - o(1)$, we have $\tau = {\tau }_{0} + o(1)$ where τ₀: ≈ 3. 053. Note that τ ≥ 1 since γ ≤ 1.

We assume that d _P log(1 ∕ γ) ≥ λτ. Let ${w}_{0}:={d}_{P}/\tau$. If w ≤ w ₀, since w < d _P (because τ ≥ 1), we have

$$f(w) \geq {\left (\frac{w\mathrm{{e}}^{-1}} {{d}_{P}} \right )}^{w}{2}^{{d}_{P} } \geq {\left (\frac{{w}_{0}\mathrm{{e}}^{-1}} {{d}_{P}} \right )}^{{w}_{0} }{2}^{{d}_{P} } ={ \left (2{\left (\frac{1} {\tau }\mathrm{{e}}^{-1}\right )}^{1/\tau }\right )}^{{d}_{P} } = {\gamma }^{-{d}_{P}/\tau } \geq {2}^{\lambda }.$$

If w ≥ w ₀, we have

$$f(w) \geq {\gamma }^{-w} \geq {\gamma }^{-{w}_{0} } = {\gamma }^{-{d}_{P}/\tau } \geq {2}^{\lambda }.$$

This leads us to the following assumption:

Assumption 7.4.

Let ℓ,P,γ be an instance of the noisy LFSR distinguishing problem. Let λ be the security parameter. Let τ be the root of $\gamma \mathrm{{e}}^{-1} = \tau {2}^{-\tau }$ . The problem is believed to require a super-polynomial complexity if

$$\gamma \leq {2}^{1-\lambda /{d}_{P} } - 1,$$

and

$${d}_{P}\log \frac{1} {\gamma } \geq \lambda \tau.$$

Indeed, these inequalities give no complexity better than Θ2^λ for advantage Ω(2^− λ) with the previous algorithms.

Note that if d _P  < 2λ, we have $\gamma > \sqrt{2} - 1$ so d _P log(1 ∕ γ) ≤ 1. 28 ×d _P . Furthermore, we have in this case τ ≥ 5 which implies that λτ ≥ 5λ. We deduce from it that 1. 28 ×d _P  ≥ 5λ which contradicts d _P  < 2λ. Hence, the hypotheses imply d _P  ≥ 2λ which was used in Assumption 7.3.

4 Presentation of the TCHo Cryptosystem

In this section, we describe the TCHo cryptosystem and give algorithms for key generation, encryption and decryption. We also prove that TCHo is a cryptosystem.

4.1 Parameters

TCHo ’s secret key consists in a low weight polynomial K over ${\mathbb{F}}_{2}[X]$ of degree d _K bounded by d and of weight w _K . The public key is a polynomial P such that P divides K and whose degree is in a given interval [d _min, d _max]. The security of the scheme relies on noise added by an LFSR with the public key as feedback polynomial and some strongly biased random noise. The bias of the noise γ along with the plaintext length k and the ciphertext length ℓ > d are the remaining parameters. Hence, for a fixed system with security parameter λ, we can define a parameter vector

$$\left (k,{d}_{\min },{d}_{\max },d,{w}_{K},\gamma ,\mathcal{l}\right ).$$

We require that k, d _min, d _max, d, w _K , ℓ are positive integers, polynomially bounded, d _max > d _min, w _K odd, 3 ≤ w _K  ≤ k, d ≥ d _max, k + d ≤ ℓ, and that γ is subject to the following requirement which is needed for correctness.

$${\gamma }^{2{w}_{K} }\frac{\mathcal{l} - d} {k} = \Omega ({\lambda }^{\alpha })$$

(7.7)

for some constant α > 0. Later, we shall add the requirements of Assumptions 7.2 and 7.4 for security.

There are two approaches for selecting the parameters: in practice, we select some for which we have good implementation performances and a fair understanding of the security. This will be covered in Sect. 7.6. In theory, we select a family of parameters based on λ so that algorithms are polynomially bounded and whose security relies on complexity assumptions. This will be addressed in Theorems 7.5 and 7.6.

4.2 Key Generation

First, a random polynomial K of degree bounded by d and odd weight w _K with constant term 1 is generated. Nonzero coefficients in K shall be selected at positions which are pairwise different modulo k. If K(X) is not coprime with X ^k − 1 (which would be exceptional), we try again. Then, an irreducible factor P of degree d _P  ∈ [d _min, d _max] is searched. This procedure is repeated with another K until an appropriate P is found:

Note that since K is sparse, it can be stored efficiently using only ⌈w _K log(d)⌉ bits.

The number of irreducible polynomials of degree d is equivalent to 2^d ∕ d. So, a random polynomial has an irreducible factor of degree d with probability 1 ∕ d. From that, we deduce that a random polynomial has an irreducible factor of degree in [d _min, d _max] with probability $O\left (({d}_{\max } - {d}_{\min })/{d}_{\max }\right )$. Hence, $O\left ({d}_{\max }/({d}_{\max } - {d}_{\min })\right )$ factorization attempts are needed in average. Using the Cantor-Zassenhaus [13] factoring algorithm, every attempt costs Od ²logdloglogd.

The total complexity of the key generation algorithm is, thus,

$$O\left ( \frac{{d}_{\max }} {{d}_{\max } - {d}_{\min }}{d}^{2}\log d\log \log d\right ).$$

We make the heuristic assumption that the complexity is the same when the polynomial K is sparse instead of being fully random. This assumption will be discussed in Sect. 7.6. However, we have no formal proof so far that this algorithm is polynomially bounded. This is left open for future work.

4.3 Encryption

Let C(m) : { 0, 1}^k → { 0, 1}^ℓ be the repetition code that, given an m ∈ { 0, 1}^k returns the ℓ bit word

$$m\|m\|\ldots \|\tilde{m},$$

where $\tilde{m}$ is the bitstring m truncated such that C(m) has length ℓ. Given a plaintext m of length k, the ciphertext y of length ℓ is

$$y:={\mathsf{Enc}}_{\textrm{ TCHo}}(P,m;{r}_{1}\|{r}_{2}) = C(m) +\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}({r}_{ 1}) +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}({r}_{ 2}),$$

where r ₁ and r ₂ are random seeds. Care has to be taken about the size of these seeds. The first seed, r ₁, consists in a random initial state for the LFSR. Hence, it has to be a random bitstring in $\{0,{1\}}^{{d}_{P}}$. The second seed, r ₂, is a random seed for a biased pseudo random bit source. To ensure a proper security, this seed needs to be at least λ-bit long, where λ is the security parameter.

The encryption cost is Oℓ ×d _P if the random bit generator has not a higher complexity. In the case of a dedicated hardware implementation, the encryption can be done in Oℓ time with Od _P gates.

4.4 Decryption

Let y ∈ { 0, 1}^ℓ be the ciphertext, i.e., $y = C(m) +\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}({r}_{1}) +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}({r}_{2})$. We decrypt y as follows.

First, we remove the contribution of the noise induced by the LFSR ℒ _P . This is done by computing $t:={\mathsf{trunc}}_{\mathcal{l}-d}(K \otimes y)$. The resulting t is truncated to ℓ − d bits.⁴ Since the multiplication operator is distributive and since K is a multiple of P, which is the feedback polynomial of ℒ _P , this operation completely removes the noise generated by the LFSR. However, this operation has also an effect on C(m) and S_γ(r ₂). We have $K \otimes {S}_{\gamma }^{\mathcal{l}} \approx {S}_{{\gamma }^{{w}_{K}}}^{\mathcal{l}-d}$ in the sense that every bit of K ⊗ S _γ ^ℓ has a bias of ${\gamma }^{{w}_{K}}$ but they are not perfectly independent. Hence, if the weight of K is low, the noise remains strongly biased. We have also K ⊗ C(m) = C(m′), where m′ = ψ _K (m), for some linear map ψ _K . Thus, $t \approx C({\psi }_{K}(m)) +\mathrm{ {S}}_{{\gamma }^{{w}_{K}}}^{\mathcal{l}-d}$. Under some conditions, ψ _K is invertible.

Since the noise $\mathrm{{S}}_{{\gamma }^{{w}_{K}}}^{\mathcal{l}-d}$ is strongly biased, we can recover ψ _K (m) by performing majority logic decoding (MJD), i.e., by taking for each bit its majority value in the repetition code. For a proper choice of w _K , γ and ℓ, the probability of error will be negligible.

MJD decodes the correct ψ _K (m) if for every $i = 0,\ldots ,k - 1$, there is a majority of j’s such that ${(K \otimes \mathrm{ {S}}_{\gamma }^{\mathcal{l}})}_{i+kj} = 0$.

Finally, we invert ψ _K to recover m. Recall that the operation K ⊗ C(m) can also be written as M _K ^{ℓ − d} C(m), with

$${ M}_{K}^{\mathcal{l}-d}:=\left [\begin{array}{*{10}c} {k}_{0} & {k}_{1} & \ldots & {k}_{d} & 0 & 0 & \ldots & 0 \\ 0 & {k}_{0} & {k}_{1} & \ldots & {k}_{d} & 0 & \ldots & 0\\ & & \ddots & & & \ddots \\ 0 & 0 & \ldots & 0 & {k}_{0} & {k}_{1} & \ldots & {k}_{d} \end{array} \right ].$$

Since C(m) is a repetition code, ψ _K (m) can be written as C _K m, with

$${ C}_{K} = \left [\begin{array}{*{10}c} {c}_{0} & {c}_{1} & \ldots & {c}_{k-1} \\ {c}_{k-1} & {c}_{0} & \ldots & {c}_{k-2}\\ \vdots & & \ddots & \vdots \\ {c}_{1} & {c}_{2} & \ldots & {c}_{0} \end{array} \right ],$$

where

$${c}_{j} = \sum\limits_{\{i\in [0,d]: i\equiv j \mathbin{\rm mod}\,\,k\}}{k}_{i}.$$

The matrix C _K is invertible if and only if ${c}_{0} + {c}_{1}X + \cdots + {c}_{k-1}{X}^{k-1}$ is coprime with X ^k − 1, which is equivalent to K(X) being coprime with X ^k − 1, which is a condition in our key generation algorithm. Hence, $m = {C}_{K}^{-1}m\prime$.

The decryption complexity is Ow _K ×ℓ + k ³ since the first operation takes Ow _K ×ℓ, the second Oℓ − d and the third Ok ³ time.

4.5 TCHo Is a Cryptosystem

In this section, we show that TCHo is a cryptosystem as defined in Definition 7.1.

Lemma 7.1.

The probability that a correctly generated ciphertext is badly decrypted satisfies

$$\Pr [\mathsf{bad\ decoding}] \leq k \times \exp \left (-\frac{1} {2}\left \lfloor \frac{\mathcal{l} - d} {k} \right \rfloor {\gamma }^{2{w}_{K} }\right ).$$

Proof.

We note from the requirement on K that nonzero coefficients have indices which are pairwise different modulo k. Hence, for a fixed i, all bits (K ⊗ S_γ ^ℓ) _i + kj are independent. So,

$$\Pr [\mathsf{bad\ decoding}] \leq \varrho ,$$

where

$$\varrho :=\sum\limits_{i=0}^{k-1}\;\: \sum\limits_{w=0}^{\frac{1} {2} \lfloor \frac{\mathcal{l}-d-i} {k} \rfloor }\left ({ \lfloor \frac{\mathcal{l}-d-i} {k} \rfloor \atop w} \right ){\left (\frac{1 + {\gamma }^{{w}_{K}}} {2} \right )}^{w}{\left (\frac{1 - {\gamma }^{{w}_{K}}} {2} \right )}^{\lfloor \frac{\mathcal{l}-d-i} {k} \rfloor -w}.$$

(7.8)

We conclude thanks to the Chernoff bound (Theorem 7.1). $\square$

Theorem 7.5.

There are some parameter selections making TCHo a cryptosystem with heuristic key generation that verifies the inequalities in Assumptions 7.2–7.4.

Proof.

Let λ be the security parameter. We select parameters satisfying

$$\begin{array}{rcl} & {w}_{K} = a\lambda \qquad k = {w}_{K} + \Theta \left (\lambda \right )\qquad d = \Theta \left ({\lambda }^{2} \times k\right ) & \\ & {d}_{\min } = \Theta \left ({\lambda }^{2}\right )\qquad {d}_{\max } = {d}_{\min } + \Theta \left ({\lambda }^{2}\right )\qquad \mathcal{l} = d + \Theta \left ({\lambda }^{2} \times k\right )\qquad \gamma = {\lambda }^{-c/\lambda },& \\ \end{array}$$

such that these are positive integers, w _K is odd, a, c > 0 and with the following condition:

$$0 < ac < 1.$$

With these parameters, key generation takes Oλ⁴ ×k ² ×logλ ×loglogλ (heuristically), encryption takes Oλ⁴ ×k, decryption Oλ³ ×k and (7.7) is verified. Furthermore, these parameters satisfy the inequalities in Assumptions 7.2 and 7.4, which will be needed to show the security of our scheme.

Since the parameters satisfy (7.7), there exists a constant f ≥ 0 such that

$$\Pr [\mathsf{bad\ decoding}] \leq k \times \exp \left (-f{\lambda }^{\alpha }\right )$$

when λ is large enough. So, this probability is negligible. Hence, the cryptosystem satisfies also the correctness property. $\square$

5 Security of TCHo

In this section, we show results on the security of TCHo. In particular, we show that TCHo is IND-CPA-secure and not OW-CCA-secure. We show also how to achieve IND-CCA security.

5.1 TCHo Is IND-CPA-Secure

Theorem 7.6 (Aumasson et al. [3]). 

Let S ₀ be an unbiased source of random bits. There exists a constant μ such that, for every TCHo parameters, if S _{ℒ P} ^ℓ + S _γ ^ℓ cannot be distinguished from S ₀ ^ℓ in time t with an advantage larger than ε, then TCHo is (t − μℓ,2ε)- IND-CPA-secure.

Proof.

Instead of proving the semantic security directly, we prove it in the real-or-random game model. Recall that in this model, the adversary submits first a chosen plaintext x following an algorithm ${\mathcal{A}}_{1}^{\textrm{ ror}}({K}_{p};\rho )$. Then, given a ciphertext z, the adversary has to decide using an algorithm ${\mathcal{A}}_{2}^{\textrm{ ror}}({K}_{p},z;\rho )$ whether z is a ciphertext corresponding to x or to another random plaintext.

We show that using this adversary ${\mathcal{A}}^{\textrm{ ror}} = ({\mathcal{A}}_{1}^{\textrm{ ror}},{\mathcal{A}}_{2}^{\textrm{ ror}})$, we can build a distinguisher between $\mathrm{{S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}$ and $\mathrm{{S}}_{0}^{\mathcal{l}}$. Let S_∗ ^ℓ be the unknown instance we have to distinguish. First we recover a plaintext $x = {\mathcal{A}}_{1}^{\textrm{ ror}}(P)$. Let $z = C(x) +\mathrm{ {S}}_{{_\ast}}^{\mathcal{l}}$. If S_∗ ^ℓ is random, then z is also a totally random bitstring. Note that this z corresponds also to a valid ciphertext, since every bitstring in {0, 1}^ℓ is valid. On the other hand, if S_∗ ^ℓ is $\mathrm{{S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}$, then z is a valid ciphertext of x. Hence, using ${\mathcal{A}}_{2}^{\textrm{ ror}}(P,z)$, we can decide, whether z is a ciphertext corresponding to x or not. The cost of this simulation is μℓ, for μ > 0 large enough. Thus, since we know by assumption that we cannot distinguish $\mathrm{{S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}} +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}$ from S₀ ^ℓ in time t with an advantage larger than ε, ${\mathcal{A}}^{\textrm{ ror}}$ has complexity at least t − μℓ. Hence, TCHo is $(t - \mu \mathcal{l},\epsilon )-$ IND-CPA secure in the real-or-random game model. This implies that TCHo is $(t - \mu \mathcal{l},2\epsilon )-$ IND-CPA secure. $\square$

Now, we just have to find suitable parameters such that the Noisy LFSR Distinguishing Problem is hard to obtain an IND-CPA-secure scheme.

5.2 TCHo Is Not OW-CCA Secure

We recall two negative results from [3] regarding the security of TCHo.

Lemma 7.2.

TCHo is malleable.

Proof.

Given a ciphertext y corresponding to a plaintext x, y + C(x′) is a valid ciphertext of x + x′ with correct distribution. $\square$

This result implies also that TCHo is not IND-CCA secure as we can just use the malleability of ciphertexts and call the decryption oracle on the modified ciphertext to play the IND-CCA game.

Lemma 7.3.

TCHo is not OW-CCA secure.

Proof.

Given a ciphertext y to invert, modify the first bit an submit it to the decryption oracle. With high probability, the obtained plaintext will correspond to the original one. $\square$

5.3 The Herrmann-Leander Attack

In PKC 2009, Herrmann and Leander presented a chosen ciphertext key recovery attack on TCHo [33]. They were able to recover the secret key in about d ^3 ∕ 2 queries to a decryption oracle. As shown in Lemma 7.3, TCHo is not OW-CCA secure. However, their attack is by far worse than the traditional OW-CCA message recovery attack since it reveals the private key. It is important to notice that their attack does not solve the LWPM problem but extracts this low weight polynomial by querying the decryption oracle in a clever way.

This proves that the key recovery problem is easy with a Dec _K oracle. This does not prove that decryption and key recovery are equivalent because we are using the Dec _K oracle with some inputs which do not follow the distribution of genuine ciphertexts. So, a decryption oracle able to decrypt ciphertexts may not fully emulate the Dec _K oracle for our purpose. We briefly present Herrmann and Leander’s attack here.

The attack is an adaptive differential attack, i.e., pairs of ciphertexts with a well-chosen difference are submitted to the decryption oracle. Let the private key be $K =\sum\limits_{j=0}^{d}{k}_{j}{X}^{j}$. Let also $N:=\mathcal{l} - d$. For simplicity, we assume that $\lfloor \frac{N} {k} \rfloor$ is odd so that there is always a non-ambiguous majority among $\lfloor \frac{N} {k} \rfloor$ bits. The idea is to recover every bit one after the other starting from k ₁ to ${k}_{{d}_{K}}$. (Note that k ₀ is fixed to 1.) To recover the key bit k _i knowing ${k}_{0},\ldots ,{k}_{i-1}$, two ciphertexts y and y′ are submitted to the decryption oracle such that the difference between them before the MJD step during the decryption process is $t \oplus t\prime = \Delta :=(1 \oplus {k}_{i},0,\ldots ,0,1,0,\ldots ,0)$, where the 1 is at index i. Let the two obtained plaintexts be respectively m and m′. If m and m′ differ, this means that the MJD algorithm made different decisions for the two ciphertexts. With a clever choice of the ciphertexts y and y′ and using our knowledge of the previous bits of K, we can ensure that t = (b, 0, r), with $b ={ \mathsf{trunc}}_{i}(1,{0}^{(2k-1)},1,{0}^{(2k-1)},\ldots \,)$ and r an uniformly distributed random bitstring of length $\mathcal{l} - i - d - 1$. The b part ensures that the first sum in the majority decoding algorithm is as much balanced as possible.

Let

$$M\prime:=\left [\begin{array}{*{10}c} {k}_{0} & {k}_{1} & \ldots & {k}_{i-1} \\ 0 & {k}_{0} & \ldots & {k}_{i-2}\\ \vdots & & \ddots & \vdots \\ 0 & \ldots & 0 & {k}_{0}\\ \end{array} \right ].$$

To construct y, we take $y:=(\hat{y},{0}^{(d+1)},r)$, where $\hat{y}$ is the solution of $M\prime\hat{y} = b$ and r is a random bit string of size $N - i - 1$. For y′, let δ be defined as

$$\begin{array}{rcl} & {\delta }_{0} =\sum\limits_{j=0}^{i-2}{\delta \prime}_{j}{k}_{j+1} \oplus 1,& \\ & {\delta }_{j} = {\delta \prime}_{j-1}\qquad \quad \qquad \text{ for }1 \leq j \leq i, & \\ & {\delta }_{j} = 0\qquad \quad \qquad \quad \;\,\text{ for }i + 1 \leq j < \mathcal{l}, & \\ \end{array}$$

where δ′ is the solution of $M\prime\delta \prime = {(0,\ldots ,0,1)}^{t}$. Then, $y\prime:=y + \delta$. We refer the reader to [33] for a proof of correctness of this construction. These two ciphertexts produce the required t and t′.

To recover k _i , we distinguish two cases:

• When $i \equiv 0 ({\rm mod} k)$, both the difference 1 ⊕ k _i and 1 in Δ contribute to the same bit during MJD. Since t ₀ = 1 and t _i  = 0, we have t ₀ ′ = k _i and t _i ′ = 1. Hence, m≠m′ implies that k _i  = 1. Thus, the resulting plaintext will be different only when $\sum\limits_{j=0}^{\lfloor N/k\rfloor }{t}_{kj} = \left \lfloor \frac{1} {2}\left \lfloor \frac{N} {k} \right \rfloor \right \rfloor$ and k _i  = 1. However, in the case k _i  = 0, the majority cannot change. By repeating this attack with a sufficient number of ciphertext pairs we recover k _i with negligible probability of error by making statistics.

• When i ≢ 0 (mod k), the difference 1 ⊕ k _i and the difference 1 does not contribute to the same bit during MJD. If k _i  = 0, t and t′ differ in their coordinates at index 0 and i and the majority at index 0 changes if $\sum\limits_{j=0}^{\lfloor N/k\rfloor }{t}_{kj} = \left \lfloor \frac{1} {2}\left \lfloor \frac{N} {k} \right \rfloor \right \rfloor$ and k _i  = 1. When k _i  = 1, this majority cannot change. The one at index i may change depending on $\sum\limits_{j=0}^{\lfloor (N-i)/k\rfloor }{t}_{kj+i}$. However, the difference m ⊕ m′ will not be the same as when the majority changes at index 0, so it can be filtered out. Like in the previous case, we recover k _i by submitting sufficiently many ciphertext pairs.

We refer the reader to [33] for further details.

This attack implies that TCHo cannot be used in its original form. We show in the next section how TCHo can be transformed into an IND-CCA secure scheme.

5.4 Achieving IND-CCA Security

Following the Fujisaki-Okamoto construction [27], we can obtain an IND-CCA secure scheme using TCHo. For this, we need first to define Γ-uniformity.

Definition 7.7 (Γ-uniformity). 

Let Asym be an asymmetric encryption scheme, with key generation algorithm Gen(1^λ) and encryption algorithm Enc _Asym (K _p , m; r) over the message space $\mathcal{M}$ and the random coins space $\mathcal{R}$. Asym is Γ-uniform if for any plaintext m ∈ ℳ, for any keys drawn by Gen, and for any y ∈ { 0, 1}^∗, we have

$$\Pr \left [h\mathop{\longleftarrow}\limits_{}^{U}\mathcal{R} : y ={ \mathsf{Enc}}_{\mathsf{Asym}}({K}_{p},m;h)\right ] \leq \Gamma ,$$

i.e., the probability that a plaintext and a ciphertext match is bounded.

Now, we recall the Fujisaki-Okamoto paradigm: Given an OW-CPA and Γ-uniform asymmetric cipher Asym with public (resp. private) key K _p (resp. K _s ), a one-time secure symmetric cipher Sym, and two random oracles G and H, the following construction is IND-CCA secure in the random oracle model:

Note that the check done at Step ?? during the decryption is necessary to obtain an IND-CCA secure scheme.

To use this construction with TCHo, we need to show that TCHo is Γ-uniform.

Lemma 7.4.

TCHo is ${\left ((1 + \gamma )/2\right )}^{\mathcal{l}}$ -uniform.

Proof.

Recall that the TCHo encryption of x is $y = C(x) +\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}({r}_{1}) +\mathrm{ {S}}_{\gamma }^{\mathcal{l}}({r}_{2})$, for random coins r ₁ and r ₂. We need to bound the probability (taken over r ₁ and r ₂) that a given plaintext x and ciphertext y match. Since in TCHo we consider only positive bias, the most probable ciphertext corresponds to $y = C(x) +\mathrm{ {S}}_{{\mathcal{L}}_{P}}^{\mathcal{l}}$, i.e., when S_γ ^ℓ is the zero bitstring. This happens with probability ${\left ((1 + \gamma )/2\right )}^{\mathcal{l}}$. When we take the average on the possible r ₁, this probability can only decrease. Hence, { TCHo} is ${\left ((1 + \gamma )/2\right )}^{\mathcal{l}}$-uniform.$\square$

Since TCHo is ${\left ((1 + \gamma )/2\right )}^{\mathcal{l}}$-uniform and since IND-CPA security implies OW-CPA security, we can use the Fujisaki-Okamoto paradigm to obtain a IND-CCA secure scheme. An example of a simple one-time secure symmetric cipher one could use is ${\mathsf{Enc}}_{\mathsf{Sym}}(\psi ,m) = m + F(\psi )$ for a random oracle F. We obtain the following cryptosystem:

6 Implementation Results

In this section, we discuss various topics regarding the implementation of TCHo. First we describe a way to find good parameters and give some examples. Next we discuss our heuristic assumption used in the key generation algorithm. Finally, we comment on TCHo software and hardware implementation.

6.1 Parameter Selection

We show now how to find good parameters vectors that can be used for TCHo in practice. Recall from Sect. 7.4.4 that the probability that a message is incorrectly decoded is bounded by ϱ, defined by (7.8). We call this value the unreliability of the system. This value has an huge impact on the ciphertext length and the maximum unreliability accepted ϱ_max has to be selected carefully depending on the application we consider. Recall that the parameters have to verify

$$({w}_{K} - 1)\log \frac{d} {{d}_{\max }} \geq \lambda \qquad \text{ and}\qquad \left({{d}\atop {{{w}_{K} - 1} < {2}^{{d}_{\min }}}}\right)\;$$

from Assumption 7.2 and

$${d}_{\min }\log \frac{1} {\gamma } \geq \lambda \tau \qquad \text{ and}\qquad \gamma \leq {2}^{1-\lambda /{d}_{\min }} - 1,$$

where τ is the root of $\gamma \mathrm{{e}}^{-1} = \tau {2}^{-\tau }$, from Assumption 7.4. We need also to verify

$$\varrho \leq {\varrho }_{\max }.$$

Inequalities in Assumption 7.3 are consequences of the ones in Assumption 7.4 as already observed.

To find the best possible parameters, we used the following approach. We fix first the plaintext length k, the security parameter λ, and ϱ _max , the maximum unreliability accepted, since all these three values will clearly depend on the application we consider and will drastically modify the ciphertext length. Then, we search for the best d _min that minimizes the ciphertext length. Indeed, d _min has a huge impact on the ciphertext length: a too small d _min implies that semantic security is harder to achieve, which leads to a smaller γ and finally to a larger ℓ too keep a tolerable unreliability. Similarly, a too large d _min implies a larger d or w _K , which leads also to a larger ciphertext length. Table 7.1 shows possible parameter vectors for k = 128, 256, 384 and 512 bits. We also set λ = k for 4 of the 5 vectors, since TCHo will mostly be used to encrypt symmetric keys and, hence, should provide at least as much security as the key length.

6.2 Heuristic Assumption for the Key Generation Algorithm

In Sect. 7.4.2, we made the heuristic assumption that the probability for a random sparse polynomial to have an irreducible polynomial factor of degree in [d _min, d _max] is the same than when the polynomial is fully random, i.e., this probability is $O\left (({d}_{\max } - {d}_{\min })/{d}_{\max }\right )$. To verify this heuristic assumption, we made some simulations in which we compared the average number of iterations N needed to generate the public key P with ${d}_{\max }/({d}_{\max } - {d}_{\min })$. The result is depicted in Fig. 7.1. We can see that both distributions are quite similar and, hence, that our heuristic assumption seems reasonable.

Table 7.1 Example of parameter vectors for TCHo

Fig. 7.1

Comparison between ${d}_{\max }/({d}_{\max } - {d}_{\min })$ (continuous line) and the average number of iterations N for the key generation algorithm with parameters k = 128, w _K  = 69, d = 32, 069 and d _min = 4, 800 and using 40 samples (points)

6.3 Software Implementation

TCHo was implemented in software [10] as an extension of Network Security Services (NSS) [48] so that it can be used as a TLS/SSL cipher suite in browsers making use of NSS. One implementation issue concerning the LFSR was raised there. LFSRs are a very efficient component in hardware since a bit can be produced every clock cycle. However, in software, the complexity necessary to compute a bit is proportional to the weight of the feedback polynomial used to describe the LFSR. Hence, for TCHo, this complexity is proportional to w _P , the weight of the public key. Note that ${w}_{P} = {d}_{P}/2$ in average.

The trivial software implementation can be improved by considering blocks of outputs instead of a single bit. Typically, the size of the block b will be a small multiple of the machine word size. Then, using methods described in [16, 17], it is possible to obtain a cost of Ow _P  ∕ b operations per bit. However, the cost needed to compute the output of the LFSR is still large and dominates the cost of encryption.

This issue shows that TCHo is meant to be a hardware-oriented cipher and is, hence, less efficient in software.

Table 7.2 shows performances for the first three parameter vectors of TCHo presented in Table 7.1. These results were performed on a 2.66 GHz Core 2 Duo with a C++ implementation using the NTL library [63].

6.4 Hardware Implementation

We discuss in this section how to implement the encryption and the decryption in hardware.

Table 7.2 Performances of TCHo

For encryption, the implementation of the repetition code is straightforward. The LFSR can be efficiently implemented using integrated circuits. However, the length of the LFSRs we are dealing with is unusually big and we assume that this length does not alter the performances too much. Encryption requires also a biased source of noise. As mentioned in [3], this can be implemented using a precomputed binary tree where each leaf corresponds to a biased sequence of bits. Then, using a uniform random bitstream fed with physical entropy, one can decide which branch to take in the binary tree and output the biased bits.

Decryption is harder to implement. However, the product K ⊗ y consists of a sequence of dot products and can, hence, be implemented using some library able to do linear algebra computations for FPGA devices—for instance [65]. Similarly, such a library can be used to compute C _K ^− 1ψ(m). Majority logic decoding is easy to implement but requires some additional memory—$k \times \log ((\mathcal{l} - d)/k))$—to store the number of occurrences of each bit.

Reference [3] estimates that a 128 bit key with λ = 80 can be encrypted with a circuit of about 10, 000 gates. Hence, TCHo is well suited for RFID.

7 Conclusion

TCHo is still a young cryptosystem and has a large margin of progression. We indicate directions for further work.

Complexity. We are still missing a rigorous complexity analysis about the key generation algorithm, although we have a heuristic complexity matching well experimental results.

A Shorter Ciphertext Length. The use of a repetition code during the encryption process leads to a very simple decryption algorithm. However, the length of the ciphertexts is quite long. A possible solution would be to replace the repetition code with a code with a smaller overhead size.

A More Efficient IND-CCA Scheme. One drawback of the Fujisaki-Okamoto construction is that a TCHo encryption has to be performed during the decryption process. If we neglect the cost of the hash functions, this increases the cost of decryption to $O\left (({w}_{K} + {d}_{P}) \times \mathcal{l} + {k}^{3} + \rho \right )$, where ρ is the complexity of decryption of the symmetric scheme. This complexity can be reduced by using other hybrid constructions like, for instance, REACT [51] or GEM [18]. For this, we need the asymmetric scheme to be OW-PCA-secure, i.e., one-way against an adversary with an plaintext-checking oracle. Hence, we wonder whether TCHo is OW-PCA-secure.

Generalization. Another further work is to generalize the TCHo construction by replacing the LFSR with a random linear code. We wonder also if we can link TCHo to lattice-based cryptography.

In conclusion, TCHo is asymptotically an efficient encryption scheme based on a new hard problem, the low weight polynomial multiple problem. It is IND-CPA secure and can be used to obtain an IND-CCA scheme. However, it still suffers from two drawbacks: the key generation algorithm is expensive and the expansion factor is huge. In this paper, we reviewed the existing previous work on TCHo. We also provided new non-heuristic proofs of correctness and new parameters for different plaintext sizes.