Implementing Babystep-Giantstep Matrix-Vector Multiplication with BFV scheme

[fedejinich]

Hi, I'm trying to transcipher from PASTA to BFV, and one of the key elements to achieve this is to evaluate a product between a plain matrix and an encrypted packed vector. The original PASTA paper suggests using the Babystep-Gigantstep algorithm and provides a reference implementation. I'm trying to reproduce it in Go, using lattigo instead of SEAL

• Does anybody know if this is achievable with lattigo?
• Can I rotate rows by 'n' steps in the same way as SEAL does?

[Pro7ech]

Hi @fedejinich,

The algorithm is implemented for the BGV scheme: linear_transforms.go. Reimplementing it for BFV should be straightforward.

Another option is the experimental branch https://github.com/tuneinsight/lattigo/tree/dev_bgvfv which implements a unification of the BFV and BGV scheme. In this branch the BFV sheme is instantiated as a wrapper of a generalization of BGV, thus it has the API for the linear transform (see bfv.go and this line for an example of how to use it).

[fedejinich]

Hi @Pro7ech thanks for the quick (and nice) response, It really helps me.
I'm trying to implement a hybrid holomorphic scheme (PASTA + BFV) and right now this is one of my main blockers.
I guess I'll experiment with both options and see the results.

Again, thank you :)

[fedejinich]

@Pro7ech Do you think the experimental branch will be included in a new version? If not, I can try to collaborate with another experimental branch with the BFV implementation

[Pro7ech]

@fedejinich Great :) I'm glad this helped. Yes this branch is PR#309, which is third in the line of the PRs that are going to be merged once they are reviewed.

[fedejinich]

okay, thank you very much!