All reports by Author Miklos Ajtai:

__
TR13-083
| 7th June 2013
__

Miklos Ajtai#### Lower Bounds for RAMs and Quantifier Elimination

__
TR11-102
| 31st July 2011
__

Miklos Ajtai#### Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

__
TR11-082
| 20th May 2011
__

Miklos Ajtai#### Secure Computation with Information Leaking to an Adversary

__
TR10-028
| 4th March 2010
__

Miklos Ajtai#### Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

__
TR07-097
| 8th October 2007
__

Miklos Ajtai, Cynthia Dwork#### The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

__
TR02-061
| 14th November 2002
__

Miklos Ajtai#### A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

__
TR99-026
| 7th July 1999
__

Miklos Ajtai#### A Non-linear Time Lower Bound for Boolean Branching Programs

__
TR98-077
| 19th December 1998
__

Miklos Ajtai#### Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

__
TR97-047
| 20th October 1997
__

Miklos Ajtai#### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

__
TR96-065
| 13th December 1996
__

Miklos Ajtai, Cynthia Dwork#### A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1
,
Comments: 1

__
TR96-007
| 29th January 1996
__

Miklos Ajtai#### Generating Hard Instances of Lattice Problems

Comments: 1

__
TR94-015
| 12th December 1994
__

Miklos Ajtai#### Symmetric Systems of Linear Equations modulo $p$

__
TR94-014
| 12th December 1994
__

Miklos Ajtai#### The Independence of the modulo p Counting Principles

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai, Cynthia Dwork

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai, Cynthia Dwork

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

Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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