{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/121640"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/121640","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Packed leveled fully homomorphic signatures from ideal lattices","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Shaar, Daniel."],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Vinod Vaikuntanathan."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:21:51Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/121640","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Vinod Vaikuntanathan."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","EECS"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Shaar, Daniel."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-07-15T20:30:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-07-15T20:30:10Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/121640"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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]."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M. Eng."]},{"key":"dc:title","label":"Title","values":["Packed leveled fully homomorphic signatures from ideal lattices"]}]}],"canonical_facts":{"dc:contributor.advisor":["Vinod Vaikuntanathan."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","EECS"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Shaar, Daniel."],"dc:date.accessioned":["2019-07-15T20:30:10Z"],"dc:date.available":["2019-07-15T20:30:10Z"],"dc:date.issued":["2018"],"dc:description":["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)."],"dc:description.abstract":["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]."],"dc:description.degree":["M. Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/121640"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Packed leveled fully homomorphic signatures from ideal lattices"],"dc:type":["Thesis"],"thesis:degree_name":["Master"]},"updated_at":"2026-07-22T22:21:51Z"}