Place : LIX, Salle Henri Poincaré
Titre : Compressing Vector OLE
Abstract : Oblivious linear-function evaluation (OLE) is a secure
two-party protocol allowing a receiver to learn any linear combination
of a pair of field elements held by a sender. OLE serves as a common
building block for secure computation of arithmetic circuits,
analogously to the role of oblivious transfer (OT) for boolean circuits.
A useful extension of OLE is vector OLE (VOLE), allowing the receiver to
learn any linear combination of two vectors held by the sender. In
several applications of OLE, one can replace a large number of instances
of OLE by a smaller number of long instances of VOLE. This motivates the
goal of amortizing the cost of generating long instances of VOLE.
We suggest a new approach for fast generation of pseudo-random instances
of VOLE via a deterministic local expansion of a pair of short
correlated seeds and no interaction. This provides the first example of
compressing a non-trivial and cryptographically useful correlation with
good concrete efficiency. Our VOLE generators can be used to enhance the
efficiency of a host of cryptographic applications. These include secure
arithmetic computation and noninteractive zero-knowledge proofs with
reusable preprocessing.
Our VOLE generators are based on a novel combination of function secret
sharing (FSS) for multi-point functions and linear codes in which
decoding is intractable. Their security can be based on variants of the
syndrome decoding assumption over large fields that resist known
attacks. We provide several constructions that offer tradeoffs between
different efficiency measures and the underlying intractability assumptions.
Toward the end of the talk, I will also discuss exciting recent
developments of this work regarding the compression of more general
(pseudo)random bilinear correlations.
Antonin Leroux, 13:30, élève école
Efficient Proactive Multi-Party Computation
Secure Multi-Party Computation (MPC) allows a set of “n” distrusting
parties to compute functions on their private inputs while guaranteeing
secrecy of inputs while ensuring correctness of the computation. Most
MPC protocols can achieve such security only against a minority of
corrupted parties (e.g., there is an honest majority > n/2). Based on
cryptographic assumptions, security against dishonest majorities can be
obtained but requires more computation and communication. These levels
of security are often not sufficient in real life especially threats
that require long-term security against powerful persistant attackers
(e.g., so called Advanced Persistent Threats). In such cases, all the
parties involved in the protocol may become corrupted at some point.
Proactive MPC (PMPC)aims to address such mobile persistent threats; PMPC
guarantees privacy and correctness against an adversary allowed to
change the set of corrupted parties over time but that is bounded by a
threshold at any given instant. Until recently, PMPC protocols existed
only against a dishonest minority. The first generic PMPC protocol
against a dishonest majority was introduced in a recent work to be
presented in September 2018, it presents a feasibility result
demonstrating that it can be achieved but with high communication
complexity: O(n^4).
This talk presents our most recent work which develops an efficient
generic PMPC protocol secure against a dishonest majority. We improve
the overall complexity of the generic PMPC from O(n^4) to O(n^2)
communication. Two necessary stepping stones for generic PMPC are
Proactive Secret Sharing (PSS) and a secure distributed multiplication
protocol. In this work we introduce a new PSS scheme requiring only
O(n^2) communications. We also present a multiplication protocol against
dishonest majorities in the proactive setting; this protocol introduces
a new efficient way to perform multiplication in dishonest majority
without using pre-computation.
--
