Date:
Thu, 09/01/202012:00-13:00
Location:
Manchester Building, Room 209
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.
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.