PICOCRYPT

ERC CoG 101001283

PICOCRYPT Seminars - December 13, 2022

A day of cryptography talks sponsored by ERC project PICOCRYPT.

Program

10:30-11:00 Welcome and coffee
11:00 Eduardo Soria-Vazquez (Technology Innovation Institute): Secure and Verifiable Computation: Beyond finite field arithmetic
12:00 Erkan Tairi (TU Wien): (Inner-Product) Functional Encryption with Updatable Ciphertexts
12:45 Lightning talks
13:00 Lunch (provided)
14:00 Paola de Perthuis (ENS & Cosmian): MyOPE: Malicious securitY for Oblivious Polynomial Evaluation
15:00 Ignacio Cascudo (IMDEA Software Institute): YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model
16:00 End

(Pending small changes if we schedule a lightning talks session)

Organizers: Ignacio Cascudo, Dario Fiore, Pedro Moreno-Sanchez.

This event is part of the project PICOCRYPT funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101001283).

EU and ERC logos

Abstracts

MyOPE: Malicious securitY for Oblivious Polynomial Evaluation
Paola de Perthuis (ENS & Cosmian)

Oblivious Polynomial Evaluation (OPE) schemes are two-party protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in her point and no additional information.

MyOPE is a “short-sighted’’ non-interactive polynomial evaluation scheme with a poly-logarithmic communication complexity in the presence of malicious senders. In addition to strong privacy guarantees, MyOPE enforces honest sender behavior and consistency by adding verifiability to the calculations.

The main building block for this new verifiable OPE is an inner product argument (IPA) over rings that guarantees an inner product relation holds between committed vectors. Our IPA works for vectors with elements from generic rings of polynomials and has constant-size proofs that consist in one commitment while the verification, once the validity of the vector-commitments has been checked, consists is one quadratic equation only.

We further demonstrate the applications of our IPA for verifiable OPE using Fully Homomorphic Encryption (FHE) over rings of polynomials: we prove the correctness of an inner product between the vector of powers of the evaluation point and the vector of polynomial coefficients, along with other inner-products necessary in this application’s proof. MyOPE builds on generic secure encoding techniques for succinct commitments, that allow real-world FHE parameters and Residue Number System (RNS) optimizations, suitable for high-degree polynomials.

Secure and Verifiable Computation: Beyond finite field arithmetic
Eduardo Soria-Vazquez (Technology Innovation Institute)

In practical constructions of both secure Multi-Party Computation (MPC) and Verifiable Computation (VC), computation is usually expressed in terms of arithmetic circuits over finite fields. This is regardless of how well the target problem is expressed as a series of addition and multiplication gates over the finite field. The main reason behind this is that constructions are easier to design and analyze thanks to a series of algebraic tricks that hold over finite fields but whose generalization to broader classes of rings is unclear. On the other hand, emulating ring arithmetic with that of a finite field can be costly in terms of the number of gates and might be possible only up to approximations. Hence, supporting arithmetic circuits over rings is both of theoretical and practical interest: Are there algebraic limitations to MPC and VC, or are we working with finite fields merely because it is easier to propose constructions? Is it possible to plug any ring into our constructions in a black-box manner? If so, does that improve or harm concrete efficiency?

In this talk, I will ellaborate on these questions and their answers based on two recent results: “Efficient Information-Theoretic Multi-party Computation over Non-commutative Rings” together with Daniel Escudero at CRYPTO’21, and “Doubly Efficient Interactive Proofs over Infinite and Non-Commutative Rings” presented at TCC this year.

(Inner-Product) Functional Encryption with Updatable Ciphertexts
Erkan Tairi (TU Wien)

We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional encryption paradigm and is carried out via so-called update tokens. However, allowing update tokens requires some care for the security definition as we want that updates can be done by any semi-trusted third party and only on ciphertexts. Our contribution is three-fold: 1) We define our new primitive with a security notion in the indistinguishability setting. Within CUFE, functional decryption keys and ciphertexts are labeled with tags such that only if the tag of the decryption key and the ciphertext match, then decryption succeeds. Furthermore, we allow ciphertexts to switch their tags to any other tag via update tokens. Such tokens are generated by the holder of the main secret key and can only be used in the desired direction. 2) We present a generic construction of CUFE for any functionality as well as predicates different from equality testing on tags, which relies on the existence of (probabilistic) indistinguishability obfuscation (iO). 3) We present a practical construction of CUFE for the inner-product functionality from standard assumptions (i.e., LWE) in the random-oracle model.

aPlonK : Aggregated PlonK from Multi-Polynomial Commitment Schemes
Miguel Ambrona (Nomadic Labs) (canceled)

PlonK is a prominent universal and updatable zk-SNARK for general circuit satisfiability. We present aPlonK, a variant of PlonK that reduces the proof size and verification time when multiple statements are proven in a batch. Both the aggregated proof size and the verification complexity of aPlonK are logarithmic in the number of aggregated statements. Our main building block, inspired by the techniques developed in SnarkPack (Gailly, Maller, Nitulescu, FC 2022), is a multi-polynomial commitment scheme, a new primitive that generalizes polynomial commitment schemes. Our techniques also include a mechanism for involving committed data into PlonK statements very efficiently, which can be of independent interest. We also implement an open-source industrial-grade library for zero-knowledge PlonK proofs with support for aPlonK. Our experimental results show that our techniques are suitable for real-world applications (such as blockchain rollups), achieving significant performance improvements in proof size and verification time.

YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model
Ignacio Cascudo (IMDEA Software Institute)

Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary’s power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda et al. in TCC 2020, Gentry et al. in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (e.g. blockchains). In this model, instead of having all parties execute an entire protocol, smaller anonymous committees are randomly chosen to execute each individual round of the protocol. After playing their role, parties encrypt protocol messages towards the the next anonymous committee and erase their internal state before publishing their ciphertexts. However, a big challenge remains in realizing YOSO protocols: efficiently encrypting messages towards anonymous parties selected at random without learning their identities, while proving the encrypted messages are valid w.r.t. the protocol. In particular, the protocols of Benhamouda et al. and of Gentry et al. require showing ciphertexts contain valid shares of secret states. We propose concretely efficient methods for encrypting a protocol’s secret state towards a random anonymous committee. We start by proposing a very simple and efficient scheme for encrypting messages towards randomly and anonymously selected parties. We then show constructions of publicly verifiable secret (re-)sharing (PVSS) schemes with concretely efficient proofs of (re-)share validity that can be generically instantiated from encryption schemes with certain linear homomorphic properties. Finally, we show that our PVSS schemes can be efficiently realized from our encyption scheme.

Lightning talks

Also in collaboration with: Logo Red