HackerTrans
トップ新着トレンドコメント過去質問紹介求人

mti

no profile record

投稿

The role of AI companies in large formalisation projects

leanprover.zulipchat.com
3 ポイント·投稿者 mti·4 か月前·0 コメント

コメント

mti
·12 か月前·議論
Good point. Note however that PIR is a rather restricted form of search (e.g., with no privacy for the server), but even so, DEPIR has polylog(n) queries (not log n), and requires superlinear preprocessing and a polynomial blowup in the size of the database. I think recent concrete estimates are around a petabyte of storage for a database of 2^20 words. So as you say, pretty impractical.
mti
·12 か月前·議論
There is an even more fundamental reason why FHE cannot realistically be used for arbitrary computation: it is that some computations have much larger asymptomatic complexity on encrypted data compared to plaintext.

A critical example is database search: searching through a database on n elements is normally done in O(log n), but it becomes O(n) when the search key is encrypted. This means that fully homomorphic Google search is fundamentally impractical, although the same cannot be said of fully homomorphic DNN inference.
mti
·昨年·議論
While not mentioned by the author, there is an alternate reason why finite field DH can be seen as a special case of ECDH, kind of: namely, there exists special elliptic curves (actual, smooth projective curves) that do have an efficiently computable endomorphism to a suitable form of the multiplicative group, via pairings. This is in essence the MOV attack against the XTR cryptosystem. That doesn't fit neatly in OP's framework, though, because the map isn't a morphism of algebraic groups (it is efficient for other reasons), and it is cheating a little bit, because the inverse map isn't efficiently computable.

Another point that the author glosses over a bit is that higher dimensional abelian varieties offer other instances of DH that are genuinely different from ECDH, and that are occasionally useful (mostly the case of Jacobians of hyperelliptic curves of genus 2). There isn't really a trick to make an arbitrary hyperelliptic curve DH/abelian variety DH instance a special case of ECDH: if anything, the relationship would be in the reverse direction.
mti
·昨年·議論
The relevant category is really abelian group schemes (because DH necessarily works in a cyclic group), so 0 is quite reasonable.