5 ms·

A lattice-based cryptographic library in Go

73 points by rch 7y ago

throwawaymath 7y ago
Note that this comes out of a group at EPFL, a university known for cryptography research. Can anyone explain how they're achieving comparable performance to C++ using Go, for someone who has never programmed in Go?
- fwip 7y ago
  Go goes pretty fast, especially if you program it like C (avoiding memory allocations).
- drvd 7y ago
  Go is fast. No interpreter, no JIT, plain machine code combined with the ability to lay out your data like you can in C.
  - Abishek_Muthian 7y ago
    But the availability numerical libraries have been lackluster in my limited exploration.
- pcwalton 7y ago
  That's surprising to me, because I don't see any SIMD use in this library. I guess the C++ libraries they're comparing against aren't using SIMD either and aren't effectively using autovectorization. I don't believe that the Go compiler autovectorizes.
  - KenoFischer 7y ago
    Yes, you are correct, the C++ libraries in this field have decent performance, but generally haven't been tuned to hell yet (though they do tend to use all the algorithmic tricks people know about). Which is good news for those of us writing non-C++ versions of these algorithms because it means state of the art performance isn't all that hard to achieve.
- dgb23 7y ago
  You have less control in Go, it being garbage collected and omitting pointer arithmetic. It also ships with a runtime and is statically compiled so the binary you get is 'large'. 'goroutines' (similar to green-threads) are very lightweight and be integrated with high-level CSP constructs (channels & select) or lower level concurrency primitives from the std lib. From what I've seen benchmark wise Go performs well. It is in the ballpark of fast, statically compiled, garbage collected languages, comparable to fast C#, Java etc. roughly speaking but surpasses them on certain tasks. If I remember correctly there are several web/http/json related tasks where Go is a top performer.
  - pjmlp 7y ago
    Go supports pointer arithmetic as unsafe code (which is what it is in practice).
Thaxll 7y ago
"RNS-accelerated Fan-Vercauteren version of Brakerski's scale invariant homomorphic" def outside of my skills ~~ Interesting nonetheless!
- KenoFischer 7y ago
  That's just a fancy way of referencing a particular paper. None of those terms mean anything outside this particular subfield.
mitchtbaum 7y ago
Lattices seem like they'll have great value, in general, once higher dimensional data structures become common geometric orientations like in crypto apps and databases.
- thecupisblue 7y ago
  Hey! Nice to see someone thinking so, do you think a lattice based database would be a good solution? I just implemented a lattice structure recently and anybody I try talking to about it looks at me like I'm crazy. I thought maybe I got something wrong about the structure but there are so many advantages.
gaahrdner 7y ago
> The Lattigo library unleashes the potential of lattice-based cryptography in secure multiparty computation for modern software stacks. To a layman like myself, what does this mean?
- littlestymaar 7y ago
  Here's my attempt: Lattice-based crypto: Regular public-key crypto mostly use one kind of mathematical structures (finite fields) who have a known hard problem (finding the discrete logarithm of a number of a finite field) while the reverse problem (calculate the power of n of a given number) is trivial. You can do crypto on every structure for which it exists such a problem. Latice are different mathematical structures, for which it exists different kinds of problems that can be used for crypto. secure multiparty computation Let say you have some confidential data X and I have some confidential data Y. What we want to do is compute f(X,Y) without sharing the X and Y because we don't trust one another (or any third party). I hope it helped.

73 points by rch 7y ago

Note that this comes out of a group at EPFL, a university known for cryptography research. Can anyone explain how they're achieving comparable performance to C++ using Go, for someone who has never programmed in Go?

fwip 7y ago
Go goes pretty fast, especially if you program it like C (avoiding memory allocations).
drvd 7y ago
Go is fast. No interpreter, no JIT, plain machine code combined with the ability to lay out your data like you can in C.
- Abishek_Muthian 7y ago
  But the availability numerical libraries have been lackluster in my limited exploration.
pcwalton 7y ago
That's surprising to me, because I don't see any SIMD use in this library. I guess the C++ libraries they're comparing against aren't using SIMD either and aren't effectively using autovectorization. I don't believe that the Go compiler autovectorizes.
- KenoFischer 7y ago
  Yes, you are correct, the C++ libraries in this field have decent performance, but generally haven't been tuned to hell yet (though they do tend to use all the algorithmic tricks people know about). Which is good news for those of us writing non-C++ versions of these algorithms because it means state of the art performance isn't all that hard to achieve.
dgb23 7y ago
You have less control in Go, it being garbage collected and omitting pointer arithmetic. It also ships with a runtime and is statically compiled so the binary you get is 'large'. 'goroutines' (similar to green-threads) are very lightweight and be integrated with high-level CSP constructs (channels & select) or lower level concurrency primitives from the std lib. From what I've seen benchmark wise Go performs well. It is in the ballpark of fast, statically compiled, garbage collected languages, comparable to fast C#, Java etc. roughly speaking but surpasses them on certain tasks. If I remember correctly there are several web/http/json related tasks where Go is a top performer.
- pjmlp 7y ago
  Go supports pointer arithmetic as unsafe code (which is what it is in practice).

Thaxll 7y ago

"RNS-accelerated Fan-Vercauteren version of Brakerski's scale invariant homomorphic" def outside of my skills ~~ Interesting nonetheless!

KenoFischer 7y ago
That's just a fancy way of referencing a particular paper. None of those terms mean anything outside this particular subfield.

mitchtbaum 7y ago

Lattices seem like they'll have great value, in general, once higher dimensional data structures become common geometric orientations like in crypto apps and databases.

thecupisblue 7y ago
Hey! Nice to see someone thinking so, do you think a lattice based database would be a good solution? I just implemented a lattice structure recently and anybody I try talking to about it looks at me like I'm crazy. I thought maybe I got something wrong about the structure but there are so many advantages.

gaahrdner 7y ago

> The Lattigo library unleashes the potential of lattice-based cryptography in secure multiparty computation for modern software stacks. To a layman like myself, what does this mean?

littlestymaar 7y ago
Here's my attempt: Lattice-based crypto: Regular public-key crypto mostly use one kind of mathematical structures (finite fields) who have a known hard problem (finding the discrete logarithm of a number of a finite field) while the reverse problem (calculate the power of n of a given number) is trivial. You can do crypto on every structure for which it exists such a problem. Latice are different mathematical structures, for which it exists different kinds of problems that can be used for crypto. secure multiparty computation Let say you have some confidential data X and I have some confidential data Y. What we want to do is compute f(X,Y) without sharing the X and Y because we don't trust one another (or any third party). I hope it helped.