An inner product (IP) argument is a proof system that convinces the verifier of an IP relation between committed integer vectors. IP arguments are crucial building blocks for range proof and zero knowledge arguments, which can be applied to verifiable computation, confidential transactions, decentralized identification, and so on. This paper proposes a novel efficient IP argument with a trustless setup. For integer vectors of size N, the proposed IP argument provides a proof size of O(log2 N), a verification cost of O(√N), and a size of public parameter size of O(√N). The construction uses bilinear pairings and its security relies solely on the discrete logarithm (DL) assumption, a well-established standard cryptographic assumption. Consequently, we obtain the first DL-based IP argument with a trustless setup that achieves a sublinear verifier and logarithmic proof size, which we call Leopard. Furthermore, We empirically evaluate the performance of Leopard. The experimental results demonstrate that Leopard is highly efficient and scalable compared to previous works.

Keystroke data collected from smart devices includes various sensitive information about users. Collecting and analyzing such data raise serious privacy concerns. Google and Apple have recently applied local differential privacy (LDP) to address privacy issue on learning new words from users' keystroke data. However, these solutions require multiple LDP reports for a single word, which result in inefficient use of privacy budget and high computational cost. In this paper, we develop a novel algorithm for learning new words under LDP. Unlike the existing solutions, the proposed method generates only one LDP report for a single word. This enables the proposed method to use full privacy budget for generating a report and brings the benefit that the proposed method provides better utility at the same privacy degree than the existing methods. In our algorithm, each user appends a hash value to new word and sends only one LDP report of an n-gram selected randomly from the string packed by each new word and its hash value. The server then decodes frequent n-grams at each position of the string and discovers the candidate words by exploring graph-theoretic links between n-grams and checking integrity of candidates with hash values. Frequencies of frequent new words discovered are estimated from distribution estimates of n-grams by robust regression. We theoretically show that our algorithm can recover popular new words even though the server does not know the domain of the raw data. In addition, we theoretically and empirically demonstrate that our algorithm achieves higher accuracy compared to the existing solutions.

There are recommendation systems everywhere in our daily life. The collection of personal data of users by a recommender in the system may cause serious privacy issues. In this article, we propose the first privacy-preserving matrix factorization for recommendation using fully homomorphic encryption. Our protocol performs matrix factorization over encrypted users’ rating data and returns encrypted outputs so that the recommendation system learns nothing on rating values and resulting user/item profiles. Furthermore, the protocol provides a privacy-preserving method to optimize the tuning parameters that can be a business benefit for the recommendation service providers. To overcome the performance degradation caused by the use of fully homomorphic encryption, we introduce a novel data structure to perform computations over encrypted vectors, which are essential for matrix factorization, through secure two-party computation in part. Our experiments demonstrate the efficiency of our protocol.

Recommender systems are collecting and analyzing user data to provide better user experience. However, several privacy concerns have been raised when a recommender knows user's set of items or their ratings. A number of solutions have been suggested to improve privacy of legacy recommender systems, but the existing solutions in the literature can protect either items or ratings only. In this paper, we propose a recommender system that protects both user's items and ratings. For this, we develop novel matrix factorization algorithms under local differential privacy (LDP). In a recommender system with LDP, individual users randomize their data themselves to satisfy differential privacy and send the perturbed data to the recommender. Then, the recommender computes aggregates of the perturbed data. This framework ensures that both user's items and ratings remain private from the recommender. However, applying LDP to matrix factorization typically raises utility issues with i) high dimensionality due to a large number of items and ii) iterative estimation algorithms. To tackle these technical challenges, we adopt dimensionality reduction technique and a novel binary mechanism based on sampling. We additionally introduce a factor that stabilizes the perturbed gradients. With MovieLens and LibimSeTi datasets, we evaluate recommendation accuracy of our recommender system and demonstrate that our algorithm performs better than the existing differentially private gradient descent algorithm for matrix factorization under stronger privacy requirements.

Recommendation systems become popular in our daily life. It is well known that the more the release of users' personal data, the better the quality of recommendation. However, such services raise serious privacy concerns for users. In this paper, focusing on matrix factorization-based recommendation systems, we propose the first privacy-preserving matrix factorization using fully homomorphic encryption. On inputs of encrypted users' ratings, our protocol performs matrix factorization over the encrypted data and returns encrypted outputs so that the recommendation system knows nothing on rating values and resulting user/item profiles. It provides a way to obfuscate the number and list of items a user rated without harming the accuracy of recommendation, and additionally protects recommender's tuning parameters for business benefit and allows the recommender to optimize the parameters for quality of service. To overcome performance degradation caused by the use of fully homomorphic encryption, we introduce a novel data structure to perform computations over encrypted vectors, which are essential operations for matrix factorization, through secure 2-party computation in part. With the data structure, the proposed protocol requires dozens of times less computation cost over those of previous works. Our experiments on a personal computer with 3.4 GHz 6-cores 64 GB RAM show that the proposed protocol runs in 1.5 minutes per iteration. It is more efficient than Nikolaenko et al.'s work proposed in CCS 2013, in which it took about 170 minutes on two servers with 1.9 GHz 16-cores 128 GB RAM.

The Tate pairing computation consists of two parts: Miller step and final exponentiation step. In this paper, we investigate the structure of the final exponentiation step. Consider an orderrsubgroup of an elliptic curve defined over Fqwith embedding degreek. The final exponentiation in the Tate pairing is an exponentiation of an element in Fqkby (qk-1)/r. The hardest part of this computation is to raise to the power λ:=Φk(q)/r, where Φk(·) denotes thekth cyclotomic polynomial. Write it as λ = λ0+λ1q+⋯+λφ(k)-1qφ(k)-1in theq-ary representation. The final exponentiation cost mostly depends on κ(λ), the size of the maximum of |λi|. In many parameterized pairing-friendly curves, the value κ is about (1-1/ρφ(k))log2qwhere ρ = log2q/log2r, while random curves will have κ ≈ log2q. We investigate how this small κ is obtained for parameterized pairing-friendly elliptic curves, and show that (1-1/ρφ(k))log2qis the lower bound for all known construction methods of parameterized pairing-friendly curves. In the second part of our paper, we propose a method to obtain a modified Tate pairing with small κ for any pairing-friendly elliptic curves including those not belonging to parameterized families. More precisely, our method finds an integermusing the lattice basis reduction such that κ(mλ)=(1-1/ρφ(k))log2q. Using this modified Tate pairing, we can reduce the number of squarings in the final exponentiation by a factor of (1-1/ρφ(k)) from the usual Tate pairing. We apply our method to several known pairing-friendly curves to verify the expected speedup.

Hoffstein and Silverman suggested the use of low Hamming weight product (LHWP) exponents to accelerate group exponentiation while maintaining the security level. With LHWP exponents, the computation costs onGF(2n) or Koblitz elliptic curves can be reduced significantly, where the cost of squaring and elliptic curve doubling is much lower than that of multiplication and elliptic curve addition, respectively. In this paper, we present a parameterized splitting system with an additional property, which is a refinement version of the system introduced in PKC'08. We show that it yields an algorithm for the discrete logarithm problem (DLP) with LHWP exponents with lower complexity than that of any previously known algorithms. To demonstrate its application, we attack the GPS identification scheme modified by Coron, Lefranc, and Poupard in CHES'05 and the DLP with Hoffstein and Silverman's (2,2,11)-exponent. The time complexity of our key recovery attack against the GPS scheme is261.82, which was expected to be278. Hoffstein and Silverman's (2,2,11)-exponent can be recovered with a time complexity of253.02, which is the lowest among the known attacks.