[Cryptography] Graphs for asymmetric crypto?

[Pawel Veselov]

On Tue, Jul 28, 2015 at 1:54 PM, Steve Weis <steveweis at gmail.com> wrote:

> On Tue, Jul 28, 2015 at 12:39 PM, Pawel Veselov <pawel.veselov at gmail.com>
> wrote:
>
>> Are there any articles or papers, or just the lists wise opinion that
>> outline how using graphs for asymmetric crypto stacks up against RSA and
>> ECC?
>>
> Do you have specific graph-based schemes in mind? Or are you asking about
> graphs in crypto in general?
>

Umm, here is what I'm looking it. I came across patent 8,411,854 (
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8,411,854.PN.&OS=PN/8,411,854&RS=PN/8,411,854
)

The suggestion there is to take the hash of the password+salt, and turn it
into permutation function that serves as a "private key". I believe the way
the function is built (I don't know how those things are called, but it
involves turning the hash into factorial polynomial, and using the
coefficient for the mapping table, then enforcing the mapping table doesn't
repeat indexes by shifting away the duplicates). The graphs (though I don't
understand what "kind") are randomly generated.

The whole patent is around ZKP. But I'm trying to understand its value
over, say, SRP6a. I really don't know whether this mechanism is better than
using RSA (or ECC, though SRP6a on its face needs to be modified to support
ECC).

But there are other statements in the patent that I find a bit off:

Graph isomorphism provides an NP (Non-deterministic Polynomial time) space
> wherein ZKP implementations can be produced without the computational
> overhead that has, until now, made ZKP inappropriate for casual user
> authentication.


I think that's really lack of adoption, not expense of the computation.

The graph isomorphism does not require users’ browsers to find co-prime
> numbers nor multiplicative inverses.


multiplicative inverses is for ECC, right? I don't get the co-prime
numbers, are they talking about dh-params? Those aren't needed to be
computed, afaik.

Typically, ZKP challenge-response protocols arc based on:
> the discrete logarithm problem, the square-root problem, or
> elliptical curve cryptography... Nonetheless, in each of the above cases,
> the user’s private key must either be available on a local machine from
> which
> they are trying to authenticate themselves, or the user must
> allow their password to be transmitted across a network.


I also don't get that statement, unless they are comparing ZKP to X.509
auth, which is not fair.

[skipped]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150729/e616e776/attachment.html>