MOBILITY ENGINEERING Produced by SAE Media Group
MOBILITY ENGINEERING
Magazines
Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Using Mathematics to Make Computing on Encrypted Data Secure and Practical

Developing new algorithms to improve data security.

In order to make computing on encrypted data more practical to use and more secure from attack, it is necessary to discover, develop, and understand the mathematics on which it is based and the mathematics that can be used to attack it.

The security of homomorphic encryption schemes is based on the presumed difficulty of mathematics problems about lattices. Discovering and fully exploring algorithms to solve these mathematical problems allow computing on encrypted data to be performed with confidence, knowing that its cryptographic security is based on sound mathematical foundations.

Hendrik Lenstra and Alice Silverberg discovered and developed algorithms to solve some lattices problems under suitable conditions, and investigated the mathematical foundations of these algorithms. A primary method of attack on homomorphic encryption schemes consists of lattice algorithms performed on ideal lattices, which are lattices with a certain type of algebraic structure. Any structure or symmetry is potentially susceptible to exploitation and attack. The work performed here gives algorithms for lattice problems for lattices that have symmetry. Recommendations are that the mathematical foundations of lattices with symmetry be further developed, in order to quantify the security of lattice-based cryptography, including especially the security of homomorphic encryption schemes.

In encryption schemes, one party encrypts a plaintext message to obtain a ciphertext. The other party decrypts the ciphertext to recover the plaintext. In Fully Homomorphic Encryption (FHE), parties that do not know the plaintext data can perform computations on it by performing computations on the corresponding ciphertexts.

The security of essentially all currently known FHE schemes is based on the presumed difficulty of some lattice problem, such as finding an approximately shortest (non-zero) vector in a high dimensional lattice. The primary known attacks on FHE schemes are variants of the LLL lattice basis reduction algorithm, originally due to Lenstra, Lenstra, and Lovász.

A number of Fully Homomorphic Encryption schemes use ideal lattices rather than arbitrary lattices, including Gentry’s first FHE scheme. Fully Homomorphic Encryption is performed more efficiently with ideal lattices than with general lattices. However, ideal lattices are very special lattices, with much structure (“symmetries”) that has the potential to be exploited, and it might turn out to be the case that lattice attacks are easier for ideal lattices than for generic lattices.

Gentry and Szydlo introduced some powerful new ideas that combined in a clever way lattice basis reduction and number theory. They used these ideas to cryptanalyze NTRU (NTRUEncrypt Public Key Cryptosystem) Signatures. The recent interest in Fully Homomorphic Encryption and in the candidate multilinear maps of Garg-Gentry-Halevi have renewed the interest in the Gentry-Szydlo results.

The algorithm of Gentry and Szydlo can be viewed as a way to find an orthonormal basis (if one exists) for an ideal lattice. Determining whether a lattice has an orthonormal basis is in general a difficult algorithmic problem. The results of this research show that this problem is easier when the lattice has many symmetries. Lenstra and Silverberg construct a provably deterministic polynomial-time algorithm that decides whether a given lattice with sufficiently many symmetries has an orthonormal basis, and finds one if it does. More precisely, they give a deterministic polynomial-time algorithm that, given a finite abelian group G, an element u in G of order 2, and a G-lattice L, decides whether L and Z〈G〉are G-isomorphic, and if they are, exhibits a G-isomorphism. The Gentry-Szydlo algorithm is put into a mathematical framework, and shown as part of a general theory of “lattices with symmetry,” shedding new light on the Gentry-Szydlo algorithm, and demonstrating that the ideas should be applicable to a range of questions in cryptography.

This work was done by Alice Silverberg and Hendrik Lenstra of the University of California, Irvine for the Air Force Research Laboratory. AFRL-0243

Topics:
Defense Mathematical models Simulation and modeling Software
This Brief includes a Technical Support Package (TSP).
Document cover
USING MATHEMATICS TO MAKE COMPUTING ON ENCRYPTED DATA SECURE AND PRACTICAL

(reference AFRL-0243) is currently available for download from the TSP library.

Don't have an account?

More From SAE Media Group

    Magazine cover
    Aerospace & Defense Technology Magazine

    This article first appeared in the October, 2016 issue of Aerospace & Defense Technology Magazine (Vol. 1 No. 7).

    Read more articles from this issue here.

    Read more articles from the archives here.

    Overview

    The document titled "Using Mathematics to Make Computing on Encrypted Data Secure and Practical" is a final technical report published by the University of California, Irvine, in December 2015, under the auspices of the Air Force Research Laboratory. The report addresses the critical need for secure computing methods on encrypted data, emphasizing the importance of mathematical foundations in developing efficient and secure systems.

    The report begins with a summary of the challenges and opportunities in the field of encrypted data computation. It highlights the growing reliance on encryption for data security and the necessity for robust methods that ensure both confidentiality and functionality. The introduction outlines the significance of homomorphic encryption, which allows computations to be performed on encrypted data without needing to decrypt it first.

    A key focus of the report is the exploration of lattice-based cryptography, particularly lattices with symmetry. The authors recommend further research into the mathematical properties of these lattices to enhance the security and efficiency of encryption schemes. The report discusses the Gentry-Szydlo algorithm, a notable method in the realm of fully homomorphic encryption, and provides insights into its implementation and potential improvements.

    The results and discussion section presents findings from various experiments and theoretical analyses, demonstrating the feasibility of secure computing on encrypted data. The authors emphasize the need for quantifying the security of homomorphic encryption schemes based on ideal lattices, which would provide a framework for comparing different encryption methods and instilling confidence in their security.

    In the recommendations section, the report advocates for the development of mathematical foundations related to symmetric lattices and the rigorous assessment of homomorphic encryption schemes. This research is deemed essential for advancing the field and ensuring that new systems are both efficient and secure.

    The document concludes with a call to action for researchers and practitioners in the field to collaborate on these mathematical foundations, thereby fostering innovation in secure computing. The report serves as a comprehensive resource for understanding the intersection of mathematics and cryptography, providing a roadmap for future research and development in secure data computation.

    Overall, this technical report is a significant contribution to the field of cryptography, offering insights and recommendations that aim to enhance the security and practicality of computing on encrypted data.

    Top Stories

    INSIDERDefense

    Feature Image F-35 Proves Nuke Drop Performance in Stockpile Flight Testing

    INSIDERMaterials

    Feature Image Using Ultrabright X-Rays to Test Materials for Ultrafast Aircraft

    INSIDERManufacturing & Prototyping

    Feature Image Stevens Researchers Test Morkovin's Hypothesis for Major Hypersonic Flight...

    INSIDERManufacturing & Prototyping

    Feature Image New 3D-Printable Nanocomposite Prevents Overheating in Military Electronics

    INSIDERRF & Microwave Electronics

    Feature Image L3Harris Starts Low Rate Production Of New F-16 Viper Shield

    INSIDERRF & Microwave Electronics

    Feature Image F-22 Pilot Controls Drone With Tablet

    Webcasts