Launch HN: Blyss (YC W23) – Homomorphic encryption as a service

Re:Launch HN: Blyss (YC W23) – Homomorphic encryption as a s... by ngneer on Tuesday March 14, 2023 @07:05PM (#35160586)

I vaguely recall basic PIR schemes turn a database from O(n) to O(n^2). While this would be transparent to users of the service, could you comment on space overhead?

[ Parent | on HN ]

Re:Launch HN: Blyss (YC W23) – Homomorphic encryption as a s... by blintz on Tuesday March 14, 2023 @07:43PM (#35161230)

The space overhead is roughly constant (or at most logarithmic in n), and varies by the scheme. In practice, it’s something like 1.5-8x overhead. This is no big deal for storage, but does make it a pain on the memory side for processing (since the full database, including the overhead factor, needs to be resident in memory).

[ Parent | on HN ]

Re:Launch HN: Blyss (YC W23) – Homomorphic encryption as a s... by ngneer on Wednesday March 15, 2023 @01:40AM (#35164344)

Awesome, thanks for taking the time to elucidate!

[ Parent | on HN ]