דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

הצפנה הומומורפית קומבינטורית
event speaker icon
איל קושניר (הרצאה סמינריונית למגיסטר)
event date icon
יום שני, 07.07.2025, 18:30
event speaker icon
מנחה: Prof. Ron Rothblum

Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography.

Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes. In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism.

Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity.

Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem f(x, y) (where x is Alice’s input and y is Bob’s input) which requires communication c, but can be solved with communication less than c when Alice is given in addition also an encryption Ek(y) of Bob’s input (using Bob’s key k).

We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.