%%%RepresentingHardLatticieswithO(nlogn)bits %%%CJTCS %%%%Apr%28%2008 %%%Latex %%%%%\cikk\stoc05\shortv \documentclass[11pt]{article} %%%\twocolumn %\setlength{\textwidth}{15cm}\hoffset=-3.5cm\voffset=-3cm %%\setlength{\textheight}{12cm}\setlength{\textwidth}{11cm}\voffset=-3.8cm\hoffset=-3.8cm %%\setlength{\textheight}{12cm}\setlength{\textwidth}{20cm}\voffset=-3.8cm\hoffset=-3.8cm \begin{document} \tolerance=10000 \def\rref{\ref} \def\llabel{\label} %%%%%%%%******** \def\nev#1{} %\def\nev#1{\marginpar{\rm [#1]}} %%%%***** %\def\llabel#1{{\label{#1}{\rm{}$\{$#1$\}$}}} %\def\rref#1{{\ref{#1}{\rm{}$\{$#1$\}$}}}%%*** \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{definition}{Definition} \newtheorem{remark}{Remark} %%%\newenvironment{cond} %%%\newtheorem{theorem}{Theorem} %%%\newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}{Conjecture} \newtheorem{cond}{} \renewcommand{\thecond}{{\rm(\arabic{cond})}} \renewcommand{\thedefinition}{{\bf\arabic{definition}}} \renewcommand{\theremark}{{}} \newcounter{bean} \newcounter{remarkbean} \newcommand{\kacsa}{\hangindent=10pt\begin{definition} \rightskip=10pt \rm} \newcommand{\tojas}{\end{definition}\rightskip =0pt } \newcommand{\liba}{\kacsa\uj} \newcommand{\megj}{\hangindent0pt\begin{remark} \rightskip=0pt \rm} \newcommand{\vege}{\end{remark}\rightskip=0pt } \def\uj{{{\addtocounter{bean}{1}{{$\bullet$}{\hskip5pt}}}}} \def\mas{{\addtocounter{remarkbean}{1}{{\bf\theremarkbean.}{\hskip 5pt}}}} \def\iev#1{#1} %%%%\def\enp#1{{\sl Q.E.D.}{#1}} \def\enp#1{{#1}{\rule{8pt}{8pt}}} \def\mev#1{{\bf #1}} \def\halmaz#1{{\lbrace 0,1,...,#1-1 \rbrace}} \def\lapozz{{\vfill\eject}} \def\err{{\bf R}} \def\qu{{\bf Q}} \def\calq{{\cal Q}} \def\cala{{\cal A}} \def\calb{{\cal B}} \def\cald{{\cal D}} \def\calh{{\cal H}} \def\cali{{\cal I}} \def\calj{{\cal J}} \def\calu{{\cal U}} \def\calm{{\cal M}} \def\caln{{\cal N}} \def\calv{{\cal V}} \def\cale{{\cal E}} \def\calg{{\cal G}} \def\calc{{\cal C}} \def\calk{{\cal K}} \def\calp{{\cal P}} \def\calq{{\cal Q}} \def\calr{{\cal R}} \def\cals{{\cal S}} \def\calf{{\cal F}} \def\call{{\cal L}} \def\calu{{\cal U}} \def\calv{{\cal V}} \def\calw{{\cal W}} \def\calt{{\cal T}} \def\calz{{\cal Z}} \def\calx{{\cal X}} \def\caly{{\cal Y}} \def\boldp{{\bf P}} \def\boldk{{\bf K}} \def\boldr{{\bf R}} \def\boldz{{\bf Z}} \def\bbfa{{\bar {\bf a}}} \def\bbfb{{\bar {\bf b}}} \def\bbfc{{\bar {\bf c}}} \def\bbfd{{\bar {\bf d}}} \def\bbfe{{\bar {\bf e}}} \def\bbff{{\bar {\bf f}}} \def\bbfg{{\bar {\bf g}}} \def\bbfh{{\bar {\bf h}}} \def\bbfi{{\bar {\bf i}}} \def\bbfj{{\bar {\bf j}}} \def\bbfk{{\bar {\bf k}}} \def\bbfl{{\bar {\bf l}}} \def\bbfm{{\bar {\bf m}}} \def\bbfn{{\bar {\bf n}}} \def\bbfp{{\bar {\bf p}}} \def\bbfq{{\bar {\bf q}}} \def\bbfr{{\bar {\bf r}}} \def\bbfs{{\bar {\bf s}}} \def\bbft{{\bar {\bf t}}} \def\bbfu{{\bar {\bf u}}} \def\bbfw{{\bar {\bf w}}} \def\bbfz{{\bar {\bf z}}} \def\bbfx{{\bar {\bf x}}} \def\bbfy{{\bar {\bf y}}} \def\bbfv{{\bar {\bf v}}} \def\bbfo{{\bar {\bf o}}} \def\bfa{{\bf a}} \def\bfb{{\bf b}} \def\bfc{{\bf c}} \def\bfd{{\bf d}} \def\bfe{{\bf e}} \def\bff{{\bf f}} \def\bfg{{\bf g}} \def\bfh{{\bf h}} \def\bfi{{\bf i}} \def\bfj{{\bf j}} \def\bfk{{\bf k}} \def\bfl{{\bf l}} \def\bfm{{\bf m}} \def\bfn{{\bf n}} \def\bfp{{\bf p}} \def\bfq{{\bf q}} \def\bfr{{\bf r}} \def\bfs{{\bf s}} \def\bft{{\bf t}} \def\bfu{{\bf u}} \def\bfw{{\bf w}} \def\bfz{{\bf z}} \def\bfx{{\bf x}} \def\bfy{{\bf y}} \def\bfv{{\bf v}} \def\bfo{{\bf o}} \def\bfC{{\bf C}} \def\bfO{{\bf O}} \def\bfE{{\bf E}} \def\bfI{{\bf I}} \def\bfJ{{\bf J}} \def\bfW{{\bf W}} \def\bfX{{\bf X}} \def\bfA{{\bf A}} \def\bfB{{\bf B}} \def\bfD{{\bf D}} \def\bfG{{\bf G}} \def\bfH{{\bf H}} \def\bfK{{\bf K}} \def\bfL{{\bf L}} \def\bfM{{\bf M}} \def\bfN{{\bf N}} \def\bfO{{\bf O}} \def\bfP{{\bf P}} \def\bfQ{{\bf Q}} \def\bfR{{\bf R}} \def\bfS{{\bf S}} \def\bfT{{\bf T}} \def\bfU{{\bf U}} \def\bfV{{\bf V}} \def\bfY{{\bf Y}} \def\bfZ{{\bf Z}} \def\bbfC{{\bar{\bf C}}} \def\bbfO{{\bar{\bf O}}} \def\bbfE{{\bar{\bf E}}} \def\bbfI{{\bar{\bf I}}} \def\bbfJ{{\bar{\bf J}}} \def\bbfW{{\bar{\bf W}}} \def\bbfX{{\bar{\bf X}}} \def\bbfA{{\bar{\bf A}}} \def\bbfB{{\bar{\bf B}}} \def\bbfD{{\bar{\bf D}}} \def\bbfG{{\bar{\bf G}}} \def\bbfH{{\bar{\bf H}}} \def\bbfK{{\bar{\bf K}}} \def\bbfL{{\bar{\bf L}}} \def\bbfM{{\bar{\bf M}}} \def\bbfN{{\bar{\bf N}}} \def\bbfO{{\bar{\bf O}}} \def\bbfP{{\bar{\bf P}}} \def\bbfQ{{\bar{\bf Q}}} \def\bbfR{{\bar{\bf R}}} \def\bbfS{{\bar{\bf S}}} \def\bbfT{{\bar{\bf T}}} \def\bbfU{{\bar{\bf U}}} \def\bbfV{{\bar{\bf V}}} \def\bbfY{{\bar{\bf Y}}} \def\bbfZ{{\bar{\bf Z}}} \def\bcall{{\bar{\cal L}}} \def\barv{{\bar{V}}} %%%\def\llabel#1{{\label{#1}{\rm [#1]}}} %%%\def\llabel{\label} %%%\def\rref#1{{\ref{#1}{\rm [#1]}}} %%%\def\rref{\ref} \def\phi{\varphi} \def\theta{\vartheta} \def\epsilon{\varepsilon} \def\barxi{\bar{\xi}} \def\barf{\bar{f}} \def\ccbc{{\call\cup\bar\call}} \def\length{{\tt length}} \def\state{{\tt state}} \def\symb{{\tt symb}} \def\send{{\tt send}} \def\arity{{\tt arity}} \def\range{{\tt range}} \def\u{\underline} \def\domain{{\tt domain}} \def\func{{\tt func}} \def\rel{{\tt rel}} \def\dir{{\tt dir}} %%%%%%\def\int#1{{\lbrace 1,\ldots ,#1\rbrace}} \def\depth{{\tt depth}} \def\bin{{\tt bin}} \def\pow{{\tt pow}} \def\dist{{\tt dist}} \def\prob{{\tt prob}} \def\val{{\tt value}} \def\mod{{\rm mod}} \def\base{{\tt base}} \def\prog{{\tt progress}} \def\bcks{{\backslash}} \def\vol{{\tt vol}} \def\var{{\tt var}} \def\term{{\tt term}} \def\head{{\tt head}} \def\transition{{\tt transition}} \def\inp{{\tt input}} \def\INP{{\tt INPUT}} \def\ch{{\tt ch}} \def\toutput{{\tt t.output}} \def\ntoutput{{\tt nt.output}} \def\tinput{{\tt t.input}} \def\ntinput{{\tt nt.input}} \def\outp{{\tt output}} \def\ioact{{\tt ioact}} \def\mem{{\tt mem}} \def\ido{{\tt time}} \def\idoo{\overline{\tt time}} \def\act{{\tt act.user}} \def\norm{{\tt norm}} \def\snormal{{\tt snormal}} \def\bfD{{\bf D}} \def\bfm{{\bf m}} \def\bfI{{\bf I}} \def\bff{{\bf f}} \def\reg {{\tt reg}} \def\register {{\tt register}} \def\cont {{\tt cont}} \def\ccont {\overline{\tt cont}} \def\universe {{\tt universe}} \def\next {{\tt next}} \def\hely {{\tt space}} \def\helyy {\overline{\tt space}} \def\ido {{\tt time}} \def\inset {{\tt inset}} \def\outset {{\tt outset}} \def\exec {{\tt exec}} \def\calrv{{\cal \calr'}} \def\seq{{\tt seq}} \def\func{{\tt func}} \def\ispace{{\tt ispace}} \def\ospace{{\tt ospace}} \def\tospace{{\tt tospace}} \def\toutp{{\tt toutput}} \def\timecount{{\tt timecount}} \def\decltime{{\tt decltime}} \def\declmem{{\tt declmem}} \def\source{{\tt source}} \def\hchain{{\tt h.chain}} \def\tchain{{\tt t.chain}} \def\pointer{{\tt pointer}} \def\sender{{\tt sender}} \def\receiver{{\tt receiver}} \def\partial{{\tt partial}} \def\accum{{\tt accum}} \def\ex{{\tt ex}} \def\attach{{\tt attach}} \def\detach{{\tt detach}} \def\owner{{\tt owner}} \def\previousblock{{\tt previousblock}} \def\length{{\tt length}} \def\inst{{\tt inst}} \def\zee{{\bf Z}} \def\lattice{{\tt lattice}} \def\inv{{\tt inv}} \def\rect{{\tt rect}} \def\cube{{\tt cube}} \def\part{{\tt part}} \def\fr{{\tt fr}} \def\ltort{{\lbrack\!\lbrack}} \def\rtort{{\rbrack\!\rbrack}} \def\lfrac{{\langle\!\langle}} \def\rfrac{{\rangle\!\rangle}} \def\size{{\rm size}} \def\distance{{\rm distance}} %%%%%12345678 %\pagestyle{myheadings} %\markboth{\today\hfil${\rm \backslash %cikk\backslash stoc05\backslash shortv}$} %{\today\hfil ${\rm %\backslash cikk\backslash %stoc05\backslash shortv}$ } %\pagestyle{myheadings} \markboth{\today\hfil${\rm \backslash %cikk\backslash kz\backslash korkz}$} {\today\hfil ${\rm \backslash %cikk\backslash kz\backslash korkz}$ } \title{ Representing Hard Lattices with $O(n\log n)$ Bits \footnote{ \rm A preliminary version of this paper has appeared in the Proceedings of the 37th ACM Symposium on Theory of Computing, see \cite{Ajtai}} } \author{\bf Mikl\'os Ajtai \\ IBM Almaden Research Center} \date{} \maketitle \begin{abstract} We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only $O(n \log n)$ bits and the encrypted text/clear text ratio is also $O(n \log n)$. This is true with the assumption that all of the participants in the cryptosystem share $O(n^{2}\log n)$ random bits which have to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. The public key is a random lattice with an $n^{c}$-unique nonzero shortest vector, where the constant $c>{1\over 2}$ can be picked arbitrarily close to ${1\over 2}$, and we pick the lattice according to a distribution described in the paper. We do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of an average-case diophantine approximation problem related to a well-known theorem of Dirichlet. \nev{5245} \end{abstract} \vskip 10 pt \section{Introduction} \subsection{Cryptosystems based on the hardness of the unique shortest vector problem} The first public-key cryptosystem based on the assumed hardness of the unique shortest vector problem was given by Ajtai and Dwork in \cite{AD}. In that paper three variants of the system have been provided. The present work is based on the second version of the system where the public key is a random lattice $L$ with a distribution $\sigma$ so that $L$ has an $n^{c}$-unique nonzero shortest vector with high probability. ($u$ is an $\alpha$-unique nonzero shortest vector of $L$ if $u\in L$, $u\not=0$ and for every $v\in L$, $\Vert v\Vert\le \alpha \Vert u\Vert $ implies that $v$ and $u$ are parallel.) The public key is a random basis of $L$ picked from a large cube. (In \cite{AD} actually the dual of $L$ is used as a public key.) It is proved in \cite{AD} that if the distribution $\sigma$ has the property that a polynomial time algorithm cannot find a nonzero shortest vector in $L$ with a polynomially large probability then the cryptosystem is secure. (For this version of the cryptosystem, there is no specific recommendation for $\sigma$, it works with any distribution $\sigma$ with the property decsribed in the previous sentence.) In this paper we define a distribution $\sigma$ which meets this requirement provided that an average-case diophantine approximation problem, related to a famous theorem of Dirichlet has no polynomial time solution. Moreover in the new system the public key consists of only $O(n \log n)$ bits and we encrypt a single bit by $O(n \log n)$ bits. (In the second system described in \cite{AD} the key has at least $n^{2}\log n$ bits. Systems with worst-case average case connection, the third system in \cite{AD} and Regev's system in \cite{Regev}, have key sizes $O(n^{4})$. The number of encrypted bits needed for a clear text bit is $O(n^{2}\log n)$ in the second version of the Ajtai-Dwork system and $O(n\log n)$ in the first version, where the lattice is represented with a basis of polynomial length. In the systems with worst-case average case equivalence this number is at least $O(n^{3})$.) The small key size of the present system is achieved in the following way. The randomization of $L$ according to $\sigma$ is done in two stages. In the first stage we randomize a sequence $b$ of $O(n^{2}\log n)$ bits. The randomization of $b$ is done only once and $b$ is available for every participants of the system. Assume now that $b$ is fixed. In the second stage of the randomization the only information that we have about the first-stage is the value of $b$. We pick a random sequence $t$ (with a distribution defined later) consisting of $O(n \log n)$ bits. $b$ and $t$ together will determine a lattice $L(b,t)$ which has an $n^{c}$-unique shortest vector (with high probability). The crucial property of the second stage of the randomization is that it can be done together with randomizing an $n^{c}$-unique nonzero shortest vector $u$ in the lattice. \nev{4020} With such a randomization a participant of the system is able to select the public key $t$ together with the private key $u$. Since $t$ determines the lattice $L(b,t)$ for a fixed publicly known $b$, $t$ indeed can serve as the public key instead of a basis of the lattice $L(b,t)$. The present paper consists of the description of the distribution $\sigma$ and the proof that it has all of the required properties. \nev{4021} The constant $c$ (in the $n^{c}$-uniqueness) may have any value greater than ${1\over 2}$. This improvement on the original $c>5$ of the second system of \cite{AD} can be proved by adapting the original proof of \cite{AD}, about the second system, to the techniques introduced by Regev in \cite{Regev} that are based on a lemma of Banaszczyk (see \cite{Banaszczyk}). Regev has improved the same constant to $c=1.5$ for cryptosystems whose security is based on the hardness of the worst-case $n^{c}$-unique shortest vector problem, where the previous best value was $c=7$. In his system encryption and decryption are done by arithmetic on the real line, instead of the $n$-dimensional space. We do not use this part of Regev's improvement. The improvement in $c$ in our cryptosystem is independent of the improvement in the size of the key and holds for any distribution $\sigma$ so that the $n^{c}$-unique shortest vector problem is hard. Therefore the contribution of the present paper is the improvement in the size of the key. \nev{5246} This last improvement in the value of the constant $c$ is possible only if we change the value of a parameter in the second cryptosystem of \cite{AD}. This is not an essential change in the cryptosystem, conceptually it works the same way as before. Yet, the original proof of the reduction of the security of the cryptosystem to the $n^{c}$-unique shortest vector problem about the lattices involved, does not remain valid without any modification. In the last section we will give a modified proof about the security of cryptosystem, namely we will show that if $\sigma$ is an arbitrary distribution which takes its values on lattices with an $n^{c}$-unique shortest vector so that for this distribution the shortest vector problem is hard, then our cryptosystem using lattices generated with distribution $\sigma$ is secure. The modified proof (described in the last section) has the same overall structure as the original one. We include it here partly to make the paper more self-contained and partly because it is very difficult to check the correctness of the modified proof if only the original proof and a list of the necessary changes are given. \nev{8040} \subsection{Notation, preliminaries} We will use the \enp{}\ \ symbol to denote the end of the proof of a theorem or a lemma, e.g. the end of the proof of Lemma X will be denoted by \enp{(Lemma X)} \kacsa \uj $\err$ denotes the set of realnumbers, and $\zee$ denotes the set of integers, and $\qu$ denotes the set of rationals. \nev{8001} \uj Assume that $\alpha\in \err$, $\ltort \alpha \rtort$ will denote the smallest nonnegative realnumber so that there is an integer $k$ with $|k-\alpha|= \ltort \alpha \rtort$. In other words, $ \ltort \alpha \rtort $ is the distance of $\alpha$ from the closest integer. \nev{3021} \uj Assume that $\alpha$ is a realnumber and $g$ is a positive integer. Let $j$ be the unique integer so that ${j\over g}\le \alpha <{j+1 \over g}$. We will use the notation $\fr(\alpha,g)={j\over g} $. \nev{1005} \uj If $a\in \err^{n}$ then $\Vert a\Vert_{p} $ will denote the $\ell_{p}$ norm of the vector $a$ and we will use the notation $\Vert a\Vert$ for the Euclidean norm. We will use without further references the inequalities $\Vert a\Vert_{\infty} \le$ $ \Vert a\Vert_{2} \le $ $ n^{1\over 2}\Vert a\Vert_{\infty} $ \nev{1140} \uj If $a_{1},...,a_{n}$ are linearly independent vectors in $\err^{n}$ then the set of their linear combinations with integer coefficients is called a lattice. $a_{1},...,a_{n}$ is a basis of the lattice. A lattice may have several different bases. The volume of the parallelepiped defined by the basis vectors is the determinant of the lattice. The dual $L^{*}$ of the lattice $L$ is the set of all $x\in \err^{n}$ so that $xa\in Z$ for all $a\in L$, where $xa$ is the inner product of the vectors $x$ and $a$. $L^{*}$ is a lattice in $\err^{n}$. \nev{8014} \uj We say that $u$ is a shortest nonzero vector (sh.n.v.) in the lattice $L$ if $u\in L$, $u\not=0$ and for all $v\in L$, $v\not=0$ we have $\Vert v\Vert\ge \Vert u\Vert $. Assume $\alpha>1$. The vector $u$ is an $\alpha$-unique shortest nonzero vector of $L$, if it is a shortest nonzero vector in $L$, and for all $v\in L$, $\Vert v\Vert \le \alpha \Vert u\Vert $ implies that $v$ and $u$ are parallel. (In this definition we may use the $\ell_{p}$ norm $\Vert a\Vert_{p} $ for each $a\in L$ instead of the Euclidean norm. This way we get the definition of an $\alpha$-unique sh.n.v. with respect to the $\ell_{p}$ norm.) \nev{8012} \uj $e_{1},...,e_{n}$ will denote the unit vectors in $\err^{n}$, that is, for all $i=1,...,n$ the $i$th component of $e_{i} $ is $1$, all of the other components of $e_{i}$ are $0$s. \nev{1004} \uj If $a_{1},...,a_{n}$ is a basis of $L$ then the unique basis $f_{1},...,f_{n}$ of $L^{*}$ so that for all $i=1,...,n$, $a_{i} f_{i}=1$ and for all $i,j\in \lbrace 1,...,n\rbrace $ with $i\not=j$, $a_{i} f_{j}=0$, is called the dual of $ a_{1},...,a_{n} $. (See e.g. \cite{MG} for further details.) \uj If $a_{1},...,a_{n}$ are linearly independent vectors in $\err^{n}$, then $\calp(a_{1},...,a_{n})$ is the set of all vectors of the form $ \sum_{i=1}^{n}\alpha_{i}a_{i}$ where $\alpha_{i}\in [0,1)$ for all $i=1,...,n$. \nev{5247} \tojas Most of the computational problems are usually formulated for lattices $L\subseteq \zee^{n}$. For the formulation of our results of algorithmic nature we will use lattices in ${\bf Q}^{n}$. This is not an essential difference (only a difference in scaling) since for every lattice $L\subseteq {\bf Q}^{n}$ there is an integer $k$ so that $kL\subseteq \zee^{n}$. Some of our results were motivated by consideration about lattices in $\err^{n}$, e.g. when the components of the vectors generating the lattice are random reals taken with uniform distribution from an interval. In this case we will formulate the result both over the reals (and after a suitable approximation) over the rationals. \nev{8010} {\bf Computational questions involving realnumbers.} In the formulation of our main result (in particular in the hardness assumption) we will allow realnumbers as inputs. We will treat this situation in a simple way described in the definition below, which is good for this particular purpose, although it is not a good solution for the treatment of real input in general. In the last section, we will need a more sophisticated approach to this problem. We will use there (only in the last section) the oracle representation of reals as it has been defined by Lov\'asz in \cite{Lovasz}. The definition below will be used only in the Hardness Assumption. \nev{8011} \liba We will allow realnumbers as inputs for our algorithms. We assume the each realnumber occurring in the input is in the interval $[0,1]$. Every realnumber is represented by the sequence of its binary bits. The algorithm can read these bits only in their natural order and reading one bit is considered as one unit of time. Therefore a polynomial time algorithm can read only a polynomial size initial segment from the sequence of binary bits of a realnumber. \nev{3100} \tojas \subsection{Highlevel description of the proposed cryptosystem} We describe now the second cryptosystem from \cite{AD} incorporating the following improvements: (a) the reduction in the size of the key which is the topic of the present paper. (b) an improved definition of the perturbation of lattice points by normal distribution as defined by Regev in \cite{Regev}, which makes possible the mentioned improvement in $c$. The original perturbation in \cite{AD} was an approximation of a normal distribution with different parameters. We may change the parameters since Regev's results based on Banaszczyk's lemma makes it possible to reach the same conclusions with the new values as with the original ones. (c) a simplified way of representing the encrypted text, by representing each point $x$ in $\err^{n}$ by an $x'\in \calp(a_{1},...,a_{n})$ with the property $x-x'\in L^{*}$, where $a_{1},...,a_{n}$ is a basis of $L^{*}$, instead of taking $x$ from a large cube. This improvement was introduced by Micciancio in \cite{Micciancio1}. Later we will describe a further improvement on the method of encryption introduced by Goldreich, Goldwasser, and Halevi in \cite{GGH}, but first we describe the system with the encryption method used in \cite{AD}. \nev{6248} The participants of the cryptosystem share the following information. (i) An integer $n$ which is the dimension of the lattices used by the cryptosystem, the constants $c={1\over 2}+\epsilon'>{1\over 2}$ and $\beta>0$. (ii) A random sequence of integers $b$ which altogether contains no more then $O(n^{2}\log n)$ bits and which is chosen according to a distribution that we describe later. (iii) A deterministic polynomial time algorithm $\calb$ which, if $b$ and a sequence of integers $t$ are given as input, computes a basis $B(b,t)$ of a lattice $L(b,t)$. (iv) A probabilistic polynomial time algorithm $\cald$ which given $b$ as an input generates $t$ and $u$, where $t$ is a random sequence of integers (with the distribution determined by $\cald$) so that the total number of bits in $t$ is $O(n \log n)$ and, with a probability exponentially close to $1$, $u$ is an $n^{c}$-unique sh.n.v. of $L(b,t)$ with $(n-1)^{{1\over 2}-\beta-\epsilon'} \le \Vert u\Vert \le 2(n-1)^{{1\over 2}-\beta} $, where the probability is taken for the randomization of $t$ only while $b$ is considered as fixed. Moreover if our Hardness Assumption holds (we will describe it later), then there is no polynomial time probabilistic algorithm which finds a sh.n.v. in $L(b,t)$ with polynomially large probability, with respect to the same randomization and the random steps of the algorithm together. \nev{6249} Sometimes it will be more convenient to consider instead of the lattice $L(b,t)$ a normalized version of it. Assume that a a constant $\epsilon> 0$ is fixed with $\epsilon'<{1\over 12} \epsilon$. The normalized version of $L(t,b)$ will the lattice $\tilde L(b,t)=n^{-({1\over 2}-\beta)-{\epsilon \over 3}}L(b,t)$. If $\tilde u$ is a shortest nonzero vector in $\tilde L(b,t)$ then $n^{-{\epsilon \over 2}}\le \Vert \tilde u\Vert \le n^{-{\epsilon \over 3}} $. \nev{8020} \megj \mas We are not able to guarantee that the algorithm $\cald$ satisfies property (iv) with an arbitrarily chosen fixed $b$. Still we will show that (iii) holds with a probability exponentially close to $1$ for the randomization of $b$. \nev{6250} \mas If $b$ is computed by a pseudo random number generator, then the proof of security (based on the Hardness Assumption) breaks down, since a potential attacker knows the seed of this generator. Indeed the pseudo random generator provides a $b$ so that for all polynomial time test $T$, if $T(b')=1$ with high probability for a random $b'$, then $T(b)=1$ with high probability with the pseudo random $b$ as well. (This guarantees that everything that we can prove about a random $b'$ will also hold for the pseudo random $b$.) However, by the definition of a pseudo random number generator, the test $T $ has this property only if the seed of the pseudo random number generator is not available for it. In other words, for an attacker who knows the seed, the sequences $b$ will not look like a random sequence, so he may be able to utilize some of its non-random properties. In spite of these potential dangers of a pseudo random $b$, it seems that if we use, for example, the binary bits of $\pi$ as $b$, perhaps we do not increase the risk of failure too much. \nev{6252} \vege The sequence $b$ and the algorithms $\calb$, and $\cald$ must be known for all of the participants of the system. We may assume that e.g. they are all part of the software implementing the system. Assume now that all of the participants are already in the possession of the sequence $b$ and the algorithms $\calb$ and $\cald$. Under these circumstances the selection of the public keys and encryption/decryption of the messages is done in the following way. \nev{6253} Selection of the public key. The participant $A$ of the system generates a random $t_{A}$ together with a sh.n.v. $u$ in $L(b,t_{A})$ using algorithm $\cald$. The public key is $t_{A}$. The private key is $u$. \nev{6254} \leftskip=10pt \rightskip=10pt {\bf Encryption.} To encrypt a $0,1$-bit $x$, to be sent to $A$, the following steps are needed. (a) Determine $f_{1},...,f_{n}$, the dual of $B(b,t)$. This is a basis of the lattice $L^{*}$. (b) if $x=0$ then let $y$ be a random point chosen from the parallelepiped $\calp(f_{1},...,f_{n})$ with uniform distribution. If $x=1$ then compute a random point $z$ in $\err^{n}$ with the normal distribution whose density function is $e^{-\pi \Vert x\Vert^{2} }$ for $x\in \err^{n}$, and determine the unique element $y$ of the parallelepiped $\calp(f_{1},...,f_{n})$ so that $y-z\in L^{*} $. Find a rational approximation $\bar y_{i}$ of each coefficient of the vector $y=\langle y_{1},...,y_{n}\rangle $ so that the denominator of $\bar y_{i}$ is $n$ and $|y_{i}-\bar y_{i}|< {1\over n} $. The vector $\bar y =\langle \bar y_{1},...,\bar y_{n}\rangle $ is the encrypted message. \nev{6255} {\bf Decryption.} $A$ determines the inner product $\alpha= \bar y u$ and the closest integer $k_{\alpha}$ to $\alpha$. If $|\alpha - k_{\alpha}| \ge \tilde c (\log n)^{1\over 2}$ then $x=0$ otherwise $x=1$, where $\tilde c$ is a large constant. \nev{5291} \leftskip=0pt \rightskip=0pt We will call the described public key cryptosystem System I. Its method of encryption has the disadvantage that with a probability of $p=2 \tilde c (\log n)^{1\over 2} \Vert u\Vert $ the decryption may be wrong. Since $n^{-{\epsilon \over 2}}\le \Vert u\Vert \le n^{-{\epsilon \over 3}} $, $p$ may be about $2 \tilde c (\log n)^{1\over 2} n^{-{\epsilon \over 3}}$. Indeed if $x=0$ then it may happen with a probability of $2 \tilde c (\log n)^{1\over 2} \Vert u\Vert $that the point $y$ chosen with uniform distribution from $\calp$ is closer than $ \tilde c (\log n)^{1\over 2} $ to a hyperplane $\lbrace w\in \err^{n}\ |\ wu=k \rbrace $ where $k\in \zee$. (The distance of neighboring hyperplanes of this type is $\Vert u\Vert^{-1}$). In this case the message $\bar y$ will be decrypted as $1$. The probability of an error of the other type when a bit $1$ is decrypted as a $0$ is less than $n^{-c'}$, where $c'$ is about ${\tilde c}^{2}$. Therefore with the right choice of $\tilde c$ we can make this probability less than polynomial. \nev{5292} An improved way of encryption, introduced by Goldreich, Goldwasser, and Halevi in \cite{GGH} eliminates the described error. (Alternatively we may use error correcting codes, but this makes the system less efficient in terms of the lengths of the messages and the computational time.) Their solution is the following. Assume that $u$ is an $\alpha$-unique sh.n.v. in $L$ where $\alpha>1$. The bit $x=0$ is represented by a perturbation $y=a+z$ of a lattice point $a\in L^{*}$, so that the inner product $a u$ is even, while for $x=1$, $a u $ is odd. More precisely the new protocol will be the following: \nev{5248} \vskip 5 pt \leftskip=10pt \rightskip=10pt {\bf Selection of the public key.} The participant $A$ of the system generates a random $t_{A}$ together with a sh.n.v. $u$ in $L(b,t_{A})$ using algorithm $\cald$. The public key is a pair $\langle t_{A},j_{A} \rangle$, where $j_{A}\in \lbrace 1,...,n\rbrace $ so that if $f_{1},...,f_{n}$ is the dual of the basis $B(b,t)$ then $f_{j_{A}} u$ is odd. The private key is $u$. \nev{5254} {\bf Encryption.} To encrypt a $0,1$-bit $x$, to be sent to $A$, the following steps are needed. (a) Determine $f_{1},...,f_{n}$, the dual of $B(b,t)$. This is a basis of the lattice $L^{*}$. (b) if $x=0$ let $s=0\in \err^{n}$ if $x=1$ then let $s=f_{j_{A}}$. Compute a random point $z$ in $\err^{n}$ with the normal distribution whose density function is $e^{-\pi \Vert w\Vert^{2} }$ for $w\in \err^{n}$, and determine the unique element $y$ of the parallelepiped $\calp(2f_{1},...,2f_{n})$ so that $y-(s+z)\in 2L^{*} $. Find a rational approximation $\bar y_{i}$ of each coefficient of the vector $y=\langle y_{1},...,y_{n}\rangle $ so that the denominator of $\bar y_{i}$ is $n$ and $|y_{i}-\bar y_{i}|< {1\over n} $. The vector $\bar y =\langle \bar y_{1},...,\bar y_{n}\rangle $ is the encrypted message. \nev{5255} {\bf Decryption.} $A$ determines the inner product $\alpha= \bar y u$. Let $k_{\alpha}$ be the closest integer to $\alpha $. If $k_{\alpha}$ is even then $x=0$ otherwise $x=1$. \nev{5256} \leftskip=0pt \rightskip=0pt \vskip 5 pt \noindent We will call this public key cryptosystem System II. \nev{5294} \subsection{The values of the efficiency parameters} From the point of view of efficiency the most important parameters are the size of the public key and the ratio between the length of the encrypted text and the clear text. For encrypting a bit, the new system requires almost exactly the same computation than the Ajtai-Dwork cryptosystem or its variants with the various improvements, so we do not discuss this question here. We only note that from the point of view of practical implementations, this is the least problematic part of the systems. {\sl The size of the public key.} Both System I and System II has keys of length $O(n\log n)$. {\sl The length of the encrypted message.} The length of the encrypted messages in System I and System II are about the same and can be estimated in an identical way. The encrypted message is a point of the parallelepiped $\calp=\calp(f_{1},...,f_{n})$ ($\calp(2f_{1},...,2f_{n})$ for System II) whose components are approximated by a precision of ${1\over n}$. Therefore the total number of bits in the encrypted message depends on the lengths of the vectors in $\calp$. Our construction will imply that each element of the basis $B(b,t)$ is of polynomial length. Unfortunately this does not imply that the lengths of the vectors in the dual basis also have a polynomial upper bound. However the special structure of the basis $B(b,t)$ will imply that there is a constant $\bar c$ so that for each $i$, if $f_{i}=\langle \phi_{1}^{(i)},...,\phi_{n}^{(i)}\rangle $ then $|\phi_{j}^{(i)}|\le n^{\bar c}$ for $j=1,...,n-1$ and $|\phi_{n}^{(i)}|\le n^{\bar c n}$. Consequently if $y=\langle y_{1},...,y_{n}\rangle $ is a point of $\calp$ then for all $j=1,...,n-1$, we have $|y_{j}|\le n^{\bar c+1}$ and $|y_{n}|\le n^{\bar c n +1}$. Therefore if $\bar y_{i}={z_{i}\over n}$, and we represent $\bar y_{i}$ by the binary form of the integer $z_{i}$ then for each fixed $j=1,..., n-1 $ the number of bits used is at most $(\bar c+1)\lceil \log_{2}n \rceil +1 $ bits, while for $j=n$ we need at most $(\bar c n+1) \lceil \log_{2}n \rceil+1 $ bits. This implies that the vector $\bar y$ can be encoded with at most $O(n\log n) $ bits. \nev{5257} {\sl The size of the keys in other lattice based cryptosystems.} In all of the cryptosystems where the public key is a lattice presented by an arbitrary basis, the number of bits in the key must be at least $\Omega(n^{2} \log n)$. Indeed there are altogether $n^{2}$ coefficients of the $n$ basis vectors and the way we use an $n^{c}$-unique shortest vector for decoding implies that these numbers must have at least $\Omega(\log n)$ bits. In this paper we save on the number of bits by presenting the lattice with a basis of special structure where the randomization of the coefficients can be done in two stages as mentioned earlier. The public-key systems based on the worst-case hardness of the $n^{c}$-unique sh.n.v. problem, the third Ajtai-Dwork cryptosystem and Regev's cryptosystem use a set of points in $\err^{n}$ resp. $\err$ as public keys. The total number of bits on both cases is $O(n^{4})$. \nev{4000} The improvement in the size of the public keys was possible because the participants share $O(n^{2}\log n)$ random bits. This idea does not seem to be applicable to the other mentioned cryptosystems. We need the specific properties of the lattices, that we use in the cryptosystem presented in this paper, for cutting the randomization into two part. It is not clear whether there is any analogue process in the case of the other systems. \nev{8002} \subsection{Lattice based cryptosystems of other types} There are other possibilities to construct lattices with cryptographic applications which can be represented by relatively few bits. Micciancio proved a worst-case average-case connection for cyclic lattices (see \cite{Micciancio}) which leads to a one-way function with $O(n\log n)$ key-size. For a description of the advantages and disadvantages of cyclic versus general lattices see \cite{Micciancio}. Another lattice based system with small key-size is the commercial system NTRU (see \cite{NTRU}). The security of the cryptographic tools provided by either cyclic lattices or NTRU is not reduced to the hardness of an algorithmic problem in a well studied area of mathematics (like our hardness assumption.) On the other hand our approach, unlike the mentioned applications based on cyclic lattices does not have a worst-case average-case connection. \nev{4001} \vskip 10pt \section{ The Hardness Assumption} First we formulate the diophantine approximation problem that we will call our Hardness Assumption, and then we will describe the way of generating the lattices which will serve as keys in the public key system. \nev{1203} The following well-known theorem was proved by Dirichlet in 1842 (see \cite{Schmidt}). \nev{3022} \vskip 5 pt {\bf Theorem A} (Dirichlet) {\sl If $\alpha_{1},...,\alpha_{n}$ are realnumbers in the interval $(0,1)$ and $M>0$ is an integer, then there is an integer $m\in [1,M^{n}]$ so that for all $i=1,...,n$ we have $\ltort m\alpha_{i}\rtort \le {1\over M}$. \nev{1210} } \vskip 5 pt The theorem holds even if $M$ is not necessarily an integer (see \cite{Schmidt}). The proof is an application of the pigeonhole principle, and so it does not give an efficient way to find an integer $m$ with the described property. We will be interested in algorithmic questions related to this theorem. Namely, we will be concerned with the case when $M=n^{c_{1}}$ and a positive integer $m$ exists so that for all $i=1,...,n$, $\ltort m\alpha_{i}\rtort \le n^{-c_{2}}M^{-1} $, where $c_{1}>0,c_{2}>0$ are constants and $n$ is sufficiently large. Our hardness assumption will state that even if the numbers $\alpha_{1},...,\alpha_{n}$ are chosen at random with the condition that there is such an $m$, still there is no efficient algorithm for finding the integer $m$. \nev{3023} {\bf Hardness Assumption.} {\sl For all $c>0,c'>0$, $c_{1}>0,c_{2}>0$ and for all probabilistic algorithms $\cala$ the following holds: if $n$ is sufficiently large and $\cala$ provides an output in time $n^{c_{1}}$ then the probability that $\cala$ solves Problem {\bf Q1} formulated below is smaller than $n^{-c_{2}}$, where the probability is taken both for the random steps of $\cala$ and the randomization in the formulation of the input. \nev{1211} Problem {\bf Q1}. Assume that $\alpha_{1},...,\alpha_{n}$ are picked at random, independently, and with uniform distribution from the interval $(0,1)$ with the condition that there is an integer $m$ so that \begin{cond} \llabel{CA1} $1\le m\le n^{c n}$ and $\ltort m\alpha_{i}\rtort\le n^{-c-c'} $ for $i=1,...,n$ \nev{1212} \end{cond} Given $n,\alpha_{1},...,\alpha_{n}$, $c,c' $ as input, find an integer $m$ with property \rref{CA1}. \nev{3028}} \megj \mas As we will show later the distribution of the realnumbers $\alpha_{1},...,\alpha_{n}$ described in Problem {\bf Q1} can be generated in polynomial time, together with an integer $m$ satisfying \rref{CA1}. (More precisely we generate an approximation of this distribution with exponentially small error, and, of course, we generate only a polynomial number of bits from the reals $\alpha_{1},...,\alpha_{n}$.) \nev{1213} \mas The assumption that problem {\bf Q1} is hard in the described sense seems reasonable, since in the last one and a half century, after Dirichlet formulated and proved Theorem~{\bfA}, the problem of diophantine approximation was intensively studied in the framework that was created by this and similar theorems formulated due to Dirichlet. The best known algorithm for finding an approximate solution for this type of problems is the $L^{3}$ algorithm given by A.~K.~Lenstra, H.~W.~Lenstra, L.~Lov\'asz in \cite{LLL} which approximates the shortest nonzero vector in a lattice up to an exponentially large factor. (For improvements on the original algorithm see \cite{Schnorr} and \cite{ARS}.) To solve Problem {\bf Q1} by lattice algorithms in a similar sense we would need a polynomial approximating factor. Of course it is possible that the formulated average case problem is easier than the worst-case lattice problem for approximating a shortest nonzero vector by a polynomial factor. Still, the long history of diophantine approximation problems suggests that it is very unlikely that an efficient solution will be found for Problem {\bf Q1}. \nev{1226} \vege \section{The statement of the results} \subsection{The distribution and encoding of the lattices used as public keys} In the definitions below we describe a way to choose $b$ and $t$ at random with the properties necessary for the security of the described cryptosystem. \nev{c501} The random construction will depend on three constants $\beta>0$, $\xi>0$, and $\gamma> \beta+\xi+ 2 $. We will prove our theorems under the additional condition $\beta- {1\over 2}>\xi$. The lattice generated with parameters $\xi,\beta$ will have an $n ^{\beta - \xi-{1\over 2} - \epsilon} $-unique nonzero shortest vector with high probability and the hardness of the lattice will follow from our Hardness Assumption with parameters $c=\xi$ and $c'=\beta-\xi$. For the cryptographic protocol we need a lattice with an $n^{{1\over 2}+\epsilon}$-unique sh.n.v. therefore we have to pick the parameters $\beta,\xi$ with $\beta-1-2\epsilon >\xi$. The number of bits needed to represent a lattice will be $\lceil \gamma n \log_{2} n \rceil$. \nev{1215} First we define a random variable $\kappa$ whose value is a lattice $L$ and another random variable $\bar\kappa$ whose value is a pair $\langle L,u\rangle $ where $L$ is a lattice (with the same distribution as in $\kappa$) and $u\in L$. When defining $\kappa$ we do not specify any representation of the lattice. Our next step will be to show that the lattices which are the values of $\kappa$ can be represented by two sequences of integers $b=\langle b_{1},...,b_{n-1}\rangle $ and $t=\langle t_{1},...,t_{n-1}\rangle $, and the randomization can be performed in two stages first picking the sequence $b$ and then the sequence $t$. After that we will formulate two theorems which say that this way of choosing a random lattice and a vector $u$ in it has the properties described earlier which make it suitable for generating the public and private keys in the cryptosystem. \kacsa \uj Suppose that $X_{i}\subseteq \err$ for $i=1,...,n$. $\prod_{i=1}^{n}X_{i}$ is the set of all $\langle x_{1},...,x_{n}\rangle\in \err^{n} $ with $x_{i}\in X_{i}$ for $i=1,...,n$. If $X\subseteq \err^{n}$ and $\alpha$ is a realnumber then $\alpha X =\lbrace \alpha x\ |\ x\in X \rbrace $. \nev{1290} \uj Suppose that $\lambda>0 $ is a realnumber. $\bfI_{n}(\lambda)$ will denote the set \hfill \break $\lbrace \langle x_{1},...,x_{n}\rangle \in \err^{n} \ | \ \ltort x_{i} \rtort\le \lambda, i=1,...,n \rbrace $ \nev{1003} \uj If $k$ is a positive integer then $\part_{n}(k) $ will denote the partition of the unit cube $[0,1)^{n}$ into subcubes of the form $\prod_{i=1}^{n}[{b_{i}\over k}, {b_{i}+1\over k})$ where $b_{1},...,b_{n}$ are integers with $0\le b_{i} 0, \xi>0$ are constants and $\beta>\xi$. Our Hardness Assumption, with $n\rightarrow n-1$, $c \rightarrow \xi$, $c'\rightarrow \beta- \xi$ implies that a polynomial time algorithm cannot find such an integer $d$ with a polynomially large probability. We want to construct a lattice $L$ depending on $\alpha_{1},...,\alpha_{n-1}$ so that it contains an $n^{c''}$-unique sh.n.v. $u$, for some constant $c''>0$, and in the knowledge of $u$ it is possible to find $d$ in polynomial time. For the moment we will work with vectors with real coefficients and disregard the problem of rounding. The basis of $L$ will be of the form $e_{1},...,e_{n-1},v$ where $$v=\rho e_{n}+ \sum_{i=1}^{n-1} \alpha_{i}e_{i} $$ (the realnumber $\rho>0$ will be defined later.) Assume now that an integer $d\in [1,(n-1)^{\xi(n-1)}]$ is given with $\ltort d\alpha_{i}\rtort \le n^{-\beta} $. Then we have $dv= d\rho e_{n}+ \sum_{i=1}^{n-1}\ltort d\alpha_{i}\rtort e_{i} +\sum_{i=1}^{n-1}a_{i}e_{i}$, where $a_{1},...,a_{n-1}$ are integers. Therefore, if $\rho d\le (n-1)^{-\beta}$ then we have $\Vert u\Vert_{\infty} \le n^{-\beta}$ where $u=dv-\sum_{i=1}^{n-1}a_{i}e_{i}$. To meet this requirement we define $\rho $ by $\rho= (n-1)^{-\xi(n-1)-\beta}$. At this point we know only that $u$ is a short vector with respect to the $\ell_{\infty}$ norm (and if $\beta >{1\over 2}$ then with respect to the Euclidean norm as well). To show the $n^{c''}$-uniqueness of $u$ for some constant $c''>0$ we will investigate the following question. Suppose that we randomize $\alpha_{1},...,\alpha_{n-1}$ as described above. It is possible that with a nonnegligible probability there is an integer $d'\not= d$, $d'\in [1,(n-1)^{\xi(n-1)}]$ so that $d' \ltort \alpha \rtort \le (n-1)^{-\xi(n-1)-c_{1}}$ for some constant $c_{1}>0$. Without further restrictions on $d'$ this really can happen e.g. with $d'=2d$. However if we exclude these type of solutions, which in the lattice would lead only to a short vector parallel to $u$, then the answer is that with a probability exponentially close to $1$ there is no $d'$ with this property. The exact formulation of this and some related statements are given in Lemma \rref{L3}, Lemma \rref{L4}, and Lemma \rref{K3}. These lemmata imply that $u$ is indeed an $n^{c''}$-unique sh.n.v. with high probability. Clearly in the knowledge of $u$ we can find $d$ since $u=dv-\sum_{i=1}^{n-1}a_{i}e_{i}$ and $v,e_{1},...,e_{n-1}$ are linearly independent. \nev{8060} Our next step is to show that this randomization of the lattice $L$ with the basis $e_{1},...,e_{n-1},v$ can be generated together with the vector $u$ in $L$. It is easy to see that this is equivalent of saying that the randomization of the reals $\alpha_{1},...,\alpha_{n-1}$ as defined above can be done together with randomizing a $d$. We prove this by showing, that with high probability, the integer $d$, with the given inequalities is unique, moreover we get the different possible integers $d$ with about the same probability. With a slightly stronger statement, formulated in Lemma \rref{L3}, it is possible to show that if we pick first $d$ with uniform distribution from the integers of $[1,(n-1)^{\xi(n-1)}]$ and then $\alpha_{1},...,\alpha_{n-1}$ with the condition $\ltort d \alpha_{i}\rtort\le (n-1)^{-\beta} $, then we get essentially the same distribution. (See Lemma \rref{L4}.) This randomization yields the vector $u$ while we randomize the lattice. To make the proof simpler we will pick the integer $d $ from the interval $[{1\over 2}(n-1)^{\xi(n-1)},(n-1)^{\xi(n-1)} ]$ (this change in the distribution does not affect our conclusions). \nev{g840} Finally we show how can we cut the randomization in two parts randomizing first $b$ and then $t$. The vector $\alpha_{1},...,\alpha_{n-1}$ is in the unit cube $[0,1)^{n-1}$. First we pick a $Q\in \part_{n-1}(k)$ with uniform distribution where $k=\lfloor (n-1)^{\xi(n-1)-1} \rfloor$ and then we pick $\langle \alpha_{1},...,\alpha_{n-1}\rangle \in Q$ with the condition $\exists d\in [1,(n-1)^{\xi(n-1)}]\forall i, \ltort d\alpha_{i}\rtort\le (n-1)^{-\beta} $. Of course this is a different distribution from the original one since we take into account the condition only in the second part of the randomization. However the choice of $k$ will imply that for each fixed $d$ the probability that $\alpha_{1},...,\alpha_{n-1}$ satisfies the conditions with this fixed $d$ is independent of $Q$ (at least up to a constant factor in the probability). This implies that in the new randomizations the probability of the events change by at most a constant factor which is acceptable for our purposes. Therefore $b$ will be the random $Q$, and $t$ will be the sequence $\alpha_{1},...,\alpha_{n-1}$ picked by the conditional distribution. As we have seen this can be generated by picking first $d$, (which will be denoted by $d$ in the final definition), and then $\alpha_{1},...,\alpha_{n-1}$. Finally to get a finite number of bits we have to round the numbers $\alpha_{i}$. The parameter controlling the precision of the rounding will be the constant $\gamma>0$. \nev{g839} The construction of the lattice $L$ depends on several parameters and also during the construction we use various realnumbers and vectors that are defined (sometimes in a probabilistic sense only) as a function of these parameters. Since all of these reals and vectors will appear repeatedly throughout the definitions and proofs we summarize in Table 1 their most important characteristics. (We have included some inequalities that will have a significance only in our theorems.) These are not definitions, the definitions will be given separately. Table 1 serves only as a reminder. \nev{8020b} \vskip 5pt \begin{table} {\sf \label{tb} \begin{tabular}{ll} $n$ & is the dimension of the lattice \\ $\beta,\gamma,\xi$ & $\beta,\gamma,\xi>0$, $\gamma >\beta+\xi +2$, $\beta > \xi+{1\over 2 }$ \\ $\xi,\beta$ & determine the parameters in the Hardness Assumption \\ & $c=\xi$, $c'=\beta -\xi$ \\ $\gamma$ & determines the precision of rounding \\ $k$ & $=\lfloor (n-1)^{\xi(n-1)-1} \rfloor$, we cut each side of the cube $Q$ into $k$ intervals \\ $Q$ & $=\prod_{i=1}^{n-1}[{b_{i}\over k},{b_{i}+1\over k} )$ \\ $d$ & is a random integer in $[{1\over 2}(n-1)^{-\xi(n-1) },(n-1)^{-\xi(n-1) } ]$ \\ $q$ & is a random point in $ \bfI_{n-1}((n-1)^{-\beta}) \cap d Q$ \\ $v$ & $=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} \fr({q_{i}\over d},kn^{\gamma}) e_{i}$ \\ $L$ & is the lattice generated by $e_{1},...,e_{n-1},v$ \\ $u$ & $=dv+\sum_{i=1}^{n}a_{i}e_{i}$, $\ltort u_{i}\rtort \le (n-1)^{-\beta}$ \\ & $u$ is an $n^{\beta- \xi- {1\over 2} -\epsilon}$-unique shortest nonzero vector in $L$ \end{tabular}} \caption{\sl Frequently ocurring objects in the definition of the lattice $L$. } \end{table} \vskip 5pt \kacsa \uj Suppose that $n\ge 3$, is an integer $\xi>0$, $\beta>0$, $\gamma>0$ are realnumbers, $k=\lfloor (n-1)^{\xi(n-1)-1} \rfloor$ and $ Q\in \part_{n-1}(k)$. We define a random variable $\kappa=\kappa_{n,Q}(\xi,\beta,\gamma)$ whose each value is a lattice $L\subseteq \err^{n}$. First we pick an integer $d$ at random, with uniform distribution from the set of all integers in the interval $[{1\over 2} (n-1)^{\xi(n-1)}, (n-1)^{\xi(n-1)}] $. Then we choose a point $q=\langle q_{1},...,q_{n-1}\rangle \in \err^{n-1} $ with uniform distribution from the set $ \bfI_{n-1}((n-1)^{-\beta}) \cap d Q$. The lattice $L$ is generated by the vectors $e_{1},..., e_{n-1},v$, where $$v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} \fr({q_{i}\over d},kn^{\gamma}) e_{i}$$ Figure 1 illustrates the position of the vector $v$ with respect to the intervals $[{b_{i}\over k}, {b_{i}+1\over k}]$ on the $i$th axis of the coordinate system. \nev{1006} \begin{figure} \llabel{F1} \setlength{\unitlength}{2pt} \begin{picture}(200,80) \thicklines \put(40,10){\vector(1,0){100}}%%$e_{1}$ \put(40,10){\vector(0,1){70}}%%$e_{n}$ \put(40,10){\vector(1,1){40}}%%$e_{2}$ \put(40,10){\vector(2,1){60}}%%$v$ \thinlines \put(70,10){\line(1,1){25}} \put(90,10){\line(1,1){25}} \put(55,25){\line(1,0){50}} \put(65,35){\line(1,0){50}} \put(100,30){\line(0,1){10}} \thicklines \put(145,10){$e_{1}$} \put(45,80){$e_{n}$} \put(85,50){$e_{2}$} \put(103,40){$v$} %\put(75,3){$Q_{1}=[{b_{1}\over{k}},{b_{1}+1\over k}]$} \put(65,3){${b_{1}\over k}$} \put(85,3){${b_{1}+1\over k}$} %\put(70,30){$Q_{2}$} \put(45,25){${b_{2}\over k}$} \put(53,35){${b_{2}+1\over k}$} \end{picture} \caption{\sf The orthogonal projection of the vector $v$ to the $\ n-1$ dimensional subspace generated by $e_{1},...,e_{n-1}$ is in a cube whose each side is of length $1\over k$. We achieve the savings in the number of bits representing the lattice, by restricting the projection of $v$ to this small cube.} \end{figure} \uj We define a random variable $\bar \kappa_{Q,n}(\xi,\beta,\gamma)$. First we pick a lattice $L$ according to distribution $\kappa_{Q,n}(\xi,\beta,\gamma)$. Assume that $L$ is a value of the random variable and $d$ is the integer and $v$ is the basis vector chosen during the randomization of $L$. We choose the integers $a_{1},...,a_{n-1}$ so that $-{1\over 2}\le e_{i} (dv -\sum _{i=1}^{n-1}a_{i}e_{i})< {1\over 2} $ for $i=1,...,n-1$. The value of the random variable $\bar \kappa_{Q,n}(\xi,\beta,\gamma)$ is the pair $\langle L,u\rangle $ where $u= dv -\sum _{i=1}^{n-1}a_{i}e_{i} $. \nev{1244} \tojas \megj \mas The definition of $\kappa$ and $\bar \kappa$ imply that with high probability $\Vert u\Vert_{\infty} \le (n-1)^{-\beta} $. (The probability is not $1$ because of the rounding involved in the definition of $v$, that is, the substitution of ${q_{i} \over d}$ by $\fr({q_{i}\over d_{i}},k n^{\gamma})$.) As we will show later, under some conditions on the parameters involved, with high probability, $u$ is a shortest nonzero vector of the lattice $L$. \nev{1291} \vege \begin{lemma} \llabel{L1} Suppose that $n\ge 3$ is an integer, $\xi>0$, $\beta>0$, $\gamma>0$ are realnumbers, $k= \lfloor (n-1)^{\xi(n-1)-1} \rfloor $, $b_{1},...,b_{n-1}\in [0,k-1]$ are integers, $ Q=\calq_{k}(b_{1},...,b_{n-1}) $, $L$ is a random value of $\kappa_{n,Q}(\xi,\beta,\gamma)$, $L$ is generated by $e_{1},..., e_{n-1}$, and $$v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} \fr({q_{i}\over d},kn^{\gamma}) e_{i}$$ where $d,q_{i}$ were selected as described in the definition of $\kappa$. \nev{1292} Then $v$ can be written in the form $$v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} ({b_{i}\over k}+{t_{i}\over kn^{\gamma}}) e_{i}$$ where $t_{i}$ is an integer and $0\le t_{i} < n^{\gamma}$. Moreover the integers $t_{i}$ with the stated conditions are uniquely determined by the lattice $L$. Consequently if $n,\xi,\beta,\gamma$ and $Q=\calq_{k}(b_{1},...,b_{n-1})$ are fixed, then every value $L$ of the random variable $\kappa_{n,Q}(\xi,\beta,\gamma)$ has a unique representation by at most $ n \lceil \gamma \log_{2} n \rceil$ bits. \nev{1293} \end{lemma} \nev{1010} {\bf Proof.} By definition we have that $\langle q_{1},...,q_{n-1}\rangle \in dQ =d\prod_{i=1}^{n-1}[{b_{i}\over k},{b_{i}+1 \over k}) $. Therefore ${q_{i}\over d}\in [{b_{i}\over k},{b_{i}+1 \over k})=$ $ [{b_{i}n^{\gamma}\over kn^{\gamma}},{(b_{i}+1)n^{\gamma} \over kn^{\gamma} }) $ for all $i=1,...,n$. Consequently the definition of $\fr({q_{i}\over d},kn^{\gamma})$ implies that $\fr({q_{i}\over d},kn^{\gamma})={b_{i}n^{\gamma} \over k n^{\gamma} }+{t_{i}\over kn^{\gamma}}$ for a suitably chosen integer $t_{i}$ in the interval $[0,n^{\gamma})$. \nev{1011} To prove the uniqueness of the sequence $t_{1},...,t_{n-1}$ assume that $t_{1}^{(j)},...,t_{n-1}^{(j)}$, $j=1,2$ are sequences of integers so that both for $j=1$ and for $j=2$, $e_{1},...,e_{n-1}$, $v^{(j)}=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} ({b_{i}\over k}+{t_{i}^{(j)}\over kn^{\gamma}}) e_{i}$ is a basis of $L$ and $0\le t_{i}< n^{\gamma}$. This implies that $v^{(1)}-v^{(2)}=\sum_{i=1}^{n-1} {t_{i}^{(1)}-t_{i}^{(2)}\over kn^{\gamma}} e_{i} $ is an element of $L$ and therefore ${t_{i}^{(1)}-t_{i}^{(2)}\over kn^{\gamma}}$ are integers for $i=1,...,n-1$. Since $k>1$ and $0\le t_{i}^{(j)}< n^{\gamma}$, this implies $t_{i}^{(1)}=t_{i}^{(2)}$. \nev{1011.5} The lattice $L$ can be represented by the binary bits of the nonnegative integers $t_{i}$. Everything else in the basis $e_{1},...,e_{n-1}$, $v$ depends only on parameters whose values has been fixed. \nev{1012} \enp{(Lemma \rref{L1})} \kacsa \uj Suppose that $n,Q,\xi,\beta,\gamma$, satisfy the conditions of the definition of $\kappa_{n,Q}(\xi,\beta,\gamma)$. We define a random variable $\tau_{n,Q}(\xi,\beta,\gamma)$ in the following way. First we pick a lattice $L$ with distribution $\kappa_{n,Q}(\xi,\beta,\gamma)$. As we have seen in Lemma \rref{L1} the lattice $L$ uniquely determines the sequence of integers $t_{1},...,t_{n-1}$ so that $0\le t_{i} < n^{\gamma}$ and $e_{1},...,e_{n-1}$, $(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} ({b_{i}\over k}+{t_{i}\over kn^{\gamma}}) e_{i}$ is a basis of $L$. The sequence $\langle t_{1},...,t_{n-1}\rangle $ is the value of $\tau_{n,Q}(\xi,\beta,\gamma)$. If $t_{1},...,t_{n-1}$ are given then the corresponding lattice $L$ will be denoted by $\call(t_{1},...,t_{n-1}, b_{1},...,b_{n-1},\xi,\beta,\gamma)$. With our earlier notation if $\xi,\beta$ and $\gamma$ are fixed, $b=\langle b_{1},...,b_{n-1}\rangle $, $t=\langle t_{1},...,t_{n-1}\rangle $ then $ L(b,t)= \call(t_{1},...,t_{n-1}, b_{1},...,b_{n-1},\xi,\beta,\gamma) $ \nev{1030} \uj We define a random variable $\bar \tau_{Q,n}(\xi,\beta,\gamma)$. First we take a random value $\langle L,u\rangle $ of $\bar \kappa_{Q,n}(\xi,\beta,\gamma) $. From the lattice $L$ we define the sequence of integers $t_{1},...,t_{n-1}$ the same way as in the definition of $\tau_{Q,n}(\xi,\beta,\gamma)$. The value of the random variable is the pair $\langle \langle t_{1},...,t_{n-1}\rangle, u \rangle $. \nev{1240} \tojas \megj \mas The only difference between $\kappa,\bar\kappa$ on one hand and $\tau,\bar \tau$ on the other hand is that the values of $\tau,\bar \tau$ give the lattice $L$ a representation by 0,1 bits namely the bits of the integers $t_{1},...,t_{n-1}$. Therefore from a computational point of view the use of $\tau$ and $\bar \tau$ are more appropriate. \nev{1241} \mas It is an immediate consequence of the definitions that if the pair $\langle \langle t_{1},...,t_{n-1}\rangle, u\rangle $ is chosen with distribution $\bar \tau_{Q,n}(\xi,\beta,\gamma)$, then the distribution of $t_{1},...,t_{n-1} $ is $\tau_{Q,n}(\xi,\beta,\gamma)$. The analogue of this observation holds for the random variables $\kappa, \bar \kappa$ as well. \nev{1242} \vege \begin{lemma} \llabel{B1} There is a $ c>0 $ and a probabilistic algorithm $\calf$ with the following properties. Suppose that $n\ge 3$ is an integer, $\xi>0$, $\beta>0$, $\gamma>0$ are realnumbers, $k= \lfloor (n-1)^{\xi(n-1)-1} \rfloor $, $b_{1},...,b_{n-1}\in [0,k-1]$ are integers, $ Q=\calq_{k}(b_{1},...,b_{n-1}) $. Given $n,\xi,\beta,\gamma,b_{1},...,b_{n-1}$ as input, $\calf$ generates in time $n^{c}$ a random variable $\tau'$ so that the distance of the distributions of $\tau'$ and $\bar\tau_{Q,n}(\xi,\beta,\gamma)$ is at most $2^{-n}$.\nev{1243} \end{lemma} The lemma is an immediate consequence of the definition of $\bar \tau$. $\calf $ does not generate $\bar \tau$ exactly because of the rounding errors. $2^{-n}$ can be replaced by $2^{-n^{c'}}$ for any constants $c'>0$, if $c$ may depend on $c'$. \begin{theorem} \llabel{T1} For all realnumbers $\theta> {1\over 2}$ and for all realnumbers $\gamma,\beta ,\xi>0$ with $\gamma>\beta+ \xi+2$, $\beta >\xi+ {1\over 2}$ and for all sufficiently small $\epsilon>0,\epsilon'>0$, if $n$ is sufficiently large then the following holds. Suppose that $\langle b_{1},...,b_{n-1}\rangle $ is a random sequence of positive integers taken independently and with uniform distribution from the interval $[0,k)$, where $k= \lfloor (n-1)^{ \xi(n-1)- 1}\rfloor$, and the sequence $\langle t_{1},...,t_{n-1}\rangle $ is picked at random according to distribution $\tau_{Q,n}(\xi,\beta,\gamma)$, where $Q=\calq_{k}(b_{1},...,b_{n-1})$. Then, with a probability of at least $1- \theta ^{n}$, the lattice $L=\call(t_{1},...,t_{n-1},b_{1},...,b_{n-1}, \xi, \beta, \gamma )$ has an $ n^{\beta -\xi -{1\over 2}- \epsilon}$-unique shortest nonzero vector. Moreover, if $\langle \langle t_{1},...,t_{n-1}\rangle ,u\rangle $ is a random value of $\bar\tau_{Q,n}(\xi,\beta,\gamma)$, then $t_{1},...,t_{n-1}$ has the same distribution as $\tau_{Q,n}(\xi,\beta,\gamma)$, and with a probability of at least $1-\theta^{n}$ the vector $u$ is a shortest nonzero vector in $L=\call(t_{1},...,t_{n-1},b_{1},...,b_{n-1}, \xi, \beta, \gamma )$, with \begin{cond} \llabel{T1.a} $(n-1)^{{1\over 2}-\beta - \epsilon' }\le $ $ \Vert u\Vert\le $ $ 2(n-1)^{{1\over 2}-\beta } $ \nev{1101} \end{cond} and the upper bound in the last inequality holds with probability $1$. \end{theorem} \begin{theorem} \llabel{T2} The following statement is a consequence of the Hardness Assumption. For all realnumbers $ \gamma>\beta>\xi > 0$, with $\beta> \xi+ {1\over 2}$, $\gamma>\beta +\xi+2$ for all $c_{1}>0,c_{2}>0$, and for all probabilistic algorithm $\cala$ if $n$ is sufficiently large and $\cala$ gives an output in time $n^{c_{1}}$, then the probability that $\cala$ solves the problem {\bf Q2} formulated below is smaller than $n^{-c_{2}}$, where the probability is taken both for the random steps of the algorithm and for the randomization in the formulation of the problem. \nev{1102} Problem {\bf Q2}. {\sl Assume that $\langle b_{1},...,b_{n-1}\rangle $ is a random sequence of positive integers taken independently and with uniform distribution from the interval $[0,k)$, where $k= \lfloor (n-1)^{\xi(n-1)- 1}\rfloor $. Suppose further the sequence of integers $\langle t_{1},...,t_{n-1} \rangle $ is picked by distribution $\tau_{Q,n}(\xi,\beta,\gamma)$, where $Q=\calq_{k}(b_{1},...,b_{n-1})$. Find a shortest nonzero vector in the lattice $L=\call(t_{1},...,t_{n-1},b_{1},...,b_{n-1}, \xi, \beta, \gamma )$ }. \nev{1103} \end{theorem} \liba The normalized version of the lattice $L(b,t)$ is $\tilde L(b,t)$ defined by $$\tilde L(b,t)= n^{-{1\over2}+\beta-{\epsilon\over 3}} L(b,t) $$ If we pick $\epsilon'>0$ in Theorem \rref{T1} with $\epsilon'<{1\over 12}\epsilon$ then inequality \rref{T1.a} shows that the unique shortest nonzero vector $\tilde u$ in the lattice $\tilde L(b,t)=n^{-({1\over 2}-\beta)-({\epsilon \over 3})}L(b,t)$ will meet the requirements $n^{-{\epsilon \over 2}}\le $ $ \Vert \tilde u\Vert \le $ $ n^{-{\epsilon \over 3}}$. $\tilde B(b,t)$ will be the basis $\nu e_{1},....,\nu e_{n-1},\nu v$, where $\nu = n^{-{1\over 2}+\beta -{\epsilon \over 3}} $ and $ v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} ({b_{i}\over k}+{t_{i}\over kn^{\gamma}}) e_{i} $ \nev{d612} \tojas \megj \mas As we have seen, from the point of view of efficient encoding of the messages, the size of the coefficients in the dual basis of $B(b,t)$ is of great importance. We may use the following trivial lemma to estimate these coefficients. \nev{d613} \vege \begin{lemma} \llabel{Z2} Assume that $\theta_{1},...,\theta_{n}$ are realnumbers and $\theta_{n}\not= 0$. Then $e_{1},...,e_{n-1}, \sum_{i=1}^{n}\theta_{i}e_{i}$ is a basis of $\err^{n}$ and if $f_{1},...,f_{n}$ is the dual of this basis then $f_{i}=e_{i}-{\theta_{i} \over \theta_{n}}e_{n} $ for $i=1,...,n-1$ and $f_{n}={1\over \theta_{n}}e_{n}$. \nev{d614} \end{lemma} Assume now that $\nu e_{1},...,\nu e_{n-1}, \nu \sum_{i=1}^{n}\theta_{i}e_{i}$ is the basis $\tilde B(b,t)$, where $ \nu = n^{-{1\over 2}+\beta -{\epsilon \over 3}} $. Then the coefficients $\theta_{1},...,\theta_{n-1}$ are in the interval $[0,\nu]$ and $\theta_{n}^{-1}=O(\nu^{-1} 2^{(\xi(n-1)+\beta)\log _{2}n })$. Therefore the lemma implies that the coefficients in the dual basis $f_{1},...,f_{n}$ remain below the bounds required for efficient encoding. \nev{d615} \vskip 10pt Finally we note that our theorems guarantee that for any fixed choice of the values parameters $\beta, \gamma,\xi$, satisfying the inequalities in the table above, if $n$ is sufficiently large and the Hardness Assumption is true, then the corresponding cryptosystem is secure. Of course, this does not tell us anything about the choice of $\beta,\xi,\gamma $ for a particular $n$. For an actual implementation when $n$ is fixed, say $n=1000$, we must pick $\beta$ and $\xi$ in a way that the corresponding Diophantine approximation problem for this particular $n$ cannot be solved in a reasonable amount of time. Our Hardness Assumption, being only an asymptotic statement, does not help in this decision. Like in the case of other Hardness Assumption (e.g. about the hardness of factoring integers), apart from the asymptotic statement, we have to make a more or less arbitrary decision about the value of the parameters where the problem is already hard from a practical point of view. It seems likely that for $n\ge 1000$ the choices $\xi=1$, $\beta=3$, and \nev{8021} $\gamma=6$ meet these requirements. \subsection{The reduction of the security of the cryptosystem to the $n^{c}$-unique shortest vector problem.} The lattice $L(b,t)$, which is used as a public key in our cryptosystem was defined in two steps. First we randomized $b$ and $t$ according to a distribution described in the previous section and then as a function of $b$ and $t$ we have defined the lattice $L(b,t)$. For the results of this section the choice of distribution is not important we will only use the fact that there are constants $c>{1\over 2}$ and $\epsilon \in (0,{1\over 4})$ so that for all sufficiently large $n$ with a probability exponentially close to one the lattice $L=\tilde L(b,t)=n^{-({1\over 2}-\beta)-{\epsilon \over 3}}L(b,t)$ meets the following requirement. \nev{8051} \begin{cond} \llabel{N1} $ L$ has an $n^{c}$ unique nonzero shortest vector $u$ with the property $n^{-{\epsilon\over 2}} \le \Vert u\Vert \le n^{-{\epsilon \over 3 }}$. \nev{8052} \end{cond} We will show that if an algorithm $\cala$ breaks the crytposystem for a participant using a lattice $L$ with property \rref{N1} as the public key, then using this algorithm as an oracle, we can find a nonzero shortest vector in $L$ in polynomial time. Therefore in the same way as in the second cyptosystem of \cite{AD}, our cryptosystem can be used with any distribution $\sigma$ on the set of pairs of integers $\langle b,t \rangle$, provided that the lattice $\tilde L(b,t)$ is defined and satisfies condition \rref{N1} with high probability, and the average case shortest vector problem for the lattices $\tilde L(b,t)$, taken with this distribution, is hard. (As we have mentioned already earlier the proof of this fact is only slightly different from the corresponding proof in \cite{AD}.) More precisely we have the following. \nev{8053} \begin{theorem} \llabel{T3} Supose that $c>{1\over 2}$, $\epsilon \in (0,{1\over 4 })$ and for each $n=1,2,...$, $\sigma_{n}$ is a distribution on pairs of integers $\langle b,t\rangle $ so that for all $c_{2}>0$ there is a $c_{1}>0$ with the following properties \nev{8054} (i) with a probability of at least $1-n^{-c_{1}}$ that lattice $L=\tilde L(b,t)$ is defined and satsifies condition \rref{N1} and \nev{8055} (ii) if $\cala$ is a polynomial time algorithm then for all sufficiently large $n$ with a probability of at least $1-n^{c_{1}}$ the algorithm $\cala$ does not find a nonzero shortest vector in the lattice $L$ if it is presented by the basis $\tilde B(b,t)$. \nev{8056} Then there is no polynomial time algorithm which breaks either system I or system II with a probability of larger than $n^{-c_{2}}$. \end{theorem} \nev{8057} The proof of this theorem togehter with a precise definition of the meaning of ``breaking the cryptosystem" will be given in the last section. \nev{8058} \section{Sketch of the proofs of the theorems} In the motivation for the definition of the random variable $\kappa$ we have already described some of the ideas behind the proofs. Here we give a more detailed and technical outline. We start with Theorem \rref{T1} but a large part of the proof this theorem will be used in the proof of Theorem \rref{T2} as well. According to the definition of the random variable $ \kappa$ the vectors $e_{1},...,e_{n-1},v$ form a basis of the lattice $L$ where $$v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} \fr({q_{i}\over d},kn^{\gamma}) e_{i}$$ The rationals $\fr({q_{i}\over d},kn^{\gamma})$ are good approximations of the reals ${q_{i}\over d}$. Since the numbers $q_{i}$, $i=1,...,n-1$ were picked with the property $\ltort q_{i}\rtort \le (n-1)^{-\beta} $, all of the coefficients $d\fr({q_{i}\over d},kn^{\gamma})e_{i}$ of the vector $dv$ will be either in the interval $[-(n-1)^{-\beta}-n^{-\gamma+1}, (n-1)^{-\beta}+ n^{-\gamma+1}]\subseteq $ $ [-2(n-1)^{-\beta},2(n-1)^{-\beta}] $ \nev{e1030} $u$ was defined as $u=dv-\sum_{i=1}^{n-1}a_{i}e_{i}$ where the integers $a_{i}$ are picked so that the first $n-1$ coefficients the vector $u$ is between $-{1\over 2}$ and ${1\over 2}$. Therefore if $u= \langle u_{1},...,u_{n-1},u_{n}\rangle $ then $ \Vert u_{i}\Vert \le (n-1)^{-\beta}+ n^{-\gamma+1} $ for $i=1,...,n-1$. By definition $u_{n}=d(n-1)^{-\xi(n-1)-\beta}$. Since we choose $d$ from the interval $[ {1\over 2}(n-1)^{\xi(n-1)}, (n-1)^{\xi(n-1)} ]$ we have that $\Vert u_{n}\Vert \le (n-1)^{-\beta}$. Therefore we have $\Vert u\Vert_{\infty}\le (n-1)^{-\beta}+n^{-\gamma+1} $. According to the assumptions in both theorems we have $\gamma>\beta+2$ this upper bound on $\Vert u \Vert_{\infty}$ is very close to $n^{-\beta}$. \nev{e240} Our next goal is to show that $u$ is an $n^{\beta-\xi -{1\over 2} -\epsilon}$-unique sh.n.v. with respect to the Euclidean norm. We will prove this by showing that it is a unique $n^{\beta-\xi- \epsilon }$ shortest vector with respect to the $\ell_{\infty}$ norm. With the change of the norms we lose only a factor of $n^{1\over 2}$. \nev{e420} Assume now that $w\in L$ with $\Vert w\Vert _{\infty}\le n^{-\xi - \epsilon} $. We want to show that $w$ is parallel to $u$. (We will also have to show that $u$ is primitive, that is, none of the vectors ${1\over 2}u,{1\over 3}u,...$ are in $L$.) According to the definition of $L$ we have $w=hv + \sum_{i=1}^{n-1}a_{i}'e_{i} $ where $h,a_{1}',...,a_{n}'$ are integers and $ v=(n-1)^{-\xi(n-1)-\beta}e_{n} +\sum_{i=1}^{n-1} \fr({q_{i}\over d},kn^{\gamma}) e_{i}$. Assume that e.g. $h$ is positive. By the upper bound on $\Vert v\Vert_{\infty} $, the $n$th coordinate of $v$ is at most $h(n-1)^{-\xi(n-1)-\beta}<1 $ therefore $h\le (n-1)^{\xi(n-1)+ \beta}$. The upper bounds on the other components of $w$, taking into account the rounding errors, yield $\ltort h{q_{i}\over d}\rtort \le (n-1)^{-\xi-{\epsilon \over 2}} $. \nev{e519} We show that if $d|h$ and ${h\over d}<{1\over 3}(n-1)^{\beta}$ then the vectors $u$ and $w$ are parallel. Assuming that $d|h$, using the upper bounds $\Vert u\Vert_{\infty}\le (n-1)^{-\beta} +n^{-\gamma +1}\le (1+{1\over 10})(n-1)^{-\beta} $, $h\le (n-1)^{\xi(n-1)+ \beta}$, the equations $u=dv + \sum_{i=1}^{n-1}a_{i}e_{i} $, and $w=hv + \sum_{i=1}^{n-1}a_{i}'e_{i} $ we get that $w={h\over d}u$. (We may easily prove this by using the fact that any lattice point $w=dv+\sum_{i=1}^{n-1}a_{i}'e_{i}$ with $\Vert w\Vert < {1\over 2}$ is uniquely determined by $d$. Therefore, since ${h\over d}u$ is a lattice vector, it must be $w$.) \nev{f1032} So far we have shown that if we pick $d,q_{1},...,q_{n-1}$ with the distribution defined by $\kappa$ then the assumption that there is a $w\in L$ with $\Vert w\Vert _{\infty} \le (n-1)^{-\xi -\epsilon} $ which is not parallel to $u$ implies the following: \nev{f1031} \begin{cond} \llabel{SK1} there is a $h\in [ 1,(n-1)^{\xi(n-1)+\beta} ] $ so that $\ltort h {q_{i}\over d} \rtort \le (n-1)^{-\xi-{\epsilon \over 2}} $, $\ltort d{q_{i}\over d}\rtort = \ltort q_{i}\rtort \le (n-1)^{-\beta} $ and either $d{\not|}h$ or ${h\over d}\ge {1\over 3}(n-1)^{\beta} $ \nev{e524} \end{cond} Assume now that $u$ is not primitive, that is, ${1\over r}u\in L$, for some integer $r\ge 2$. Let $z={1\over r}u$. We have $$z={1\over r}u={d\over r}v - \sum_{i=1}^{n-1}{a_{i}\over r}\ e_{i'}\in L $$ so ${d\over r}$, ${a_{i}\over r}$, $i=1,...,n-1$ must be integers. $h$ will denote now the integer $d\over r$. Since $r\ge 2$ we clearly have $d{\not{|}}h$. Moreover, since each component of $z$ is smaller by a factor of $r$ than the corresponding component of $u$, we get that $\ltort h {q_{i}\over d} \rtort $ $ \le (n-1)^{-\beta}\le $ $ (n-1)^{-\xi-{\epsilon \over 2}} $. Consequently we got that if $u$ is not primitive then condition \rref{SK1} is satisfied. Therefore we have shown that if $u$ is not a unique n.sh.v., then the requirements of \rref{SK1} are met. We have to show that \rref{SK1} holds only with a negligible probability (for the randomization of $d,q_{1},...,q_{n}$). When we speak about the random choice of $d$, and $\langle q_{1},...,q_{n}\rangle $ as defined in the definition of $\kappa_{Q,n}(\xi,\beta,\gamma)$ we consider $n,\xi,\beta$ and $\gamma$ as fixed but we include the randomization of $Q$ in the random choice of $q_{i}$ and $d$. Therefore our conclusion about $w$ will not be valid for all $Q\in \part_{n-1}(k)$ but only for almost all $Q$. \nev{e1103} Let $\Theta$ be the probability measure defined on the Borel subsets of $\zee\times \err^{n-1}$ defined by $\Theta(X) =\prob( \langle d,\langle {q_{1}\over d},...,{q_{n-1}\over d}\rangle \rangle \in X)$, where we randomize $d$, and $\langle q_{1},...,q_{n-1}\rangle $, as described above. \nev{f932} We are not able to prove directly about the distribution $\Theta$ that the probability of \rref{SK1} is small. We will modify $\Theta$ in a way that it will be more manageable and so that the probabilities do not decrease very much. After a sequence of such modifications we get a probability measure $\Theta _{3}$ so that for any event $A$ if $\Theta(A)$ is nonnegligible then $\Theta_{3}(A)$ is also nonnegligible. Therefore it will be enough to show that \rref{SK1} holds with a negligible probability with respect to $\Theta_{3} $. \nev{g3333} We modify the probability measure $\Theta$ by changing the randomization of $d$ and $\langle q_{1},...,q_{n-1}\rangle $. In the original randomization we picked a $Q\in \part_{n-1}(k)$ first and then a $d\in [{1\over 2}(n-1)^{\xi(n-1)}, (n-1)^{\xi(n-1)} ]$ and then a $\langle q_{1},...,q_{n-1}\rangle \in dQ $ so that $\ltort q_{i}\rtort \le (n-1)^{-\beta}$. Each time we picked with uniform distribution from the given set. \nev{g334} The first change is that we do not choose a random $Q$ but, after picking $d$, we choose $\langle q_{1},...,q_{n-1}\rangle $ from $d\bigcup Q=d[0,1)^{n}=[0,d)^{n}$ so that $\ltort q_{i}\rtort \le (n-1)^{-\beta}$. This changes the distribution a little since the $n-1$ dimensional volumes of the sets of points $\lbrace \langle q_{1},...,q_{n-1}\rangle \in Q \ |\ \ltort q_{i}\rtort\le (n-1)^{-\beta} \rbrace $ are slightly different for different cubes $Q$. Still we will show that these differences are not large, so after this change in the randomization the nonnegligible sets remain nonnegligible. \nev{g335} The remaining change is only an extension of the interval from where we pick the integer $d$. Namely we will pick $d$ from the interval $[1,(n-1)^{\xi(n-1)+\beta}]$ with uniform distribution instead of the original $[1,(n-1)^{\xi(n-1)}]$. Since the length of the interval has increased only by a factor of $2(n-1)^{\beta}$ the probabilities of the events may decrease by only with the same factor. Therefore nonnegligible sets remain nonnegligible. \nev{g336} Since we choose the realnumbers $q_{i}$ from the interval $[0,d)$ with the additional condition $\ltort q_{i}\rtort \le (n-1)^{\beta} $, this is the same as if we choose that real $\alpha_{i}={q_{i}\over d}\in [0,1)$ with the additional condition $\ltort d\alpha_{i}\rtort \le (n-1)^{\beta} $. \nev{g337} Therefore we may reformulate the randomization and \rref{SK1} using $\alpha_{i}$ instead of ${q_{i}\over d}$. With this reformulation our goal is the following: \nev{g338} Assume that an integer $d$ is picked with uniform distribution from the interval $[1,(n-1)^{\xi(n-1)+\beta}]$ and the reals $\alpha_{1},...,\alpha_{n-1}$ are picked independently, with uniform distribution and with the condition $\ltort d\alpha_{i}\rtort \le (n-1)^{-\beta} $ from the interval $[0,1)$ for $i=1,...,n-1$. Show that the probability of the following event is small: \nev{g339} \begin{cond} \llabel{SK2} there is a $h\in [ 1,(n-1)^{\xi(n-1)+\beta} ] $ so that $\ltort h {\alpha_{i}} \rtort \le (n-1)^{-\xi-{\epsilon \over 2}} $, $\ltort d{\alpha_{i}}\rtort \le (n-1)^{-\beta} $ and either $d{\not|}h$ or ${h\over d}\ge {1\over 3}(n-1)^{\beta} $ \nev{h856} \end{cond} The next step in the proof is to show that we get essentially the same distribution if instead of randomizing $d$ we pick $\alpha_{1},...,\alpha_{n-1}$ independently, with uniform distribution and with the condition that there is a $j\in [1,(n-1)^{\xi(n-1)+\beta}]$ so that $\ltort j\alpha_{i}\rtort \le (n-1)^{\beta} $ and $d$ is the smallest integer $j$ with this property. (With high probability $j$ is unique.) We will use the following lemma to prove this. \liba Suppose that $\nu_{1},\nu_{2}$ are probability measures on the $\sigma$-algebra $\calx$. The distance of $\nu_{1}$ and $\nu_{2}$ is $\sup \lbrace |\nu_{1}(A)-\nu_{2}(A)| + |\nu_{1}(B)-\nu_{2}(B)| \ |\ A,B\in \calx, A\cap B=\emptyset \rbrace$ \nev{1015} \tojas \begin{lemma} \llabel{L4} Assume that $c_{1}>c_{2}>0$, $\epsilon>0$, $n$ is a sufficiently large integer, $\beta,c\in [c_{2},c_{1}]$ are realnumbers with $\beta-c>c_{2}$. Suppose further that $ \langle \alpha_{1},...,\alpha_{n} \rangle$ are realnumbers taken from the interval $(0,1)$ at random, independently, and with uniform distribution. Let $B$ be the event that there is an $m\in [1,n^{cn}]$ so that $\ltort m \alpha_{i}\rtort \le n^{-\beta}$, for all $i=1,...,n$. Let $D_{1}$ be the conditional distribution of $\alpha_{1},...,\alpha_{n}$ with the condition $B$. We define a probability distribution $D_{2}$ in the following way. First we pick a random integer $m$ with uniform distribution from the interval $[1, n^{cn}]$. Then we choose $\alpha_{1},...,\alpha_{n}$ at random, independently, and with uniform distribution from the interval $(0,1)$ with the condition $\ltort m\alpha\rtort \le n^{-\beta} $. This conditional distribution is $D_{2}$. Then the distance of $D_{1}$ and $D_{2}$ is at most $({1\over 2}+\epsilon)^{n}$ \nev{1055} \end{lemma} We will sketch the proof of this lemma later. Lemma \rref{L4} gives only another way of randomizing the integer $d$ and the realnumbers $\alpha_{i}$ but it does not provide any way to estimate the probability of the existence of the integer $h$ with the properties given in \rref{SK2}. Lemma \rref{K3} below will give such an estimate. \nev{h1127} \begin{lemma} \llabel{K3} Assume that $c_{1}>c_{2}>0$, $\epsilon>0$, $n$ is a sufficiently large integer, $\beta,\rho,c\in [c_{2},c_{1}]$ are realnumbers with $\beta>\rho>c$, $\beta-c>c_{2}$. Suppose further that $\alpha_{1},...,\alpha_{n}$ are realnumbers taken from the interval $(0,1)$ at random independently and with uniform distribution. Let $B$ be the event that there is an $m\in [1,n^{cn}]$ so that $\ltort m \alpha_{i}\rtort \le n^{-\beta}$, for all $i=1,...,n$. \nev{3049} If $k,l$ are positive integers then $q_{k,l}$ will denote the probability of the event \begin{cond} \llabel{K3.1} $k\alpha_{i} \le n^{-\beta}$, $l\alpha_{i}\le n^{-\rho}$ for all $i=1,...,n-1$ \end{cond} Let $\Phi(x)$ be the set of all pairs $\langle k,l\rangle $ with the property that $k,l\in [1,x]$ and if $k$ is a divisor of $l$ then ${l\over k} \ge {1\over 3} n^{\beta}$. Then \begin{cond} \llabel{K3.12} $\sum \lbrace q_{k,l}\ |\ \langle k,l\rangle \in \Phi(n^{cn}) \rbrace \le ({1\over 2}+ \epsilon)^{n}n^{cn}(2n^{-\beta})^{n} $ \nev{1153} \end{cond} Moreover the conditional probability of the event ``$\exists \langle k,l\rangle\in \Phi(n^{cn})$ so that \ref{K3.1} holds" with the condition $B$ is at most $({1\over 2}+\epsilon)^{n}$. \nev{h1043} \end{lemma} Using Lemma \rref{K3} we can show that the probability of \rref{SK2} is smaller than $\theta^{n}$, if $\theta>{1\over 2}$ is a constant and $n$ is sufficiently large. This completes the sketch of the proof of the fact that $u$ is an $n^{\beta-\xi-{1\over2}}$-unique n.sh.v. $u$. The estimate \rref{T1.a} on the length of $\Vert u\Vert $ will follow easily from the fact that if $u=\langle u_{1},...,u_{n}\rangle$ then the random variables $u_{1},...,u_{n-1}$ are independent and their values are in the interval $[-(n-1)^{-\beta}, (n-1)^{\beta}]$. This completes the sketch of the proof of Theorem \rref{T1} \nev{h1042} {\sl Sketch of the proof of Theorem \rref{T2}.} We show that if problem {\bf Q2} in Theorem \rref{T2} has a polynomial time solution with a polynomially large probability then this is also true about Problem {\bf Q1} of he Hardness Assumption. We modify the randomization of $d$ and $q_{1},...,q_{n-1}$ in the same way as we have done it in the proof of Theorem \rref{T1}, with the only difference that now we extend the interval from where we pick the integer $d$ only to $[1, (n-1)^{\xi-1}]$. We get that the modified randomization is the following. We pick the interval $d$ with uniform distribution from $[1, (n-1)^{\xi-1}]$ and then $\alpha_{1},...,\alpha_{n-1}$ with uniform distribution from $[0,1)$ with the condition that $\ltort d\alpha_{i}\rtort \le (n-1)^{-\beta}$ for $i=1,...,n-1$. ($q_{i}$ is defined by $q_{i}=d \alpha_{i}$.) If $\Psi$ is the probability measure defined on the Borel sets $X$ of $d\times \err^{n-1}$ by $\Psi(X)=\prob(\langle d,\langle \alpha_{1},...,\alpha_{n-1}\rangle \rangle \in X)$ then every nonnegligible set with respect the $\Theta$ is also a nonnegligible set with respect to $\Psi$. Using Lemma \rref{L4} we can show that the distribution $\Psi$ is essentially the same (apart from an exponentially small error), as the following distribution: we pick $\alpha_{1},...,\alpha_{n-1}$ independently and with uniform distribution from $[0,1)$ and with the condition that there exists a $j\in [1, (n-1)^{\xi-1}]$ so that $\ltort j\alpha_{i}\rtort\le (n-1)^{-\beta} $, $i=1,...,n-1$, and $d$ is the smallest $j$ with this property. This is however the same distribution that we get from problem {\bf Q1} with parameters $n\rightarrow n-1$, $c\rightarrow \xi$, $c'\rightarrow \beta- \xi$. Therefore if we would be able to find a sh.n.v. $u=\langle u_{1},...,u_{n}\rangle $ in the lattice then we could find the integer $d$ (since $u_{n}=\pm d(n-1)^{-\xi(n-1)-\beta}$) and so the solution of the corresponding problem of Problem {\bf Q1}. This completes the sketch of the proof of Theorem \rref{T2}. \nev{i923} \section {The proof of the main result } \subsection{The proofs of Lemma \rref{L4} and Lemma \rref{K3}} First we sketch the proof of Lemma \rref{L4}. The lemma states that if we randomize the reals $\alpha_{1},...,\alpha_{n}$ with the condition that there is an $m$ so that $\ltort m\alpha_{i}\rtort $ is small then we get the same distribution as if we first pick a value of $m$ with uniform distribution from all of the possible values and then randomize $\alpha_{i}$ with the condition that $ \ltort m\alpha_{i}\rtort $ is small with that particular value of $m$ for all $i=1,...,n$. \nev{i922} Such a switch in the order randomization would be clearly possible if the events $A_{m}\equiv$ "$\ltort m\alpha_{i} \rtort \le n^{-\beta}$ for all $i=1,...,n$'' would be pairwise disjoint for the various values of $m$ and would have the same probability with respect to choosing $\alpha_{1},...,\alpha_{n-1}$ independently, with uniform distribution from $[0,1]$ and without any condition. Only the second statement holds that is the probabilities of the described events are equal, but the first one holds only in an approximate sense. Namely we will prove that the sum of the probabilities of the pairwise intersections of these events is small. Lemma \rref{L5}, that we will formulate later, guarantees that we can reach the desired conclusion even from this approximate version of the condition. (Lemma \rref{L5} is a general statement about probabilities which does not use the specifics of the definition of the events $A_{m}$.) The remaining and more important part of the proof is to show that the events $A_{m}$ are really pairwise disjoint in this approximate sense. The following lemma gives the exact formulation of this statement. \nev{i921} \begin{lemma} \llabel{L3} Assume that $c_{1}>c_{2}>0$, $\epsilon>0$, $n$ is a sufficiently large integer, $\beta,c\in [c_{2},c_{1}]$ are realnumbers with $\beta-c>c_{2}$, and $\alpha_{1},...,\alpha_{n}$ are realnumbers taken from the interval $(0,1)$ at random, independently, and with uniform distribution. Let $B$ be the event that there is an $m\in [1,n^{cn}]$ so that $\ltort m \alpha_{i}\rtort \le n^{-\beta}$, for all $i=1,...,n$. Then \begin{cond} \llabel{L3.05} $P(B)\ge (1- ({1\over 2}+\epsilon)^{n} )(2n^{-\beta})^{n}n^{cn} $ \end{cond} \noindent and the conditional probability, with condition $B$, that there exist $k,l\in [1,n^{cn}]$, $k\not=l$ so that \begin{cond} \llabel{L3.1} $\ltort k \alpha_{i}\rtort \le n^{-\beta}$, $\ltort l \alpha_{i}\rtort \le n^{-\beta} $ for all $i=1,...,n$ \end{cond} is at most $ ({1\over 2}+\epsilon)^{n} $. \nev{1049} Let $p_{k,l}$ be the probability of the event \rref{L3.1}, if $k,l$ are positive integers. Then $p_{1,1}=(2n^{-\beta})^{n}$ and \begin{cond} \llabel{L3.12} $\sum \lbrace p_{k,l}\ |\ k,l\in [1,n^{cn}], k\not=l \rbrace \le ({1\over 2}+ \epsilon)^{n}n^{cn}p_{1,1} $ \end{cond} \end{lemma} We will prove this lemma by showing that ${2\over M}( {2\over N}+ {1\over k})$ is an upper bound on the probability of the event ``$\ltort k\alpha \rtort \le {1\over M} $ and $\ltort l\alpha\rtort \le {1\over N} $" where $k,l$ are fixed integers with $(k,l)=1$, $N,M>1$ are also fixed and $\alpha$ is chosen with uniform distribution from $(0,1)$. Lemma \rref{K2}, that we will formulate later, describes this statement. Using this upper bound we will be able to prove inequality \rref{L3.12} of Lemma \rref{L3}. In \rref{L3.12} we estimate the sum of all of the probabilities $p_{k,l}$ where $p_{k,l}$ is the probability of ``$\ltort k\alpha_{i}\rtort \le n^{-\beta}$ and $\ltort l\alpha_{i}\rtort \le n^{-\beta}$ for all $i=1,...,n$". Here we may have $(k,l)>1$ so Lemma \rref{K2} cannot be applied directly. We group the terms in $\sum p_{k,l}$ according to the value of $(k,l)$. In a fixed group where, $(k,l)=d$ we are able to give an upper bound on the sum using that the distribution of $d\alpha_{i}$ is the same as the distribution of $\alpha _{i}$. This last observation makes it possible to reduce the general case to the $(k,l)=1$ special case and makes Lemma \rref{K2} applicable. We also use the fact that the different reals $\alpha_{i}$ are independent so the corresponding probabilities can be multiplied. This way we get an upper bound for each fixed $d=(k,l)$. The sum of these upper bounds yields the required estimate. The proof of Lemma \rref{L3} goes according to the same ideas. This completes the sketch of the proof of Lemma \rref{L4}, Lemma \rref{L3}, and Lemma \rref{K3}. In the remaining part of this section we give these proofs in detail. \nev{i920} \begin{lemma} \llabel{L1.5} Assume that $M>1$ is an integer, $k$ is a positive integer and $x_{1},x_{2},...$ is a periodic infinite sequence of realnumbers with period $k$, that is, $x_{i}=x_{i+k}$ for all $i=1,2,...$, and \nev{1041} \begin{cond} \llabel{L1.52} $\forall i,j\in [1,k]$, $i\not= j \rightarrow x_{i} \not \equiv x_{j}$ $(\mod \ 1)$. \end{cond} Suppose further that \nev{1042} \begin{cond} \llabel{L1.55} $x_{i+1}-x_{i} \equiv x_{j+1}-x_{j}$ $(\mod \ 1)$ for all $i,j\in \lbrace 1,2,....\rbrace $ \end{cond} Then, the number of integers $i\in [1,k]$ with the property $ \ltort x_{i}\rtort \le {1\over M}$ is at most ${2k\over M}+1$. \nev{1043b} \end{lemma} {\bf Proof.} For $k=1$ the conclusion of the lemma trivially holds so we may assume $k>1$. Let $\pi$ be a permutation of the set $\lbrace 1,...,k\rbrace $, so that $x_{\pi(1)}<...2, N>2$ and $\alpha$ is a realnumber chosen with uniform distribution from the interval $(0,1)$. Let $A$ be the event: $ ``\ltort k\alpha\rtort <{1\over M}$ and $ \ltort l\alpha\rtort \le {1\over N}" $. Then $$\prob(A) \le {2\over M}\Bigl( {2\over N}+ {1\over k}\Bigl)$$ If $M=N$, then $$\prob(A)\le {2\over M}\Bigl({2\over M}+{1\over \max \lbrace k,l \rbrace}\Bigr)$$ \nev{3045} \end{lemma} {\bf Proof.} Let $X=\lbrace x\in [0,1)\ | \ \ltort kx\rtort \le {1\over M} \rbrace $, $Y=\lbrace x\in [0,1)\ | \ \ltort kx\rtort \le {1\over M}, \ltort lx\rtort \le {1\over N} \rbrace $. Clearly $x\in Y$ iff $x\in X$ and $\ltort lx\rtort \le {1\over N} $. $\prob(A)=\lambda(Y)$, where $\lambda$ is the one dimensional Lebesgue measure. \nev{3046} We randomize the number $\alpha$ in the following way. First we pick a random $\beta$ from $[0,1)$ with uniform distribution and then we select an element of the set $\lbrace \beta,\beta+{1\over k},..., \beta+{k-1 \over k} \rbrace$ at random and with uniform distribution. If the selected number is $z$ then $\alpha=z- \lfloor z \rfloor$. Clearly $\alpha$ has uniform distribution on $[0,1)$. We estimate $\prob(A)=\prob(\alpha \in Y)$ in the following way. Let $\lfrac x \rfrac=x- \lfloor x \rfloor$ for all $x\in \err$. The definition of $X$ implies that \nev{c845} \begin{cond} \llabel{K2.0} for a fixed $\beta$ either all of the numbers $\lfrac\beta\rfrac , \lfrac\beta+{1\over k}\rfrac ,...,\lfrac \beta+{k-1 \over k}\rfrac $ are in $X$ or none of them. \nev{c844} \end{cond} This implies that \begin{cond} \llabel{K2.1} $\lambda(X)=k \lambda (X\cap [0,{1\over k}))$ \nev{c835} \end{cond} If $\beta $ has uniform distribution on $[0,1)$ then $\lfrac k\beta \rfrac$ also has uniform distribution on the same interval and therefore $\prob (\beta\in X)\le {2\over M}$ (if $M\ge 2$ then we have equality). We estimate for each fixed $\beta$ with $\beta \in X$ the probability of $\ltort l\alpha\rtort \le {1\over N} $, where according to the definition of the random variable $\alpha$, if $\beta$ is fixed $\alpha$ is picked from the set $\lbrace \beta,\beta+{1\over k},..., \beta+{k-1 \over k} \rbrace $ with uniform distribution. We apply Lemma \rref{L1.5} with $x_{1+j}=l(\beta+{j' \over k})$, $j=0,1,...$, where $j'$ is the least nonnegative residue of $j$ modulo $k$. The assumption $(l,k)=1$ implies that property \rref{L1.52} is satisfied and property \rref{L1.55} is an immediate consequence of the definition of $x_{i}$. Therefore we get that if the number of elements $z$ in the set $\lbrace \beta,\beta+{1\over k},..., \beta+{k-1 \over k} \rbrace $ with $\ltort lz\rtort\le {1\over N} $ is $\nu$, then $\nu \le{2k \over N}+1$. \nev{2230} Let $\chi$ be the characteristic function of the set $Y$ defined on the interval $[0,1)$ and let $T$ be the set $\lbrace 0,{1\over k},...,{k-1 \over k}\rbrace $. We define a measure $\mu$ on the subsets of $T$ by $\mu(S)=|S|$, for all $S\subseteq T$. We have \nev{2231} $\prob(\alpha\in Y)=\lambda(Y)$ $=\int_{0}^{1}\chi(x)dx =$ $\sum_{i=0}^{k-1} \int _{{i\over k}}^{^{i+1\over k}}\chi(x) dx =$ $ \sum_{i=0}^{k-1}\int_{0}^{{1\over k}}\chi(x+{i\over k})dx=$ $\int_{T}\int_{0}^{{1\over k}}\chi(x+y)dx d\mu_{y} $. The function $\chi(x+y)$ is integrable on the product space $T \times [0,1)$ therefore Fubini's theorem (see \cite{Halmos}) implies that the order of integration can be reversed and so $\prob(\alpha\in Y)= \int_{0}^{1\over k}\int_{T}\chi(x+y) d\mu_{y} dx=$ $\int _{X \cap [0,{1\over k})}\int _{T}\chi(x+y) d\mu_{y}dx +$ $\int_{ [0,{1\over k})\bcks X} \int_{T } \chi(x+y) d\mu_{y}dx $. By the definition of $X$ and \rref{K2.0} the second term is $0$. We estimate the first term using our upper bound on $\nu$ and \rref{K2.1}. We get \nev{2232} $\int _{X \cap [0,{1\over k})}\int _{T}\chi(x+y) d\mu_{y}dx \le$ $ \int_{X\cap [0,{1\over k})}({2k\over N} +{1\over k}) dx=$ ${2\over kM}( {2k\over N}+ {1})= $ $ {2\over M}( {2\over N}+ {1\over k}) $ \enp{(Lemma \rref{K2})} %%%%The original place of Lemma L3 {\bf Proof of Lemma \rref{L3}}. Let $d\in [1,n^{cn}]$. We estimate the probability $p_{d}$ of the event that there are $k,l \in [1,n^{cn}]$, $k\not=l$ with $(k,l)=d$ and with property \rref{L3.1}. Since the distribution of $d\alpha_{1},...,d\alpha_{n}$ modulo $1$ is the same as the distribution of $\alpha_{1},...,\alpha_{n}$, $p_{d}$ is also the probability of the following event: there are $k,l \in [1,d^{-1}n^{cn}]$, $k\not=l$ with $(k,l)=1$ and with property \rref{L3.1}. \nev{1050} For each pair of positive integers $k,l$ and for each fixed $i=1,...,n$ let $p_{k,l}^{(i)}$ be the probability of the event described in \rref{L3.1} with this particular $i$. Since the random variables $\alpha_{i}$ are independent, $p_{k,l}=\prod_{i=1}^{n}p_{k,l}^{(i)}$. \nev{1051} Therefore according to Lemma \rref{K2} $p_{k,l}\le (2n^{-\beta}(2n^{-\beta} + {1\over \max \lbrace k,l\rbrace }))^{n}$. \nev{1052} The definition of $p_{d}$ implies that $p_{d}\le \sum \lbrace p_{k,l}\ |\ 1<\max\lbrace k,l\rbrace \le n^{\beta}\rbrace+ $ $ \sum \lbrace p_{k,l}\ |\ \max\lbrace k,l\rbrace > n^{\beta}\rbrace $. The first term is at most $(n^{\beta})^{2}((2n^{-\beta}(2n^{-\beta} +{1\over2} ))^{n}\le $ $(2n^{-\beta})^{n}({1 \over 2}+{\epsilon \over 4})^{n} $ if $n$ is sufficiently large. The second term is at most $d^{-2} n^{2cn}(2n^{-\beta}(2n^{-\beta} + n^{-\beta}))^{n}=$ $ d^{-2} n^{2cn} 6^{n}n^{-2\beta n}\le d^{-2}6^{n}n^{cn}n^{-\beta n} n^{(c-\beta)n} \le d^{-2}6^{n}n^{cn}n^{-\beta n} n^{-c_{2}n} \le d^{-2}n^{cn}n^{-\beta n} n^{- {c_{2}\over 2}n} $ if $n$ is sufficiently large. Adding the upper bounds of all $p_{d}$ we get that the probability that there are $k,l\in [1,n^{cn}]$, $k\not= l$ with property \rref{L3.1} is at most $\sum_{d=1}^{n^{cn}} ( (2n^{-\beta})^{n}({1 \over 2}+{\epsilon \over 4})^{n} +d^{-2} n^{cn}n^{-\beta n} n^{- {c_{2}\over 2}n}) \le $ $n^{cn} ({1\over 2} +{\epsilon \over 4})^{n} (2n^{-\beta})^{n}+ {\pi^{2}\over 6} n^{cn}n^{-\beta n} n^{- {c_{2}\over 2}n} \le$ $n^{cn} ({1\over 2}+{\epsilon \over 2})^{n}(2n^{-\beta})^{n} $. This proves \rref{L3.12}. \nev{2001} Now we prove the lower bound on $P(B)$. $P(B)\ge \sum_{i=1}^{n^{cn}}p_{i,i}-\sum\lbrace p_{k,l}|,k,l\in [1,n^{cn}], k\not=l\rbrace \ge n^{cn}p_{1,1}-({1\over 2}+{\epsilon \over 2})^{n}n^{cn}p_{1,1}=(1-({1\over 2}+{\epsilon \over 2})^{n})n^{cn}p_{1,1}$ as claimed in \rref{L3.05}. \rref{L3.12} gives an upper bound on the probability of the event in \rref{L3.1} and together with \rref{L3.05} they yield the upper bound on the conditional probability of event \rref{L3.1}. \enp{(Lemma~\rref{L3})} %%%%%%Lemma L4 eredeti helye \begin{lemma} \llabel{L5} { Assume that $A_{1},...,A_{t}$ are events in an arbitrary probability space with the following properties: \nev{1056} (i) $\prob(\bigcup_{i=1}^{t}A_{i})=1$ (ii) $\prob(A_{i})= \prob(A_{j})$ for all $i,j\in [1,t]$ (iii) $\sum\lbrace \prob(A_{i}\cap A_{j})\ |\ i,j\in [1,t], i\not=j\rbrace \le \sigma $ Then for an arbitrary event $W$ we have $|\prob(W)-\sum_{i=1}^{t} {1\over t}\prob(W|A_{i})|\le 3\sigma $. \nev{1057} } \end{lemma} {\bf Proof.} We define another probability measure $\prob'$ on the same $\sigma$-algebra where $\prob$ is defined by $ \prob(Y)=\sum_{i=1}^{t} {1\over t}\prob(Y|A_{i}) $. This is indeed a probability measure since it is the linear combination of probability measures so that the coefficients are nonnegative and their sum is $1$. \nev{1058} By (ii) there is a $p$ so that $p=A_{i}$ for $i=1,...,n$. According to (i) $tp\ge 1$. On the other hand we claim that (iii) implies $tp \le 1+\sigma$. Indeed $1=\prob(\bigcup A_{i})\ge $ $\sum_{i}\prob (A_{i}) -\sum_{i\not= j} \prob(A_{i} \cap A_{j})\ge $ $ tp-\sigma $. Therefore we have \begin{cond} \llabel{L5.05} ${1\over t}\le p\le {1\over t} +{\sigma \over t}$. \nev{1059} \end{cond} Let $X=\bigcup \lbrace A_{i} \cap A_{j} \ |\ i,j\in [1,t], i\not=j\rbrace $. Property (iii) implies that $\prob(X)\le \sigma$. \nev{1060} If $Z$ is an event and there is an $i\in [1,n]$ so that $Z\subseteq A_{i}\bcks X$ then $\prob'(Z)={1\over t}\prob(Z| A_{i})={1\over tp}\prob(Z)$. Therefore \rref{L5.05} implies that \begin{cond} \llabel{L5.1} $ \prob'(Z)\le \prob(Z) \le (1+\sigma)\prob'( Z) $. \end{cond} Clearly these inequalities remain valid for any $Z \subseteq \bar X$ where $\bar X$ is the complement of $X$. Applying it to $Z=\bar X$ we get $\prob'(\bar X)\ge $ $(1+\sigma )^{-1}\prob(\bar X)\ge (1+\sigma)^{-1}(1-\sigma)\ge 1-2\sigma$. Therefore $\prob'(X)\le 2\sigma$. \nev{1061} Assume now that $W$ is an arbitrary event. $\prob(W)=\prob(W\cap X)+ \prob(W\bcks X)$ and $\prob'(W)=\prob'(W\cap X)+ \prob'(W\bcks X)$. Taking the difference of the two equations we get $|\prob(W)- \prob'(W)| =|\prob(W\cap X)- \prob'(W\cap X)| + |\prob(W\bcks X)- \prob'(W\bcks X)| $. Since $0\le \prob(X)\le \sigma$ and $0\le \prob'(X)\le 2\sigma $ we have $ |\prob(W\cap X)- \prob'(W\cap X)|\le 2\sigma $. As we have noted \rref{L5.1} holds for any $Z\subseteq \bar X$ therefore $|\prob(W\bcks X)- \prob(W\bcks X)|\le \sigma \prob'(W\bcks X)\le \sigma $. The two upper bounds imply the conclusion of the lemma. \nev{1062} \enp{(Lemma \rref{L5})} We prove the statement of Lemma \rref{L4} applying Lemma \rref{L5} with the following choices of the parameters. $t=n^{cn}$, the probability space consists of the measurable subsets of $B$ with the probability distribution $D_{1}$, and $\sigma= {1\over 3}({1\over 2}+\epsilon)^{n} $. Condition (i) follows from the definition of the probability space. Condition (ii) is a consequence of the fact that the probability of the event ``$\ltort m\alpha_{i}\rtort \le n^{-\beta} $ for all $i=1,...,n$" is $(2n^{-\beta})^{n}$ independently of the choice of $m$. Lemma \rref{K2} implies that $\sum\lbrace \prob(A_{i}\cap A_{j})(\prob(B))^{-1}\ |\ i,j \in \ [1,n^{c}] \rbrace\le ({1\over 2}+\epsilon')^{n}n^{cn}p_{1,1}$. This together with the lower bound \rref{L3.05} on $P(B)$ implies (iii). The conclusion of Lemma \rref{L5} gives the required upper bound on the distance of the two distributions. \enp{(Lemma~\rref{L4})} \nev{1064} %%%Lemma K3 eredeti helye {\bf Proof of Lemma \rref{K3}.} The proof of this lemma is very similar to the proof of Lemma \rref{L3}. Still there are a few differences which need additional attention. Let $d\in [1,n^{cn}]$. We estimate the probability $q_{d}$ of the event that there are $k,l \in \Phi(n^{cn})$ with $(k,l)=d$ and with property \rref{K3.1}. The distribution of $d\alpha_{1},...,d\alpha_{n}$ is the same as the distribution of $\alpha_{1},...,\alpha_{n}$, consequently $q_{d}$ is the probability of the following event as well: there are $k,l \in \Phi(d^{-1}n^{cn}) $ with $(k,l)=1$ and with property \rref{K3.1}. \nev{3050} For each pair of positive integers $k,l$ and for each fixed $i=1,...,n$, let $q_{k,l}^{(i)}$ be the probability of the event \rref{K3.1}. Since the random variables $\alpha_{i}$ are independent, $q_{k,l}=\prod_{i=1}^{n}q_{k,l}^{(i)}$. \nev{3051} Therefore according to Lemma \nev{K2} the following two inequalities hold. \begin{cond} \llabel{I1} $q_{k,l}\le (2n^{-\beta}(2n^{-\rho} + {1\over k }))^{n}$\end{cond} \begin{cond} \llabel{I2} $q_{k,l}\le ((2n^{-\beta}+{1\over l})2n^{-\rho} )^{n}$. \end{cond} \nev{3052} $q_{d}\le \sum \lbrace q_{k,l}\ |\ \langle k,l\rangle \in \Phi(d^{-1}n^{cn}), k\le n^{\beta}, l\le n^{\beta}\rbrace+ $ $ \sum \lbrace q_{k,l} \ |\ \langle k,l\rangle\in \Phi(d^{-1}n^{cn}), k\le n^{\beta}, l> n^{\beta}\rbrace +$ $ \sum \lbrace q_{k,l}\ |\ \langle k,l\rangle \in \Phi(d^{-1}n^{cn}), k>n^{\beta} \rbrace $. We estimate the three terms separately. If $k>1$ we use inequality \rref{I1} for each fixed pair in the first term and we get that this part of the first term is at most $(n^{\beta})^{2}((2n^{-\beta}(2n^{-\rho} +{1\over2} ))^{n}$. If $k=1$ then by the definition of $\Phi$ we have $l\ge {1\over 3}n^{\beta}$. We use inequality \rref{I2}, and we get the upper bound $n^{\beta} ((2n^{-\beta}+ 3n^{-\beta}) 2n^{-\rho}) ^{n} $ on the corresponding part of the first term. If $n$ is sufficiently large then the sum of the two upper bounds is at most $(2n^{-\beta})^{n}({1 \over 2}+{\epsilon \over 4})^{n} $. \nev{1175} We use inequality \rref{I2} for the second term for each fixed pair $k,l$. The number of choices for $k$ is at most $n^{\beta}$, the number of choices for $l$ is at most ${1\over d}n^{cn}$, so we get the upper bound $n^{\beta}d^{-1}n^{cn}((2n^{-\beta}+{1\over l})2n^{-\rho})^{n}\le $ $ (2n^{-\beta})^{n}({1 \over 2}+{\epsilon \over 4})^{n} $. \nev{1160} To get an upper bound on the third term we use inequality \rref{I1}. We get $d^{-2} n^{2cn}(2n^{-\beta}(2n^{-\beta} + n^{-\beta}))^{n}\le$ $ d^{-2}(2n^{-\beta})^{n}({1 \over 2}+{\epsilon \over 4})^{n} $ if $n$ is sufficiently large. \nev{1156} Adding these upper bounds for all $d\in [1,n^{cn}]$ and using that $ \sum_{d=1}^{\infty}d^{-2}<\infty$ we get that $\sum\lbrace q_{k,l} \ |\ \langle k,l\rangle \in \Phi(n^{cn}) \rbrace \le (2n^{-\beta})^{n}({1 \over 2}+{\epsilon })^{n} $ as claimed in \rref{K3.12}. \nev{1157} The upper bound in \rref{K3.12} gives an upper bound on the probability of the event described in the last statement of the lemma. The upper bound on the conditional probability follows from this and the lower bound on $P(B)$ given in Lemma \rref{L3}. \nev{3053} \enp{(Lemma \rref{K3})} \vskip 10pt \subsection {The proofs of Theorem \rref{T1} and Theorem \rref{T2}} {\bf Proof of Theorem \rref{T1}.} Let $\langle \langle t_{1},....,t_{n-1}\rangle ,u\rangle $ be a random value of $\bar\tau_{Q,n}(\xi,\beta,\gamma) $ and $L=\call(t_{1},...,t_{n-1}, b_{1},...,b_{n-1}, \xi,\beta,\gamma) $. We will use the notation $u_{L}=u$ if we need the emphasize the dependency on $L$. We will show that with a probability of at least $1-2^{-n}$ we have $\Vert u_{L}\Vert _{\infty} \le (n-1)^{-\beta}+n^{-\gamma+1 }$. Then we show that with the probability indicated in the theorem the following holds. Assume that $w\in L$ and $\Vert w\Vert_{\infty} \le (n-1)^{-\xi-\epsilon/2 }$. Then $w$ and $u_{L}$ are parallel. Therefore $u_{L}$ is an $(n-1)^{-\xi+\beta-\epsilon}$-unique nonzero shortest vector with respect to the $\ell_{\infty}$-norm and consequently it is an $(n-1)^{-\xi+\beta-\epsilon -{1\over 2}}$-unique shortest nonzero vector with respect to the Euclidean norm. (Since $(n-1)^{-\xi+\beta-\epsilon -{1\over 2}}\ge n^{-\xi+\beta-{\epsilon \over 2}-{1\over 2}} $ it does not matter whether the base is $n-1$ or $n$ in this expression.) \nev{1161} We have defined $L$ as the lattice generated by $e_{1},...,e_{n-1}$ and $v$, where $v= (n-1)^{-\xi(n-1)-\beta}e_{n}+ \sum_{i=1}^{n-1}\fr({q_{i}\over d},kn^{\gamma})e_{i} $. Therefore $dv=d(n-1)^{-\xi(n-1)-\beta}e_{n}+ d\sum_{i=1}^{n-1}\fr({q_{i}\over d},kn^{\gamma})e_{i}\in L$. By the definition of $\fr({q_{i}\over n}d,kn^{\gamma})$ we have $dv=v'+v_{R}$, where $v'= d(n-1)^{-\xi(n-1)-\beta}e_{n}+ \sum_{i=1}^{n-1}{q_{i} }e_{i}$ and $v_{R}= \sum_{i=1}^{n-1}\delta_{i} e_{i} $, $|\delta_{i}|\le d {1\over kn^{\gamma}}\le {1\over n^{\gamma-1}}$. Let $s_{i}$ be the closest integer to $q_{i}$ and let $\tilde u=dv-\sum_{i=1}^{n-1}s_{i}e_{i}$. We claim that $\tilde u =u_{L}$, $\tilde u\not=0$, and $\Vert \tilde u\Vert _{\infty}\le (n-1)^{-\beta }+n^{-\gamma+ 1 } $. $\tilde u\not= 0$ follows from the fact the the coefficient of $e_{n}$ is not $0$ if we write $u$ as a linear combination of the unit vectors $e_{i}$. \nev{1125} $\tilde u=v'-\sum_{i=1}^{n-1}s_{i}e_{i} +v_{R}=$ $ d(n-1)^{-\xi(n-1)-\beta}e_{n}+ \sum_{i=1}^{n-1}(q_{i}-s_{i})e_{i}+ v_{R} =$ $ d(n-1)^{-\xi(n-1)-\beta}e_{n}+ \sum_{i=1}^{n-1}\ltort q_{i}\rtort e_{i}+ v_{R} $, where $\Vert v_{R}\Vert_{\infty}\le n^{-\gamma + 1} $. The definition of $q_{i}$ implies that $\ltort q_{i}\rtort \le (n-1)^{-\beta}$, and $d\le (n-1)^{\xi(n-1)} $ implies that the coefficient of $e_{n}$ in absolute value is also at most $(n-1)^{-\beta}$, therefore $\Vert \tilde u\Vert_{\infty}\le (n-1)^{-\beta}+ n^{-\gamma+ 1}<(1+{1\over 10}) (n-1)^{-\beta} $. This inequality and the definitions of $u_{L}$ and $\tilde u$ imply that $\tilde u=u_{L}$. \nev{1126} The definition of $u$ and the proof above also implies the following that we will use later. \nev{d1015} \begin{lemma} \llabel{T1.09} Let $u_{L}=\langle u_{1},...,u_{n}\rangle $. Then $u_{n}=d(n-1)^{-\xi(n-1)-\beta}\le n^{-\beta}$ and for all $i=1,...,n-1$ $u_{i}=\ltort q_{i} \rtort + \delta_{i}$, where $|\delta_{i}| \le n^{\gamma -1}$ \nev{d1014} \end{lemma} To prove that $u_{L}$ is indeed an $ (n-1)^{\beta -\xi -\epsilon}$-unique nonzero shortest vector with respect to the $\ell_{\infty}$ norm, as a first step, we show the following \nev{1130} \begin{lemma} \llabel{T1.1} Assume that $\xi,\beta,\gamma, \epsilon$ are given as in Theorem \rref{T1}, the integer $n$ is sufficiently large, $L$ is a value of the random variable $\kappa_{Q,n}(\xi,\beta,\gamma)$, and $d$ is the integer and $q_{1},...,q_{n}$ are the realnumbers from the definition of $\kappa_{Q,n}(\xi,\beta,\gamma)$ in the case when the value of $\kappa$ is $L$. Then $\Vert u_{L}\Vert_{\infty} < (1+{1\over 10})(n-1)^{-\beta} $. Suppose further that there is a $w\in L$, $w\not= 0$ which is not parallel to $u$ so that $\Vert w\Vert_{\infty} \le (n-1)^{-\xi -\epsilon}$. Then there is an integer $h$ so that the pair $d,h$ meets the following requirements: $\ltort h{q_{i}\over d}\rtort\le (n-1)^{-\xi-{\epsilon \over 2}} $, $h \in [1,(n-1)^{\xi(n-1)+\beta}]$, $\ltort d{q_{i}\over d} \rtort \le (n-1)^{-\beta} $, $d\in [1,(n-1)^{\xi(n-1)}]$ and either $d{\not|}h$ or ${h\over d}\ge {1\over 3}(n-1)^{\beta} $ \nev{1129} \end{lemma} We have already proved the upper bound on $\Vert u_{L} \Vert _{\infty} $. Since $w\in L$ we have $w=hv+\sum_{i=1}^{n-1} g_{i}e_{i}$, where $hv= h(n-1)^{-\xi (n-1)-\beta}e_{n} + h\sum_{i=1}^{n-1}\fr({q_{i} \over d}, kn_{\gamma})e_{i} $ and $g_{1},...,g_{n-1}$ are integers. $\Vert w\Vert \le 1 $ implies that $|h (n-1)^{-\xi(n-1)-\beta}|\le 1$ and so $h\le (n-1)^{\xi(n-1)+\beta}$. \nev{1127} We have $\fr({q_{i}\over d},kn^{\gamma})={q_{i}\over d} +{\tau_{i}\over kn^{\gamma}}$, where $0\le \tau_{i}<1$. Therefore $hv=h(n-1)^{-\xi(n-1)-\beta}e_{n} +$ $ \sum_{i=1}^{n-1} (h{q_{i}\over d} +\delta_{i})e_{i}$ where $|\delta_{i}| \le (n-1)^{\xi(n-1)+\beta}{1\over (n-1)^{\xi(n-1) -1 }n^{\gamma}}\le (n-1)^{\beta+1 -\gamma} \le (n-1)^{-\xi-1} $. \nev{1128} Consequently the upper bound on $\Vert w\Vert_{\infty} $ implies that $ \ltort h{q_{i}\over d} +\delta_{i}\rtort\le (n-1)^{-\xi-\epsilon} $. The upper bound on $\delta_{i}$ and the assumption $\beta>\xi$ of Theorem \rref{T1} imply that $\ltort h{q_{i}\over d}\rtort \le (n-1)^{-\xi-{\epsilon\over 2}} $ if $n$ is sufficiently large. \nev{1132} Assume now that $d|h$. The definition of $u_{L}$ and $w=hv+\sum_{i=1}^{n-1}g_{i}e_{i}$ imply, that $w={h\over d}u +\sum_{i=1}^{n-1}a_{i} e_{i} $, where $a_{1},...,a_{n-1}$ are integers. Suppose now that contrary to the statement of Lemma \rref{T1.1} we have ${h\over d}< {1\over 3}(n-1)^{\beta}$. Therefore $\Vert u_{L}\Vert_{\infty} \le (1+{1\over 10})(n-1)^{-\beta}$ implies that $\Vert {h\over d}u_{L} \Vert_{\infty} \le ({1+{1\over 10}})(n-1)^{-\beta}{1\over 3} (n-1)^{\beta}<{1\over 2} $ if $n$ is sufficiently large. This inequality, $\Vert w\Vert_{\infty}\le $ $(n-1)^{-\xi-\epsilon}< $ ${1\over 2} $, and the equation $w={h\over d}u_{L}+\sum_{i=1}^{n-1}a_{i}e_{i}$ imply that $a_{1}=...=a_{n-1}=0$, and so $u$ and $w$ are parallel, in contradiction to our assumption. \nev{1145} \enp{(Lemma \rref{T1.1})} \liba We consider the process of choosing a random $Q$ from $\part_{n-1}(k)$ with uniform distribution and then choosing a random $L$ according to $\kappa_{Q,n}(\xi,\beta,\gamma)$, as a single randomization. During this randomization we pick an integer $d$ from the interval $[{1\over 2}(n-1)^{\xi(n-1)}, (n-1)^{\xi(n-1)}] $ with uniform distribution and a vector $q=\langle q_{1},...,q_{n-1} \rangle $ form the set $\lbrace \langle x_{1},...,x_{n-1}\rangle \in dQ\ |\ \ltort x_{i}\rtort\le (n-1)^{-\beta}, i=1,...,n-1\rbrace $ with uniform distribution with respect to the $n-1$-dimensional volume. Let $\calx$ be the $\sigma$-algebra of all Borel subsets of $\zee \times \err^{n-1}$. We will denote by $\Theta$ the probability measure on $\calx$ defined by $\Theta(X)=\prob(\langle d, \langle {q_{1}\over d},...,{q_{n} \over d}\rangle \rangle \in X ) $ for all $X\in \calx$, where $d,q_{1},...,q_{n}$ are picked according to the randomization described above. \nev{1180} \uj We say that the pair $\langle d,\langle s_{1},...,s_{n-1}\rangle \rangle $, $d\in \zee$, $\langle s_{1},...,s_{n-1}\rangle \in\err^{n-1}$ is singular if the following condition is satisfied: \nev{1146} \begin{cond} \llabel{E1} Let $q_{i}=ds_{i}$ for $i=1,...,n-1$. Then there is an integer $h$ so that $\ltort h{q_{i}\over d}\rtort\le (n-1)^{-\xi-{\epsilon \over 2}} $, $h \in [1,(n-1)^{\xi(n-1)+\beta}]$, $\ltort d{q_{i}\over d} \rtort \le (n-1)^{-\beta} $, and either $d\not|h$ or ${h\over d}\ge {1\over 3}(n-1)^{\beta} $ \nev{1147} \end{cond} \tojas \megj \mas We used the notation $s_{i}={q_{i}\over d}$ to indicate the connection of this definition to the definition of the lattice $L$. \vege \liba Assume that for each positive integer $n$, $\Gamma_{n}$ is a probability measure on $\calx$ and suppose that we chose the pair $\langle d, \langle s_{1},...,s_{n-1}\rangle \rangle \in \zee \times \err^{n-1} $ according to distribution $\Gamma_{n}$. We say that the family of distributions $\Gamma_{n}$, $n=1,2,....$ is regular if for all $\theta>{1\over 2}$ and for all sufficiently large $n$ the probability, with respect to $\Gamma_{n}$, that $\langle d, \langle s_{1},...,s_{n}\rangle \rangle $ is singular is at most $\theta^{n}$. \nev{1300} \tojas It is an immediate consequence of Lemma \rref{T1.1} that in order to complete the proof of Theorem \rref{T1} it is sufficient to show that the distribution $\Theta$ is regular. (Naturally, $\Theta $ depends on $n$ so we can consider it as a family of distributions.) Indeed, this would show that a vector $w$ with the properties described in Lemma \rref{T1.1} exists only with a probability of less than $\theta^{n}$ with respect to the randomization of $Q$ and $\kappa_{Q,n}(\xi,\beta,\gamma)$ if $n$ is sufficiently large. Therefore with a probability of at least $1-\theta^{n}$, with respect to the two randomizations together, there is an $(n-1)^{-\xi-\epsilon}$-unique nonzero shortest vector, with respect to the $\ell_{p}$ norm, in the lattice $L$, as claimed by Theorem \rref{T1}. \nev{1301} Our next goal is to show that $\Theta$ is regular. We will define a sequence of distributions $\Theta$ (already defined), $\Theta_{1}$, $\Theta_{2}$, $\Theta_{3}$, $\Psi'$ and show that the regularity of each of these distributions in the sequence follows from the regularity of the next one. Finally we will show that $\Psi'$ is regular using Lemma \rref{L4}. \nev{1302} First we define another probability measure $\Psi$ on the $\sigma$-algebra $\calx$. $\Psi$ is defined by the following randomization. We pick the realnumbers $\alpha_{1},...,\alpha_{n-1}$ independently and with uniform distribution from $(0,1)$, and with the condition ``There exists an integer $j$ in the interval $[1,(n-1)^{\xi(n-1)}]$ so that $\ltort j \alpha_{i}\rtort\le (n-1)^{-\beta} $ for all $i=1,...,n-1$", the integer $d$ will be the smallest $j$ with this property. For each $X\in \calx$, $\Psi(X)=\prob(\langle d, \langle \alpha_{1},...,\alpha_{n-1}\rangle \rangle \in X)$. (Lemma \rref{L3} implies that with a probability of at least $1-({1\over 2}+\epsilon')^{n}$ there is a unique $j$ with the given property.) \nev{1165} We will use the following lemma in the proof of Theorem \rref{T2}, however some of the partial results will be useful for the proof of Theorem \rref{T1} as well. \nev{1192} \begin{lemma} \llabel{K5} There is a $c'>0$ so that for all $\epsilon'>0$, if $\xi,\beta ,\gamma$ are given with the properties described in Theorem \rref{T1} and $n$ is sufficiently large, then for all $A\in \calx$ with $\Theta(A)>({1\over 2}+\epsilon')^{n}$ we have $\Psi(A)\ge c'\Theta(A) $. \nev{1170} \end{lemma} {\bf Proof.} Let $\Theta_{1}$ be the probability distribution that we get by modifying the randomization performed according to $\Theta$ in the following way. We leave the randomization of $d$ unchanged. Suppose that $d$ have been already selected. Let $F=\lbrace \langle r_{1},...,r_{n}\rangle \in \err^{n-1} \ |\ \ltort r_{i}\rtort \le (n-1)^{-\beta}, i=1,...,n-1\rbrace $. Instead of picking first $ Q $ and then $q$ from $F\cap dQ$, (as we have done for the randomization of $\Theta$), now we pick $q$ from the set $F\cap \bigcup \lbrace dQ \ |\ Q\in \part_{n-1}(k) \rbrace= $ $ F\cap [0,d)^{n-1}$ with uniform distribution with respect to the $n-1$ dimensional volume. This creates a slightly different distribution on the set of possible vectors $q=\langle q_{1},...,q_{n-1}\rangle $ since the various sets $dQ\cap F$ for different cubes $Q\in \part(k)$ may have different $n-1$-dimensional volumes. To estimate the ratio of probabilities according to the two distributions we give upper and lower bounds on the $n-1$ dimensional volume of the set $dQ\cap F$ where $Q$ is an arbitrary element of $\part_{n-1}(k)$. \nev{1320} Suppose that $Q=\prod_{i=1}^{n-1} [{b_{i}\over k},{b_{i}+1\over k}) $. The definition of $F$ implies that $\vol_{n-1}(dQ\cap F)= \prod_{i=1}^{n-1} \lambda(F_{i}\cap [{d\over k}b_{i},{d\over k}(b_{i}+1)] ) $, where $\lambda$ is the one dimensional Lebesgue measure and $F= \prod _{i=1}^{n} F_{i}$. Let $[a,b]$ be a maximal interval with integer endpoints so that $[a,b] \subseteq I$, where $I= [{d\over k}b_{i},{d\over k}(b_{i}+1)] $. Clearly ${d\over k}\ge b-a\ge {d\over k}-2$. $\lambda (F\cap I)=\lambda(F_{i}\cap [a,b]) +\lambda(F_{i}\cap (I\bcks [a,b]) ) $. We have $\lambda(F_{i}\cap [a,b])=2(n-1)^{-\beta}(b-a)$ and $0\le \lambda( F_{i}\cap (I\bcks [a,b]) ) ) \le 4(n-1)^{-\beta}$. This implies that \begin{cond} \llabel{K5.01} $({d\over k}-2)2(n-1)^{-\beta} \le \lambda (F_{i}\cap I)\le ({d\over k}+2)2(n-1)^{-\beta} $. \end{cond} Therefore $ (({d\over k}-2)2(n-1)^{-\beta})^{n-1} \le \vol_{n-1} (F\cap dQ)\le (({d\over k}+2)2(n-1)^{-\beta})^{n-1} $ and so $({d\over k})^{n-1}(1-{2k\over d})^{n-1}2^{n-1}(n-1)^{-(n-1)\beta} \le \vol_{n-1} (F\cap dQ) \le ({d\over k})^{n-1}(1+{2k\over d})^{n-1}2^{n-1}(n-1)^{-(n-1)\beta} $. By the definition of $d$ and $k$ we have $0\le {2k \over d}\le {4\over n-1} $, therefore $c_{1}({d\over k})^{n-1} 2^{n-1}(n-1)^{-(n-1)\beta} \le \vol_{n-1} (F\cap dQ) \le c_{2}({d\over k})^{n-1} 2^{n-1}(n-1)^{-(n-1)\beta} $, where $c_{1}>0,c_{2}>0$ are absolute constants. This shows that the probabilities defined by the two randomizations of $q_{i}$ may differ at most by a constant factor, that is, $\Theta_{1}(A)\ge c_{3}\Theta(A)$ for all $A\in \calx$ where $c_{3}>0$ is an absolute constant. Therefore the regularity of $\Theta_{1}$ implies the regularity of $\Theta$. \nev{1172} Let $\Theta_{2}$, be the probability measure that we get from $\Theta_{1}$ if we change only the randomization of $d$ namely we pick $d$ with uniform distribution from the interval $[1,n^{\xi(n-1)}]$. Clearly $\Theta_{2}(A)\ge {1\over 3} \Theta_{1}(A)$ for all $A\in \calx$ and so the regularity of $\Theta_{2}$ implies the regularity of $\Theta_{1}$. \nev{1171} The remaining part of the proof of Lemma \rref{K5} is not needed for the proof of Theorem \rref{T1}. The definition of the distribution $\Psi$ and Lemma \rref{L4} implies that the distance of distributions $\Psi$ and $\Theta_{2}$ is at most $({1\over 2}+\epsilon)^{n}$, where we may assume that $\epsilon > 0$. This fact and the inequalities between $\Theta(A)$, $ \Theta_{1}(A)$, $\Theta_{2}(A)$ and $\Psi(A) $ imply the statement of the lemma. \enp{(Lemma \rref{K5})} \nev{1195} We continue the proof of Theorem \rref{T1}. From the proof of Lemma \rref{K5} we know that the regularity of $\Theta_{2}$ implies the regularity of $\Theta$. Let $\Theta_{3}$ be the distribution that we define the same way as $\Theta_{2}$ with the only difference that we pick the integer $d$ with uniform distribution from the integers of the interval $[1,(n-1)^{\xi(n-1)+\beta}]$ instead of the interval $[1,(n-1)^{\xi(n-1)}]$. Clearly for every $A\in \calx$ we have $\Theta_{2}(A)\le {1\over 2}n^{-\beta} \Theta_{3}(A) $. Therefore the regularity of $\Theta_{3}$ implies the regularity of $\Theta_{2} $. Let $\Psi'$ be the following distribution: we pick the realnumbers $\alpha_{1},...,\alpha_{n-1}$ at random, independently and with uniform distribution from the interval $(0,1)$ with the condition that ``$\exists j\in [1,(n-1)^{\xi(n-1)+\beta}]$ so that $\ltort j\alpha_{i}\rtort \le (n-1)^{-\beta} $, $i=1,...,n-1$". The smallest integer $j$ with this property will be $d$ and $\Psi'(X)=\prob(\langle d,\langle \alpha_{1},...,\alpha_{n-1}\rangle \rangle \in X)$ for all $X\in \calx$. \nev{1196} \megj \mas The only difference between the distributions $\Psi$ and $\Psi'$ is that in $\Psi'$ the integer $j$ can be picked from the interval $[1,(n-1)^{\xi(n-1)+\beta}]$ while in $\Psi$ it can be picked from the shorter interval $[1,(n-1)^{\xi(n-1)+\beta}]$. \vege According to Lemma \rref{L4} the distance of the distributions $\Theta_{3}$ and $\Psi'$ is at most $({1\over 2}+\epsilon')^{n}$ for all $\epsilon'>0$ if $n$ is sufficiently large. Therefore if $\Psi'$ is regular then $\Theta_{3}$ is also regular. To complete the proof of the regularity of $\Theta$ we have to show that $\Psi'$ is regular. \nev{1197} Assume that a $\theta> {1\over 2}$ is fixed. We show that if $n$ is sufficiently large and we randomize the pair $\langle d,q\rangle $ according to $\Psi'$ then the probability that $\langle q,d\rangle $ is singular is at most $\theta^{n}$. We apply Lemma \rref{K3} with $n\rightarrow n-1$, $\beta \rightarrow \beta$, $\rho \rightarrow \xi+{\epsilon \over 2} $, $c\rightarrow \xi+ {\beta \over n-1} +\xi$, $\alpha_{i}\rightarrow {q_{i}\over d}$. The choices $c_{1}= \beta$, $c_{2}= {1\over 2}\min \lbrace \xi, \beta -\xi \rbrace$ clearly meet the requirement of Lemma \rref{K3}. The conclusion of the lemma implies that the probability that $\langle q,d\rangle $ is singular is at most $\theta^{n}$. Finally we prove inequality \rref{T1.a} of Theorem 1. The upper bound on $u$ holds for every possible value of $u= \langle u_{1},...,u_{n}\rangle $. Indeed by Lemma \rref{T1.09} each component of $u$ is in the interval $[1,(n-1)^{-\beta}]$. We prove the lower bound by estimating $\nu$, the number of components $u_{i}$ of $u$ with $|u_{i}|>{1\over 10} (n-1)^{-\beta}$. As we have seen already this inequality always holds for $i=n$. According to lemma \rref{T1.09} $|u_{i}|> \ltort q_{i} \rtort +{1\over 10}(n-1)^{-\beta}$ therefore $\nu$ is not smaller then the number of integers $i\in [1,n-1]$ with $\ltort q_{i} \rtort \ge {1\over 5 } (n-1)^{-\beta}$. \rref{K5.01} implies that for each fixed $i$ the probability of $\ltort q_{i} \rtort \le {1\over 2} (n-1)^{-\beta}$ is at least ${3\over 4}$. The random variables $q_{i}$, $i=1,...,n-1$ are mutually independent. Therefore the probability that $\ltort q_{i} \rtort \ge {1\over 2} (n-1)^{-\beta}$ holds for less than $(n-1)^{1-{1\over 2}\epsilon'}$ integers $i$ in $[1,n-1]$ is at most ${n-1 \choose (n-1)^{{1\over 2}\epsilon'}}({1\over 4})^{n-(n-1)^{1-{1\over 2}\epsilon'}}<\theta^{n} $. Therefore with a probability of at least $1-\theta^{n}$ we have $\nu \ge (n-1)^{1-{1\over 2}\epsilon'}$. Therefore $\Vert u\Vert\ge (n-1)^{{1\over 2}-{1\over 4} \epsilon'}{1\over 10}(n-1)^{-\beta} $ which implies inequality \rref{T1.a} of Theorem \rref{T1}. \enp{(Theorem \rref{T1})} \nev{1152} {\bf Proof of Theorem \rref{T2}.} Assume that contrary to our statement there is an algorithm $\cala$ which solves problem {\bf Q2} for some choice of $\xi, \beta$ and $\gamma$ with a probability of at least $n^{-c_{2}}$ in time $n^{c_{1}}$. We show that using $\cala $ as an oracle we can solve problem {\bf Q1} (with parameters $c\rightarrow \xi$, $c'\rightarrow \beta- \xi$) in polynomial time with a polynomially large probability in contradiction to the Hardness Assumption. \nev{1181} Assume that the realnumbers $\alpha_{1},..,\alpha_{n-1}$ are chosen at random independently and with uniform distribution from $(0,1)$ and with the condition that there is an integer $m\in [1,(n-1)^{\xi(n-1)}]$ so that $\ltort m \alpha_{i} \rtort \le (n-1)^{-\beta}$, $i=1,...,n-1$. We have to find such an $m$ in polynomial time with a polynomially large probability. Let $d$ be the smallest integer $m$ with this property and let $q_{i}=d\alpha_{i}$, $q=\langle q_{1},...,q_{n-1}\rangle $. The distribution of the pair $\langle d,\langle {q_{1}\over d},...,{q_{n-1}\over d}\rangle \rangle $ is $\Psi$. Assume now that a pair $d,q$, $d\in [1,n^{\xi(n-1)}]$, $q\in \prod_{i=1}^{n-1}(0,1)$ is fixed. For the moment we do {\it not} consider them as random variables. We may construct a lattice $L_{d,q}$ generated by the basis $e_{1},...,e_{n-1},v$ described in the definition of random variable $\kappa_{Q,n}(\xi,\gamma,)$. Let $A'$ be the set of all pairs $\langle d, \langle {q_{1}\over d},...,{q_{n-1}\over d} \rangle \rangle $ with the property that if $\cala$ gets $L_{d,q}$ as an input ($q=\langle q_{1},...,q_{n-1}\rangle $) then it returns a shortest nonzero vector with a probability of at least ${1\over 2}n^{-c_{2}}$ in time $n^{c_{1}}$, where the probability is taken for the random steps in $\cala$. Our assumption about $\cala$ implies that $\Theta(A') \ge {1\over 2} n^{-c_{2}} $. Let $A$ be the set of all lattices in $L$ which has a $2$-unique shortest nonzero vector. Theorem \rref{T1} implies that $\Theta(A) \ge \Theta(A')-({3\over 4})^{n} $ and so $\Theta(A)\ge {1\over 3}n^{-c^{2}} $. Therefore by Lemma \rref{K5} we have that $\Psi(A)\ge c' \Theta(A) \ge c''n^{-c_{2}}$, where $c''>0$ is an absolute constant. This implies that if we pick $\langle d, \langle {q_{1}\over d},...,{q_{n-1}\over d} \rangle\rangle $ with distribution $\Psi$ then with a polynomially large probability $\cala$ finds a shortest nonzero vector in the lattice $L_{d,q}$ and this is $xv+\sum_{i=1}^{n}a_{i}e_{i}$, where $x,a_{1},...,a_{i}$ are integers then $x=d$ and so we have found the solution of Problem {\bf Q1}. \enp{(Theorem \rref{T2})} \nev{1182} \section {The hardness of the $n^{c}$-unique SVP and the security of the cryptosystem} In this section we prove Theorem \rref{T3}. The statement of the theorem differs only from the corresponding result about the second cryptosystem of \cite{AD} because the normal perturbations used in the definition of the system has different parameters. The improvement in the constant $c$ (in $n^{c}$-uniqueness) is based on a result of Regev (Lemma 3.14 in \cite{Regev}). Regev's proof is using a lemma of Banaszczyk given in \cite{Banaszczyk}. \nev{5270} We formulate our proof for System I, but based on this, in the same way as it is done in \cite{GGH}, the security of System II can be proved as well. \nev{5294b} \subsection{Notation, preliminaries} As we have already indicated earlier, in this section we will be interested algorithms whose inputs can be realnumbers. In this section when realnumbers are inputs for algorithms we will consider them as oracles. For the formulation of the hardness assumption the binary form of realnumbers was satisfactory. Now we need a somewhat more sophisticated, treatment of the representations of reals. The reason is the following. In the hardness assumption the reals which served as inputs for algorithms were random realnumbers, chosen with uniform distribution from $(0,1)$ and therefore with probability $1$ they had a unique representation. Moreover if the random real with this distribution was provided by another algorithm then this second algorithm was able to compute the bits of this unique binary representation of the realnumber $\alpha$ with the required precision in polynomial time for almost all $\alpha $, where the set of exceptional numbers $\alpha$ is exponentially small. In this section we will deal with more complicated distributions, whose density function may be an arbitrary Borel measurable functions so these properties would be more difficult to check. However if we treat realnumbers as oracles then we avoid all of these problems. \nev{5277} The oracle representation of reals was introduced by Lov\'asz in \cite{Lovasz}. We will use this representation in our proofs. For the reader who is not familiar with this representation of the realnumbers we provide here a compact equivalent definition which has a more limited scope (e.g. we do not consider the issue of unifying the representation of integers, rational and reals). This simplified definition will be sufficient for our present purposes. The equivalence of the two oracle representation of the reals means, that they are equivalent from the point of view of polynomial time computation. In other words the times required by the same algorthm in the two different models can differ by only a polynomial factor. \nev{8016} \liba We assume that each realnumber is represented by an oracle. Suppose now that $\alpha$ is a fixed real and an algorithm has access to this oracle. The algorithm may get information about $\alpha$ in the following way. The algorithm gives a positive integer $i$ as input to the oracle and the oracle returns a rational ${t\over 2^{i+1}}$, so that $t$ is an integer and $|\alpha -{t\over 2^{i+1}}|\le 2^{-i}$. We may think that the algorithm, by giving the integer $i$ to the oracle, asks for an approximation of $\alpha$ with the described precision and in the described form. By definition the asking such a question and receiving the answer will count as $\lfloor \log_{2} (|\alpha|+1) \rfloor +i+1$ additional time for the algorithm. (Roughly one time unit for each bit in the binary form of the number $t\over 2^{i+1}$.) The answer of the oracle is not uniquely determined. An answer meeting the listed requirements can be determined even by knowing only a rational approximation of $\alpha$ with a precision more than ${1\over 2^{i+1}}$ (and without knowing $\alpha$ itself). This is a crucial property if another algorithm has to play the role of an oracle. When we say that an algorithm gives an output with property $P$ at input $\alpha$, we mean that the algorithm gives an output with property $P$ for every possible choices of the answers provided by the oracle representing $\alpha$. \nev{5278} \tojas The following definitions describe the normal perturbations that we use in our cryptosystem. Most of these definitions can be found in \cite{Regev}. \liba Suppose that $L\subseteq \err^{n}$ is a lattice, $a_{1},.