[Cryptography] Where to Find PQC Crypto Libraries?

Jeff Burdges burdges at gnunet.org
Mon Aug 8 12:38:05 EDT 2016


Yes, I'm not going to stand by that claim at all.  :)

I'll attempt to explain what I meant with this quote form page 18 of
https://eprint.iacr.org/2011/506 : 

"For both ordinary and supersingular curves, there is a natural
bijection between isogenies (up to isomorphism) and (left) ideals in the
endomorphism ring. In the ordinary case the endomorphism ring is
commutative, and ideal classes form a finite abelian group. This
property has been used by Childs et al. [10] to solve the ordinary
analogue of CSSI in quantum subexponential time. It is natural to ask
whether their algorithm can be adapted to the supersingular setting,
but, in this case, the endomorphism ring is a maximal order in a
noncommutative quaternion algebra, and the left ideal classes do not
form a group at all (they form a groupoid, though). Since the algorithm
of Childs et al. depends crucially on the properties of abelian groups,
we believe that no reasonable variant of this strategy would apply to
supersingular curves."

I am not overly sold on the idea that non-commutativity per se buys you
much resistance to quantum algorithms.  There are interesting quantum
algorithms for nilpotent and dihedral hidden subgroup problems, for
example.  

Instead, I suspect our post-quantum algorithms real resistance comes
more from not even being based on a group.  And that quantum algorithms
cannot adapt themselves terribly well to structures like these
groupoids.  Intuitively most products do not even make sense in a
groupoid, so you attempt to say compute periods with a QFT then you just
get zeros.  I think you can embed the groupoid into a larger algebra
where I suppose the QFT makes sense again, but that algebra becomes very
high dimensional, so no longer useful for space reasons.  

I am **not** an expert in this stuff, so do not take anything I say
seriously!  :)

Jeff

p.s. There is something more concrete one can say about this in the
hierarchy of lattice-based systems : Unique SVP is reducible to dihedral
HSP, but apparently not in a way that's useful for breaking crypto
systems based on unique SVP.  As I understand it, LWE based crypto
systems without the ring, like that one in
https://eprint.iacr.org/2016/659 called Frodo, have no known reduction
to group HSP problems.  Again I do not understand this stuff well.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160808/5e02573c/attachment.sig>


More information about the cryptography mailing list