All reports by Author Dima Grigoriev:

__
TR06-046
| 1st April 2006
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### A Complete Public-Key Cryptosystem

Comments: 1

__
TR05-076
| 2nd July 2005
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### Time hierarchies for cryptographic function inversion with advice

__
TR02-042
| 7th June 2002
__

Dima Grigoriev#### Public-key cryptography and invariant theory

__
TR01-103
| 14th December 2001
__

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik#### Complexity of semi-algebraic proofs

Revisions: 3

__
TR01-011
| 21st January 2001
__

Dima Grigoriev, Edward Hirsch#### Algebraic proof systems over formulas

__
TR96-058
| 25th November 1996
__

Dima Grigoriev, Marek Karpinski#### Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

__
TR95-063
| 19th December 1995
__

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky#### A Lower Bound for Randomized Algebraic Decision Trees

__
TR95-057
| 24th November 1995
__

Dima Grigoriev, Marek Karpinski, A. C. Yao#### An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We prove a time hierarchy theorem for inverting functions

computable in polynomial time with one bit of advice.

In particular, we prove that if there is a strongly

one-way function, then for any k and for any polynomial p,

there is a function f computable in linear time

with one ...
more >>>

Dima Grigoriev

Public-key crypto

Contact: dima@maths.univ-rennes1.fr

Author: Dima Grigoriev

Title: Public-key cryptography and invariant theory

Abstract: Public-key cryptosystems are suggested based on invariants of group

representations

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>

Dima Grigoriev, Edward Hirsch

We introduce two algebraic propositional proof systems F-NS

and F-PC. The main difference of our systems from (customary)

Nullstellensatz and Polynomial Calculus is that the polynomials

are represented as arbitrary formulas (rather than sums of

monomials). Short proofs of Tseitin's tautologies in the

constant-depth version of F-NS provide ...
more >>>

Dima Grigoriev, Marek Karpinski

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the

general model of \emph{randomized computation trees} solving

the \emph{Knapsack Problem}, and more generally \emph{Restricted

Integer Programming}. This is the \emph{first nontrivial} lower

bound proven for this model of computation. The method of the ...
more >>>

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees

to the case of {\em randomized} algebraic decision trees (with

two-sided error) for languages being finite unions of hyperplanes

and the intersections of halfspaces, solving a long standing open

problem. As an application, among ...
more >>>

Dima Grigoriev, Marek Karpinski, A. C. Yao

We prove an exponential lower bound on the size of any

fixed-degree algebraic decision tree for solving MAX, the

problem of finding the maximum of $n$ real numbers. This

complements the $n-1$ lower bound of Rabin \cite{R72} on

the depth of ...
more >>>