2t-sized post-quantum public key criptosystem

[Daniel]

Informally speaking, we define a function of two numbers modulo p, p
prime. That function is f(a,b)=(ab+1)/(b-a), operated mod p. This
function is not commutative and is not associative. To make this clearer
lets use another notation, a*b is f(a,b). Now, we have a property that's
that (a*b)*(c*d)=(a*c)*(b*d). We can exchange b and c in the formula and
get the same result. With this a public key criptosystem can be built,
the proof is in the link in the more formal description bellow. Now we
define a fibonacci exponentiation that's the same procedure as the
ordinary exponentiation by squaring but the element i of the table of
squares, that will be t[i]=t[i-1]^2, we use two initial values in t[0]=a
and t[1]=b and the next elements in the table are t[i]=t[i-2]*t[i], were
* is the function already defined. So we can call this fibonacci
exponentiation as mixf(a,b,k) or with another notation (a,b)^k. Now, the
operation allowed is that ((a,b)^k1,(c,d)^k1)^k2=((a,c)^k2,(b,d)^k2)^k1.
Now, mixf in respect to the k is not additive. mixf produces an erratic
sequence of results mod p with some series but no constant period at
all. There's not a workable g(k) such that (a,b)^k=(a,b)^g(k) for every
(a,b). In particular f(k) is not f(k)=k+c, c constant. So no quantum
algorithm based on hidden abelian subgroups works. More work must be
done in criptoanalysis and quantum computer considerations, so I need
help... Unrhu?

daniel...@gmail.com



Now the more formal description:


Our working numbers will be positive integers modulo a prime p, this is
in the range [0..p-1]. Next we need to define a function of two such
values, a and b, so:

f(a,b)=(ab+1)/(b-a) (mod p)

This function takes two values as parameters and produce a result value,
and inverse modulo p should be computed. The property needed for the
system work is that (see demonstration here
https://danielnbl.files.wordpress.com/2016/09/key_demonstration.pdf),
for every a,b,c and d:

f(f(a,b),f(c,d))=f(f(a,c),f(b,d))

So from left part of the equality to right we have interchanged b and c.
In order to make calculations faster we can work with fractions num/den
and when a value is needed convert they to num/1 by calculating the
inverse of the denominaton. A zero denominator is possible with very
small probability, but can be handled anyway.

Now a mixing function is needed, let's call it mixf, that takes two
values mod p, and a bit string key as parameters:

r=mixf(a,b,k)

Let's construct a table of values enough to fit the size of k:

t[0]=a
t[1]=b
t[i]=f(t[i-2],t[i-1])
...

Now let's set r to the element in t[i] corresponding to the index of the
first 1 in k. From there on and in increasing order we operate

r=f(r,t[j])

for each k[j]=1 until the key is exhausted. This is similar to the
procedure used for exponentiation by squaring, but in a fibbonacci form.

Hard Problem:

Given r=mixf(a,b,k), where a and k are known and b is secret, finding b
is hard, as hard of the bit size of the prime p. The signature and
intermediate values in key agreement are t-sized being t the security
threshold. So, for example, for a p of 96 bits we have 96 bits of
security and a 96 bits signature.


Scheme to build a criptosystem:

Let's focus on the following representation:

a---b---------->i1
| | k2 |
c---d---------->i2
| | |
| | |
|k1 | |k1
| | |
v v k2 v
i3--i4--------->r

i1=mixf(a,b,k1)
i2=mixf(c,d,k2)
i3=mixf(a,c,k2)
i4=mixf(b,d,k2)

r=mixf(i1,i2,k1)=mixf(i3,i4,k2)
r=mixf(mifx(a,b,k2),mixf(c,d,k2),k1)=mixf(mixf(a,c,k1),mixf(b,d,k1),k2)


Signature:

The signer public credentials with and agreed prime p are:

a,b,c,k2,i1,i2

d is keep secret. Now the hash to sign is k1 and the signature value is i4.

The verifier can compute itself i3 and check that r is coherent by both
possible paths, that's mixf(i1,i2,h)=mixf(mixf(a,c,h),i4,k2).


Secret value agreement:

First beside choosing a common prime p, some public a and d must be
agreed. Then one partner choses a path and the other gets the alternate
path to r.

Partner one publishes k2 and i1. Keeps b secret. Partner two publishes
k1 and i3 and keeps c secret.
Both can now arrive to r that's the agreed secret value.


On the periodicity of mixf and it's post-quantum candidature:

mixf function is virtually unperiodical. Iterating keys in
r=mixf(a,b,ki) now and then the result will be r=b for some ki, but in
an non-periodic behavior. Furthermore, experiments show that these
coincidences depend on b, intended to be secret, so no feasible attacks
on the order should work. In particular Pollard's Rho, Shor, Index
Calculus and so on. Even a meet-in-the-middle cannot be build as with
one result the table Ti cannot be recalculated, and one base parameter
is unknown.

[Chris M. Thomasson]

Need to read this interesting information in a deeper sense.

Thank you Daniel.

[Daniel]

El 16/01/17 a les 20:58, Chris M. Thomasson ha escrit:

> On 1/16/2017 5:00 AM, Daniel wrote:
>> Informally speaking, we define a function of two numbers modulo p, p

<snip due to server limitations>

>> On the periodicity of mixf and it's post-quantum candidature:
>>
>> mixf function is virtually unperiodical. Iterating keys in
>> r=mixf(a,b,ki) now and then the result will be r=b for some ki, but in
>> an non-periodic behavior. Furthermore, experiments show that these
>> coincidences depend on b, intended to be secret, so no feasible attacks
>> on the order should work. In particular Pollard's Rho, Shor, Index
>> Calculus and so on. Even a meet-in-the-middle cannot be build as with
>> one result the table Ti cannot be recalculated, and one base parameter
>> is unknown.
>
> Need to read this interesting information in a deeper sense.
>
> Thank you Daniel.

You're wellcome. I think it's promising and is a years' work (with sad
moments). I think I've found it. But other people has to have the same
opinion. So thank you too.

Regards
Daniel

[austin...@hotmail.com]

Hi Chris,

Yes, this is interesting to say the very least. My intuitive take is that Daniel is planning a number system of some sort that is less transparent than the traditional number line that may have any period and any direction. I am guessing that it will use some system of asymmetric periodicity between integers that is somehow serviced by modular arithmetic ? and of course is reversibly controllable so as to be decipherable by Bob.

He has extended the hand of welcome to you which I read as a sound move - Good Luck to you both.

adacrypt

[Daniel]

El 18/01/17 a les 09:38, austin...@hotmail.com ha escrit:

> On Monday, January 16, 2017 at 7:58:07 PM UTC, Chris M. Thomasson
> wrote:
>> On 1/16/2017 5:00 AM, Daniel wrote:
>>> Informally speaking, we define a function of two numbers modulo
>>> p, p prime. That function is f(a,b)=(ab+1)/(b-a), operated mod p.
>>> This function is not commutative and is not associative. To make
>>> this clearer

<snip>

> Calculus and so on. Even a meet-in-the-middle cannot be build as
> with
>>> one result the table Ti cannot be recalculated, and one base
>>> parameter is unknown.
>>
>> Need to read this interesting information in a deeper sense.
>>
>> Thank you Daniel.
>
> Hi Chris,
>
> Yes, this is interesting to say the very least. My intuitive take is
> that Daniel is planning a number system of some sort that is less
> transparent than the traditional number line that may have any period
> and any direction. I am guessing that it will use some system of
> asymmetric periodicity between integers that is somehow serviced by
> modular arithmetic ? and of course is reversibly controllable so as
> to be decipherable by Bob.
>
> He has extended the hand of welcome to you which I read as a sound
> move - Good Luck to you both.
>
> adacrypt
>

I guess I'm not doing a favor to myself answering you but I must admit
that your insistence in criticizing the number line has influenced my
thoughts. I will speak more about number circle, since exponentiation
modulo p and product in elliptic curves are more a circle than a line.
Anyway the idea is to escape from cyclic groups. Well. I've published
this here because I think is a good finding, and as someone say only an
idiot keeps its findings for himself. Good sentence, provided and idiot
can find anything worth and the question if it's preferable for idiots
to actually keep their findings private.

Regards
Daniel

[austin...@hotmail.com]

Cheers - Austin



























- Austin

[richar...@gmail.com]

On Wednesday, January 18, 2017 at 6:53:42 AM UTC-5, Daniel wrote:
> El 18/01/17 a les 09:38, austin..@hotmail.com ha escrit:

Hi Daniel,

On first pass this looks promising. I'd love to dig deeper into this and help write it.

Richard

[Daniel]

El 22/01/17 a les 11:58, richar...@gmail.com ha escrit:

Thank you. How we do this? There's some solved issues not explained in
the original post, nothing bad. I've done my own criptoanalisys and
seems ok. I'm not seeing myself writing a latex paper, but some
explanations (dig deeper) must be done. But, first, let me introduce me:

My name is Daniel Nager Piazuelo, I'm 47, I left computer engineering
due to boredom and personal problems, I'm from Barcelona (spain yet) and
still live in Barcelona, I've paranoid schizophrenic disorder but good
ability for logic.

Next, do you want to do this in public or in private? I personally
prefer public discussion. So, how we do this? :) I'm clueless.

Daniel

[amplituhedron]

On Sunday, January 22, 2017 at 8:45:37 AM UTC-5, Daniel wrote:
> El 22/01/17 a les 11:58, richard..@gmail.com ha escrit:

Hey Daniel,

Thanks for sharing your work. Honestly, I think there's arguments for working publicly and privately. In my experience, I think it's better to work under the radar as much as reasonably possible until it's all fleshed out.

[Daniel]

El 22/01/17 a les 16:42, amplituhedron ha escrit:
> On Sunday, January 22, 2017 at 8:45:37 AM UTC-5, Daniel wrote:
>> El 22/01/17 a les 11:58, richard..@gmail.com ha escrit:

>>> On Wednesday, January 18, 2017 at 6:53:42 AM UTC-5, Daniel
>>> wrote:
>>>> El 18/01/17 a les 09:38, austin..@hotmail.com ha escrit:
>>>>> On Monday, January 16, 2017 at 7:58:07 PM UTC, Chris M.
>>>>> Thomasson wrote:
>>>>>> On 1/16/2017 5:00 AM, Daniel wrote:
>>>>>>> Informally speaking, we define a function of two numbers
>>>>>>> modulo p, p prime. That function is f(a,b)=(ab+1)/(b-a),
>>>>>>> operated mod p.

<snip>

>>>> Regards Daniel
>>>
>>> Hi Daniel,
>>>
>>> On first pass this looks promising. I'd love to dig deeper into
>>> this and help write it.
>>>
>>> Richard
>>>
>>
>> Thank you. How we do this? There's some solved issues not explained
>> in the original post, nothing bad. I've done my own criptoanalisys
>> and seems ok. I'm not seeing myself writing a latex paper, but some
>> explanations (dig deeper) must be done. But, first, let me
>> introduce me:
>>
>> My name is Daniel Nager Piazuelo, I'm 47, I left computer
>> engineering due to boredom and personal problems, I'm from
>> Barcelona (spain yet) and still live in Barcelona, I've paranoid
>> schizophrenic disorder but good ability for logic.
>>
>> Next, do you want to do this in public or in private? I personally
>> prefer public discussion. So, how we do this? :) I'm clueless.
>>
>> Daniel

>

> Hey Daniel,
>
> Thanks for sharing your work. Honestly, I think there's arguments

> for working publicly and privately. In my experience the community
> is not very friendly to newcomers who have "aha" moments.
>
> Consider the reaction to early ideas of Quantum Computing and
> DNA/Molecular Computing back in 2000. There were leading experts in
> cryptography /mocking/ the idea that there was even commercial value
> in any of it. Most argued that QCs would simply be faster computers.
>
>
> Most were unfamiliar with the ideas of Quantum Superposition, and
> although some knew about they knew about Shor's algorithm since 1994,
> they didn't really read it closely, or they would have realized the
> fact that if you could implement Shor's algorithm with a QC (or
> analog computer, or DNA/RNA/molecular computer), it would allow a
> whole class of hard problems to be solved.
>
> Some said, what's the point of even trying to implement it. They
> didn't see even the value behind having an efficient solution to the
> Traveling Salesman Problem, because they didn't see that it
> generalizes to all kinds of graphs, and has unbounded utility.
>

You're right, with private I meant exchanging emails with Richard Hein
exclusively or do some work here in sci.crypt, that's almost private
because we are four and the grandmother (spanish expression). But
anyway, I haven't got a decent webserver or newsserver, no research
department and really nothing usable.

I take the word of Richard and I'm expecting his answer. Needless to say
my English really needs help.

Daniel

[amplituhedron]

That's me.

I would encourage you to continue discussions here for a while about the design. I'm not suggesting keeping everything secret, just not advertising everything yet.

- Richard Hein

[Chris M. Thomasson]

I wish you all the luck in the world! Documentation vs Tutorial. The
former teaches the meaning, the latter helps implement the former. I
need to work on the former. I guess my only advise, that I reaped from
this group, is to assume the reader is a man on the street. Can they get
it after reading your paper?

[Jeffrey Goldberg]

On 1/16/17 7:00 AM, Daniel wrote:

> Our working numbers will be positive integers modulo a prime p, this is
> in the range [0..p-1]. Next we need to define a function of two such
> values, a and b, so:
>
> f(a,b)=(ab+1)/(b-a) (mod p)

[...]

> Now a mixing function is needed, let's call it mixf, that takes two
> values mod p, and a bit string key as parameters:
>
> r=mixf(a,b,k)
>
> Let's construct a table of values enough to fit the size of k:
>
> t[0]=a
> t[1]=b
> t[i]=f(t[i-2],t[i-1])
> ...
>
> Now let's set r to the element in t[i] corresponding to the index of the
> first 1 in k. From there on and in increasing order we operate
>
> r=f(r,t[j])
>
> for each k[j]=1 until the key is exhausted. This is similar to the
> procedure used for exponentiation by squaring, but in a fibbonacci form.
>
> Hard Problem:
>
> Given r=mixf(a,b,k), where a and k are known and b is secret, finding b
> is hard, as hard of the bit size of the prime p.

Do you have a good reason to claim that that is hard?

Also, given your point that mixf() is a lot like exponentiation in
a finite field, how do you support the claim that even if this is
classically hard, it is post-quantum?

Cheers,

-j

--
Jeffrey Goldberg http://goldmark.org/jeff/
I rarely read HTML or poorly quoting posts
Reply-To address is valid

[Daniel]

El 06/02/17 a les 07:00, Jeffrey Goldberg ha escrit:

It's like an exponentiation in a finite field, but just the aspect of
the operations involved, as the operation I use (in a finite field will
be product) is nor associative neither commutative then no operations on
the 'exponent' can be done. It's just a string of bits.

Let me explain this better with an example of an exponentiation, I'll
use a*b instead of f(a,b) to make notation simpler. The table of
'squares' is:

a, b, a*b, b*(a*b), (a*b)*(b*(a*b)), and so on.

Remember '*' operation is not associative so you cannot conclude that:

(a*b)*(b*(a*b))=a^2*b^3

so you have a growing formula that after, say, 256 'squaring' gives a
tree of brakets the size of fibbonaci(256), that's intractable and you
cannot remove brackets. If you try to develop a polynomial P(b)
developing the formula f(a,b)=(ab+1)/(b-a) (mod p) you'll get an
intractable polynomial in the numerator with fibbonaci(256) terms,
something like:

c1 b^(fib(256))+c2 b^(fib(256)-1)+c3 b^(fib(256)-2), and so on (c1, c2,
c3... are the coefficients of each term. That's intractable as well.


Now if your exponent has bits in it's upper part, the msb, and provided
that the exponent, that's only a key, doesn't have an apparent inverse
and cannot be mapped to an operation where the secret or hidden base can
be found, then is safe, and post-quantum, as long as some different
algorithm than Shor is invented. Groover can work the usual way (well,
as I understand it as I'm not claiming being an expert in quantum
computer, my only premise is that the pseudo-exponentiation is
orderless, it's order has little sense and depends on base values a and
b, and b is secret).

Finally, (Z/pZ, f(a,b)) is not a group. No commutativity, no
associativity, no neutral element, no identity element. Well. It's main
property is the absence of properties, at least group properties. This
aids in safety.

A marginal comment is that is an unknown base schema like ("like") the
old rsa. If I give you b^e(mod pq) and I hide b and publish e you cannot
get b without factoring pq. This is just an analogy, remember the "like".

Regards
Daniel

And excuse me if I'm too concise, writing English is painful to me. I
get a red underlined word out of each two.