Packed leveled fully homomorphic signatures from ideal lattices
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/121640 |
| _version_ | 1826206685763469312 |
|---|---|
| author | Shaar, Daniel. |
| author2 | Vinod Vaikuntanathan. |
| author_facet | Vinod Vaikuntanathan. Shaar, Daniel. |
| author_sort | Shaar, Daniel. |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T13:36:59Z |
| format | Thesis |
| id | mit-1721.1/121640 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:36:59Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1216402019-09-14T03:09:21Z Packed leveled fully homomorphic signatures from ideal lattices Shaar, Daniel. Vinod Vaikuntanathan. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018 Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (page 20). Fully homomorphic signature (FHS) schemes allow users to cryptographically verify the results of arbitrary computation on their signed data by an untrusted server. In a leveled scheme, the maximal circuit depth d of the computation must be fixed during setup. More concretely, a user Alice signs a large dataset {x₁,....,xN} yielding short signatures {[sigma]₁,....,[sigma]N}. She then sends the signed dataset to Bob, an untrusted party, who will perform some computation y = g(x₁,....,xN). Bob will then homomorphically derive a new short signature [sigma][subscript g,y], such that anyone with Alice's verification key can verify the correctness of the computation without the underlying dataset. In this work, we modify a previous FHS scheme [GVW15] by basing our solution on the hardness of the ring small integer solution problem (Ring-SIS) in ideal lattices. Working in this ring setting allows for shorter signatures, smaller key sizes, and more ecient computation. To further improve the eciency of this signature scheme, we also show how to sign a collection of many data items with one short signature. This packing technique is based on batch optimization techniques introduced in [BGV12]. As a modular building block for our homomorphic signature scheme construction, we present a homomorphic trapdoor function (HTDF) construction that supports all functions on its inputs. Additionally, when working with packed inputs, we support two types of operations - pairwise addition (l-Add) and pairwise multiplication (l-Mult). Unlike in [GHS12], we do not show how to perform a data permutation operation (l-Permute), which would allow for arbitrary computation on packed data. Finally, we present an implementation using the PALISADE Lattice Cryptography Library, which we benchmark on certain operations motivated by practical applications. We utilize PALISADE's implementation of an ecient Gaussian sampling algorithm for lattice trapdoors [GPR+17], which is based on the ring setting of [MP12]. by Daniel Shaar. M. Eng. M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2019-07-15T20:30:10Z 2019-07-15T20:30:10Z 2018 2018 Thesis https://hdl.handle.net/1721.1/121640 1098180403 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 20 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Shaar, Daniel. Packed leveled fully homomorphic signatures from ideal lattices |
| title | Packed leveled fully homomorphic signatures from ideal lattices |
| title_full | Packed leveled fully homomorphic signatures from ideal lattices |
| title_fullStr | Packed leveled fully homomorphic signatures from ideal lattices |
| title_full_unstemmed | Packed leveled fully homomorphic signatures from ideal lattices |
| title_short | Packed leveled fully homomorphic signatures from ideal lattices |
| title_sort | packed leveled fully homomorphic signatures from ideal lattices |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/121640 |
| work_keys_str_mv | AT shaardaniel packedleveledfullyhomomorphicsignaturesfromideallattices |