#### 26 lines 2.0 KiB TeX Raw Permalink Blame History

 In the previous chapter, we saw that cryptography has to rely on \emph{computational hardness assumptions}.  Besides \emph{information-theoretic cryptography}, most hardness assumptions are built on top of suitable algebraic structures.  For instance the discrete logarithm assumption (Definition~\ref{de:DLP}) is based on a cyclic group structure.  %That is, in some groups it is assumed that computing the discrete logarithm is an intractable problem for any probabilistic polynomial time algorithms.    The existence of such structures proves useful when it comes to designing protocols.  For this purpose, constructions take advantage of the mathematical properties of the structure to enable the functionality.  An example is the multiplicative homomorphism of the ElGamal cryptosystem which is made possible by underlying cyclic group structure.  %Namely, an El Gamal encryption of a message $M$ under the public key $h = g^\alpha_{} \in \GG$ is a couple $(c_1^{}, c_2^{}) = (g^r_{}, M \cdot h^r_{}) \in \GG^2_{}$, which can be decrypted with the knowledge of the secret key $\alpha \in \Zp$: $M = c_2^{} \cdot c_1^{-\alpha}$.  %Then, the cyclic group structure of $\GG$ leads to the ability to compute a valid ciphertext for $M \cdot M'$ given ciphertexts $(c_1^{}, c_2^{})$ and $(c'_1, c'_2)$ of $M$ and $M'_{}$ respectively.  %The resulting ciphertext is $(c_1^{} \cdot c'_1, c_2^{} \cdot c'_2) = (g^{r \cdot r'_{}}, M \cdot M' \cdot h^{r \cdot r'_{}})$    In this chapter, we describe the different structures on which the cryptographic primitives we design in this thesis are based on, namely bilinear groups and lattices, as well as related hardness assumptions.    \section{Pairing-Based Cryptography}  \addcontentsline{tof}{section}{\protect\numberline{\thesection} Cryptographie à base de couplage}  \label{se:pairings}    \input sec-pairings    \section{Lattice-Based Cryptography}  \addcontentsline{tof}{section}{\protect\numberline{\thesection} Cryptographie à base de réseaux euclidiens}  \label{se:lattices}    \input sec-lattices