Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Application of Multilinear Forms in Cryptography

Tomáš Rabas

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.

Related papers

Two applications of multilinear maps: group key exchange and witness encryption

Seiko Arita, Sari Handa

Constructing multilinear maps has been long-standing open problem, before recently the first construction based on ideal lattices has been proposed by Garg et al. After this breakthrough, various new cryptographic systems have been proposed. They introduce the concept of level into the encodings, and the system has a function that extracts a deterministic value at only a specific level, and the encodings are unable to downgrade to the lower levels. These properties are useful for cryptography. We study how this graded encoding system be applied to cryptosystems, and we propose two protocols, group key exchange and witness encryption. In our group key exchange, we achieve the communication size and the computation costs per party are both O(1) with respect to the number of parties by piling the encodings of passed parties in one encoding. A witness encryption is a new type cryptosystem using NP-complete problem. The first construction is based on EXACT-COVER problem. We construct it based on another NP complete Hamilton Cycle problem, and prove its security under the Generic Cyclic Colored Matrix Model.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 30, 2014•7 citations

Design and Implementation of Lattice-Based Cryptography

Tancrède Lepoint

Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems. In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices and remains as of today a promising primitive for post-quantum cryptography. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.

•Jun 30, 2014•8 citations

Frontiers in Lattice Cryptography and Program Obfuscation

Daniel Apon

In this dissertation, we explore the frontiers of theory of cryptography along two lines. In the first direction, we explore Lattice Cryptography, which is the primary sub-area of post-quantum cryptographic research. Our first contribution is the construction of a deniable attribute-based encryption scheme from lattices. A deniable encryption scheme is secure against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. An attribute-based encryption scheme allows ``fine-grained'' access to ciphertexts, allowing for a decryption access policy to be embedded in ciphertexts and keys. We achieve both properties simultaneously for the first time from lattices. Our second contribution is the construction of a digital signature scheme that enjoys both short signatures and a completely tight security reduction from lattices. As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix, which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians. In the second direction, we explore Cryptographic Program Obfuscation. A program obfuscator is a type of cryptographic software compiler that outputs executable code with the guarantee that ``whatever can be hidden about the internal workings of program code, is hidden.'' Indeed, program obfuscation can be viewed as a ``universal and cryptographically-complete'' tool. Our third contribution is the first, full-scale implementation of secure program obfuscation in software. Our toolchain takes code written in a C-like programming language, specialized for cryptography, and produces secure, obfuscated software. Our fourth contribution is a new cryptanalytic attack against a variety of ``early'' program obfuscation candidates. We provide a general, efficiently-testable property for any two branching programs, called partial inequivalence, which we show is sufficient for launching an ``annihilation attack'' against several obfuscation candidates based on Garg-Gentry-Halevi multilinear maps.

•Jan 1, 2017•0 citations

Lattice Cryptography for the Internet.

Chris Peikert

In recent years, lattice-based cryptography has been recognized for its many attractive properties, such as strong provable security guarantees and apparent resistance to quantum attacks, flexibility for realizing powerful tools like fully homomorphic encryption, and high asymptotic efficiency. Indeed, several works have demonstrated that for basic tasks like encryption and authentication, lattice-based primitives can have performance competitive with (or even surpassing) those based on classical mechanisms like RSA or Diffie-Hellman. However, there still has been relatively little work on developing lattice cryptography for deployment in real-world cryptosystems and protocols. In this work we take a step toward that goal, by giving efficient and practical lattice-based protocols for key transport, encryption, and authenticated key exchange that are suitable as “drop-in ” components for proposed Internet standards and other open protocols. The security of all our proposals is provably based (sometimes in the random-oracle model) on the well-studied “learning with errors over rings” problem, and hence on the conjectured worst-case hardness of problems on ideal lattices (against quantum algorithms). One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth reconciliation technique that allows two parties who “approximately agree ” on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost. 1

•Jan 1, 2014•0 citations

Applications of Ring Theory in Post-Quantum Cryptography

Dr. Muhammed Basheer

Post-quantum cryptography (PQC) aims to develop cryptographic protocols resistant to attacks by quantum computers, which threaten classical schemes based on integer factorization and discrete logarithm problems. Among various approaches, lattice-based cryptography has emerged as one of the most promising candidates for PQC. Within this domain, ring theory plays a foundational role by providing the algebraic structures—specifically polynomial rings modulo cyclotomic polynomials—used to define hard problems like Ring Learning With Errors (Ring-LWE). These problems underpin efficient and secure cryptographic primitives such as key exchange, encryption, digital signatures, and homomorphic encryption. This paper explores the theoretical background of ring theory relevant to PQC and discusses how it enables the construction of cryptosystems with strong security assumptions and practical efficiency. We also analyze specific schemes that utilize ring-based lattices, including New Hope, NTRUEncrypt, and Dilithium, highlighting the advantages of ring structures in reducing key sizes and improving computational speed. Furthermore, we review the implementation challenges and potential future directions for integrating ring theory into next-generation cryptographic protocols suitable for a post-quantum world.

International Journal for Research in Applied Science and Engineering Technology•Jun 5, 2025•0 citations

New Applications of Homomorphic Cryptography

Sina Shiehian

Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.

•Jan 1, 2019•0 citations
We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.
Constructing multilinear maps has been long-standing open problem, before recently the first construction based on ideal lattices has been proposed by Garg et al. After this breakthrough, various new cryptographic systems have been proposed. They introduce the concept of level into the encodings, and the system has a function that extracts a deterministic value at only a specific level, and the encodings are unable to downgrade to the lower levels. These properties are useful for cryptography. We study how this graded encoding system be applied to cryptosystems, and we propose two protocols, group key exchange and witness encryption. In our group key exchange, we achieve the communication size and the computation costs per party are both O(1) with respect to the number of parties by piling the encodings of passed parties in one encoding. A witness encryption is a new type cryptosystem using NP-complete problem. The first construction is based on EXACT-COVER problem. We construct it based on another NP complete Hamilton Cycle problem, and prove its security under the Generic Cyclic Colored Matrix Model.
Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems. In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices and remains as of today a promising primitive for post-quantum cryptography. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.
In this dissertation, we explore the frontiers of theory of cryptography along two lines. In the first direction, we explore Lattice Cryptography, which is the primary sub-area of post-quantum cryptographic research. Our first contribution is the construction of a deniable attribute-based encryption scheme from lattices. A deniable encryption scheme is secure against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. An attribute-based encryption scheme allows ``fine-grained'' access to ciphertexts, allowing for a decryption access policy to be embedded in ciphertexts and keys. We achieve both properties simultaneously for the first time from lattices. Our second contribution is the construction of a digital signature scheme that enjoys both short signatures and a completely tight security reduction from lattices. As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix, which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians. In the second direction, we explore Cryptographic Program Obfuscation. A program obfuscator is a type of cryptographic software compiler that outputs executable code with the guarantee that ``whatever can be hidden about the internal workings of program code, is hidden.'' Indeed, program obfuscation can be viewed as a ``universal and cryptographically-complete'' tool. Our third contribution is the first, full-scale implementation of secure program obfuscation in software. Our toolchain takes code written in a C-like programming language, specialized for cryptography, and produces secure, obfuscated software. Our fourth contribution is a new cryptanalytic attack against a variety of ``early'' program obfuscation candidates. We provide a general, efficiently-testable property for any two branching programs, called partial inequivalence, which we show is sufficient for launching an ``annihilation attack'' against several obfuscation candidates based on Garg-Gentry-Halevi multilinear maps.
In recent years, lattice-based cryptography has been recognized for its many attractive properties, such as strong provable security guarantees and apparent resistance to quantum attacks, flexibility for realizing powerful tools like fully homomorphic encryption, and high asymptotic efficiency. Indeed, several works have demonstrated that for basic tasks like encryption and authentication, lattice-based primitives can have performance competitive with (or even surpassing) those based on classical mechanisms like RSA or Diffie-Hellman. However, there still has been relatively little work on developing lattice cryptography for deployment in real-world cryptosystems and protocols. In this work we take a step toward that goal, by giving efficient and practical lattice-based protocols for key transport, encryption, and authenticated key exchange that are suitable as “drop-in ” components for proposed Internet standards and other open protocols. The security of all our proposals is provably based (sometimes in the random-oracle model) on the well-studied “learning with errors over rings” problem, and hence on the conjectured worst-case hardness of problems on ideal lattices (against quantum algorithms). One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth reconciliation technique that allows two parties who “approximately agree ” on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost. 1
Post-quantum cryptography (PQC) aims to develop cryptographic protocols resistant to attacks by quantum computers, which threaten classical schemes based on integer factorization and discrete logarithm problems. Among various approaches, lattice-based cryptography has emerged as one of the most promising candidates for PQC. Within this domain, ring theory plays a foundational role by providing the algebraic structures—specifically polynomial rings modulo cyclotomic polynomials—used to define hard problems like Ring Learning With Errors (Ring-LWE). These problems underpin efficient and secure cryptographic primitives such as key exchange, encryption, digital signatures, and homomorphic encryption. This paper explores the theoretical background of ring theory relevant to PQC and discusses how it enables the construction of cryptosystems with strong security assumptions and practical efficiency. We also analyze specific schemes that utilize ring-based lattices, including New Hope, NTRUEncrypt, and Dilithium, highlighting the advantages of ring structures in reducing key sizes and improving computational speed. Furthermore, we review the implementation challenges and potential future directions for integrating ring theory into next-generation cryptographic protocols suitable for a post-quantum world.
Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.