Cryptosystem based on asymmetric numeral systems

I'm thinking about new concept of cryptosystem -I wanted to ask You about any ideas of breaking not using brute force (age of university required...) ?

This encryption is based on that for a given irrational number 'a', the sequence of 'fractional parts of a*n' (for n natural), covers [0,1) uniformly, but for each 'a' - in completely different way - we can use 'a' as a crypto key (it's rational in practice).

The simplest version of this cryptography system:

Let we have D symbols and some probability distribution on them (p_i)
We have:
I_i:=[p_1+p_2+...+p_{i-1},p_1+p_2+...+p+i)
the division of [0,1), SUCH THAT the PROBABILITY that fract(xd) is in I_d is p_d (for large x).
We want to encode a sequences of symbols (for example of {0,1} fixing p(0)=1/2 or blocks of bits) into a sequence of bits.

It will be one-state system, states are x\in{2^R,..,2^{R+1}-1} for some R (the number of bits we will work on).

Decoding x will produce a symbol and decrease x, if we get below 2^R, the youngest bits are taken from the input.
Encoding in the reverse way: put a few youngest bits of x to output, such that encoding (increasing x) of given symbol is possible.

Firstly, we have to initiate the tables - such that x_i is unique and about x*p_i:

x=2^R;x_1=ceiling(x*p_1);...;x_{D-1}=ceiling(x*p_{D-1});x_D=x-x_1-...-x_{D-1};
For x=2^R to 2^{R+1}-1
{find d that fract(x*a)\in I_d;
dec[x]=(d,x_d); //or cod[d][x_d]=x
x_d++; }

Now the decoding is a loop:
(d,x)=dec[x] //d,x are encoded on some bits
while(x<2^r) x=2*x+'bit from input';

encoding (we have d):
while(x>minimal value for decoding d) {put to output x&1; x=x shr 1}
x=cod[d][x]

It can be done without 'while's by storing in dec/cod the number of bits to get/put.

It was the simplest version, but the number of initializations consistent with statistics is huge (double exponential of R) - we can for example using crypto key to:
- vary the probabilities below precision
- in fact, instead of fract(ax), we can use ANY RANDOM NUMBER GENERATOR (eg fract(a x^2))which gives sequence on [0,1) with uniform distribution and initiate it using the key!
Good luck with breaking it!

Simpler version of this method has been just used as simpler alternative for the arithmetic coding (the heart of good compression rate compressors):
www.c10n.info
This version would allow to compress and encrypt in one time in amazing speed!

The question is: do You see any way to break it not using brute force?

This is not worth serious analysis.
Is "a" rational or irrational? Pick one, by definition, a number can't be both.

If you pick 'rational' how do you propose that a computer store it exactly? Only some rational numbers can be stored in floating point.

if you pick 'irrational' how do you propose to store it? While one can talk about 'pi' or 'e', neither can be stored in a computer.

I'm sorry- fract(an) is only an example of random number generator.
In fact we can use ANY RANDOM NUMBER GENERATOR which can be initiated with some key, and gives uniform distribution, (eg fract(n^2 a)) - it's completely enough to make it unbreakable.

Any generator You choose, x is jumping almost randomly on the whole range while coding/decoding.
And takes different number of bits in each step...

The probability distribution doesn't have to correspond to the data.
But the better it will correspond, the better output will be compressed.

Returning to the question (using fract(ax) ) - we need only a finite sequence, 'ugly' enough rational will be fine - we can eg. take something like 0.101******110, where * is the key ... or ask any random number generator expert about some different family of such generators, that can be parametrized ...

Each key (parameter) produce completely different cod/dec tables (and output). It's impossible even to generate these tables in different way than point by point!

If we use large R - initializations takes longer, but thanks of this we don't even need to use long keys to make it safe!

About the details - I've just updated my paper with this generalization of aymetric binary system
arxiv.org/PS_cache/arxiv/pdf/0710/0710.3861v2.pdf

There can be thought attacks based on possible beginnings while uncoding the data - to prevent it we can add a few random bytes there.

The limitation that the probability distribution is fixed, can be weakened by using a few of them.
For example we can use probability distribution in the general case and separately for the successor of a few most probable symbols.

So we have a few separate coding/decoding tables - we can initialize them using the key in many ways.
While encoding we have to use proper table, remembering that the decoding will be in the reverse order.

So it can be as fast as Huffman, as precise as arithmetic coding and as safe as...?

[QUOTE=Jarek Duda]I'm sorry- fract(an) is only an example of random number generator.
In fact we can use ANY RANDOM NUMBER GENERATOR which can be initiated with some key/QUOTE]

You have not addressed any of my questions.

In addition, you have raised more:
What do you mean by 'random number generator'?

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.
John von Neumann, 1951, quoted by Knuth

It's pseudo-random of course and 'produced' in unique way using the key. The only importance about it, is that the sequence is uniform in [0,1), that means: (\forall [a,b]\subset [0,1))
\lim_{n\to \infty} #{0<=x<n:rand(x)\in [a,b]}/n=p([a,b])=b-a
There was a theorem (Bohl, Sierpinski, Weyl), that fract(ax) fulfills that condition for 'a' irrational. When it's 'near' irrational - the behavior isn't much worse (for inshortable rational k/l covers uniformly {0,1/l,2/l,...,(l-1)/l})
And there are many much better generators!

But even with the simplest, I think it's unbreakable (not using brute force) - the generator is only used to construct extremely complicated coding/decoding table - slight different for every key.
The uniformness of the generator is required to fulfills condition, that
x_i is about x*p_i
This condition is used to encode in given symbol proper amount of information (about log_2 (x/x_i)=~ -log_2 (p_i) bits (eg in the binary p_i=1/2, we store 1 bit per symbol)).

The encryption is based on that 'x_i is about x*p_i' condition can be fulfilled in huge number of ways - we choose one using the generator.

The initialization creates the unique raltion x<->(x_d,d).
The 'x_d++' makes that every (x_d,d) will be used exactly once.
Coding/decoding are a bit more complicated, to ensure that we works constantly in some finite range [2^R,2{R+1}-1].

One of the most important advantage is that this cryptosystem in fact uses blocks of varied, not natural length!
And the change of one bit, changes the length of the next block.

Ok - in fact we require a bit more from the generator - good behavior on I=[2^R,2^{R+1}-1] range of 'x':
#{x\in I:rand(x)\in [a,b]}/#I is about p(a,b)=b-a
and to have better compression rate - the subset on the left side should be distributed more or less uniformly on I.
But practically every generator should fulfill this conditions.

And if a symbol is possible, it has to occur at least one on this range - if not we had to insert it artificially (for example by rounding up its probability).

This algorithm combines two nice properties:
- that random number generators are ideal for cryptography - if we have good family of them, even the simplest algorithm looks safe - just XOR the data with sequence of uncorrelated, equipropable bits generated for given key
- that good compressor should create sequence of uncorrelated, equipropable bits with p(1)=1/2, so not knowing the exact decompression method (like the key for random number generator) it's extremely difficult to get any information from the file.

Finally in ANS we don't know the initial state (one of 2^R), we don't know pseudo-random transition function (even knowing the key we would have to initialize the whole table earlier).
We only see the least important bits of practically random numbers.

I though about attacks that someone can encrypt his own data and analyze the output to get the key.
But even using sequence of zeros and knowing the initial decomposition of x, x still represents some large number - for large files it should give a period ... but how to get anything from it???
Eventually to ultimately prevent it, we could for example XOR some bytes of input with some constant eg generated using our key.

If we don't have full reliability, we can put some redundancy to make the error correction possible.

For example we can set given bit in every byte to 0 (after eventual prediction, of course ).
Now if while decoding we get there 1, we know that there was an error in a bit in at most a few bytes before (in the last with p=1/2, previous with p=1/4 ...).
We should flip bit by bit and try to decode - if the density of errors isn't too large, we should be able to localize and correct the error with large probability.

If putting 0 makes You worry about the safetyness, there can be put for example bit from another position or XOR of the rest bits instead.

Eventually if we lose larger fragment, we have to guess the new initial state and a beginning of block - if we've put some redundancy, it's rather doable state by state in not too large time.

I'm moving here discussion from
http://www.c10n.info/archives/720

Matt Mahoney says:

ANS main encryption power is in the coding/decoding tables (generated using the key) - they defines the rule of practically random jumping between states - state is hidden variable - slightest change of the tables (or input) and we are in a completely different place … and the hacker sees only the least important bits of the states - they are useless, because he cannot track his current location…

Both AES and SHA just takes constant length block and mix it as long as it doesn’t look breakable - instead of just enlarging the size of block every few years, maybe try use something unpredictable, eg use good random number generator, which uses theory of chaos ...
Another advantage of ANS is that it uses variable block lengths, even if we use equal probability, for example byte will sometimes give 7 or 9 bits - we cannot even decide how to block the file to use statistical methods.

I personally believe that even in the simplest version (with added random byte on the beginning of file) ANS is already safe - that means the only possible attack is brute force.
But it has nice protection against this kind of attacks:

In other encryptors we can just take next key and try to decrypt - analyzing the beginning of output we can decide if we’ve found the correct key.
In ANS before starting decryption process we just have to initialize whole decoding table using the key.
Choosing the number of bits we are working on (R), we can make the time needed to check every key as long as we want.
So even using short key should be safe with ANS.

If it will occur that we can start decoding without initializing the whole table, we can just take better (less predictable) random number generator.

RSA needs gigantic key, is extremely slow and in fact we don’t know if somebody hasn’t polynomial in time decomposition algorithm (3-4 years ago was officially shown polynomial algorithm that checks if number is prime).
But RSA has large advantage - asymmetric key, so I compare ANS with symmetric key encryptors only.

And the QUICKNESS …
After constant time for initialization, ANS encrypt/decrypt maaaaany times faster than AES or SHA … and compress it well by the way

But of course - many should think about it, before it will be widely believed safe and used.
And if it's not safe enough, we can for example before putting into ANS, XOR every byte with something generated by our generator ...
It's much better and faster way of complicating than inserting some new permutations...

For the cryptography it would be best if it doesn't use uniform probability distribution especially in power of 2 number of symbols (like byte) - all time we are diffusing around one state - it could be a bit vulnerable to adaptive plaintext methods.

To repair this uniform byte version, the best would be if the probability wouldn't be uniform - for example:
- for some bytes take only 7 bits, and move one bit to be coded later.
Selected 7bit symbols have larger probability. We use tables as before, but remembering to store one bit for selected bytes (eg above some value), finally having 8 of them - encode (good but complicated solution) or
- we can artificially (using our generator) change the probability distribution a bit (good and simple solution, but increasing a bit the size of output) or
- just make the prediction process (add header but compress file, doesn't work with compressed files, but they haven't too much sequences of zeros).

Alternatively we could make another complication, for example before putting into ANS, XOR every byte with something generated by our generator.

Thanks of the last post, I've finally realized that the standard deviation of (x_i-x*p_i) can be significant for good rate compressors in presented before versions of initialization.
Thanks of this diffusion, even uniform byte version (with initialization started from some point inside [2^R,2^{R+1}-1]) should be already quite safe against adaptive chosen plaintext attacks.

The minus is that this deviation changes a bit the probability we encode optimally.
Standard deviation of x_i/x is about sqrt(p_i/2^R)/2 - it's relatively small - in uniform byte version the output should be larger about something like 0.1%, we can just ignore it.
But if someone wants to use it for good rate compressor, there is required more precise version of the initialization.

Here is general perfect initialization algorithm (like the formula for ABS):
We need some priority queue (eg heap): insert, getmin - retrieve pair with the smallest first coordinate, which is expected position of the next occurrence of x giving this symbol.

For i=1 to D insert (1/p_i,i);
x=0;x_1=0;...;x_D=0;
For x=0 to some_value
{(y,d)=getmin;
dec[x]=(d,x_d) //or cod[d][x_d]=x;
x_d++;
insert(y+1/p_d,d);
}

In practice, we can start from x=2^R, x_1=x*p_i ...

To make it able to encrypt we can for example using our generator choose one of the smallest instead of just taking the smallest(many options).
This time I'm completely sure that even using the simplest generator, hacker cannot omit full initialization.
It takes longer (what can be advantage!) and shouldn't be used with uniform probability, but it's already version rather for good rate compressors.

ps. If we would like to enforce the initialization be artificially longer, we can for example start initialization from a distant point (in this version, generally - be careful with the deviation)
Another way is to use generator which needs a lot of time - for example the next number is generated by taking large number of iteration of some chaotic function.

I want to give some intuition about ANS and why it's so safe.

From the beginning...
We will base on that in a natural number x is stored about lg(x) bits.
You probably would like to add ceiling there - yes: we have to round it up to store it in bits, but the trick of ANS is that this equation is more accurate.

In symbol(d) which have probability p is stored -lg(p) bits of information (eg in 0/1 with probability 0.5 is stored 1 bit).
So if we would like to place this information with information stored in x, it would take about lg(x)-lg(p) bits of information, so
x should be transformed into about x/p.
See that we have it in usual binary system: to store b=0/1 bit with information stored in x, we can make x->2x+b (it's about x/0.5) - it's bijection - we can reverse this transform.

Now generally if x-> about x/p, so (x+1)-> about x/p + 1/p
We can do it by placing somehow uniformly with probability p, places which will correspond to this symbol and analogously with other symbols - we get the tables for ANS initialization:
bijection: (x_d,d)<->x such that x_d is about x*p_d

In practice we cannot operate on infinitely large numbers, so after growing above some limit, we forget for a while (move to output) about some least important digits and work only on first R+1 most important digit (it almost doesn't change lg(x)) .
So in x is always stored something between R and R+1 bits - it's storing fractional parts of bits, and spit out whole bits when they cumulate.
Precisely: when encoding symbol with probability q, we would increase the number of bits in x by -lg(p), so we have to put into output floor(lg(x)-lg(p)-R) bits before.

In version for cryptography we place digits uniformly by using random generator initialized with the key.
So the symbol(byte?) we get, and so the state we will go to are fixed, but in fact in random way, depends on the whole context - STATE (x) - DETERMINED BY THE WHOLE HISTORY.
The smallest change and we are in a completely different place and behave completely diff