blocks|key|863204|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|-4|4|5|6|B|7|@]|8|@]|9|$]]]|A|$]]

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a way to discuss homomorphic encryption as well without essentially writing some (informal) lecture notes, so won't in this answer.
The LWE Problem:
The central hard problem for building constructions in lattice-based cryptography is the Learning With Errors problem.
There is a search and decisional form. The decisional form is to distinguish:
$$(A, As + e)\stackrel{?}{\approx}_c(A, u)$$
Here:
<ol>
<li>$A \gets\mathbb{Z}_q^{m\times n}$ is a uniformly random matrix</li>
<li>$s\gets \mathbb{Z}_q^n$ is a uniformly random vector</li>
<li>$e\gets \chi^m$ is a random &quot;concentrated&quot; value (meaning $\lVert e\rVert_\infty$ is &quot;small&quot;).</li>
</ol>
The search problem is to recover $s$, given $(A, As + e)$.
This problem has a natural coding-theoretic [1] interpretation --- we can view $A$ as being the &quot;generator matrix&quot; of a random code, and $As + e$ being an encoding of $s$ under the aforementioned code that is sent through some &quot;noisy&quot; channel.
In this setting, the problem of recovering $s$ is equivalent to the problem of decoding a random linear code, which is thought to be hard. Note that this is a problem we would want to do in practice --- random linear codes tend to achieve optimal parameters (up to constant factors), so coding theorists would be very happy if we could decode them.
Average-case Hardness:
Before discussing lattices more, I'll quickly discuss average-case hardness (as this is quite relevant to lattice-based cryptography). There are roughly two settings where one can discuss the complexity of some problem:
<ol>
<li>In a &quot;worst-case&quot; setting. I.e., given any input instance, how long does it take you to solve the problem?</li>
<li>In an &quot;average-case&quot; settting. I.e., given an input instance drawn at random from a particular distribution, how long does it take you to solve the problem?</li>
</ol>
Concepts such as NP-hardness discuss the former, but they are not particularly useful for cryptography.
This is because one can have problems that are worst-case hard, but &quot;most&quot; instances of the problem are easy.
If one chose an &quot;easy&quot; instance of the problem during key generation in some cryptographic construction, it could lead to the scheme breaking, despite the problem being worst-case hard.
This means that cryptographic constructions have to pin down some distribution such that the underlying problem is thought to be average-case hard.
This can be more involved than you may think. If you think the underlying problem for RSA being &quot;Factoring&quot; vaguely, then one quickly runs into the unfortunate fact that random numbers are not too difficult to factor (for example, they are divisible by 2 with probability $1/2$ --- depending on how you define the factoring problem this may already suffice to &quot;break&quot; it). One can think about the problem of factoring semi-primes as being the general factoring problem where one specifies a plausible average-case hard distribution (that of semi-primes). This distribution is only plausibly hard though, and there are a number of non-trivial attacks depending on how a particular RSA instance is generated (for example, <a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" rel="noreferrer">Pollard's $p-1$ algorithm</a>). This is all to say that you can find some distribution over RSA instances which is likely average-case hard, but it is a more involved process than &quot;just picking things randomly&quot;, and that the existence of non-trivial attacks even against the factoring of semi-primes means that we are really left with heuristic hardness of factoring in the end (although this has been fairly resilient over the years).
Lattice-based cryptography differs from this in a significant way due to the existence of worst-case to average-case reductions [2]. This essentially means that there exists some worst-case problem called SIVP (a slight generalization of the shortest vector problem you allude to) such that one can roughly [3] prove something of the form:
<blockquote>
If SIVP is worst-case hard, then LWE is average-case hard
</blockquote>
This is to say that lattice-based cryptography has a formal proof that the LWE distribution has a certain amount of average-case hardness, provided that a certain natural problem is worst-case hard.
The Ring Setting:
In the above I have only talked about LWE. The &quot;Ring&quot; setting (so working with RLWE rather than LWE) can be viewed as not choosing $A$ to be uniformly random, but instead uniformly random over some &quot;structured subset of all matrices&quot;. This is not the most natural way to discuss things from a mathematical perspective, but may be useful initially.
This structured subset admits a compact representation, and more efficient operations generically.
This is to say that RLWE is mostly a way to improve efficiency, which while quite important in practice is not necessary to get the broad picture of lattice-based cryptography.
<hr />
[1] There are some nuances here, the linear code should not be viewed as being a code in the binary symmetric channel (i.e. a &quot;code with respect to the Hamming norm&quot;), but instead in the additive white gaussian noise channel (say if you take $\chi$ to be discrete Gaussian, which is common).
[2] Note that there are other cryptographic problems with randomized &quot;self-reductions&quot; (for example it is know that if the discrete-log problem is worst-case hard, then it is average-case hard as well). The reductions in lattice cryptography are notable for being to an independently-studied (at least in the non-ring setting) worst-case problem.
[3] There are many caveats one must state here, but the largest one is that one does not work with SIVP in lattice-based cryptography, but instead an approximate version of it. It is known that this approximation problem is in $\text{NP}\cap\text{coNP}$, i.e. is not NP hard unless the polynomial hierarchy completely collapses, which is thought to be unlikely. Other caveats are mostly that there are many ancillary parameters that must satisfy certain inequalities. This is important in practice, but can ignored when just trying to get intuition.

Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice cryptography as well as Vaikuntanathan's course.
Looking around I found <a href="http://www.wisdom.weizmann.ac.il/%7Ezvikab/localpapers/IdealHom.pdf" rel="nofollow noreferrer">Fully Homomorphic Encryption from Ring-LWEand Security for Key Dependent Messages</a> which didn't really help me solidify the concepts I'm learning.
I &quot;know&quot; that lattice cryptography revolves around lattices and finding shortest vectors which is thought to be(?) NP-hard. I also found <a href="https://crypto.stackexchange.com/questions/11835/homomorphic-encryption-lwe-and-practical-applications">Homomorphic Encryption, LWE, and Practical Applications</a> but it seems the asker there is ahead of me in terms of understanding how everything ties together

How is R-LWE related to lattice cryptography and homomorphic encryption?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

有人能帮我把所有东西都绑起来吗？我对H.E感兴趣，我有一些AES，DES，RSA等方面的背景。在四处阅读时，我无意中发现了Shai Halevi关于格型密码学的课程以及Vaikuntanathan的课程。环顾四周，我发现基于环、LWEand和的全同态加密与密钥相关消息的安全性并没有真正帮助我巩固我正在学习的概念。我“知道”格密码学以格为中心，寻找被认为是(？)的最短向量。NP-很难。我也找到了同态

问related与格密码学和同态加密有什么关系？
EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问related与格密码学和同态加密有什么关系？EN