Homomorphic encryption and signatures from vector decomposition

Tatsuaki Okamoto*, Katsuyuki Takashima

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

101 Citations (Scopus)


This paper introduces a new concept, distortion eigenvector space; it is a (higher dimensional) vector space in which bilinear pairings and distortion maps are available. A distortion eigenvector space can be efficiently realized on a supersingular hyperelliptic curve or a direct product of supersingular elliptic curves. We also introduce an intractable problem (with trapdoor) on distortion eigenvector spaces, the higher dimensional generalization of the vector decomposition problem (VDP). We define several computational and decisional problems regarding VDP, and clarify the relations among them. A trapdoor bijective function with algebraically rich properties can be obtained from the VDP on distortion eigenvector spaces. This paper presents two applications of this trapdoor bijective function; one is multivariate homomorphic encryption as well as a two-party protocol to securely evaluate 2DNF formulas in a higher dimensional manner, and the other is various types of signatures such as ordinary signatures, blind signatures, generically (selectively and universally) convertible undeniable signatures and their combination.

Original languageEnglish
Title of host publicationPairing-Based Cryptography - Pairing 2008 - Second International Conference, Proceedings
Number of pages18
Publication statusPublished - 2008
Externally publishedYes
Event2nd International Conference on Pairing-Based Cryptography, Pairing 2008 - Egham, United Kingdom
Duration: 2008 Sept 12008 Sept 3

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5209 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Conference on Pairing-Based Cryptography, Pairing 2008
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Homomorphic encryption and signatures from vector decomposition'. Together they form a unique fingerprint.

Cite this