Sparse subset sum problem from Gentry–Halevi's fully homomorphic encryption. (1st January 2017)

• Record Type: Journal Article
• Authors: Lee, Moon Sung
• Is Part Of: IET information security. Volume 11:Number 1(2017)
• Page Start: 34
• Page End: 37
• Publication Date: 2017-01-01
• Subjects: public key cryptography -- geometry -- lattice theory -- set theory; sparse subset sum problem -- Gentry‐Halevi fully homomorphic encryption scheme -- SSSP -- public key -- geometric progressions -- lattice‐based attack -- middle attack; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2015.0263
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : In Gentry's fully homomorphic encryption scheme, a sparse subset sum problem (SSSP) is used and a big set is included in the public key. In the implementation of a variant, to reduce the size of the public key, Gentry and Halevi used a specific form of a SSSP constructed from geometric progressions. In this study, the authors solve Gentry and Halevi's sparse subset sum challenges for the first time. Owing to the aggressive choice of parameters, the process is fairly easy and can be done by simply modifying their lattice‐based attack. Their experiment shows that even a large challenge can be solved within two days. As a second contribution, considering other attacks such as a hybrid attack combining a meet in the middle attack with a lattice‐based attack, they provide a new condition for hard instances of the SSSP from geometric progressions.