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 >>>