Back to Events

Seminar Series

February 17

Functional Commitments for All Functions, under Transparent Setup and Standard Lattice Assumptions

Leo de Castro

Part Of

10:30A
- 12:00P

Location

RM G-882
Add to Calendar 2023-02-17 10:30:00 2023-02-17 12:00:00 America/New_York Functional Commitments for All Functions, under Transparent Setup and Standard Lattice Assumptions A functional commitment scheme enables a user to concisely commit to a function from a specified family, then later concisely and verifiably reveal values of the function at desired inputs. Useful special cases, which have seen applications across cryptography, include vector commitments and polynomial commitments. To date, functional commitments have been constructed (under falsifiable assumptions) only for functions that are essentially linear.In this talk, we give the first functional commitment scheme for nonlinear functions — indeed, for all functions of any bounded complexity — under a standard setup and a falsifiable assumption. More specifically, the setup is "transparent," requiring only public randomness (and not any trusted entity), and the assumption is the hardness of the standard Short Integer Solution (SIS) lattice problem. Our construction also has other attractive features, including: stateless updates via generic composability; excellent asymptotic efficiency for the verifier, and also for the committer in important special cases like vector and polynomial commitments, thanks to preprocessing (which can even be outsourced to an untrusted party); and post-quantum security, since it is based on SIS. This is joint work with Chris Peikert. RM G-882

February 10

Nearly Optimal Property Preserving Hashing

LaKyah Tyner
Northeastern University

Part Of

10:30A
- 12:00P

Location

G-882, Hewlett Room
Add to Calendar 2023-02-10 10:30:00 2023-02-10 12:00:00 America/New_York Nearly Optimal Property Preserving Hashing Property-preserving hashing (PPH) consists of a family of compressing hash functions h such that, for any two inputs x, y, we can correctly identify whether some property P(x, y) holds given only the digests h(x), h(y). In a basic PPH, correctness should hold with overwhelming probability over the choice of h when x, y are worst-case values chosen a-priori and independently of h. In an adversarially robust PPH (RPPH), correctness must hold even when x, y are chosen adversarially and adaptively depending on h. Here, we study (R)PPH for the property that the Hamming distance between x and y is at most t.       The notion of (R)PPH was introduced by Boyle, LaVigne and Vaikuntanathan (ITCS ’19), and further studied by Fleischhacker, Simkin (Eurocrypt ’21) and Fleischhacker, Larsen, Simkin (Eurocrypt ’22). In this work, we obtain improved constructions that are conceptually simpler, have nearly optimal parameters, and rely on more general assumptions than prior works. Our results are: We construct information-theoretic non-robust PPH for Hamming distance via syndrome listdecoding of linear error-correcting codes. We provide a lower bound showing that this construction is essentially optimal.We make the above construction robust with little additional overhead, by relying on homomorphic collision-resistant hash functions, which can be constructed from either the discrete-logarithm or the short-integer-solution assumptions. The resulting RPPH achieves improved compression compared to prior constructions, and is nearly optimal.We also show an alternate construction of RPPH for Hamming distance under the minimal assumption that standard collision-resistant hash functions exist. The compression is slightly worse than our optimized construction using homomorphic collision-resistance, but essentially matches the prior state of the art constructions from specific algebraic assumptions.Lastly, we study a new notion of randomized robust PPH (R2P2H) for Hamming distance, which relaxes RPPH by allowing the hashing algorithm itself to be randomized. We give an informationtheoretic construction with optimal parameterSpeaker Bio: LaKyah is a second-year student at Northeastern University working with Daniel Wichs and abhi shelat. She is currently doing work with     property preserving hashing and threshold signatures. G-882, Hewlett Room