Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Homomorphic encryption and multilinear maps based on the approximate-GCD problem Lima Pereira, Hilder Vitor Doctoral thesis (2020) Cryptographic schemes are constructed on top of problems that are believed to be hard. In particular, recent advanced schemes, as homomorphic primitives and obfuscators, use the approximate greatest ... [more ▼] Cryptographic schemes are constructed on top of problems that are believed to be hard. In particular, recent advanced schemes, as homomorphic primitives and obfuscators, use the approximate greatest common divisor (AGCD) problem, which is simple to describe and easy to implement, since it does not require complex algebraic structures nor hard-to-sample probability distributions. However, in spite of its simplicity, the AGCD problem generally yields inefficient schemes, usually with large ciphertext expansion. In this thesis, we analyze the AGCD problem and several existing variants thereof and propose a new attack on the multi-prime AGCD problem. Then, we propose two new variants: 1. The vector AGCD problem (VAGCD), in which AGCD instances are represented as vectors and randomized with a secret random matrix; 2. The polynomial randomized AGCD problem (RAGCD), that consists of representing AGCD samples as polynomials and randomizing them with a secret random polynomial. We show that these new variants cannot be easier than the original AGCD problem and that all the known attacks, when adapted to the VAGCD and the RAGCD problem, are more expensive both in terms of time and of memory, allowing us then to chose smaller parameters and to improve the efficiency of the schemes using the AGCD as the underlying problem. Thus, by combining techniques from multilinear maps and indistinguishability obfuscation with the VAGCD problem, we provide the first implementation of a N-party non-interactive key exchange resistant against all known attacks. Still aiming to show that the VAGCD problem can lead to performance improvements in cryptographic primitives, we use it to construct a homomorphic encryption scheme that can natively and efficiently operate with vectors and matrices. For instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and 128x128 matrices in less than one second. We also use our scheme in two applications: homomorphic evaluation of nondeterministic finite automata and a Naïve Bayes classifier. Finally, using the RAGCD problem, we construct a new homomorphic scheme for polynomials and we propose new fast bootstrapping procedures for fully homomorphic scheme (FHE) over the integers. Therewith, we can for the first time bootstrap AGCD-based FHE schemes in less than one second in a common personal computer. For the best of our knowledge, only FHE schemes based on the LWE problem had subsecond bootstrapping procedures, while AGCD-based schemes required several seconds or even minutes to be bootstrapped. [less ▲] Detailed reference viewed: 44 (3 UL)Efficient AGCD-Based Homomorphic Encryption for Matrix and Vector Arithmetic Lima Pereira, Hilder Vitor in Applied Cryptography and Network Security (2020, August) We propose a leveled homomorphic encryption scheme based on the Approximate Greatest Common Divisor (AGCD) problem that operates natively on vectors and matrices. To overcome the limitation of large ... [more ▼] We propose a leveled homomorphic encryption scheme based on the Approximate Greatest Common Divisor (AGCD) problem that operates natively on vectors and matrices. To overcome the limitation of large ciphertext expansion that is typical in AGCD-based schemes, we randomize the ciphertexts with a hidden matrix, which allows us to choose smaller parameters. To be able to efficiently evaluate circuits with large multiplicative depth, we use a decomposition technique à la GSW. The running times and ciphertext sizes are practical: for instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and 128×128 matrices in less than one second. We show how to use our scheme to homomorphically evaluate nondeterministic finite automata and also a Naïve Bayes Classifier. [less ▲] Detailed reference viewed: 37 (5 UL) |
||