Kara's utopia

TFHE２

ドーナツ食べたくなくなった(*´_ゝ｀)

LHE 对于每一个函数，存在参数使得其能被同态计算。FHE 一组参数可以用来计算任何函数。给定安全参数，和要计算的函数，一个全同态方案的好坏可以由其可实现的基本操作，密钥大小，每个基本操作的时间开销，和密文开销衡量。最简单的全同态方案只需要一个可自举的 NAND 门。自举的位运算依旧比明文运算慢十亿倍。但全同态操作的基本元素是向量，可以以 SIMD 方式打包他们对运算速度进行了一定补偿。...

Posted by kara on October 3, 2022

TFHE

ドーナツ食べたくなった(*´_ゝ｀)

其实是一个 TFHE 随便记记。非常感谢作者 Ilaria Chillotti 的讲解和 FHE_org 让我这种笨比也有机会领会这么高级的 FHE 方案。 Part I: Ciphertext types Part II: Encodings and linear leveled operations Part III: Key switching and leveled multi...

Posted by kara on September 22, 2022

algebra

你是一个一个一个一个抽象带师

简单记一下自己可能用的到的代数结论。 Lagrange’s Theorem \[\small\mathrm{IF}\normalsize\enspace H\leq G,\small\mathrm{THEN}\normalsize\enspace\abs{H}\enspace\text{divides}\abs{G}\] 并不是存在性结论比如 $\abs{A_4}=12$，但它其他阶的...

Posted by kara on September 12, 2022

Fully H0M0morphic Encryption

ホモホモホモホモホモモモ

单就讲讲对称的全同态加密。也不能叫对称吧，反正就是 cipher，加密解密都是同一个密钥。叫私钥加密又容易误解。反正懂的都懂，HE 的典中典了。反正也可以用常规手段变为非对称公钥加密方案：一般做法是上文的人可以用加解密的私钥对很多 0 进行加密作为公钥，另一个想要用这个公钥进行加密的人先将这些加密后的 0 线性组合，再将它与想要加密的消息相加。这样无法得知消息，也无法得知加密公钥的私钥，...

Posted by kara on September 1, 2022

Ring Lattices

Lesser lord kusanari

Origin 大佬们觉得普通随机格效率低，于是转向特定代数格。一般随机格效率真的低吗？看看原来的 $\mathrm{SIS}$ 函数 $f_{\mathbf{A}} \colon \qty{0,1}^m \to \mathbb{Z}_{q}^{n}$ 计算复杂度近似 $O(n m \log q) \approx O\left(n^{2}\right)$。但在密钥穷举攻击下只需要 $2^{O...

Posted by kara on August 30, 2022

Commitment Schemes

Dendro Archon KAWA11!

Commitment Schemes Commitment 中文老翻译成承诺，我感觉跟承诺的语义没啥关系啊，更像是单纯的提交，比如 github 里的 commit。也不知道为什么一翻译就翻译成承诺了。很麻。这个密码学功能实际上跟一般对称加密很类似，只不过接收者收到密文没办法解密回原来的 $(m,r)$ 只能解密回另外一组 $(m’,r’)$。接受者要验证这个 commitment 对...

Posted by kara on August 30, 2022

Lattice Cryptography II

kinda tough aha?

随机格和对偶性上文讲了各种平均情况格困难问题，并将其描述为对单向函数求逆或是寻找碰撞。现在可以将这些和特定随机格上的计算问题联系起来。确定正整数 $n\leq m\leq q$，其中 $n$ 和/或 $m-n$ 作为主要安全参数。通常 $m$ 是 $n$ 较小的倍数，e.g.，$m=O(n)$ 或 $m=O(n\log n)$，$q$ 是一个大小为 $O(\log n)$ 比特的小素...

Posted by kara on August 16, 2022

怪怪的冲突

FncK λ0n, WgcK D0MN¡

总结一些最近遇到的 markdown 和所用的 $\LaTeX$ 渲染引擎之间的符号冲突问题。 Jekyll 里使用 $\LaTeX$ 渲染公式暂时没找到更好的工具。但必须忍受 markdown 和 $\LaTeX$ 语法在一些符号上的冲突问题。姑且将其记下于此，以后有闲心再去解决。但届时真要解决怕不是要修改之前取消转义之后的所有屎山代码 :-( 行内公式有问题： $\mathbf{...

Posted by kara on August 8, 2022

Lattice Cryptography

Cryptomania, son!(m9

本篇讲一讲密码学组建所用到的平均情况格计算问题。上一篇跟这一篇之间应该还差一些很关键的关于格计算问题复杂度的归约问题，涉及到为什么咱基于平均情况计算问题所构建的方案的安全性基于最坏情况的格计算问题复杂度。但这方面内容涉及到很多数学内容包括对偶格，高斯分布等等内容，并且这些晦涩的复杂度研究对于咱构造方案这个上层建设过程并没有影响。感兴趣的可以看一看，相关的资料也有很多，可以了解到为什么我们构造...

Posted by kara on July 26, 2022

Lattice Basic

Nanomachines, son!(m9

一堆定理引理懒得在这里写了，用到的时候再查罢。直接整点密码学。为什么研究格？格在密码学中的作用与有限域上的椭圆曲线类似，都是一种代数，而在这种代数上有很多密码学家所期望的数学性质，比如后面将会讲到的格密码作为欧几理德空间(向量空间)的离散子集，主要使用的是有限域上的加模、乘模运算，无需使用经典代数里的指数、对数运算等，运算效率会高很多；一些格上的计算问题存在从最坏情况到平均情况的归约...

Posted by kara on July 13, 2022

l'enfer, c'est les Autres.