Ted Chinburg (U Penn): Using capacity theory to plug leaks

January 9, 12:00-13:00, Seminar room 209, Manchester building.

Abstract:  A famous problem in cryptography has to do with determining the prime factors p and q of a product N = pq given N and leaked information about some fraction of the digits of either p or q.  Coppersmith showed that if N has m digits, and one has either the lowest order m/4 digits of p or the highest order m/4 digits of p, then one can determine N in polynomial time.  In this talk I will discuss how capacity theory shows you can't improve the constant 1/4 in this result using Coppersmith's method. It also shows that the middle m/4 digits of either p or q won't suffice.  In fact, no fraction less than 1 of the middle digits will suffice if one tries to apply Coppersmith's method. 


Thu, 09/01/2020 - 12:00 to 13:00


Manchester Building, Room 209