基于格密码的零知识系统与Vadim Lyubashevsky

对吧？

Right?

所以即使是基于格的签名，这也是最近被NIST标准化为MLDSA的东西，之前它被称为delithium。

So even a lattice based signature, this is the thing that got standardized by by NIST recent MLDSA, so before it was called delithium.

它比简单的Schnorr协议要混乱得多。

It is so much more messy than just the snore protocol.

你做了类似Schnorr的事情，然后说，啊，但现在向量太大了，所以我们不发送全部，然后就是等等等等。

So you do kind of the snore thing, then you say, ah, but now the vectors are too big, so let's not send all of them, and then you know yada yada yada.

这里有一大堆乱七八糟的东西。

There's a there's a big mess.

即便如此，即使是签名，它们也没有完全证明我们所知道的。

And even then, even the signatures, right, they don't quite prove what we know.

在Schnorr中，你知道一个x，g的x次方等于y，你证明我知道x，所以g的x次方等于y。

So in Schnorr, you know an x, the g to the x equals y, you prove that I know x, so that g to the x equals y.

而在格空间签名中，我知道一个x使得a乘以x等于y。

That's Here in the in the Lattice Space signatures, I know an x so that a x equals y.

我并没有证明x是例如0-1系数的向量。

I don't prove an x is a zero one coefficients for example.

我没有向你证明x具有0-1系数。

I don't prove to you that x has zero one coefficients.

我向你证明的是存在某个小x，其系数可能高达一千。

I prove to you that there is a some small x maybe with coefficients that are up to a thousand.

这是一个宽松得多的条件。

So much more relaxed thing.

甚至我都没有向你证明a乘x等于y。

And not even I don't even prove to you that a x equals y.

我向你证明的是a乘x是y的某个倍数。

I prove to you that a x is some multiple of y.

所以我们证明的是一个弱得多的命题。

So we're proving something much much weaker.

而当你想要做零知识证明时，当你实际需要证明0-1性质时。

And now when you wanna do zero knowledge, when you act, you know, zero knowledge proofs, when you actually do care about proving the zero one.

对吧？

Right?

比如说我想为零知识证明提供证据，比如我钱包里有多少钱，或者那22美元的总和，我需要一个确切的数字。

Like let's say I'm trying to give a zero knowledge proof of, I don't know, how much I have in my wallet or something that that sum of $22 amount is I need I need an exact thing.

我不能说，嗯，大概是这么多。

I can't say, well, it's approximately this.

然后事情就变得非常非常复杂了。

And then it becomes much much more complicated.

即便是这个最基础的东西——仅仅证明这个单向函数，直到大约七年前，这个证明本身（我们还没用到任何SNARK技术），根本不算什么。

And this is something that even this basic basic thing, just proving this one way function, up until let's say seven years ago, this, just the proof itself, you know, we're not doing any snark, this is nothing.

我们只是要求一个线性大小的证明，它就已经长达数兆字节了。

We're just asking for a linear size proof, it was already, you know, megabytes long.

哦。

Oh.

直到最近我们才意识到，其实还有很多其他技术手段可以采用。

And then only only recently we said, okay, there's lots of other techniques that we can do.

我们可以应用并发明一些方法，将这些兆字节的数据缩减到现在仅需几千字节的量级。

We can apply, we can kind of invent that will allow us to you know, reduce these megabytes to something on the order of kilobytes now.

所以回到你关于格密码能做什么、替代什么的问题，我真正喜欢的是我们必须采用特定技术而非通用方案。

And so the thing that I I really like, kind of goes back to your question of what what do lattices do, what do they replace, is that we have to instead of applying generic techniques.

当然我们可以说，哦，格密码就是个哈希函数。

So we could of course say, oh, lattices is just a hash function.

对。

Yeah.

它就是个取代了

It's just commitment scheme replaces the

默克尔树之类的方案。

Merkle Yeah, fry or something.

没错。

Yeah.

正是如此。

Exactly.

取代了Merkle树等等之类的结构。

Replaces the Merkle tree and blah blah blah.

好的。

Okay.

显然你可以这么做，而且这确实是我们最初尝试的第一步，就想看看能否实现。

You can obviously do that, and you know, this is something that we did do as a first step saying, hey, can we do it?

但这种通用方法永远无法得到最优解。

But this generic thing never results in something optimal.

嗯。

Mhmm.

所以我喜欢这样思考：你必须真正运用一些格理论特有的技术，才能充分发挥格密码的潜力。

So like what I what I like, I like to think that, hey, you have to actually use some, I don't know, lattice y techniques to to kinda get the most out of lattices.

这正是近年来格构造和零知识证明取得诸多突破的原因。

And this is what led to a lot of recent improvements in lattice constructions and zero knowledge proof.

这么说吧，直到三四年前，我们还几乎无法高效生成线性规模的证明。

So let's say up until three or four years ago, we could barely do linear sized proofs with any sort of efficiency.

现在我们能实现SNARKs了。

And now we can do SNARKs.

有意思。

Interesting.

好的。

Okay.

所以从你的话中我理解到，我们看待SNARKs的方式有点像即插即用。

So what I'm hearing from you is like the way we think of SNARKs, where there's this sort of like plug in plug out.

就像你可以选择一种加密技术。

Like there's you sort of choose a type of cryptography.

比如你可以用Fry或者KZG。

I mean, you could use Fry or you can use KZG.

基本上，你可以用Fry这类东西来替代KZG。

Know, like, basically, you can take things like Fry and that could replace KZG.

是的。

Yes.

你必须调整它，但某种程度上可以适配进去。

You have to alter it, but like you can kind of fit it in.

在Lattice的情况下，听起来你实际上需要在一个更抽象的层面上重新思考你希望通过整个系统实现什么。

In the case of Lattice, it sounds like you actually have to rethink maybe at a more meta level what you're trying to accomplish with the overall system.

这大概是我从你那里得到的理解，就是你无法简单地即插即用。

This is like sort of what I'm getting from you, that you can't necessarily just like plug and play.

所以你可以做到，因为你知道，同样的密码学原语可以从格中获取，当然你可以把它们插入。

So you you can because, you know, the same cryptography, like primitives you can get from lattices, and so of course you can plug them in.

但你不会得到什么有趣的东西。

But you won't get something that's interesting.

或者高效运作的东西。

Or something that works well, that's efficient.

是啊。

Yeah.

对我来说这两者是一回事。

Well, to me those are the same thing.

举个例子，让我这么说吧。

So like for example, let me say this.

为什么格子在密码学中如此有趣，并能提供像全同态加密（FHE）这样的东西？

Why are lattices in why are they interesting and give you something like FHE?

对吧？

Right?

如果你考虑配对或任何指数运算，你把它看作某种映射，对吧？这个映射将一个数字映射到一个群中。

So if you think about pairings or whatever your exponentiation, you take it you it's at some map, right, that takes a number and and maps it into a group.

对吧？

Right?

配对操作将某物映射到某个群，然后你就基本完成了。

The pairing takes something, maps it to some group, and you're kind of done.

你无法持续进行这个操作。

You cannot keep doing this operation.

而使用格运算，这个ax等于y，我取一个向量，只是将它映射到另一个向量。

Whereas with the with lattice operations, right, this this ax equals y, I'm taking a vector and I'm just mapping it to another vector.

因此，值域的代数结构与定义域的代数结构非常相似。

And so the algebra of the range is pretty similar to the algebra of the domain.

如果你想充分利用格点，就必须利用这一点。

And this is what you have to take advantage of if you want to kinda get the most out of lattices.

因为我认为这是它们的特殊之处。

Because this is I think their special feature.

对吧？

Right?

所以很多构造都是这样完成的。

So this is what a lot of this is what is done in a lot of constructions.

你计算这个函数，这个格点函数，也就是a乘以x。

You compute some that this function, this lattice function, so the a times x x.

现在你得到了另一个向量。

And then now you now you have another vector.

唯一的区别是，现在的系数不再是小的，而是大的。

The only difference is now it's instead of having small coefficients, it has big coefficients.

嗯。

Mhmm.

所以如果你再这样做，现在它就不再是个难题了。

So if you do this again, now it's no longer a hard problem.

我想从验证者的角度来看，我们需要知道组合操作是否正确完成。

I guess from the perspective of a verifier, we need to know that the composition was done correctly.

对吧？

Right?

因此这会增加额外的证明和验证步骤。

And so that would add extra steps of proving and verifying.

是的。

Yeah.

那是正确的。

That that's right.

没关系。

That's okay.

好的。

Okay.

这不算什么大问题。

Like that's not too much of a problem.

对。

Yeah.

因为我们总能进行二进制分解，这只是个线性操作。

Because we can always binary decompose, and that's just a linear operation.

所以只要能证明线性关系和小数性质，我们就能证明这些哈希、二进制分解、哈希、二进制分解的多次操作。

So if we can prove linear relations and smallness, we can prove as many of these hashing, binary decomposition, hashing, binary decomposition.

明白吗？

Okay?

所以这很不错。

So that's that's nice.

另一个好处是，当你映射时因为它保留了代数结构，现在你可以再次进行这些线性操作，可以线性组合所有这些上层结果，或许你能证明它们的线性组合性质而非单个结果。

And the other the other nice thing is that when you map into because it retains its algebraic structure, now you can again do these linear, you can linearly combine all these upper all these results, And maybe you can prove something about the linear combination of them instead of each of individuals.

现在你不需要存储所有内容，只需存储线性组合即可。

Now you don't need to store everything, can just store linear combination.

再次强调，这里输出代数结构与输入的基本相同这一事实确实帮了我们大忙。

And again, this is where the fact that the algebra of the outputs is basically the same, the simple algebra of the input really helps us out.

另外我只是列举了这些——你知道的——我们过去几年里添加到工具箱中的所有方法。

Another thing is I'm just listing all these you know, these things in our that we put into our toolbox in the last in the last couple of years.

好的。

Okay.

所以要证明某个量很小。

So proving that something is small.

明白。

Okay.

就是证明范数很小。

It's proving that the norm is small.

对吧？

Right?

为了提高效率，我们在格密码中工作的环并非整数环。

And the the ring over which we work in lattices for efficiency is not not the integers.

对，而是一个多项式环。

Right, but it's a polynomial ring.

虽然可以在整数上操作，但在多项式环上效率要高得多。

So you can work over the integers, but it's much more efficient over polynomial rings.

所有NIST标准都基于多项式环。

All the NIST standards are over polynomial rings.

关键在于，多项式环上的基本运算正是我们所需的。

And the nice thing is that, hey, over polynomial rings, that's our basic operation.

若要做内积运算，实际上只需看首项系数就是两个多项式的乘积。

If you wanna do inner product, well that's actually the product of two polynomials if you just look at the first coefficient.

嗯。

Mhmm.

只要对它们进行适当的变换。

If you kind of transform them correctly.

因此我们甚至可以将范数——这种格运算所需的基本概念——描述出来。

So we can even describe the norm, the kind of this basic thing that we need as a lattice operation.

对。

Right.

另一件事是，为了证明短性，你可以使用所谓的约翰逊-林登斯特劳斯引理。

Another thing is to prove shortness, you can use something called the Johnson Lindenstrauss Lemma.

对吧？

Right?

它被用于降低数据的维度。

It was used for reducing the dimensionality of, you know, data.

基本上，你有很多高维空间中的点，可以说，我要观察一个线性对数维度的空间，其范数基本上会保持不变。

So basically, you have a lot of points, you know, in high dimensions, you can actually say, hey, I'm gonna look at a linear, you know, I'm gonna look at the like some logarithmic number of dimensions, and it and basically the norm is gonna be preserved.

虽然会有缩放，但会被保持。

You know, it's gonna be scaled but preserved.

我们在格上也能做到类似的事情。

That's something we can do for lattices as well.

我们可以说，看，要证明某个量很小，实际上可以证明当你将这个随机变换应用到更低维空间时，如果结果很小，那么原始量也很小。

We can say, hey, look, to prove that something is small, let's actually prove that when you apply this this random transformation into a much smaller dimensional space, if that's small, then your original thing was small too.

这一点非常关键，如果你的核心论证可能依赖于这个范数的话。

And that's kind of pretty crucial if if your heart probably relies on this norm.

但当然，这也会带来一个问题。

But but of course, this this causes a problem.

我想Dan Bonnet可能提到过，现在如果用这个矩阵做乘法，结果会变得非常冗长。

I think this is something that maybe maybe was mentioned by Dan Bonnet that now if you're multiplying by this matrix, now it's very long.

这样一来验证者就无法高效运作了。

So now the verifier cannot be efficient.

所以如果我们关心验证效率的话，可能不应该这么做，但有时我们可能并不在意验证效率。

So that's, you know, that's something maybe we shouldn't do if we care about efficient verifiers, but maybe sometimes we don't care about efficient verifiers.

因此我们可以这样做。

So we can do that.

这些都是新技术，之前并不存在，因为其他领域并不需要它们。

So these are all these new techniques where which didn't exist, right, for with with anything else just because they weren't needed there.

对吧？

Right?

这些是在结合ZK时引入的，还是在尝试将其融入FHE时引入的？

Are these being introduced in once you combine it with ZK or once you're trying to get it into FHE?

FHE实际上并没有怎么用到那些技术。

So FHE did not really use much of that.

当然，它用的是多项式环，但不是那些。

Of course, it was polynomial rings, but not that.

不过如果你想在ZK里开始证明东西的话...嗯...

But yeah, if you wanna start proving things in ZK Mhmm.

那你就会真正开始关心如何证明简短性了。

Then you you start actually caring about proving shortness.

明白了。

Got it.

是的，所以这些技术与这些证明系统密切相关。

And yeah, so these techniques are very much related to these these proof systems.

它们就是为这个目的开发的。

They were developed for this purpose.

我想再确认一下，因为我最初的问题是关于SNARK的。

I do wanna double check because I think I, you know, my initial question was about a SNARK.

你更多是在讲零知识和格密码，而不一定是SNARK和格密码的关系。

You're talking more about like z k and lattices, but not necessarily snarks and lattices.

没错。

So Right.

但格密码也被用来构建SNARK吗？

But are lattices being used to construct snarks as well?

是的。

Yes.

好的。

Okay.

现在我们工具箱里有了这些技术。

So once we got these these techniques in the toolbox.

对吧？

Right?

然后你可以问，我们还能做什么？

Then you could say, okay, what else can we do?

实际上我们可以得到一些相当像SNARK的东西。

And actually we can get something that is fairly snarky.

所以就有了这个

So there was this

类似于SNARK的那种？

Resembles a snark kind of?

是的。

Yeah.

没错。

Yeah.

对。

Right.

明白了。

Got it.

这也是为什么我们可能不会一对一替换的原因。

And this is why again, maybe we don't replace one to one.

好的。

Okay.

是的。

Yeah.

因为你知道，'snark'对不同人可能有不同含义——有人认为必须要有高效验证器，有人则认为不需要，诸如此类。

So because you know, snark again could means different things to too many to different like some people say it has to have an efficient verifier, some people say it doesn't, things like that.

所以我想说得更准确些，IBM的两位同事曾提出过一个非常高效的方案，叫Labrador。

So yeah, it's I wanna be maybe a little precise so that maybe there was a very efficient scheme proposed by two colleagues at IBM, so Labrador by Yes.

Ward Boilens和Gregor Zeiler。

Ward Boilens and Gregor Zeiler.

这个方案实际上运用了我之前提到的工具箱里的许多技术，来生成非常简短的证明。

And this actually uses a lot of the things that were developed in this this toolbox that I was talking about to come up with very short proofs.

所以验证者的规模仍然是线性的，但证明的大小大约是50千字节。

So the verifier is still linear size, but the proofs are, you know, let's say about 50 kilobytes.

因此它们永远无法超越基于配对的证明，但会优于基于哈希的证明

So they'll never beat pairing based proofs, but they will beat hash based proofs

好的。

Okay.

在大小方面。

In size.

它的渐进复杂度是多少？

What is it asymptotically?

渐进复杂度上，我认为几乎是log log n。

Asymptotically, it's I think it's almost log log n I think.

好的。

Okay.

很棒。

Lovely.

是的，没错。

It is yeah.

如果你看他们的论文，证明的大小几乎不随约束条件的数量增加而增长。

There is if you look at their paper, the size of the proof barely increases with the number of constraints.

可能从一千个约束到十亿个约束，证明大小仅从50增加到55。

Maybe it goes from 50 to 55 as you go from like a thousand to a billion constraints.

所以它很简短。

So it's it's short.

但有趣的是，能否让验证过程更高效？

But the interesting thing is, okay, can you make the verifier efficient?

现在有些新思路可能采用了更传统的零知识技巧。

So now there's these other ideas that maybe are using more traditional zero knowledge tricks.

折叠？

Folding?

对，折叠。

Fold folding.

是的。

Yeah.

对。

Right.

对。

Right.

还有递归组合。

Recursive composition as well.

正是如此。

Exactly.

正是如此。

Exactly.

直到最近，研究这些阶梯性事物和零知识证明的确实是两个不同的群体。

Until recently, it's really been two different groups of people that were working on these laddicy things and the zero knowledge thing.

现在它们正逐渐融合。

And now they're being slowly merged.

我认为，零知识领域的人正在学习格密码技术，而格密码领域的人也在学习零知识技术。

And I think you you have the zero knowledge people learning the lattice techniques and you have the lattice people learning the zero knowledge techniques.

这样应该能够实现更高效的技术方案。

And and you you should be able to get things that are more efficient.

以我自己为例，我认为甚至在研究SNARKs之前，就有许多有趣的事情可以做。

So for myself, for example, I think even before getting to snarks, there's a lot of interesting things that one can do.

例如，所有不需要SNARKs——或者至少不需要高效验证者的匿名凭证和身份解决方案。

For example, all the anonymous credentials and identity solutions thing that doesn't require snarks or at least doesn't require efficient verifiers.

因为这些声明的长度并不长。

Because the the statements are not very long.

它确实需要简短的证明，因为你不想输出太多内容，但高效的验证者在这里并不是关键。

It does require small proofs because you don't wanna output too much, but efficient verifiers is not something crucial there.

是的。

Yeah.

仅仅因为我们还没遇到大问题。

Simply because we don't get to big problems.

对吧？

Right?

确实如此。

So Right.

这无关紧要。

It doesn't matter.

对。

Right.

没错。

Right.

所以用格密码可以完成所有事情。

So so you can do everything with lattices.

唯一的问题是，能否高效实现？

The only question is, can you do it efficiently?

是的。

Yeah.

它比目前正在使用的方法更好吗？

And is it better than what already is being used there?

是的。

Yeah.

是的。

Yeah.

实际上，你提到了我现在想询问的两件事。

Actually, you've touched on two things that I now wanted to inquire about.

一个是效率问题。

It's efficiency.

具体来说，这些方法与基于离散对数的系统相比如何？

Like, actually, how do these things compare to discrete log based systems?

从实际应用角度，我们该如何部署这类系统，以及如何编写这类证明？

And practically, like, how do we deploy these kind of systems, and how do we write these sort of proofs?

好的。

Okay.

在底层实现上，我认为格密码应该比其他任何方案都高效得多，包括传统方案。

So at a at a low level, I would say that lattices should be a lot more efficient than anything else, even the classical stuff.

举个例子，在NIST竞赛中，最终选定的现行标准MLChem，其速度超过其他所有加密方案。

So as an example, so so in the NIST competition, right, so we so we have the the current standard that that was chosen, MLChem, it is faster than any other encryption scheme.

就计算规模而言，它可能快几个数量级，因为这些多项式运算非常快，尤其当你能利用硬件并行性时。

So in terms of computation size, it is maybe orders of magnitude faster just because these polynomial operations are so fast and especially if you can take advantage of the parallel parallelism in in hardware.

对吧？

Right?

而这确实可以实现。

Which which you can.

对吗？

Right?

现在的AVX2或AVX-512指令集，这些都给我们带来了巨大帮助。

This AVX two or AVX five twelve now, so this this all helps us enormously.

不过它体积更大。

It's bigger though.

所以如果传输是个问题，那么现在你得权衡哪种方式更节省资源，是本地计算的高效率还是传输效率。

So if you if transmission is an issue, then then now you have to kinda count what saves you more, the high efficiency of your local computation versus the transmission.

对吧？

Right?

就这一点而言，格基密码非常出色。

So in terms of that, lattices are are great.

我刚才问的是效率问题，同时也对实用性感到好奇，比如我们如何部署这些证明？

I was asking about efficiency, was also curious about practicality, like how do we deploy these proofs?

我们如何编写使用格基密码学的匿名凭证系统？

How do we write anonymous credentials, systems that use lattice based cryptography?

嗯。

Mhmm.

是的。

Yeah.

这确实很难。

This is this is hard.

对吧？

Right?

这些证明，可以说并不简单。

These proofs are, let's say not trivial.

这些东西的基础构建模块相当混乱。

The the building blocks are quite messy of these things.

我和这里的同事们一直在尝试编写这些基础构建模块，然后提供一个友好的接口供人们使用。

Something that I've been trying to do with my colleagues here is to actually write these these basic building blocks, and then have a nice interface so people can use them.

所以我们开发了这个名为laser的库。

So this is so we we have this laser library that we've been working on.

它允许你在零知识条件下证明某些关系，在Python中，你只需调用这些格操作和证明，用大约50到100行简单的Python代码，就能编写匿名凭证、盲签名、聚合签名等。

So it allows you to prove some relations in zero knowledge, and then the the you in Python, you can just call these call these lattice operations, call these proofs, and let's say in let's say 50 to a 100 lines of simple Python, you can actually write your anonymous credentials, your blind signatures, things like that, your aggregate signatures.

但我认为很多研究——也许这与零知识无关——一旦涉及加密和签名之外的领域，大量研究应该聚焦于可验证性。

But I I would say a lot of the research, and maybe this is not even like zero knowledge related, but once you get to anything past encryption and signatures, I feel like a lot of research should be on verifiability.

对吧？

Right?

你需要一些代码或逻辑系统来验证你所写的内容确实是正确的。

You need you need some code or some logical system to verify that what you've written is actually correct.

因为这些系统非常非常复杂。

Because these systems are are very very complicated.

那么明确一下，你指的是某种形式化验证

So just to be clear here, you mean like some kind of formal verification

的代码。

of the code.

是的。

Yeah.

没错。

Exactly.

正是如此。

Exactly.

我认为形式化验证是密码学中更重要的领域之一，因为现在英语国家与非英语国家之间存在争论。

So formal verification is I think one of the more important areas of cryptography because there's an argument now between kind of the English speaking countries and non English speaking countries.

我不明白为何会演变成这样，但这就是争论的焦点。

I don't know why it broke down this way, but that's the argument.

这就是边界当初被划分的方式。

That's how that's how the borders were drawn.

在新的量子安全密码学领域，一旦开始采用这些量子安全方案，是否还需要与传统方案结合使用？嗯。

That in the new quantum safe cryptography world, once you start using these quantum safe schemes, do you use them in conjunction with the classical ones Mhmm.

采用混合模式吗？

In hybrid mode?

还是干脆认为传统方案无关紧要，我们对量子安全方案有信心，直接单独使用量子安全方案？

Or do you just say, look, the classical ones we don't care about, we are confident in the quantum safe ones, let's just use the quantum safe ones.

比方说非英语国家阵营——这个观点完全合理——他们认为：我们曾信任这些传统方案，

So the let's say the non English speaking world, and this is a perfectly valid argument, say, hey look, we trusted these classical schemes.

继续将它们与更新的量子安全方案并行使用并不会造成危害。

It doesn't harm anyone to keep using them in parallel with the quantum safe, the newer quantum safe ones.

而另一方则认为：尽管理论上结合两者很简单，但现实中所有错误恰恰都发生在这种结合环节。

The the other side is saying, hey, look, actually combining the two, even though it's trivial, like theoretically, actually that's where all the mistakes happen in the real world.

对吧？

Right?

所以即便是像简单组合两种加密方案这样的小事，人们也担心会出错。

So so even for something so trivial as just combining two schemes together, people are afraid that mistakes will be made.

因此，如果连这种小事都让人担忧，那么对于那些正在部署的极其复杂的软件——老实说没多少人在仔细检查的——我会更加担心。

So even if that that is kind of a worry, then I I would worry a lot about these extremely complicated pieces of software being rolled out that, let's say, not many people are looking at to to be to be honest.

对吧？

Right?

有多少人会去检查这些十万行代码呢？

How many people look at these 100,000 line

哦，你说的是那些编写了数十亿行代码却无人审查的程序员群体...确实，这里有很多需要检查的地方。

Oh, you're talking at a community of people who writes billions of lines of code and no one's looking at it, and we But, love yeah, there's a lot to to be checked here.

是的。

Yeah.

不过我认为验证可能是更紧迫的研究领域。

But but I would say that that's maybe verification is the more urgent research area.

对吧？

Right?

因为我们有很多密码学技术。

Because we we have a lot of cryptography.

对吧？

Right?

我们掌握密码学，能用它实现一切。

We we cryptography, we can do everything with it.

但我们有足够的密码学或攻击技术吗？

But do we have enough cryptology or attack techniques?

正是如此。

Exactly.

攻击。

Attack.

攻击吗？

Attacking?

是的。

Yeah.

这个领域确实需要更多研究，需要更多人投身其中，还需要形式化验证。

That that's an area that that needs to needs a lot more research, needs a lot more people to go into it, and formal verification.

对。

Yeah.

但这些...我不太确定。

So but but those are not the I don't know.

这些不是最酷的领域，也不是最吸引人的方向。

These are not the the cool areas, not the sexy areas.

对吧？

Right?

大家都想设计高效的SNARKs。

You wanna be designing efficient snarks.

大家都想做这类工作。

You wanna be doing this.

而且没人愿意做这个，你知道，几乎就是审计工作。

And no one wants to do this, you know, this auditing almost.

是啊。

Yeah.

如果你对吧？

If you right?

这这确实是个问题，但情况一直如此。

This is this is a bit of an issue, but that's it's been like that all the time.

嗯哼。

So mhmm.

我想稍微退一步，回到我们之前讨论的一些技术点。

I wanna go back just one step to some of the techniques that you were that we were talking about.

我记得我们开始讨论查找参数时，提到目前这方面还没有太多探索。

I think we got we started talking about lookup arguments, are not something that's being explored right now.

但你确实提到了折叠技术，还有递归组合。

But you did mention folding, and you mentioned so, Nico, you mentioned recursive composition.

我只是觉得我们在对话中有点偏离了这个话题。

I just I I feel like we kinda moved away from that in the conversation.

实际上，我想我们可能会在未来的节目中更详细地讨论这个问题。

And actually, I think we might be covering this on a future episode in more detail.

但我确实想简单和你聊聊折叠技术如何与格结构结合使用。

But I did wanna just briefly talk to you about how is folding being used alongside lattices.

格结构是否具有某些特性使其特别容易进行折叠操作？

Do lattices have certain qualities that make them like extra easy to fold?

是的。

Yes.

我认为由于格的代数结构特性，它们非常容易进行折叠操作。

I think lattices are very easy to fold because of their algebraic structure.

就像我说的，如果你直接应用格函数，这个a x等于y。

Like I said, if you just apply the lattice function, this a x equals y.

对吧？

Right?

现在你可以把x分成两部分，嗯哼。

Now you can just break up your x into two parts Uh-huh.

线性组合它们。

Linearly combine them.

这基本上就是你的折叠操作。

That's basically your folding.

对吧？

Right?

所以为了证明你已知的这个y，你只需将x分成两部分，线性组合它们，而且因为我们所有的函数都是线性的

So to to prove that you know this y, you can just break up x into two parts, linearly combine them, and because all our functions are just linear

嗯哼。

Uh-huh.

这本质上就是折叠。

It's it's essentially folded.

对吧？

Right?

不错。

Nice.

困难的部分总是证明微小性。

The hard part is always proving smallness.

麻烦的部分总是证明微小性。

The messy part is always proving smallness.

对吧？

Right?

你甚至可以自己尝试这个实验。

So you can even try this as an experiment yourself.

比如，假设难题在于不涉及微小性，你不需要证明微小性。

Like, let's pretend that the hard problem is there's no smallness involved, you don't have to prove smallness.

明白吗？

Okay?

我认为设计这些SNARK会很简单。

I think I think these snarks will be trivial to design.

对吧？

Right?

所以你可能只是因为折叠功能如此自然地融入其中，我甚至可以告诉你们格雷戈尔和沃德在拉布拉多工作时的故事。

So you could be just because it it lends itself so naturally to folding, I could even tell us that the story when when Gregor and Ward were working in Labrador.

我是说，他们最初的草稿版本，你知道的，是在研究防弹证明的工作

I mean, their first kind of drafts, they were, you know, work working of bulletproofs

哦，是的。

Oh, yeah.

并试图从中实现折叠功能。

And trying to get the the folding from there.

然后，你知道，他们尝试过——我们当时也在尝试，这在我之前参与的某篇理论论文中也有涉及，我们当时就说好吧，我们要试着模仿防弹证明。

And then, you know, they were try we they were trying, and this is something I was involved in before as well in some theoretical paper, and we kind said, okay, we're gonna, you know, try to mimic bulletproofs.

对吧？

Right?

这就像你之前说的，你们尝试过这些技术吗？

And this is kind of what you were saying before, like, have you tried these techniques?

我当时说，我希望尝试过格点相关的方法。

And I was saying, I wish tried the lattice y things.

对吧？

Right?

所以在尝试将格点理论融入防弹证明时

So when trying to to put lattices into the bulletproofs

构造。

Construction.

鸽巢原理之类的。

Pigeonhole or whatever.

构造。

Construction.

对。

Yeah.

没错。

Yeah.

这项技术。

The technique.

是啊。

Yeah.

你能得到一些东西。

You could get something.

对吧？

Right?

但最终他们意识到，嘿，这种折叠对格结构来说太自然了。

But then eventually they realize, hey, this this folding is just so natural to lattices.

我们根本不需要这些。

We don't need any of it.

我们甚至在做的时候都不需要考虑防弹证明。

We don't even need to think about bulletproofs when we do it.

现在回想起来，这种线性组合的做法几乎显而易见。

Just this linear combination thing is, in retrospect, almost obvious.

我认为这基本上就是所有这些其他论文中也在使用的方法。

And I think that's what's being used kind of in all these these other papers as well.

就像我说的，难点在于如何证明微小性。

And like I said, the hard part is how do you prove smallness.

我很高兴现在有很多不同的技术来证明微小性，有很多想法。

I I I like that there's a lot of different techniques now for proving smallness, lots of ideas.

你知道，有Szymczek的方法，有我们采用的Lyndon Johnson Lindenstrauss的方法。

You know, there's the Szymczek way, there's the the way we were doing the Lyndon Johnson Lindenstrauss way.

有趣的是它具有非常好的可组合性。

And the interesting thing is that it is very nicely composable.

对吧？

Right?

所以你可以从一个技术开始。

So you could because you could start with one technique.

对吧？

Right?

你得到的结果可以说导向了一个高效的验证器，然后转而采用另一种技术，实际上这能产生简洁的证明。

You get which is, let's say leads to an efficient verifier, and you switch to the other technique which actually leads to efficient it's small proofs.

对吧？

Right?

因为在第一步之后，你就不再需要关心高效验证器了。

Because after the first step, you don't care about efficient verifier anymore.

对吧？

Right?

我认为这种可组合性——我的预测是——这将成为处理格点问题的方法。

And I think the this composability is my prediction is this is the way it's gonna be done with Lattices.

我们将从一种技术开始，然后可能逐步转向类似Labrador的方法作为收尾。

We're gonna start with one technique and then move move over to possibly something like Labrador at the end.

你大致强调了格点结构带来的几个优势。

You kind of highlighted a few things that lattices bring.

我们讨论过它们具有后量子时代的特性。

We talked about like they're post quantum.

在某些情况下，它们的性能可能更优。

They in certain cases can perform better.

但我确实好奇，我记得第一次听说基于格的零知识证明，实际上是在全同态加密（FHE）的背景下。

But I did wonder I I think the first time I heard about lattice based ZK was actually in the context of FHE.

使用格密码的另一个好处是否在于，可以更轻松地实现全同态加密与零知识证明的结合？

Would another benefit of using lattices just be that you could then start to do like combined FHE and ZK in an easier way?

因为底层使用了一些相同的数学原理？

Like, because you're using some of the same maths underneath?

确实如此。

For sure.

确实如此。

For sure.

这一点在设计高效方案时相当重要，你需要保持代数结构的一致性。

This is this is something that that is pretty important for designing efficient schemes, that you want the algebraic structure to be the same.

对吧？

Right?

举个例子，这就是为什么在设计匿名凭证时，我们希望证明某些格关系，并且使用基于格的零知识证明来验证这些关系是合理的，因为它们的代数结构是兼容的。

So for example, this is why when designing anonymous credentials, we wanna prove some lattice relations because and it makes sense to use lattice based zero knowledge proofs to prove these relations because the the algebra is compatible.

对吧？

Right?

所以这绝对是有帮助的。

So that that absolutely helps.

是的。

Yeah.

当然，你也可以使用Fry来证明某些格关系。

You you could of course do you know, you can just use fry, right, to prove some lattice relation.

虽然有人尝试过，但效率极低。

And people have tried it, but it's extremely inefficient.

明白了。

Okay.

只是因为代数结构需要转换——当然，如果你使用的FHE本质上采用了相同的环结构，嗯。

Just because the algebra, you have to convert one So of the and it doesn't yes, of course, if if you have FHE which uses which is basically using the same ring structure Mhmm.

可能是更大的环，但环结构相同，当你想证明相关性质时，使用LiveSpace零知识技术会非常合理

Maybe bigger rings, but the ring structure is the same, and you wanna prove something about it, it makes a lot of sense that you will use LiveSpace ZK techniques

这很酷。

That's cool.

来证明它。

To to prove it.

所以这绝对会有所帮助。

So that should definitely help.

不错。

Nice.

有个问题我一直想问，虽然我们在节目中已经涉及了不同技术和协议，但我想了解目前格基解密和格基简洁证明的最新技术进展如何？

One thing I I did want to ask, and we sort of touched upon different techniques and different protocols throughout the episode, but I wanted to ask what does the state of the art look like for lattice based decay and lattice based succinct proofs?

好的。

Okay.

我认为我们仍处于简洁证明技术的非常早期阶段。

So I would say we're still in a very very early stage of succinct proofs.

就目前最先进的技术而言，如果只关注证明尺寸的简洁性，那么Labrador方案大约能实现50KB的任意规模证明。

So currently the state of the art, if you just care about succinctness in terms of proof size, then it's the Labrador scheme, which is, I would say about 50 kilobytes for arbitrary sized proofs.

如果关注验证者的简洁性，这方面已有大量研究成果。

Then if you care about succinct verifiers, there's now been a lot of work on this.

大约两年前出现了Labrador的Greyhound扩展方案。

There's the kind of Greyhound addition to to Labrador, which came out maybe two years ago.

是的。

Yeah.

现在还有Lattice Fold、Lattice Fold Plus等等方案

Now there's Lattice Fold, Lattice Fold Plus, you know, and it's

很多折叠操作啊。

A lot of folding.

虽然不确定保密程度如何，但作为密码学会议委员会成员，我看到有大量关于ZK格基NorX的论文投稿。

I don't know if it's how confidential it is, and I'm I'm on the committee for the crypto conference, and you know there's tons of papers being submitted about ZK lattice based NorX.

可以看出部分研究来自格密码学界，也有部分来自零知识证明社区尝试学习格密码的内容。

And you can see that it's really some of it is by lattice community, but some of it is by the zero knowledge community trying to learn lattices.

你可以看到他们在文献研究上还不太到位，就像格密码研究者对零知识证明文献也不太熟悉，但这让我感到非常有希望。

And you you see that they're not quite there on the literature, just like the lattice people are probably not quite there on the ZK literature, but it's very hopeful to me.

我非常高兴看到这一点，这显然是一个会快速发展的领域，就像哈希系统的发展历程一样。

I'm I'm very happy to see this that the that it's clearly an area that's gonna grow, like hash based systems, for example.

我是说，它们已经有二十年的先发优势了。

I mean, they've had a twenty twenty year head start Yeah.

也许吧。

Perhaps.

所以我相当乐观，如果我们再投入五到十年，格证明的效率会比现在更高。

So I'm quite quite optimistic that if we spend another five, ten years, Lattice proofs will be even more efficient than they are now.

酷。

Cool.

你刚才提到了哈希系统这方面。

You just mentioned the hash based side of things.

你在谈论格密码时提到，它们具有后量子特性，能抵御量子计算机攻击。

When you were talking about lattices, you know, they're post quantum, they're quantum like secure against quantum computers.

但至少基于哈希的SNARKs也应该能抵御量子计算机的攻击。

But hash based SNARKs, at least, are also supposed to be safe against quantum computers.

那么，格密码是否更胜一筹？

Like, are lattices better?

它们更安全吗？

Are they more safe?

这方面有任何比较数据吗？

Is there any sort of comparative there?

换句话说，至少在这个指标上，是否有理由更倾向于选择格密码？

Like, is there a reason why, at least on that metric lattices would be preferred?

就安全性而言，我认为基于哈希的方案需要假设的前提条件要少得多。

So in terms of safety, I would say the hash based schemes require you to assume much less.

它们只需要假设类似SHA或AES这样的算法是难以破解的。

They just require to assume that something like SHA or AES is is hard.

明白了。

Okay.

要知道，这些问题几乎没有什么结构可言，而我们确实相信SHA和AES是难以攻破的。

And you know, these problems have very little structure and we do believe that SHA and AES are hard.

嗯。

Mhmm.

因此在假设方面，基于哈希的方案显然更胜一筹。

So in terms of assumptions, hash based schemes are definitely preferable there.

而格密码则不同，它们需要依赖某些代数结构，或许量子计算机能利用这种代数或几何结构来破解它们。

Lattices on the other hand, they do require some algebraic structure and you know, maybe there's a way that quantum computers can latch on to some structure, this algebraic or geometric structure to break them.

所以如果要下注的话——任何人都会赌基于哈希的方案被攻破的概率远低于格密码这类方案。

So the assumptions, if I were to bet, if if anyone were to bet, they would of course bet on hash based having a smaller chance of being broken than any thing like lattice based cryptography.

这就是基于哈希方案的优势所在。

So that's where hash based is better.

但由于格密码具有这些代数假设，其背后的数学实现起来相对更容易。

But because lattices have these algebraic assumptions, the the math behind them is is let's say is easier to implement.

哦。

Oh.

所以它们的速度会更快。

So they're going to be faster.

因此我认为，格密码在效率上更胜一筹，而基于哈希的密码则在安全性上占优。

So lattices I believe, will win on efficiency, whereas hash based wins on Security.

你知道，就是被攻破的概率。

You know, the probability of being broken.

有意思。

Interesting.

很难说它们在安全性上更胜一筹。

It's hard to say that they win on security.

对吧？

Right?

因为两者可能同样难以攻破。

Because they both could be equally hard.

好的。

Okay.

对吧？

Right?

只是说如果你要下注，有人告诉你其中一个——你知道，如果有人明确告诉你其中一个肯定被破解了，那多半会是格密码。

It's just that if you're gonna bet and somebody tells you one of them is, you know, someone somebody tells you one of them is definitely broken, well, it's gonna be lattices.

对吧？

Right?

所以，呃

So so

好吧。

Alright.

是不是因为它们出现的时间没那么长？

Is it just because they've been around lot like, not as long?

它们还没经过实战检验？

They haven't been battle tested?

不是。

No.

格。

Lattices.

在这个语境下的格。

Lattices in this context.

哦，不。

Oh, no.

我想说即使是对于经典算法也是如此。

I would I would say even for classical algorithms.

对吧？

Right?

离散对数配对，这些比任何基于哈希的算法更容易被攻破。

Discrete log pairings, those are much more likely to be broken than anything hash based.

这是结构化与非结构化的问题吗？

Is this structure versus unstructured thing?

正是如此。

Exactly.

没错，Nick。

Exactly, Nick.

你说得对。

You're right.

因为格密码和其他离散对数假设都是有结构的，它们有量子计算机可以抓住的特性。

Because lattices and all these other discrete log assumptions, they're all structured, they have something that quantum computers can latch onto.

但这始终关乎效率，而结构正是在这方面有所帮助。

But it's always about the efficiency, and this is where the structure helps.

不过我要稍微搅局一下——我们所有基于哈希的证明都只在随机预言模型中被证明是安全的。

I will throw a little spanner in the works though, which is that all our hash based proofs are only proven secure in the Random Oracle model.

是的。

Yeah.

基于格密码的证明也是如此吗？

Is that also the case with lattice based proofs

或者说，是的。

or Yes.

是的。

Yes.

哦，这也是在随机预言模型中吗？

Oh, it's also a Random Oracle?

所有有趣的东西都会出现在随机预言模型中。

All the anything interesting is going to be in the Random Oracle model.

好的。

Okay.

对。

Yeah.

这非常有趣，因为基于格的证明仍然在随机预言模型中，而对于离散对数和基于配对的证明，我们确实有系统处于结构化参考阅读模型中，完全不涉及随机预言。

That's super interesting that lattice based proofs are still in the random Oracle model because with discrete log and like pairing based proofs, we do have systems that are in the structured reference reading model, but no random oracles involved at all.

明白了。

Okay.

现在我可能要说些非常错误的话，但我认为如果做出一些疯狂假设，或许可以避免使用随机预言。

So now I I could be saying something very wrong, but I think there could be a way to not have random oracles if you make some crazy assumptions.

对。

Right.

在配对密码学领域，至少据我这个可能了解不深的外行所知，还没有出现过这些疯狂假设导致问题的情况。

And in the pairing world, nothing has at least nothing that I know of, as somebody who's maybe not very deep into it, but just an outsider, that has gone wrong with these crazy assumptions.

而在格密码领域，确实出过问题。

Whereas in the lattice world, things have gone wrong.

最近有篇非常有趣的论文揭示了许多知识假设的问题——就是那种'你只有知道这个才能做到那个'的假设。

So all there's been a very interesting recent paper that showed a lot of knowledge assumptions where you say, ah, the only way for you to do this is if you know this.

基本上，如果你知道如何做到这点，那么就有提取器能从你这里提取信息——人们试图在格密码中应用这种假设，结果发现它在量子层面完全失效。

Basically, if you know how to do this, then there is an extractor that can extract this information from you that people try to make about lattices, and it turns out to be completely broken in the quantumly.

有意思。

Interesting.

对吧？

Right?

所以是的，这些知识假设，这些无法证伪的假设，我认为在零知识证明领域相当重要——如果你不想使用随机预言机之类的东西的话。

So yeah, so it is a bit, and these these these knowledge assumptions, these unfalsifiable assumptions, I think they are quite important in the you know, ZK world, if you're gonna not use maybe random oracles or something like that.

但对格密码来说，做出这些假设是危险的。

But they are dangerous to make for lattice.

所以我更倾向于使用随机预言机。

So I would much rather go with random oracles.

我认为它们没什么大问题，总比那些尚未证明自身稳定性的假设要好。

I don't see a big problem with them, rather than these assumption these assumptions which have not shown themselves to be very stable.

是的。

Yep.

有道理。

Fair.

你参与了NIST加密和签名标准的制定工作，我们之前提到过MLChem和MLDSA。

So you've been involved in the development of standards for encryption and signatures for NIST, we've mentioned them a bit earlier, MLChem and MLDSA.

能详细介绍一下它们的工作原理，以及与现有加密签名技术的比较吗？

Can you tell us a bit more about them and how they work and how they compare to existing encryption and signature techniques?

我认为理解格密码与离散对数差异的最佳方式，就是通过密钥交换来思考。

I I think the best way to understand what the difference between lattice and discrete log is to under to just think about the key exchange.

Diffie-Hellman密钥交换。

So Diffie Hellman key exchange.

对吧？

Right?

在Diffie-Hellman中，g的x次方等于，比如g的x1次方等于y1，g的x2次方等于y2，然后g的x1x2次方就是共享的密钥。

So Diffie Hellman, you have g to the x equals, you know, g to the x one equals y one, g to the x two equals y two, and then you have g to the x one x two is the is the shared Yep.

就是这样。

Thing.

而在格密码中，由于g^x的等效形式是LWE函数（即a乘x加误差项），所以无法实现这种交换。

So with lattices, you don't have that because the the equivalent of like g to the x is the LWE function, like a times x plus an error.

对。

Right.

当你得到a乘x加误差项，对方得到x1乘a加误差项时，你们可以进行相应计算。

And now, if you have a times x plus error, and the other guy has like some x one times a plus error, you can do the appropriate thing.

但最终会引入误差项。

But now you end up with errors.

现在你最终还要把误差也乘进去。

You now you end up multiplying by the errors as well.

对。

Right.

我们会出现这些交叉项之类的东西。

We have these cross terms sort of that start appearing.

是的。

Yeah.

没错。

Exactly.

正是。

Exactly.

这些交叉项我们无从得知，因为我不知道你的误差，你不知道我的误差，我们不知道交叉项是什么

These cross terms which you don't know about because I don't know your error, you don't know my error, we don't know what the cross terms

显然我们不能向对方透露自己的误差，否则整个系统就崩溃了。

we obviously cannot reveal our errors to each other, otherwise it's all broken.

确实如此。

Exactly.

完全正确。

Exactly.

所以Diffie-Hellman密钥交换实际上是一种行不通的方案。

So so Diffie Hellman key exchange is actually something that does not work.

这个Nike对实验室来说相当糟糕。

This Nike is quite bad for lab.

你可以调整参数使其大概率能成功，但那样效果会变得非常差。

You can do it, you can set the parameters so that it it works out with high probability, but then it becomes really terrible.

但在公钥加密中情况没那么糟，因为那里涉及一些交互过程。

But with public key encryption it's not so bad, because because there we're we're not there there is some interaction involved.

对吧？

Right?

而这里没有任何交互机制，我们确实可以做些改进。

Whereas in the there's no interaction here, you we can do something.

但这又回到了清除这些错误的问题上。

But it's again about clearing out these errors.

这就是MLChem的实质。

So this is what this is what MLChem is.

就像自然地应用El Gamal算法那样，如何将其转换到格密码上，然后处理其中的误差。

It's like the it's how you naturally apply El Gamal, how you translate El Gamal to lattices, and then you take care of the errors.

而这正是最棘手的部分。

And that's the messy part.

MLDSA，这是我们之前提到过的东西。

The MLDSA, it's this is something we mentioned before.

我说过，好吧，你是在尝试做零知识证明，并且尽可能高效地完成这个证明，证明某些足够好的东西。

I said, okay, you you it's it's you're trying to do the zero knowledge proof and you try to do as efficient as your knowledge proof as possible, proving something that's good enough.

对于签名来说已经足够好了。

It's good enough for signatures.

就是这样。

And this is yeah.