IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series (S3)

Software Seminar Series (S3)

Emanuele Giunta

Tuesday, October 25, 2022

11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)

Emanuele Giunta, PhD Student, IMDEA Software Institute

On the Impossibility of Algebraic Vector Commitments

Abstract:

Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, {\em algebraic} constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known. In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize. Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.


Time and place:
11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)
IMDEA Software Institute, Campus de Montegancedo
28223-Pozuelo de Alarcón, Madrid, Spain


Dimitris Kolonelos

Tuesday, October 18, 2022

11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)

Dimitris Kolonelos, PhD Student, IMDEA Software Institute

Succinct Zero-Knowledge Batch Proofs for Set Accumulators

Abstract:

Cryptographic accumulators are a common solution to proving information about a large set . They allow to compute a short digest of and short certificates of some of its basic properties, notably membership of an element. Accumulators also allow to track set updates: a new accumulator is obtained by inserting/deleting a given element. In this work we consider the problem of generating membership and update proofs for batches of elements so that we can succinctly prove additional properties of the elements (i.e., proofs are of constant size regardless of the batch size), and we can preserve privacy. Solving this problem would allow to obtain blockchain systems with improved privacy and scalability.


Time and place:
11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)
IMDEA Software Institute, Campus de Montegancedo
28223-Pozuelo de Alarcón, Madrid, Spain


Juan Manuel Copia

Tuesday, September 27, 2022

11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)

Juan Manuel Copia, PhD Student, IMDEA Software Institute

LISSA: Lazy Initialization with Specialized Solver Aid

Abstract:

Programs that deal with heap-allocated inputs are difficult to analyze with symbolic execution (SE). Lazy Initialization (LI) is an approach to SE that deals with heap-allocated inputs by starting SE over a fully symbolic heap, and initializing the inputs' fields on demand, as the program under analysis accesses them. However, when the program's assumed precondition has structural constraints over the inputs, operationally captured via repOK routines, LI may produce spurious symbolic structures, making SE traverse infeasible paths and undermining SE's performance.

In this talk I will present LISSA, our solution to efficiently detect and prune paths containing spurious symbolic structures. LISSA employs a novel structural constraint solver, SymSolve, capable of deciding satisfiability of partially symbolic structures. We experimentally assess LISSA against related techniques over various case studies, consisting of programs with heap-allocated inputs with complex constraints. The results show that LISSA is faster and scales better than related techniques.


Time and place:
11:00am Meeting room 302 & Zoom3 https://zoom.us/j/3911012202 (pass: @s3)
IMDEA Software Institute, Campus de Montegancedo
28223-Pozuelo de Alarcón, Madrid, Spain


Software Seminar Series (S3) - Spring 2022