Tatra Mountains Mathematical Publications

An Lwe-Based Key Transfer Protocol with Anonymity

Adela Georgescu

Published Dec 1, 2012• 2 citations

Abstract

ABSTRACT We introduce a new cryptographic protocol based on the wellknown LearningWith Errors (LWE) problem: a group key transfer protocol which achieves anonymity of the members against each others. This issue is almost absent in the key transfer protocols from the literature but we argue it is a practical property. We motivate our construction by a practical need. We use two essential cryptographic primitives built from LWE: LWE Diffie-Hellman key exchange derived from Regev’s work [Regev, O.: On lattices, learning with errors, random linear codes, and cryptography, in: Proc. of the 37th Annual ACM Symposium on Theory of Computing-STOC ’05 (H. N. Gabow and R. Fagin, eds.), Baltimore, MD, USA, 2005, ACM, New York, 2005, pp. 84-93] and a public key cryptosystem secure under the LWE hardness. We provide a security definition for anonymous key transfer protocol and we achieve anonymity against IND-CPA adversaries.

DOI: 10.2478/v10127-012-0042-8

Related papers

Securely Instantiating Cryptographic Schemes Based on the Learning with Errors Assumption

Florian Göpfert

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

Jan 1, 20162 citations

Public-Key Encryption Schemes with Auxiliary Inputs. Theory of Cryptography

Yevgeniy Dodis, Shafi Goldwasser

Abstract. We construct public-key cryptosystems that remain secure even when the adversary is given any computationally uninvertible function of the secret key as auxiliary input (even one that may reveal the secret key informationtheoretically). Our schemes are based on the decisional Diffie-Hellman (DDH) and the Learning with Errors (LWE) problems. As an independent technical contribution, we extend the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields. 1

Feb 1, 20101 citation

Augmented Learning with Errors: The Untapped Potential of the Error Term.

Rachid El Bansarkhani, Özgür Dagdelen, Johannes A Buchmann

Abstract. The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security. To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem. As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.

Jan 1, 20141 citation

New variant for Learning with Errors Problem

Xuyang Wang, Aiqun Hu, Hao Fang

The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.

Procedia Computer ScienceJan 1, 20183 citations

Integration of post-quantum cryptography in the TLS protocol (LWE Option)

Luís Da Costa

With the possibility of quantum computers making an appearance, possibly capable of breaking several well established and widespread crytposystems (especially those that implement public key cryptography), necessity has arisen to create new cryptographic algorithms which remain safe even against adversaries using quantum computers. Several algorithms based on different mathematical problems have been proposed which are considered to be hard to solve with quantum computers. In recent years, a new lattice-based mathematical problem called Learning With Errors (and its variant Ring - Learning With Errors) was introduced, and several cryptosystems based on this problem were introduced, some of which are becoming practical enough to compete with traditional schemes that have been used for decades. The primary focus in this work is the implementation of two Ring - Learning With Errors based schemes (one key exchange mechanism and one digital signature scheme) on the TLS protocol via the OpenSSL library as a way of checking their overall viability in real-world scenarios, by comparing them to classical schemes implementing the same functionalities.

Jan 1, 20190 citations

Zero-Knowledge Proof for Knowledge of RLWE (Ring-Learning with Errors) Secret Keys

Saraswathy Rv

Key Exchange is an essential primitive in cryptography that originated from the breakthrough idea of Diffie Hellman (DH) protocol presented in 1976.Following this work, there are many successful variants of DH using Elliptic curves, Isogeny and RLWE (Ring Learning with Errors).The Ring-Leaning with Errors (RLWE), Search and Decision version are hard problems in mathematics and it has been shown that solving worst case hard problems in ideal lattices can be reduced to solving RLWE in the average case.The reduction forms the basis of provable security for RLWE based key exchange against passive adversaries.The hardness of the decision version of RLWE, which means indistinguishability of RLWE samples from Uniform, makes it challenging to validate a RLWE form public key.This proves to be an advantage for malicious users to create public keys that deviate from a protocol to recover the secret of reused keys in Key Exchange (KE) protocols.In this thesis, we provide a cryptanalysis of RLWE key exchange, presenting two polynomial time strategies to exploit key reuse.Then we propose a defense against such exploits by presenting a Zero Knowledge authentication protocol to verify the prover's knowledge of a secret corresponding to his public key.The protocol is Statistical Zero Knowledge with negligible soundness and completeness errors so that the prover does not reveal any information about the secret in the proof.This is to ensure that a malicious verifier cannot impersonate the prover after the proof.The authentication protocol uses the signal function defined in RLWE key exchange to perform the verification.Firstly, I would like to express my gratitude to my advisor Prof.Ding for his expert advice, strong encouragement and support throughout my PhD study

Jan 1, 20180 citations