Crypto-Day@DMI 2014

Martedì 15 Luglio 2014 si terrà la prima edizione del Crypto-Day@DMI durante il quale ricercatori internazionali e locali del settore illustreranno recenti risultati nell’ambito della Crittografia moderna.

I seminari saranno tenuti in italiano e sono aperti a tutti gli interessati (docenti e studenti). I lavori si svolgeranno presso l’aula 25 del Dipartimento di Matematica e Informatica a partire dalle ore 9:40 secondo il seguente programma:

  • 9:40: Presentazione degli speaker
  • 10:00: Nelly Fazio (Assistant Professor presso City University of New York – US)

    Titolo: How to Broadcast a Secret Covertly
    Abstract: We initiate the study of broadcast steganography (BS), an extension of steganography to the multi-recipient setting. BS enables a sender to communicate covertly with a dynamically designated set of receivers, so that the recipients recover the original content, while unauthorized users and outsiders remain _unaware_ of the covert communication. One of our main technical contributions is the introduction of a new variant of anonymous broadcast encryption that we term outsider-anonymous broadcast encryption with pseudorandom ciphertexts (oABE). Our oABE construction achieves sublinear ciphertext size and is secure in the standard model. Besides being of interest in its own right, oABE enables an efficient construction of BS secure in the standard model against adaptive adversaries with sublinear communication complexity.

  • 10:40: Antonio Nicolosi (Associate Professor presso Stevens Institute of Technology – US)

    Titolo: Hard Learning Problems Over Non-Commutative Groups
    Abstract: Building on the success of the Learning Parity with Noise (LPN) and Learning With Errors ( LWE) problems as source of intractability for cryptographic applications, in 2011 Baumslag et al. proposed generalized learning problems over arbitrary, possibly non-commutative groups. We study the average-case hardness of an instantiation of this framework with a family of non-commutative groups known as free Burnside groups of exponent 3. In our main result, we demonstrate that this problem, termed Learning Burnside Homomorphisms with Noise, enjoys a strong form of random self-reducibility. Along the way, we also prove a sequence of lemmas regarding homomorphisms of free Burnside groups of exponent 3 that may be of independent interest.

  • 11:20: Orazio Puglisi (PhD Student presso DMI) – PDF

    Titolo: Authenticating Computation on Groups: New Homomorphic Primitives and Applications
    Abstract: In this paper we introduce new primitives to authenticate computation on data expressed as elements in (cryptographic) groups. As for the case of homomorphic authenticators, our primitives allow to verify the correctness of the computation without having to know of the original data set. More precisely, our contributions are two-fold.
    First, we introduce the notion of linearly homomorphic authenticated encryption with public verifiability and show how to instantiate this primitive (in the random oracle model) to support Paillier’s ciphertexts. This immediately yields a very simple and efficient (publicly) verifiable computation mechanism for encrypted (outsourced) data based on Paillier’s cryptosystem.
    As a second result, we show how to construct linearly homomorphic signature schemes to sign elements in bilinear groups (LHSG for short). Such type of signatures are very similar to (linearly homomorphic) structure preserving ones, but they allow for more flexibility, as the signature is explicitly allowed to contain components which are not group elements. In this sense our contributions are as follows. First we show a very simple construction of LHSG that is secure against weak random message attack (RMA). Next we give evidence that RMA secure LHSG are interesting on their own right by showing applications in the context of on-line/off-line homomorphic and network coding signatures. This notably provides what seems to be the first instantiations of homomorphic signatures achieving on-line/off-line efficiency trade-offs. Finally, we present a generic transform that converts RMA-secure LHSG into ones that achieve full security guarantees.

  • 12:00: Rosario Gennaro (Full Professor presso City University of New York – US) – PDF

    Titolo: Efficiently Verifiable Computation on Encrypted Data
    Abstract: We study the task of efficient verifiable delegation of computation on encrypted data. First, we improve previous definitions in order to tolerate adversaries that learn whether or not clients accept the result of a delegated computation. Then, in this strong model, we show a scheme for arbitrary computations, and we propose highly efficient schemes for delegation of various classes of functions, such as linear combinations, high-degree univariate polynomials, and multivariate quadratic polynomials. Notably, the latter class includes many useful statistics. Using our solution, a client can store a large encrypted dataset with a server, query statistics over this data, and receive encrypted results that can be efficiently verified and decrypted.
    As a key contribution for the efficiency of our schemes, we develop a novel homomorphic hashing technique that allows us to efficiently authenticate computations, at the same cost as if the data were in the clear, avoiding a 10^4 overhead, which would occur with a naive approach. We confirm our theoretical analysis with extensive implementation tests that show the practical feasibility of our schemes.

  • 12:40: Chiusura