D. J. Bernstein
unread,Oct 4, 2023, 5:30:26 AM10/4/23Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to kpqc-b...@googlegroups.com
It appears to be possible to efficiently find secret keys from IPCC7
public keys with high probability. Please see the attached Sage script
for details. Inserting
for (long long i = 0;i < 6*NUMPDS;++i)
printf("pk %lld %d %d\n",i,(int) pk[i][0],(int) pk[i][1]);
printf("pkend\n");
into the C code for IPCC7 produces the appropriate input format for the
Sage script. In experiments with 10 keys, 7 partitioned the vertices
into four sets of size 64, and 3 partitioned the vertices into two sets
of size 64, two sets of size 63, and two sets of size 1. Any of the sets
of size 64 should work for decryption, and we checked that one example
matches the original secret key. We sent our script to the designers,
and they say they see similar results.
We also noticed that the public keys include A-B edges followed by A-C
edges, allowing a simpler attack that intersects those edges to find A.
Sorting the edges before releasing public keys would stop this simpler
attack, but would not affect the attached Sage script.
---D. J. Bernstein, Jolijn Cottaar, and Tanja Lange