Product Subset Problem : Applications to number theory and cryptography

2020/02/10 by Draziotis, K. A., Martidis, V., Tiganourias, S.
#11A51 #11T71 #11Y16 #68R05 #94A60 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2002.07095

Abstract

We consider applications of Subset Product Problem (SPP) in number theory and cryptography. We obtain a probabilistic algorithm that attack SPP and we analyze it with respect time/space complexity and success probability. In fact we provide an application to the problem of finding Carmichael numbers and an attack to Naccache-Stern knapsack cryptosystem, where we update previous results.

Related

• Multiple Subset Problem as an encryption scheme for communication
• Division algorithms for the fixed weight subset sum problem
• Tackling A Class of Hard Subset-Sum Problems: Integration of Lattice Attacks with Disaggregation Techniques
• Polynomial-time Method of Determining Subset Sum Solutions
• A knapsack McEliece-based public key cryptosystem