The search functionality is under construction.

Keyword Search Result

[Keyword] homomorphic encryption(22hit)

1-20hit(22hit)

  • Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their Applications

    Daisuke MAEDA  Koki MORIMURA  Shintaro NARISADA  Kazuhide FUKUSHIMA  Takashi NISHIDE  

     
    PAPER

      Pubricized:
    2023/09/14
      Vol:
    E107-A No:3
      Page(s):
    234-247

    We propose how to homomorphically evaluate arbitrary univariate and bivariate integer functions such as division. A prior work proposed by Okada et al. (WISTP'18) uses polynomial evaluations such that the scheme is still compatible with the SIMD operations in BFV and BGV schemes, and is implemented with the input domain ℤ257. However, the scheme of Okada et al. requires the quadratic numbers of plaintext-ciphertext multiplications and ciphertext-ciphertext additions in the input domain size, and although these operations are more lightweight than the ciphertext-ciphertext multiplication, the quadratic complexity makes handling larger inputs quite inefficient. In this work, first we improve the prior work and also propose a new approach that exploits the packing method to handle the larger input domain size instead of enabling the SIMD operation, thus making it possible to work with the larger input domain size, e.g., ℤ215 in a reasonably efficient way. In addition, we show how to slightly extend the input domain size to ℤ216 with a relatively moderate overhead. Further we show another approach to handling the larger input domain size by using two ciphertexts to encrypt one integer plaintext and applying our techniques for uni/bivariate function evaluation. We implement the prior work of Okada et al., our improved version of Okada et al., and our new scheme in PALISADE with the input domain ℤ215, and confirm that the estimated run-times of the prior work and our improved version of the prior work are still about 117 days and 59 days respectively while our new scheme can be computed in 307 seconds.

  • On Extension of Evaluation Algorithms in Keyed-Homomorphic Encryption

    Hirotomo SHINOKI  Koji NUIDA  

     
    PAPER

      Pubricized:
    2023/06/27
      Vol:
    E107-A No:3
      Page(s):
    218-233

    Homomorphic encryption (HE) is public key encryption that enables computation over ciphertexts without decrypting them. To overcome an issue that HE cannot achieve IND-CCA2 security, the notion of keyed-homomorphic encryption (KH-PKE) was introduced (Emura et al., PKC 2013), which has a separate homomorphic evaluation key and can achieve stronger security named KH-CCA security. The contributions of this paper are twofold. First, recall that the syntax of KH-PKE assumes that homomorphic evaluation is performed for single operations, and KH-CCA security was formulated based on this syntax. Consequently, if the homomorphic evaluation algorithm is enhanced in a way of gathering up sequential operations as a single evaluation, then it is not obvious whether or not KH-CCA security is preserved. In this paper, we show that KH-CCA security is in general not preserved under such modification, while KH-CCA security is preserved when the original scheme additionally satisfies circuit privacy. Secondly, Catalano and Fiore (ACM CCS 2015) proposed a conversion method from linearly HE schemes into two-level HE schemes, the latter admitting addition and a single multiplication for ciphertexts. In this paper, we extend the conversion to the case of linearly KH-PKE schemes to obtain two-level KH-PKE schemes. Moreover, based on the generalized version of Catalano-Fiore conversion, we also construct a similar conversion from d-level KH-PKE schemes into 2d-level KH-PKE schemes.

  • I/O Performance Improvement of FHE Apriori with Striping File Layout Considering Storage of Intermediate Data

    Atsuki KAMO  Saneyasu YAMAGUCHI  

     
    LETTER-Data Engineering, Web Information Systems

      Pubricized:
    2023/03/13
      Vol:
    E106-D No:6
      Page(s):
    1183-1185

    Fully homomorphic encryption (FHE) enables secret computations. Users can perform computation using data encrypted with FHE without decryption. Uploading private data without encryption to a public cloud has the risk of data leakage, which makes many users hesitant to utilize a public cloud. Uploading data encrypted with FHE avoids this risk, while still providing the computing power of the public cloud. In many cases, data are stored in HDDs because the data size increases significantly when FHE is used. One important data analysis is Apriori data mining. In this application, two files are accessed alternately, and this causes long-distance seeking on its HDD and low performance. In this paper, we propose a new striping layout with reservations for write areas. This method intentionally fragments files and arranges blocks to reduce the distance between blocks in a file and another file. It reserves the area for intermediate files of FHE Apriori. The performance of the proposed method was evaluated based on the I/O processing of a large FHE Apriori, and the results showed that the proposed method could improve performance by up to approximately 28%.

  • Private Decision Tree Evaluation by a Single Untrusted Server for Machine Learnig as a Service

    Yoshifumi SAITO  Wakaha OGATA  

     
    PAPER

      Pubricized:
    2021/09/17
      Vol:
    E105-A No:3
      Page(s):
    203-213

    In this paper, we propose the first private decision tree evaluation (PDTE) schemes which are suitable for use in Machine Learning as a Service (MLaaS) scenarios. In our schemes, a user and a model owner send the ciphertexts of a sample and a decision tree model, respectively, and a single server classifies the sample without knowing the sample nor the decision tree. Although many PDTE schemes have been proposed so far, most of them require to reveal the decision tree to the server. This is undesirable because the classification model is the intellectual property of the model owner, and/or it may include sensitive information used to train the model, and therefore the model also should be hidden from the server. In other PDTE schemes, multiple servers jointly conduct the classification process and the decision tree is kept secret from the servers under the assumption they do not collude. Unfortunately, this assumption may not hold because MLaaS is usually provided by a single company. In contrast, our schemes do not have such problems. In principle, fully homomorphic encryption allows us to classify an encrypted sample based on an encrypted decision tree, and in fact, the existing non-interactive PDTE scheme can be modified so that the server classifies only handling ciphertexts. However, the resulting scheme is less efficient than ours. We also show the experimental results for our schemes.

  • IND-CCA1 Secure FHE on Non-Associative Ring

    Masahiro YAGISAWA  

     
    PAPER-Cryptography and Information Security

      Pubricized:
    2020/07/08
      Vol:
    E104-A No:1
      Page(s):
    275-282

    A fully homomorphic encryption (FHE) would be the important cryptosystem as the basic scheme for the cloud computing. Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, some fully homomorphic encryption schemes were proposed. In the systems proposed until now the bootstrapping process is the main bottleneck and the large complexity for computing the ciphertext is required. In 2011 Zvika Brakerski et al. proposed a leveled FHE without bootstrapping. But circuit of arbitrary level cannot be evaluated in their scheme while in our scheme circuit of any level can be evaluated. The existence of an efficient fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the field of the cloud computing. In this paper, IND-CCA1secure FHE based on the difficulty of prime factorization is proposed which does not need the bootstrapping and it is thought that our scheme is more efficient than the previous schemes. In particular the computational overhead for homomorphic evaluation is O(1).

  • Verifiable Privacy-Preserving Data Aggregation Protocols

    Satoshi YASUDA  Yoshihiro KOSEKI  Yusuke SAKAI  Fuyuki KITAGAWA  Yutaka KAWAI  Goichiro HANAOKA  

     
    PAPER

      Vol:
    E103-A No:1
      Page(s):
    183-194

    Homomorphic encryption allows computation over encrypted data, and can be used for delegating computation: data providers encrypt their data and send them to an aggregator, who can then perform computation over the encrypted data on behalf of a client, without the underlying data being exposed to the aggregator. However, since the aggregator is merely a third party, it may be malicious, and in particular, may submit an incorrect aggregation result to the receiver. Ohara et al. (APKC2014) studied secure aggregation of time-series data while enabling the correctness of aggregation to be verified. However, they only provided a concrete construction in the smart metering system and only gave an intuitive argument of security. In this paper, we define verifiable homomorphic encryption (VHE) which generalizes their scheme, and introduce formal security definitions. Further, we formally prove that Ohara et al.'s VHE scheme satisfies our proposed security definitions.

  • Fully Homomorphic Encryption Scheme Based on Decomposition Ring Open Access

    Seiko ARITA  Sari HANDA  

     
    PAPER

      Vol:
    E103-A No:1
      Page(s):
    195-211

    In this paper, we propose the decomposition ring homomorphic encryption scheme, that is a homomorphic encryption scheme built on the decomposition ring, which is a subring of cyclotomic ring. By using the decomposition ring the structure of plaintext slot becomes ℤpl, instead of GF(pd) in conventional schemes on the cyclotomic ring. For homomorphic multiplication of integers, one can use the full of ℤpl slots using the proposed scheme, although in conventional schemes one can use only one-dimensional subspace GF(p) in each GF(pd) slot. This allows us to realize fast and compact homomorphic encryption for integer plaintexts. In fact, our benchmark results indicate that our decomposition ring homomorphic encryption schemes are several times faster than HElib for integer plaintexts due to its higher parallel computation.

  • Hardware-Accelerated Secured Naïve Bayesian Filter Based on Partially Homomorphic Encryption

    Song BIAN  Masayuki HIROMOTO  Takashi SATO  

     
    PAPER-Cryptography and Information Security

      Vol:
    E102-A No:2
      Page(s):
    430-439

    In this work, we provide the first practical secure email filtering scheme based on homomorphic encryption. Specifically, we construct a secure naïve Bayesian filter (SNBF) using the Paillier scheme, a partially homomorphic encryption (PHE) scheme. We first show that SNBF can be implemented with only the additive homomorphism, thus eliminating the need to employ expensive fully homomorphic schemes. In addition, the design space for specialized hardware architecture realizing SNBF is explored. We utilize a recursive Karatsuba Montgomery structure to accelerate the homomorphic operations, where multiplication of 2048-bit integers are carried out. Through the experiment, both software and hardware versions of the SNBF are implemented. On software, 104-105x runtime and 103x storage reduction are achieved by SNBF, when compared to existing fully homomorphic approaches. By instantiating the designed hardware for SNBF, a further 33x runtime and 1919x power reduction are achieved. The proposed hardware implementation classifies an average-length email in under 0.5s, which is much more practical than existing solutions.

  • Proxy Re-Encryption That Supports Homomorphic Operations for Re-Encrypted Ciphertexts

    Yutaka KAWAI  Takahiro MATSUDA  Takato HIRANO  Yoshihiro KOSEKI  Goichiro HANAOKA  

     
    PAPER

      Vol:
    E102-A No:1
      Page(s):
    81-98

    Homomorphic encryption (HE) is useful to analyze encrypted data without decrypting it. However, by using ordinary HE, a user who can decrypt a ciphertext that is generated by executing homomorphic operations, can also decrypt ciphertexts on which homomorphic evaluations have not been performed, since homomorphic operations cannot be executed among ciphertexts which are encrypted under different public keys. To resolve the above problem, we introduce a new cryptographic primitive called Homomorphic Proxy Re-Encryption (HPRE) combining the “key-switching” property of Proxy Re-Encryption (PRE) and the homomorphic property of HE. In our HPRE, original ciphertexts (which have not been re-encrypted) guarantee CCA2 security (and in particular satisfy non-malleability). On the other hand, re-encrypted ciphertexts only guarantee CPA security, so that homomorphic operations can be performed on them. We define the functional/security requirements of HPRE, and then propose a specific construction supporting the group operation (over the target group in bilinear groups) based on the PRE scheme by Libert and Vergnaud (PKC 2008) and the CCA secure public key encryption scheme by Lai et al. (CT-RSA 2010), and prove its security in the standard model. Additionally, we show two extensions of our HPRE scheme for the group operation: an HPRE scheme for addition and an HPRE scheme for degree-2 polynomials (in which the number of degree-2 terms is constant), by using the technique of the recent work by Catalano and Fiore (ACMCCS 2015).

  • Efficient Homomorphic Encryption with Key Rotation and Security Update

    Yoshinori AONO  Takuya HAYASHI  Le Trieu PHONG  Lihua WANG  

     
    PAPER

      Vol:
    E101-A No:1
      Page(s):
    39-50

    We present the concept of key-rotatable and security-updatable homomorphic encryption (KR-SU-HE) scheme, which is defined as a class of public-key homomorphic encryption in which the keys and the security of any ciphertext can be rotated and updated while still keeping the underlying plaintext intact and unrevealed. After formalising the syntax and security notions for KR-SU-HE schemes, we build a concrete scheme based on the Learning With Errors assumption. We then perform several careful implementations and optimizations to show that our proposed scheme is efficiently practical.

  • Input and Output Privacy-Preserving Linear Regression

    Yoshinori AONO  Takuya HAYASHI  Le Trieu PHONG  Lihua WANG  

     
    PAPER-Privacy, anonymity, and fundamental theory

      Pubricized:
    2017/07/21
      Vol:
    E100-D No:10
      Page(s):
    2339-2347

    We build a privacy-preserving system of linear regression protecting both input data secrecy and output privacy. Our system achieves those goals simultaneously via a novel combination of homomorphic encryption and differential privacy dedicated to linear regression and its variants (ridge, LASSO). Our system is proved scalable over cloud servers, and its efficiency is extensively checked by careful experiments.

  • Privacy-Enhanced Similarity Search Scheme for Cloud Image Databases

    Hao LIU  Hideaki GOTO  

     
    LETTER-Information Network

      Pubricized:
    2016/09/12
      Vol:
    E99-D No:12
      Page(s):
    3188-3191

    The privacy of users' data has become a big issue for cloud service. This research focuses on image cloud database and the function of similarity search. To enhance security for such database, we propose a framework of privacy-enhanced search scheme, while all the images in the database are encrypted, and similarity image search is still supported.

  • Challenges of Fully Homomorphic Encryptions for the Internet of Things Open Access

    Licheng WANG  Jing LI  Haseeb AHMAD  

     
    INVITED PAPER

      Pubricized:
    2016/05/31
      Vol:
    E99-D No:8
      Page(s):
    1982-1990

    With the flourish of applications based on the Internet of Things (IoT), privacy issues have been attracting a lot of attentions. Although the concept of privacy homomorphism was proposed along with the birth of the well-known RSA cryptosystems, cryptographers over the world have spent about three decades for finding the first implementation of the so-called fully homomorphic encryption (FHE). Despite of, currently known FHE schemes, including the original Gentry's scheme and many subsequent improvements as well as the other alternatives, are not appropriate for IoT-oriented applications because most of them suffer from the problems of inefficient key size and noisy restraining. In addition, for providing fully support to IoT-oriented applications, symmetric fully homomorphic encryptions are also highly desirable. This survey presents an analysis on the challenges of designing secure and practical FHE for IoT, from the perspectives of lightweight requirements as well as the security requirements. In particular, some issues about designing noise-free FHE schemes would be addressed.

  • Privacy-Preserving Logistic Regression with Distributed Data Sources via Homomorphic Encryption

    Yoshinori AONO  Takuya HAYASHI  Le Trieu PHONG  Lihua WANG  

     
    PAPER

      Pubricized:
    2016/05/31
      Vol:
    E99-D No:8
      Page(s):
    2079-2089

    Logistic regression is a powerful machine learning tool to classify data. When dealing with sensitive or private data, cares are necessary. In this paper, we propose a secure system for privacy-protecting both the training and predicting data in logistic regression via homomorphic encryption. Perhaps surprisingly, despite the non-polynomial tasks of training and predicting in logistic regression, we show that only additively homomorphic encryption is needed to build our system. Indeed, we instantiate our system with Paillier, LWE-based, and ring-LWE-based encryption schemes, highlighting the merits and demerits of each instantiation. Besides examining the costs of computation and communication, we carefully test our system over real datasets to demonstrate its utility.

  • Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation

    Pyung KIM  Younho LEE  Hyunsoo YOON  

     
    PAPER-Fundamental Theories for Communications

      Vol:
    E99-B No:5
      Page(s):
    1070-1086

    In this paper, we present a faster (wall-clock time) sorting method for numerical data subjected to fully homomorphic encryption (FHE). Owing to circuit-based construction and the FHE security property, most existing sorting methods cannot be applied to encrypted data without significantly compromising efficiency. The proposed algorithm utilizes the cryptographic single-instruction multiple-data (SIMD) operation, which is supported by most existing FHE algorithms, to reduce the computational overhead. We conducted a careful analysis of the number of required recryption operations, which are the computationally dominant operations in FHE. Accordingly, we verified that the proposed SIMD-based sorting algorithm completes the given task more quickly than existing sorting methods if the number of data items and (or) the maximum bit length of each data item exceed specific thresholds.

  • Packing Messages and Optimizing Bootstrapping in GSW-FHE

    Ryo HIROMASA  Masayuki ABE  Tatsuaki OKAMOTO  

     
    PAPER

      Vol:
    E99-A No:1
      Page(s):
    73-82

    We construct the first fully homomorphic encryption (FHE) scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from Õ(n3) to Õ(n2.5). By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption without successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.

  • On Discrete Logarithm Based Additively Homomorphic Encryption

    Jae Hong SEO  Keita EMURA  

     
    LETTER-Cryptography and Information Security

      Vol:
    E96-A No:11
      Page(s):
    2286-2289

    In this paper, we examine additive homomorphic encryptions in the discrete logarithm setting. Recently, Wang et al. proposed an additive homomorphic encryption scheme by modifying the ElGamal encryption scheme [Information Sciences 181(2011) 3308-3322]. We show that their scheme allows only limited number of additions among encrypted messages, which is different from what they claimed.

  • An Efficient Non-interactive Universally Composable String-Commitment Scheme

    Ryo NISHIMAKI  Eiichiro FUJISAKI  Keisuke TANAKA  

     
    PAPER-Secure Protocol

      Vol:
    E95-A No:1
      Page(s):
    167-175

    This paper presents a new non-interactive string-commitment scheme that achieves universally composable security. Security is proven under the decisional composite residuosity (DCR) assumption (or the decisional Diffie-Hellman (DDH) assumption) in the common reference string (CRS) model. The universal composability (UC) is a very strong security notion. If cryptographic protocols are proven secure in the UC framework, then they remain secure even if they are composed with arbitrary protocols and polynomially many copies of the protocols are run concurrently. Many UC commitment schemes in the CRS model have been proposed, but they are either interactive commitment or bit-commitment (not string-commitment) schemes. We note, however, that although our scheme is the first non-interactive UC string-commitment scheme, a CRS is not reusable. We use an extension of all-but-one trapdoor functions (ABO-TDFs) proposed by Peikert and Waters at STOC 2008 as an essential building block. Our main idea is to extend (original deterministic) ABO-TDFs to probabilistic ones by using the homomorphic properties of their function indices. The function indices of ABO-TDFs consist of ciphertexts of homomorphic encryption schemes (such as ElGamal, and Damgåd-Jurik encryption). Therefore we can re-randomize the output of ABO-TDFs by re-randomization of ciphertexts. This is a new application of ABO-TDFs.

  • Multiparty Computation from El Gamal/Paillier Conversion

    Koji CHIDA  Hiroaki KIKUCHI  Keiichi HIROTA  Gembu MOROHASHI  

     
    PAPER-Secure Protocol

      Vol:
    E92-A No:1
      Page(s):
    137-146

    We propose a protocol for converting the encryption function of a ciphertext into another encryption function while keeping the corresponding message secret. The proposed protocol allows conversions of the El Gamal and Paillier cryptosystems and has the potential to design an efficient multiparty protocol intended for circuits consisting of arithmetic and logical operations. We clarify the condition of circuits such that the multiparty protocol based on the proposed protocol provides better performance than previous approaches. In addition, we introduce some privacy-preserving statistical computations as an effective application of the proposed protocol.

  • Efficient Divisible Voting Scheme

    Natsuki ISHIDA  Shin'ichiro MATSUO  Wakaha OGATA  

     
    PAPER-Application

      Vol:
    E88-A No:1
      Page(s):
    230-238

    Electronic voting is a prime application of cryptographic tools. Many researches are addressing election or confidence voting in this area. We address a new type of voting scheme "Divisible Voting Scheme," in which each voter has multiple ballots where the number of ballots can be different among the voters. This type of voting is popular. We first define the divisible voting scheme and show naive protocols based on existing voting schemes. Then we propose two efficient divisible voting schemes. The first scheme uses multisets, the second scheme uses L-adic representation of the number of ballots. The total cost for a voter is O(M 2 log (N)) in the first scheme and O(M log (N)) in the second scheme where M is the number of candidates to vote for and N is the number of ballots for a voter.

1-20hit(22hit)