% !TeX spellcheck = hu_HU
%%% Ez az uj piros téma, Van pár overfill hiba. 2009.11.03.
% my_pdfxup -x 1 -y 2 -l 0 KodalapuPosztkvantumKripto_2022_jegyzethez.pdf 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Normál üzemmód, vetítéshez
\documentclass[compress,ucs,handout]{beamer}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{pgfpages}
\pgfpagesuselayout{resize to}[a4paper,landscape,border shrink=5mm]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Szövegfájl típusú nyomtatáshoz
%\documentclass{article}
%\usepackage{beamerarticle,amssymb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>
{
  \usetheme{CambridgeUS}
  \setbeamertemplate{navigation symbols}{}
  \setbeamertemplate{footline}[frame number]
  \setbeamercovered{transparent}
}
\usecolortheme{orchid}
% color themes: albatross, beaver, beetle, **crane, default, dolphin, dov, fly,
% lily, **orchid, rose, seagull, seahorse, sidebartab, structure, whale,
% wolverine
\usefonttheme{serif}
% font themes: default, professionalfonts, serif, structurebold,
% structureitalicserif, structuresmallcapsserif
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{t1enc}
\usepackage{pifont}
\usepackage{txfonts}
\usepackage{mathtools}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[utf8x]{inputenc}

\usepackage[magyar]{babel}
\usepackage{array}
\frenchspacing

\usepackage{color, colortbl}
\usepackage{tikz}
\usetikzlibrary{intersections}
\usetikzlibrary{calc}
\usetikzlibrary{shadows}
\usetikzlibrary{mindmap}
\usetikzlibrary{arrows,decorations.pathreplacing,shapes.misc}
\usepackage{qrcode}
\usepackage{wasysym}
\usepackage{marvosym}

\graphicspath{{pics/}}

\newcommand{\megjegyzes}{\structure{Megjegyzés.} }
\newcommand{\megj}{\structure{Megj.} }
\newcommand{\bizonyitas}{\structure{Bizonyítás.} }
\newcommand{\biz}{\structure{Biz.} }
\newcommand{\megoldas}{\structure{Megoldás.} }
\newcommand{\id}{\mathrm{id}}
\newcommand{\tg}{\mathrm{tg}}
\newcommand{\ctg}{\mathrm{ctg}}

\newcommand{\bm}[1]{\boldsymbol{#1}}
\newcommand\encircle[1]{\raisebox{.2pt}{\textcircled{\raisebox{-.4pt} {\scriptsize$#1$}}}}

\title{Kód alapú posztkvantum kriptográfia}
\subtitle{tudománynépszerűsítő előadás}
\author{Nagy~Gábor~Péter}
\institute[SZTE Bolyai Intézet]{Szegedi Tudományegyetem\\ Bolyai Intézet}
\date[2022]{2022. május 9.}

\subject{Matematika}

\AtBeginSection[]
{
    \begin{frame}
        \frametitle{Tagolás}
        \tableofcontents[currentsection]
    \end{frame}
}

\begin{document}

\setlength{\abovedisplayskip}{6pt plus 3pt minus 6pt}
\setlength{\belowdisplayskip}{6pt plus 3pt minus 6pt}
\setlength{\abovedisplayshortskip}{0pt plus 3pt}
\setlength{\belowdisplayshortskip}{0pt plus 3pt}

%\includeonlyframes{current}

\begin{frame}
  \titlepage
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}
  \frametitle{Tagolás}
  \tableofcontents
  % Die Option [pausesections] könnte nützlich sein.
\end{frame}


\section{Hibajavító kódok}

\subsection{Alapfogalmak}

\begin{frame}{A hibajavító kódok elméletének megalapozása}
\begin{columns}
\begin{column}{6cm}
\begin{center}
\includegraphics[width=5.5cm]{./Richard_Hamming} 
\\\textbf{Richard Hamming} \\(1915-1998) \\amerikai matematikus
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[width=5cm]{./Claude_Shannon} 
\\\textbf{Claude Shannon} \\ (1916-2001) \\amerikai matematikus
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Hibajavítás zajos kommunikációs csatornán}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=east] (A1) at (0,0) {FELADÓ};
\node[drop shadow,rounded rectangle, draw, fill=yellow!60,align=center,inner sep=2mm,anchor=west] (A3) at (7.2,0) {CÍMZETT};
\visible<2->{\node[drop shadow,rectangle, draw, fill=green!20,align=center,inner sep=2mm,anchor=center,above=22mm] (K1) at (A1.north) {KÓDOLÁS};}
\node[drop shadow,rectangle, draw, fill=blue!20,align=center,inner sep=2mm,anchor=center] (A2) at (3.6,3) {ZAJOS\\CSATORNA\\{\LARGE\Lightning\;\Lightning\;\Lightning}};
\visible<3->{\node[drop shadow,rectangle, draw, fill=green!20,align=center,inner sep=2mm,anchor=center,above=22mm] (K2) at (A3.north) {DEKÓDOLÁS};}
\draw [->,thick] (A1) -- node[align=center,left] {küldött\\üzenet} node[right,color=blue] {[\textbf{ABC}]} (K1);
\visible<2->{\draw [->,thick] (K1) -- node[align=center,above] {kódolt\\üzenet} node[below,color=blue] {[\textbf{ABC}|DE]} (A2.west);}
\visible<3->{\draw [->,thick] (A2) to node[align=center,above] {megkapott\\üzenet} node[below,color=blue] {[\textbf{A\color{red}{X}\color{blue}{C}}\color{blue}|DE]} (K2);}
\visible<4->{\draw [->,thick] (K2) to node[align=center,left] {kézbesített\\üzenet} node[right,color=blue,font=\bfseries] {[ABC]} (A3);}
\visible<5->{\node[left] at (A3.west) {\resizebox{10mm}{10mm}{\Smiley}};}
\end{tikzpicture}
\end{center}
\end{frame}


\begin{frame}{Példa: Hibajavítás a QR-kódban}
\begin{center}
\begin{tikzpicture}
\draw (0,0) node {\qrcode[height=3.5cm,level=L]{Introduction\ to\ code-based\ post-quantum\ cryptography\ 2022}};
\draw (6,0) node {\qrcode[height=3.5cm,level=H]{Introduction\ to\ code-based\ post-quantum\ cryptography\ 2022}};
\visible<2>{%
\draw (0,0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (0,-0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (6,0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};
\draw (6,-0.5) node[red,scale=2.4] {\textsf{\textbf{NOISE}}};}
\end{tikzpicture}
\end{center}
\begin{itemize}
\item A QR-kódokban az \alert{$\mathbb{F}_{256}$} véges test felett értelmezett \alert{Reed-Solomon kódokat} használják.
\end{itemize}
\end{frame}

\begin{frame}{Lineáris kódok fő paraméterei}
A továbbiakban $\mathbb{F}_q$ egy $q=p^m$ rendű véges testet jelöl, ahol $p$ prím.
\begin{alertblock}{Definíció: $n$ hosszúságú lineáris kód}
\begin{itemize}
\item A $Q$ \textbf{ábécé} az \alert{$\mathbb{F}_q$} véges test.
\item $C\leq \mathbb{F}_q^n$ egy \alert{lineáris altér.}
\end{itemize}
\end{alertblock}
A főbb paraméterek:
\begin{itemize}
\item \textbf{Hosszúság} $n$
\item \textbf{Dimenzió} $k$
\item \textbf{Információs ráta} $R=k/n$
\item \textbf{Minimum távolság} $d$
%\item \textbf{Dekódolási küszöb} $t$
\end{itemize}
\begin{block}{Singleton-korlát}
$k+d\leq n+1$.
%A \structure{legközelebbi szomszéd} algoritmus dekódolási köszöbe \alert{$t=\lfloor\frac{d-1}{2}\rfloor$.}
\end{block}
\end{frame}

\begin{frame}
\frametitle{A Reed--Solomon-kódok}
\begin{itemize}
\item Legyen \structure{$0\leq k \leq n \leq q$.} Legyenek \structure{$\alpha_1,\ldots,\alpha_n$} az $\mathbb{F}_q$ különböző elemei.
\item \alert{$\mathbf{RS}_k=\{(f(\alpha_1),\ldots,f(\alpha_n) \mid f\in \mathbb{F}_q[X], \deg(f)<k \}$}
\end{itemize}
\begin{block}{Tétel}
\begin{itemize}
\item A Reed--Solomon-kód minimum távolsága \structure{$d=n+1-k$.} 
\item A \textbf{Peterson-algoritmus} ki tud javítani \alert{$\lfloor \frac{n-k}{2}\rfloor=\lfloor \frac{d-1}{2}\rfloor$} hibát.
\end{itemize}
\end{block}
\begin{columns}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=3.5cm]{./Reed_Solomon} 
\\\textbf{Irving S. Reed} (1923-2012) 
\\\textbf{Gustave Solomon} (1930-1996) 
\end{center}
\end{column}
\begin{column}{6cm}
\begin{center}
\includegraphics[height=3.5cm]{./Wesley_Peterson} 
\\\textbf{W. Wesley Peterson} \\ (1924-2009)
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Random kódok}
Nincs annál \textit{könnyebb,} mint jó paraméterekkel rendelkező bináris lineáris kódokat készíteni:
\begin{columns}
\begin{column}{7cm}
\begin{block}{Zajos csatornakódolási tétel (Shannon 1948)}
Értelmezzük a \alert{bináris entrópiafüggvényt:}
\[H(p)=-p\log_2 p-(1-p)\log_2(1-p).\]
Rögzítsük az \structure{$0<R<1$} rátát. Ekkor:
\begin{itemize}
\item kellően nagy $n$ esetén
\item az \alert{$n$ hosszúságú} és \alert{$R$ rátájú}
\item \textbf{``random''} bináris lineáris kód
\item minimum távolsága legalább 
\[\alert{n\cdot H^{-1}(1-R)}.\]
\end{itemize} 
\end{block}
\end{column}
\begin{column}{4cm}
\begin{tikzpicture}[scale=3.2]
%\[H(p)=-p\log_2 p-(1-p)\log_2(1-p).\]
\draw [help lines,color=gray!50] (0,0) grid [step=0.1] (0.7,1);
\draw[very thick] (0,1) node[left] {$1$} -- (0,0) node[below left] {$0$} -- (0.7,0) node[below] {$0.7$};
%\draw[thick,blue] plot [domain=0.001:1,samples=100] (\x,-{\x*log2(\x)-(1-\x)*log2(1-\x)});
\draw[thick,blue] plot [domain=0.001:0.7,samples=100] (\x,{1+\x*log2(\x)+(1-\x)*log2(1-\x)});
\draw (0.35,0) node[below] {$p$};
\draw (0.7,1) node[above] {$1-H(p)$};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}

\subsection{Dekódolási algoritmusok}

\begin{frame}{A hibajavító kódolás}
\begin{itemize}
\item \textbf{Véges ábécé} $Q=\{0,1,\ldots\}$; általában \alert{bináris:} $Q=\{0,1\}$
\item Egy \textbf{$n$ hosszúságú kód} a \structure{ $C\subseteq Q^n$} halmaz részhalmaza
\end{itemize}
\begin{center}
\tikzstyle{place}=[circle,scale=0.5,draw=blue!50,fill=blue!20,thick]
\begin{tikzpicture}[line cap=round,line join=round,>=latex',scale=0.7]
\draw[rounded corners=10,very thick,drop shadow,fill=yellow!30] (-4.5,-1) rectangle (6,6);
\node at (5.4,5.5) [font=\Large] {$Q^n$};
\node (A0) at (-3.76,3.09) [place] {0};
\node (A1) at (-0.5,-0.51) [place] {1};
\node (A2) at (5.34,2.09) [place] {2};
\node (A3) at (1.12,3.67) [place] {3};
\node (A4) at (0.54,5.49) [place] {4};
\node (A5) at (-1.82,1.03) [place] {5};
\node (A6) at (1.84,1.13) [place] {6};
\node (A7) at (-0.06,2.85) [place] {7};
\node (A8) at (3.44,4.17) [place] {8};
\node (A9) at (-1.5,4.37) [place] {9};
\draw[<->] (A3) -- (A8) node[pos=0.5,above] {$d_H$};
\draw[dotted] (A6) circle (1.5);
\draw[thin] (A6) -- +(-30:1.5) node[pos=0.5,above] {$r$};
\draw[thin] (A6)+(30:1.5) node[right] {$B_r(\bm{x})$};
\end{tikzpicture}
\end{center}
\begin{itemize}
\item<1-> Példa: \textbf{3-szoros ismétlő kód:} \alert{$0\mapsto 0|00, \; 1\mapsto 1|11$.}
\item $Q=\{0,1\}$, $C=\{000,111\} \subseteq \{0,1\}^3$.
\end{itemize}
\end{frame}

\begin{frame}{Legközelebbi szomszéd \textit{(maximum likelihood)} dekódolás}
\begin{center}
\tikzstyle{place}=[circle,scale=0.5,draw=blue!50,fill=blue!20,thick]
\begin{tikzpicture}[line cap=round,line join=round,>=latex',scale=0.8]
\draw[rounded corners=10,very thick,drop shadow,fill=yellow!30] (-4.5,-1) rectangle (6,6);
\node at (5.4,5.5) [font=\Large] {$Q^n$};
\node (A0) at (-3.76,3.09) [place] {0};
\node (A1) at (-0.5,-0.51) [place] {1};
\node (A2) at (5.34,2.09) [place] {2};
\node (A3) at (1.12,3.67) [place] {3};
\node (A4) at (0.54,5.49) [place] {4};
\node (A5) at (-1.82,1.03) [place] {5};
\node (A6) at (1.84,1.13) [place] {6};
\node (A7) at (-0.06,2.85) [place] {7};
\node (A8) at (3.44,4.17) [place] {8};
\node (A9) at (-1.5,4.37) [place] {9};
\visible<2->{\node (R) at (2.3,2) [place,draw=red!80,fill=red!50] {y};
\draw[->,red] (3.8,3.5) node[align=center,right] {megkapott\\$y\not\in C$} -- (R);}
\visible<3>{\foreach \x in {0,...,9} \draw[very thin] (A\x) -- (R);};
\visible<4->{\draw[thick,->] (R) -- (A6);
\node[align=center,below right] at (A6) {legközelebbi kódszó\\$x=y-e$};}
\end{tikzpicture}
\end{center}
\begin{itemize}
\item<1->$\textcolor{blue}{0|00,1|00,0|10,0|01} \mapsto 0|00 \mapsto \mathbf{0}$\\ $\textcolor{blue}{1|10,1|01,0|11,1|11} \mapsto 1|11 \mapsto \mathbf{1}.$ 
\item $\mathrm{Prob}(\text{$k$ hiba}) > \mathrm{Prob}(\text{$k$-nál több hiba})$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A dekódolási feladat}
\begin{exampleblock}{A legközelebbi szomszéd dekódolási feladat}
\textbf{Adott:} a \structure{$C\subseteq Q^n$} kód és az \structure{$\bm{y} \in Q^n$} vektor. \\ \smallskip
\textbf{Keresünk:} olyan \structure{$\bm{x}\in C$} kódszót, amire \alert{$d_H(\bm{x},\bm{y})$ minimális.}
\end{exampleblock}
\begin{exampleblock}{A küszöbértékes dekódolási feladat}
\textbf{Adott:} a \structure{$C\subseteq Q^n$} kód, az \structure{$\bm{y} \in Q^n$} vektor és a \structure{$t$} pozitív egész. \\ \smallskip
\textbf{Keresünk:} olyan \structure{$\bm{x}\in C$} kódszót, amire 
\[\alert{d_H(\bm{x},\bm{y})\leq t.}\]
Ha nincs ilyen, akkor az eredmény legyen \textbf{``NINCS''.}
\end{exampleblock}
\begin{itemize}
\item A \textbf{küszöbértékes dekódolás} lényegesen könnyebb a legközelebbi szomszéd dekódolásnál, ha \structure{$t<d(C)/2$.}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A dekódolási feladat lineáris kódokra}
Legyen $C$ \textbf{lineáris kód} a szokásos paraméterekkel: \structure{$q,n,k,d$.}
\begin{itemize}
\item $C$ megadható egy $\mathbb{F}_q$ feletti \alert{$k\times n$} \textbf{generátormátrixszal.} 
\item A generátormátrix $nk$ elemet tartalmaz, tehát a feladat mérete bitben számolva
\[\alert{(nk+n)\log_2(q).}\]
\item Mivel \structure{$k\leq n$,} a feladat méretének nagyságrendjét tekinthetjük \alert{$n^2$-nek.}
\end{itemize}
\begin{block}{Állítás}
\begin{itemize}
\item A \textbf{kimerítéses keresési eljárás} mindkét dekódolási feladatra \alert{exponenciális bonyolultságú} megoldási algoritmust ad az \structure{$n$ paraméterben.} 
\item \alert{Rögzített $q$} mellett a Reed--Solomon-kódok dekódolása \structure{\textit{könnyű.}}
\item A Petersen-algoritmus bonyolultsága \alert{$n$-ben polinomiális.} 
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{A dekódolás \textit{nehéz} --- még a bináris esetben is}
Random bináris lineáris kódok \textit{használhatatlanok}  a gyakorlatban:
\begin{block}{Tétel (Berlekamp, McEliece, van Tilborg, 1978)}
Bináris lineáris kódok esetén a küszöbértékes dekódolási feladat \textbf{\textit{nagyon nehéz}} (\textit{''NP-teljes''}).
\end{block}
\begin{columns}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./McEliece} 
\\\textbf{Robert McEliece} \\(1942-2019) 
\end{center}
\end{column}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./Berlekamp} 
\\\textbf{Elwyn Berlekamp} \\(1940-2019) 
\end{center}
\end{column}
\begin{column}{4cm}
\begin{center}
\includegraphics[height=3.5cm]{./vanTilborg} 
\\\textbf{Henk van Tilborg} \\(1947-) 
\end{center}
\end{column}
\end{columns}
\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}






\subsection{Résztest részkódok}

\begin{frame}
\frametitle{Az általánosított Reed--Solomon-kód}
\begin{alertblock}{Definíció: Általánosított Reed--Solomon-kód}
Legye $q$ prímhatvány, $0\leq k\leq n \leq q$. Legyenek \structure{$\alpha_1,\ldots,\alpha_n$} az $\mathbb{F}_q$ különböző elemei, \structure{$v_,\ldots,v_n$ az $\mathbb{F}_q$} nem nulla elemei.
\[\alert{\mathbf{GRS}_k(\bm{\alpha},\bm{v})=\{(v_1f(\alpha_1),\ldots,v_nf(\alpha_n)) \mid f\in\mathbb{F}_q[X],\, \deg(f)<k\}.}\]
\end{alertblock}
\begin{itemize}
\item A \textit{Reed--Solomon} és az \textit{általánosított Reed--Solomon-kódok} paraméterei \alert{megegyeznek.}
\item A \structure{Peterson-dekódolás} az általános esetben is működik.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Lineáris kódok résztest részkódjai}
\begin{alertblock}{Definíció: Résztest részkód}
Legyen \structure{$q=p^m$ prímhatvány} és \structure{$C\leq \mathbb{F}_q^n$} lineáris kód $\mathbb{F}_q$ felett. Legyen
\[\alert{C|_{\mathbb{F}_q}=C\cap \mathbb{F}_p^n.}\]
Ekkor $C|_{\mathbb{F}_q} \leq \mathbb{F}_p^n$ \textit{lineáris kód} $\mathbb{F}_p$ felett.  
\end{alertblock}
\pause
\begin{itemize}
\item A résztest részkód \structure{minimum távolsága} legalább akkora, mint az eredeti kódé.
\item Az eredeti kód \textbf{dekódolási eljárásai alkalmazhatók} a résztest részkód esetén is
\item Küszöbértékes dekódolás esetén a küszöbérték \alert{megőrződik.} 
\item A résztest részkód \structure{dimenziója} 
\[\dim(C|_{\mathbb{F}_q})\geq n-m(n-k).\]
\item Nagy $m$-re pontatlan a becslés, de \textbf{nehéz} sokkal jobbat mondani.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Reed--Solomon-alapú bináris kódok}
\begin{alertblock}{Definíció: Alternáns kód}
Az általánosított Reed--Solomon-kódok résztest részkódjait \alert{alternáns kódoknak} nevezzük.
\end{alertblock}
\begin{itemize}
\item Az alternáns kód konstrukcióval bináris lineáris kódok egy széles osztályát kapjuk.
\item Ezek paraméterei nem különösebben jók.
\item Nagy előnyük, hogy ismert hozzájuk polinomiális dekódolási eljárás.
\item Tehát megfelelő \structure{$t$ küszöbértékkel} a \alert{dekódolásuk \textit{könnyű}.}
\end{itemize}
\pause
Fontos alternáns kód altípusok:
\begin{itemize}
\item \structure{BCH} \textit{(jól skálázható)}
\item \structure{bináris Goppa} \textit{(a várt küszöbérték duplájáig dekódolható)}
\item \structure{Srivastava}
\end{itemize}
\end{frame}

\definecolor{cadmiumgreen}{rgb}{0.0, 0.42, 0.24}
\definecolor{darkpastelgreen}{rgb}{0.01, 0.75, 0.24}

\begin{frame}
\frametitle{Az $n,k,q$ paraméteres kódok tengere}
\begin{center}
\begin{tikzpicture}
\node at (7.9,6.3) {$n$ hosszúságú, $k$ dimenziós lineáris kódok $\mathbb{F}_q$ felett};
\filldraw[fill=blue!40,rounded corners=20] (0,0) rectangle (12,6);
\node at (6,4) [blue,right,font=\huge] {random kódok};
\filldraw[fill=green!40,rounded corners=5] (0.6,0.5) rectangle (1.5,1.3);
\node at (1.5,1.1) [cadmiumgreen,right,font=\Large] {strukturált kódok};
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}
\frametitle{A strukturált kódok szigete}
\begin{center}
\begin{tikzpicture}
\fill[fill=blue!40] (-1,-1) rectangle (6,6);
\filldraw[fill=green!40,rounded corners=10] (-0.3,-0.3) rectangle (5.3,5.3);
\draw[thick] (-0.3,4.5) -- (-2,4) node[left] {strukturált kódok};
% 2-
\visible<2->{\draw[very thick,dashed] (0.2,0.2) rectangle (4.8,4.8);
\draw[thick] (0.2,4) -- (-2,3) node[left] {kódok gyors dekóderrel};}
% 3-
\visible<3->{\filldraw[fill=gray!40,rounded corners=10] (0.8,0.8) rectangle (3,3);
\draw[thick] (0.8,2.5) -- (-2,2) node[left] {alternáns kódok};}
% 4-
\visible<4->{\filldraw[fill=darkpastelgreen,rounded corners=3] (1.1,1.2) rectangle (1.8,2);
\draw[thick] (1.1,1.5) -- (-2,1) node[left] {bináris Goppa kódok};}
\end{tikzpicture}
\end{center}
\end{frame}

%\begin{frame}
%\frametitle{}
%\begin{itemize}
%\item 
%\end{itemize}
%\end{frame}


\section{Kód alapú kriptográfia}

\subsection{Klasszikus McEliece}

\begin{frame}
\frametitle{A McEliece-féle kriptoséma (1978)}
Tegyük fel, hogy \structure{Alice} egy $k$ bites \alert{$\bm{m}\in \mathbb{F}_2^k$} titkos üzenetet akar \structure{Bobnak} küldeni.

%\textbf{Kulcs generálás}
\begin{exampleblock}{Kulcs generálás}
\begin{enumerate} [<+->]
\item Bob választ egy kellően nagy \structure{$q=2^m$} $2$-hatványt, \structure{$k<n\leq q$} egészt és \structure{$t$ küszöbszámot} úgy, hogy a megfelelő paraméterekkel rendelkező \textbf{alternáns kód} létezik. 
\item Bob választ random \alert{$\alpha_1,\ldots,\alpha_n$} és \alert{$v_1,\ldots,v_n\in \mathbb{F}_q$} elemeket és megkonstruálja a 
\[C=\mathbf{GRS}_k(\bm{\alpha},\bm{v}) \cap \mathbb{F}_2^n\]
bináris alternáns kódot.
\item Bob \structure{képes $t$ hibát javítani} $C$-ben, mert ismeri az \alert{$\alpha_i,v_i$} értékeket. Ezek az értékek alkotják Bob \textbf{privát kulcsát.} 
\item Legyen \structure{$G$} a $C$ egy \textit{generátormátrixa.} Ez Bob \textbf{nyilvános kulcsa,} ezt elküldi Alicenak.
\end{enumerate}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Titkosítás és visszafejtés a McEliece-sémában}
%\textbf{Titkosítás}
\begin{exampleblock}{Titkosítás}
\begin{enumerate} %[<+->]
\item Alice generál egy \textbf{random} \alert{$t$ súlyú} \structure{$n$ hosszú} \alert{$\bm{e}\in\mathbb{F}_2^n$} vektort.
\item Alice kiszámítja az
\[\bm{m}'=\bm{m}G+\bm{e}\]
vektort és elküldi Bobnak.
\end{enumerate}
\end{exampleblock}
%\textbf{Visszafejtés}
\begin{exampleblock}{Visszafejtés}
\begin{enumerate}[<+->]
\item Bob \textit{(polinomiális) dekódolási algoritmusa} meg tudja határozni azt az \textbf{egyetlen} \structure{$\bm{y}\in C$} kódszót, amire
\[d_H(\bm{m'},\bm{y})\leq t.\]
\item Ez pontosan az \alert{$\bm{m}G$} kódszó. 
\item Az
\[\bm{m}G=\bm{y}\]
lineáris egyenletrendszer megoldásával Bob \structure{meghatározza az $\bm{m}$ üzenetet. }
\end{enumerate}
\end{exampleblock}
\end{frame}

\subsection{Kriptoanalízis}

\begin{frame}
\frametitle{A McEliece-séma biztonsági elemzése \textit{(kriptoanalízis)}}
\begin{itemize}
\item \textbf{Privát kulcs:} \alert{$\alpha_1,\ldots,\alpha_n,v_1,\ldots,v_n$.} Ezekből konstruáljuk a \structure{$C$ alternáns kódot.}
\item \textbf{Nyilvános kulcs:} Az alternáns kód \alert{$G$ generátormátrixa.}
\item A séma biztonságos, ha a \structure{nyilvános kulcsból} a \structure{privát kulcs} meghatározása \textbf{nehéz feladat.}
\item Ennél kicsit többet várunk el: $G$ \alert{ne legyen megkülönböztethető} egy hasonló méretű \textbf{random mátrixtól.} 
\item Ekkor a biztonságot garantálja, hogy random mátrix esetén a \structure{dekódolási felada}t \textbf{nehéz} (Berlekamp--McEliece--van Tilborg-tétel).
\item Ehhez az \alert{$n,k,t$} értékeket \textbf{kellően nagyra} kell választani. 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Klasszikus McEliece modern köntösben}
\begin{itemize}
\item McEliece eredeti 1978-as javaslata a \textbf{bináris Goppa kódokra} épül.
\item Ez a \structure{$v_1,\ldots,v_n$} \textit{multiplikátoroknak} egy speciális megválasztását jelenti.
\item Erre az osztályra a mai napig \alert{nem sikerült} a privát kulcs visszafejtése.
\item Az \textbf{eredeti javaslatban} szereplő paraméterek:
\[\alert{n=1014, \quad k=524, \quad t=50.}\]
\item A \textbf{2020-as NIST javaslatban} a legmagasabb 256 bites biztonsági szinthez javasolt paraméterek:
\[\alert{n=6686, \quad k=128, \quad t=13.}\]
\item \textbf{Túl nagy nyilvános kulcs:} \structure{$32$, illetve $836$ kilobyte.} 
\item \textit{Rengeteg ötlet és javaslat a nyilvános kulcs méretének lényeges csökkentésére -- \alert{eddig sikertelenül...}}
\end{itemize}
\end{frame}




\end{document}

