\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{arithmetic cryptography}

[[!redirects Arithmetic cryptography]]

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{arithmetic_cryptography}{}\paragraph*{{Arithmetic cryptography}}\label{arithmetic_cryptography}

[[!include analytic geometry -- contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{necessary_tools}{Necessary tools}\dotfill \pageref*{necessary_tools} \linebreak
\noindent\hyperlink{aims}{Aims}\dotfill \pageref*{aims} \linebreak
\noindent\hyperlink{possible_constraints_on_the_theory}{Possible constraints on the theory}\dotfill \pageref*{possible_constraints_on_the_theory} \linebreak
\noindent\hyperlink{possible_methods}{Possible methods}\dotfill \pageref*{possible_methods} \linebreak
\noindent\hyperlink{related_references}{Related references}\dotfill \pageref*{related_references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

Arithmetic cryptography is the developing subject that describes \href{http://en.wikipedia.org/wiki/Public-key_cryptography}{public key} [[cryptography]] systems based on the use of arithmetic geometry of schemes (or [[global analytic spaces]]) over $\mathbb{Z}$.

There are two well known examples of such systems:

\begin{enumerate}%
\item The first and most used one, which is very efficient \textbf{because} it is conformal to the \href{http://en.wikipedia.org/wiki/KISS_principle}{KISS principle}, is based on the fact that it is very difficult (from the computational viewpoint) to factorize a natural number into a product of two big prime numbers.


\item The second one is based on the \href{http://en.wikipedia.org/wiki/Discrete_logarithm}{discrete logarithm} problem on elliptic curves (or more generally abelian varieties) over finite fields. It has the advantage on the first algorithm of allowing to make shorter keys, without compromising security (NSA has generalized the use of \href{http://en.wikipedia.org/wiki/Elliptic_curve_cryptography}{elliptic curve cryptography} algorithm both for commercial and classified use, as explained on the wikipedia page on elliptic curve cryptography).



\end{enumerate}
The basic idea of arithmetic cryptography is to use a finite family $X$ of polynomials with integer coefficients $P_1,\dots,P_m\in \mathbb{Z}[X_1,\dots,X_n]$ (or more generally a quasi-projective scheme $X$ of finite type over $\mathbb{Z}$, or even maybe a [[global analytic space]] $X$ over a convenient Banach ring), encoded in a finite number of integers (the coefficients and degrees of the corresponding polynomials), together with some additional data (such as a way to cut a part of the associated motive) to define a \href{http://en.wikipedia.org/wiki/Public-key_cryptography}{public key cryptosystem}.

Some computational aspects of general motives have been investigated in the case of motives of modular forms by Bass Edixhoven and Jean-Marc Couveignes, using \'e{}tale cohomological methods. Kedlaya and Lauder-Wan also studied the Dwork approach from a computational viewpoint.

\hypertarget{necessary_tools}{}\subsection*{{Necessary tools}}\label{necessary_tools}

Since the space $X$ to be used is given by a non-linear equation, it is not directly adapted to the use of computational methods. One will thus need to extract linear invariants from $X$, by the use of a kind of `differential calculus' (in Quillen's sense, i.e., using a convenient [[tangent (infinity,1)-category]]) and/or the definition of convenient `cohomological invariants.

It seems that \'e{}tale cohomological methods, that were originally used by Grothendieck and Deligne (and more recently, Laumon) to prove the full Weil conjectures, are not so easy to implement on a computer (see however the book of Edixhoven and Couveignes). It seems that ``[[p-adic]] methods'', based on p-adic differential calculus and Fourier transform, and now completely developed by Berthelot, Lestum, Caro and Kedlaya (p-adic proof of the Weil-conjectures) are better adapted to computations (e.g., of L-functions over finite fields, i.e., characteristic polynomials of frobenius acting on cohomology).

It thus looks like an important project to develop ``[[p-adic]] methods'' in [[global analytic geometry]], starting with the definition of two types of cohomology theories for [[global analytic spaces]]: an [[absolute cohomology]] theory (related to the Chern character from K-theory to negative cyclic cohomology) and a [[geometric cohomology]] theory (with characteristic $0$ coefficients, e.g., in the full ring $\mathbb{A}$) of ad\`e{}les). It may also be interesting to develop a notion of [[global Fourier transform]].

One of these cohomology theories (the absolute one) should give a natural way to study various conjectures on [[special values of L-functions]] and the other (the geometric one) should give a natural way to study the position of zeroes and poles of L-functions by spectral methods.

The [[geometric cohomology theory]] should also be (since it has characteristic $0$ coefficients) related to the theory of motives and [[global automorphic representations]], and thus give more generally a spectral way of studying zeroes and poles of the L-function of the rational motive of an [[arithmetic variety]].

\hypertarget{aims}{}\subsection*{{Aims}}\label{aims}

The aim of arithmetic cryptography is to define a good [[geometric cohomology]] theory for [[global analytic spaces]] based on analytic methods and differential calculus that would allow the definition of \href{http://en.wikipedia.org/wiki/Public-key_cryptography}{public key cryptography} systems based on the datum of a [[global analytic space]] $X$ and of (say) a part $M$ of the associated (maybe absolute) rational motive $M(X)$. The definition of such methods would not give any new attacks to the previous ones, but may give a bigger class of public keys, that may allow the use of shorter ones. However, it is not yet clear that such a general approach will be conformal to the \href{http://en.wikipedia.org/wiki/KISS_principle}{KISS principle}. In particular, as explained by Edixhoven in a preprint, it seems to be quite a hard computational task to determine if two cohomology classes are equal, at least in the $\ell$-adic setting.

\hypertarget{possible_constraints_on_the_theory}{}\subsection*{{Possible constraints on the theory}}\label{possible_constraints_on_the_theory}

The constraints on such a theory would be the following:

\begin{enumerate}%
\item get back the classical discrete logarithm elliptic public key cryptography method when one starts from an elliptic curve over a finite field (or maybe a corresponding weak formal scheme over the ring of p-typical Witt vectors).


\item get back the original prime factorization public key cryptography method when one starts from $\mathbb{Z}$.


\item It must be clearly stressed here that the proper theoretical setting for such a general theory may be very hard to develop, since it should involve the definition of a proper cohomology for the Riemann zeta function, that would allow a spectral proof of its functional equation (as in Tate's thesis) {\colorbox[rgb]{1.00,0.93,1.00}{\tt and}} of the [[Riemann hypothesis]]. The full project thus looks like a very far reaching one, since there is, up to now, no precise idea of a way of constructing such a [[geometric cohomology]] theory (even if ideas on the constraints that it should fulfill are widespread in the mathematical litterature, e.g., in Deninger's work, in the [[field with one element]] litterature, in [[Langlands program]] and in the study of [[Weil-étale cohomology]]). Moreover, the use of adelic coefficients instead of complex ones seems necessary to treat the $p$-adic and archimedean cohomologies on equal footing.


\item One may use the classical GRH conjectures (without proving them) to get the estimates analogous to the classical estimate of the number of primes smaller than a given prime. From this point of view, it seems that representation theoretic approaches may be more interesting.



\end{enumerate}
\hypertarget{possible_methods}{}\subsection*{{Possible methods}}\label{possible_methods}

It is not at all clear that the following propositions will be conformal to the KISS principle. They may also be attacked by quantum computing methods, by higher dimensional generalizations of Shor's algorithm, but one may hope that allowing the use of arbitrary arithmetic schemes may make the quantum computing methods more difficult to apply and/or implement in general. This also means that these propositions may be very hard to implement in practice.

A starting point for crash-testing the compatibility of higher dimensional arithmetic cryptography with the \href{http://en.wikipedia.org/wiki/KISS_principle}{KISS principle} may be to test it in the finite characteristic case (with p-adic methods, say derived analytic spaces over $\mathbb{Z}_p$, for computational purposes). First remark that the discrete logarithm problem for an elliptic curve over $\mathbb{F}_p$ may be understood as a discrete logarithm problem in the first (\'e{}tale torsion) cohomology group of the curve, given by torsion points. One may try to generalize this problem to the higher dimensional situation by giving an algebraic cohomology class $[c]$, and computing $[d]=n.[c]$. The public key is given by the pair $([c],[d])$ and the message is the number $n$. As pointed out by Edixhoven in a preprint, computing a cohomology class may be a very hard computational task, so that this idea may not be conformal to the KISS principle.

One may also devise another ``product type'' approach to the definition of a public key: given two prime cohomology classes $[c]$ and $[d]$ (classes of irreductible subvarieties of a given codimension), compute their product class $[e]=[c].[d]$ in the cohomology ring. One may try, given $[e]$, to find back $[c]$ and $[d]$, and this may be a very hard problem.

\hypertarget{related_references}{}\subsection*{{Related references}}\label{related_references}

Computing zeta functions of arithmetic schemes, David Harvey, \href{http://arxiv.org/abs/1402.3439}{arXiv}



\end{document}