[Cryptography] Graphs for asymmetric crypto?

Ray Dillinger bear at sonic.net
Wed Jul 29 19:52:08 EDT 2015

Zamir Bavel published a tractable method for finding isomorphisms
in automata (directed graphs in which transitions are driven by
inputs) some years ago.  In general directed graphs (in the
absence of inputs that drive transitions a ) I think it's
probably the best available algorithm but it's still at least
potentially exponential.  In practice though?  Usually faster.
You have to construct some deliberately pathological graphs to
get any exponential behavior with a "base" higher than about

I was in one of his grad classes at University and we covered it
there. It was in this book:  (our text for that class)


He labeled it "Introduction" but don't kid yourself. It's pretty
chewy, even for grad students. I think that these days it's
considered the Standard Reference on automata theory.  It used
to be two volumes, one for graph theory and one for automata;
I think the one for sale now might be both volumes bound in a
single cover. The page count given would support that theory


On 07/29/2015 11:24 AM, Pawel Veselov wrote:
> 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]
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150729/501f98d3/attachment.sig>

More information about the cryptography mailing list