# Provably secure cryptosystem

```Hello.

```
I humbly say that I *might* have devised a provably secure cryptosystem that actually *might* work in reality. It provides secure authentication and possibly might be extended to something else. Sounds too good to be true? Well, you're right. In reality it's a bit more complicated.
```
```
I'm risking again making fool of myself, but what the heck ;-) At least I think it's something you all know, at least to some extent.
```
```
I have searched for some other provably secure schemas for MACs/signatures/etc., they use many similar assumptions (e.g. random oracle assumption, strong one-way hash function with uniform distribution assumption) and some similar techniques.
```
```
In the system I can prove there *is* a random oracle (this is also not so entirely true, but...you'll see).
```

OK, the point:
```
In complexity theory with random oracle, NP != P (cf. Shoup 1997: Lower Bounds for Discrete Logarithms and related problems, Baker-Gill-Solovay 1975). The trick is based on this fact.
```
```
Keys in the cryptosystem are not *data*, but *programs*, i.e. (partially) recursive functions. The trick is to simulate random oracle by a program, each program is the key describing a random permutation on some subset of natural numbers.
```
```
The cryptosystem is based on the following observation (extension of halting problem): Given a program L as an input that takes 1..n as input, L stops exactly for one 1<=j <=n. If we give this program to a DTM (deterministic Turing machine), no finite algorithm can decide for all possible input programs L and numbers n, for which j the input program L will stop in polynomial time.
```
```
In another words, no finite program can detect every virus (virus is defined to be a self-replicating program) or check if other program will draw prescribed picture for a given input, etc. in polynomial time.
```
```
So, the paper can be found here (alpha-draft, by no means complete, some parts such as related work and references, acks are not complete):
```
--
http://urtax.ms.mff.cuni.cz/~abyssal/PS.pdf
--

```
Be warned, it may be at least *partially* false, because I *deliberately* left out one proof ("protecting the keyspace", though it's security by obscurity). Well, hopefully there are no more serious glitches ;-]
```
```
The system as whole is secure, but every single instance can be of course broken by man (stealing the key, guessing the key, cryptanalysis). Integer factorization problem, (generalized) discrete logarithm problem are also elements of the system (it is a set).
```
At least I hope you'll have some fun.

OM

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
```