IPCC7 key recovery

[D. J. Bernstein]

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