For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

For each natural number $d$ we consider a finite structure $M_{d}$ whose
universe is the set of all $0,1$-sequence of length $n=2^{d}$, each
representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace
$ in binary form.
The operations included in the structure are the
constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

Assume that Alice is running a program $P$ on a RAM, and an adversary
Bob would like to get some information about the input or output of the
program. At each time, during the execution of $P$, Bob is able to see
the addresses of the memory cells involved in ... more >>>

Abstract. We show that oblivious on-line simulation with only
polylogarithmic increase in the time and space requirements is possible
on a probabilistic (coin flipping) RAM without using any cryptographic
assumptions. The simulation will fail with a negligible probability.
If $n$ memory locations are used, then the probability of failure is ... more >>>

We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually ... more >>>

A measure $\mu_{n}$ on $n$-dimensional lattices with
determinant $1$ was introduced about fifty years ago to prove the
existence of lattices which contain points from certain sets. $\mu_{n}$
is the unique probability measure on lattices with determinant $1$ which
is invariant under linear transformations with determinant $1$, where a
more >>>

We prove that for all positive integer $k$ and for all
sufficiently small $\epsilon >0$ if $n$ is sufficiently large
then there is no Boolean (or $2$-way) branching program of size
less than $2^{\epsilon n}$ which for all inputs
$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$
the parity of ... more >>>

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose ... more >>>

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>

Suppose that $p$ is a prime number $A$ is a finite set
with $n$ elements
and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the
elements of
$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an
$n$ is sufficiently large.) We will ... more >>>

The modulo $p$ counting principle is a first-order axiom
schema saying that it is possible to count modulo $p$ the number of
elements of the first-order definable subsets of the universe (and of
the finite Cartesian products of the universe with itself) in a
consistent way. It trivially holds on ... more >>>