MAK Seminar

If you want to receive the e-mails with information about future sessions of our seminar, please send an e-mail to Jorge Villar.

LAST and COMING SEMINARS

November 27th, 2024, 12h30, Miquel Guiot (Universitat Rovira i Virgili, Tarragona): "Reducing the Share Size of Weighted Threshold Secret Sharing Schemes via Chow Parameters Approximation" 

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In weighted threshold access structures, each party has a weight, and subsets are authorized if their combined weight reaches a threshold. For these access structures, the current upper bound on the share size is quasipolynomial in the number of parties. To improve efficiency, the access structure can be approximated. This talk focuses on balancing efficiency and accuracy in such approximations by using techniques based on the Chow parameters. 

This is a joint work with Oriol Farràs and will be presented in Theory of Cryptography Conference (TCC) 2024.

October 9th, 2024, 12h30, Tamir Tassa (Open University, Israel): "Fear Not, Vote Truthfully: Secure E-Voting Protocols for Score- and Order-Based Rules" 

Electronic voting systems are essential for holding virtual elections, and the need for such systems increases due to the COVID-19 pandemic and the social distancing that it mandates. One of the main challenges in e-voting systems is to secure the voting process: namely, to certify that the computed results are consistent with the cast ballots, and that the privacy of the voters is preserved. We propose secure voting protocols for elections that are governed by two central families of voting rules: score-based and order-based rules. Our protocols offer perfect ballot secrecy, in the sense that they issue only the required output, while no other information on the cast ballots is revealed. Such perfect secrecy, which is achieved by employing secure multiparty computation tools, may increase the voters’ confidence and, consequently, encourage them to vote according to their true preferences. The protocols' high level of privacy, and their extremely lightweight nature, make them a most adequate and powerful tool for democracies of any size.

Joint work with Lihi Dery and Avishay Yanai

January 24th, 2020, 11h00, Ignacio Cascudo (IMDEA Software, Madrid): "On universally composable secure homomorphic commitment schemes" 

Commitment schemes are the digital equivalent to a safe-box. A committer can put a value in the box (commit), lock it and then send it to a receiver. At a later point the committer can open the commitment (sending the keys to the safe-box).  After receiving the box but before receiving the keys, while the receiver cannot see the message, the committer can no longer change it. Commitment schemes are very useful for secure multiparty computation, for which we often want some additional properties: homomorphic properties allow to open some agreed-upon functions of some committed messages; universal composable (UC) security gives strong guarantees of security when commitments are used as a part of larger protocol. In this talk I will describe some highlights of a line of work which constructs UC-secure homomorphic commitments from error-correcting codes and simpler cryptographic primitives. The talk is based on a series of papers from PKC 2015, Crypto 2016, Asiacrypt 2019 jointly with Ivan Damgård, Bernardo David, Nico Döttling, Rafael Dowsley, Irene Giacomelli, Jesper Buus Nielsen and Roberto Trifiletti.

November 29th, 2019, "Zero-Knowledge Morning", two talks related to zero-knowledge systems, starting at 10h00.

· Talk 1, by Carla Ràfols (UPF, Barcelona): 'A survey on SNARKs'

Zero-Knowledge proofs are among the oldest and most useful cryptographic primitives. Efficient proofs for ``simple"  languages (non NP complete) have been known for a long time, in different security models and based on various different computational assumptions. SNARKs or Succint Non-Interactive Arguments of Knowledge, proposed by Groth in 2010, allow to prove circuit satisfiability in zero-knowledge. The most efficient constructions are not only succinct (independent of the witness size) but also very efficient concretely. SNARKs have had a major impact in cryptographic research and practice, partly due to their application to anonymous financial transactions in cryptocurrencies.  In this talk, I will survey some of the main results, techniques and applications in the area.

 · Talk 2, by Ramiro Martínez (UPC, Barcelona): 'RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations'

Ring Learning With Errors (RLWE) samples are pairs of polynomials in Z_q[x] / <x^n + 1> , obtained from a distribution that depends on a secret polynomial. RLWE samples are computationally indistinguishable from uniformly random pairs of polynomials. We present efficient Zero-Knowledge Proofs of Knowledge (ZKPoK) for linear and multiplicative relations among secret messages hidden as RLWE samples. Our proposed protocols for a ZKPoK are based on the celebrated paper by Stern on identification schemes using coding problems (Crypto'93). Our 5-move protocol achieves a soundness error slightly above 1/2 and perfect Zero-Knowledge.
As an application we present ZKPoK of relations between committed messages. The resulting commitment scheme is perfectly binding with overwhelming probability over the choice of the public key, and computationally hiding under the RLWE assumption. Compared with previous Stern-based commitment scheme proofs we decrease computational complexity, improve the size of the parameters and reduce the soundness error of each round.

November 15th, 2019, "Secret Sharing Morning (II)", two talks (more or less) related to secret sharing, starting at 11h00.

· Talk 1, by Michael Olugbenga Bamiloshin (URV, Tarragona): 'Common Information, Matroid Representation, and Secret Sharing for Matroid Ports'

A secret sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. The information ratio of a secret sharing scheme is the size in bits of the largest share of the scheme divided by the size of the secret. Farràs, Kaced, Martín and Padró presented an improvement in the linear
programming technique to derive lower bounds on the information ratio of the schemes for an access structure that use the Ahlswede–Körner lemma and the common information of random variables, avoiding the use of explicit non-Shannon information inequalities (EUROCRYPT 2018).
In this work we apply this linear programming technique to the classification of matroids on eight and nine points. Namely, we apply this technique to check if a matroid is multilinearly representable, algebraic or almost entropic. We also present some hitherto unknown non-representable matroids and new bounds on the information ratio of schemes for ports of non-representable matroids.
(This is a joint work with Aner Ben-Efraim, Oriol Farràs and Carles Padró.)

· Talk 2, by Victor Peña-Macias (Univ. Nacional de Colombia): 'Characteristic-Dependent Linear Rank Inequalities and Applications to Network Coding'

In Linear Algebra over finite fields, a characteristic-dependent linear rank inequality is a linear inequality that holds by ranks of subspaces of a vector space over a finite field of determined characteristic, and does not in general hold over
fields with other characteristic.

In this talk, we show a new method to produce these inequalities. We also discuss some results of application to Network Coding, among these, for each finite or co-finite set of primes P, we show that there exists a sequence of networks {N(t)}_{t \in \N} in which each member is linearly solvable over a field if and only if the characteristic of the field is in P; and the linear capacity, over fields whose characteristic is not in P, tends to 0 as t tends to infinity.

October 10th, 2019, "Secret Sharing Morning", two talks on secret sharing, starting at 11h00.

· Talk 1, by Chen Yuan (CWI Amsterdam): 'Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary'
 
Robust secret sharing enables the reconstruction of a secret-shared message in the presence of up to t (out of n) incorrect shares. The most challenging case is when n = 2t + 1, which is the largest t for which the task is still possible, up to a small error probability and with some overhead in the share size. In this work,we propose a new robust secret sharing scheme that offers full security against a rushing adversary. We also answer the open question posed by Cevallos et al.(Eurocrypt 2012) who proposed a scheme with overhead of O(n+K) and asked whether the linear dependency on n was necessary or not.
(This is a joint work with Serge Fehr.)

· Talk 2, by Oriol Farràs (Univ. Rovira i Virgili, Tarragona, Spain): 'Secret-Sharing Schemes for General Access Structures'

A secret-sharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $2^{n−o(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) reduced the share size to $O(2^{0.994n})$. We improved the general construction, obtaining a share size $O(2^{0.892n})$. For the special case of linear secret-sharing schemes, we get an exponent of $0.942$ (compared to $0.999$ of Liu and Vaikuntanathan).
(Joint work with Benny Applebaum, Amos Beimel, Oded Nir and Naty Peter. Paper in Eurocrypt'2019)

July 23rd, 2019, 11h00. Shahram Khazaei (Sharif University of Technology, Tehran, Iran): 'Group-homomorphic Secret Sharing Schemes Are Group-characterizable with Normal Subgroups'

Since the seminal work of Frankel, Desmedt and Burmester [Eurocrypt'92 & Crypto'92] there has been almost no result on the algebraic structure of homomorphic secret sharing schemes. In this paper, we revisit group-homomorphic schemes--- those whose secret and share spaces are groups---via their connection to \emph{group-characterizable random variables} [Chan and Yeung 2002].
A group-characterizable random variable is induced by a joint distribution on the (left) cosets of some subgroups of a main group. It is easy to see that a group-characterizable secret sharing with \emph{normal} subgroups in the main group is group-homomorphic. In this paper, we show that the converse holds true as well.
To achieve the above claim, we present a necessary and sufficient condition for a joint distribution to be inherently group-characterizable (i.e., up to a relabeling of the elements of the support). Then, we show that group-homomorphic secret sharing schemes satisfy the sufficient condition and, consequently, they are inherently group-characterizable. We strengthen our result by showing that they indeed have a group characterization with normal subgroups in the main group.
Group-characterizable random variables are known to be quasi-uniform (namely, all marginal distributions are uniform). As an additional contribution, we present an example of a quasi-uniform random variable which is not inherently group-characterizable.

(Joint work with Reza Kaboli and Maghsoud Parviz.   Preprint: https://eprint.iacr.org/2019/576 )

December 12th, 2018, 16h15. Alonso González (École Normale Supérieure, Lyon, France): 'Shorter Ring Signatures from Standard Assumptions'

June 26th, 2018, 11h00. Antonio Faonio (IMDEA Software, Madrid, Spain): 'Optimistic Mixing, Revised'

Mixing Networks are protocols that allow a set of senders to send messages anonymously.
Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting.
Back in 2002, Golle et al proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. If, on the other hand, one or more mix-servers cheat, then the attack is recognized and one can back up to a different, slow mix-net.Unfortunately, Abe and Imai (ACISP'03) and independently Wikstr\"om (SAC'03) showed several major flaws in the optimistic protocol of Golle et al.

In this wok we give another look at optimistic mixing networks. Our contribution is mainly threefold.
First, we give formal definitions for optimistic mixing in the UC model. Second, we propose a compiler for obtaining a UC-secure mixing network by combining an optimistic mixing with a traditional mixing protocol as backup mixing. Third, we propose an efficient UC-secure realization of optimistic mixing based on the DDH assumption in the non-programmable random oracle model.
As a key ingredient of our construction, we give a new randomizable replayable-CCA secure public key encryption (PKE) that outperforms in efficiency all previous schemes.

(Joint work with Dario Fiore.)

April 19th, 2018. Carles Padró (Universitat Politècnica de Catalunya, Spain): 'Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing'. 

We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.
 
This is a joint work with Oriol Farràs, Tarik Kaced, and Sebastià Martín

March 21st, 2018. Oriol Farràs (Universitat Rovira i Virgili, Spain): 'Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes'. 

The main objective of this work is to find properties of the access structures that admit efficient secret sharing schemes. The specific question we consider is to know whether access structures that are close admit secret sharing schemes with similar information ratios. Answers to this question will help understand the limitations of secret sharing and the behavior of the optimal information ratio, seen as a function from the set of all the access structures with a positive number of participants to the real numbers.

We show that for every two access structures $\Gamma$ and $\Gamma'$ the difference between their optimal information ratios is at most $|\Gamma\cup \Gamma'|-|\Gamma\cap\Gamma'|$.  As a consequence of this result, we see that close access structures admit secret sharing schemes with similar information ratio. We show that this property is also true for particular classes of secret sharing schemes and models of computation, like the family of linear secret sharing schemes, span programs, Boolean formulas and circuits.

In order to understand this property, we also study the limitations of the techniques for finding lower bounds on the information ratio and other complexity measures. We analyze the behavior of these bounds when we add or delete subsets from an access structure.

(It is a joint work with Jordi Ribes-González and Sara Ricci.)

June 21st, 2017. Barcelona Crypto Day.  Four talks given by Benoît Libert (ENS, Lyon), Fabien Laguillaumie (ENS, Lyon - LIRMM, Montpellier), Carla Ràfols (UPF, Barcelona) and Javier Silva (UPF, Barcelona). Titles and abstracts of the talks are available here.

December 14th, 2016, 12h00. Javier Herranz (Universitat Politècnica de Catalunya, MAK, Barcelona): 'IBE and ABE: Rela(xa)tions and Open Problems'.

In this seminar we will recall the notions of Identity-based encryption (IBE) and Attribute-based encryption (ABE). We will see how the (folkloric, well-known?) implication ABE => IBE can be actually proved.
Then, since IBE (and thus ABE) based on standard settings like RSA or classical Discrete Logarithm seems hard (or maybe impossible) to obtain, we will propose some relaxations of the IBE and ABE notions which may have both theoretical and practical interest. We will end up by enumerating some open problems in this area. 

November 9th, 2016, 12h00. Javier Silva (Universitat Pompeu Fabra, Barcelona): 'A signature scheme from supersingular isogeny problems'.

In this talk, we present an identification protocol and a signature scheme due to Galbraith, Petit and Silva. We rely on the hardness of an isogeny problem on supersingular elliptic curves, which is believed to be a hard problem, and even the best known quantum algorithms to solve it run in exponential time.
Our identification protocol relies on two key ingredients. First, the good mixing properties of supersingular isogeny graphs, which allow us to move through the graph efficiently and at the same time achieve random-looking outputs.
Second, we make use of Deuring’s correspondence, which identifies endomorphism rings of supersingular elliptic curves with maximal orders in a certain quaternion algebra.  We use the algorithm of Kohel-Lauter-Petit-Tignol (ANTS 2014) to compute ideals of a certain norm between maximal orders in the quaternion algebra. This will allow to simulate the protocol with indistinguishable distribution.
Finally, we use the standard technique of Fiat-Shamir to derive a signature scheme from the identification protocol, and we discuss its security.
Background on elliptic curves, quaternion algebras and expander graphs will be provided at the beginning of the talk, only cryptography definitions are required.

October 27th, 2016, 12h30. Giulia Traverso (TU Darmstadt, Germany): 'AS^3: Improving distributed storage systems through adaptive social secret sharing'.

Distributed storage allows to outsource a document to the cloud such that multiple users can easily access the file. The protection of the document stored relies on secret sharing, which generates and distributes shares of the document to the storage servers. However, the users have to trust that a certain amount of storage servers behaves honestly and do not lose (retrievability) or reveal (confidentiality) the document. To address this so called social secret sharing schemes were developed that allow to adjust the distribution of shares according to the experience made with the involved storage servers. In this work, we provide a framework called AS$^3$ that allows to build social secret sharing schemes based on dynamic secret sharing. The resulting protocol has more freedom in adjusting the parameters of the shares distribution and therefore leads to more efficient and accurate solutions as well as an optimal storage consumption. Furthermore, we provide measures to detect and to prevent that the document is lost or accidentally revealed to individual storage servers. We also demonstrate how to compute trust values for storage servers, how to initialize trust values for newcomers, and provide a proof of concept implementation.

June 16th, 2016, 11h00. Jacek Pomykała (University of Warsaw): 'L-functions and large sieve application in cryptology'

In Part I I will focus on the efficient generation of cryptographic systems parameters and some derandomization problems.
In Part II on mutual reductions between the familiar hard computational problems.
In Part III I will present some motivations for using the values of Kronecker's symbols to provide the idea for construction of candidats of one-way functions.

April 22nd, 2016, 12h00. Tarik Kaced (LACL-UPEC, France): 'Information inequalities, secret sharing and applications'.

Given some random variables X_1, ... , X_n, one can form a vector of size 2^n-1 with the entropies of subsets of variables: [H(X_1), H(X_2), H(X_1,X_2), ... , H(X_1,...,X_n)]. The set of all possible such vectors is an object in the Euclidean space delimited by hyperplanes: information inequalities. Perhaps the most famous inequality is Shannon's basic inequality H(A,C) + H(B,C) <= H(A) + H(A,B,C).
We will see which role do these inequalities play in problems like secret sharing. I will also discuss a recent result on the geometry of inequalities based on duality of polymatroid.


April 6th, 2016, 11h30. Romain Gay (ENS, Paris, France): 'Recent Results on Attribute-Based Encryption'.

In this talk [1] and [2] will be discussed.
[1] Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption.
[2] Improved Dual System ABE in Prime-Order Groups via Predicate Encodings.

[1] We initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parameters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.
(Joint work with Iordanis Kerenidis and Hoeteck Wee.)

[2] We present a modular framework for the design of efficient adaptively secure attribute-based encryption (ABE) schemes for a large class of predicates under the standard d -Lin assumption in prime-order groups. Via this framework, we obtain concrete efficiency improvements for several ABE schemes. Our framework has three novel components over prior works: (i) new techniques for simulating composite-order groups in prime-order ones, (ii) a refinement of prior encodings framework for dual system ABE in composite-order groups, (iii) an extension to weakly attribute-hiding predicate encryption (which includes anonymous IBE as a special case).
(Joint work with Jie Chen and Hoeteck Wee.)


March 18th, 2016, 12h00. Giulia Traverso (TU Darmstadt, Germany): 'Dynamic and Verifiable Hierarchical Secret Sharing'.

In this work we provide a framework for dynamic secret sharing and present the first dynamic and verifiable hierarchical secret sharing scheme based on Birkhoff interpolation. Since the scheme is dynamic it allows, without reconstructing the message distributed, to add and remove shareholders, to renew shares, and to modify the conditions for accessing the message. Furthermore, each shareholder can verify its share received during these algorithms protecting itself against malicious dealers and shareholders. While these algorithms were already available for classical Lagrange interpolation based secret sharing, corresponding techniques for Birkhoff interpolation based schemes were missing. Note that Birkhoff interpolation is currently the only technique available that allows to construct hierarchical secret sharing schemes that are efficient and allow to provide shares of equal size for all shareholder in the hierarchy. Thus, our scheme is an important contribution to hierarchical secret sharing and to other techniques using this primitive, such as social secret sharing based cloud storage.


September 29th, 2015, 15h30. Diego Mirandola (CWI Amsterdam, The Netherlands, and Université Bordeaux, France): 'Squares of Random Linear Codes'.

Given a linear error-correcting code, its square is defined to be the span of the componentwise products of all pairs of codewords. We explain how a code gives rise to a linear secret-sharing scheme and how the multiplicativity properties of that secret-sharing scheme are related to the square of the code. We sketch how the code-square properties can be exploited to attack some instances of McEliece (code-based) cryptosystem.
These connections motivate our interest in squares of codes. In particular we study whether the square of a random code of a certain dimension fills the whole space with high probability. We show that this is indeed the case as soon as the dimension is larger than the square root of the length. Combinatorial arguments about quadratic forms over finite fields play an important role.
(This is joint work with I. Cascudo, R. Cramer and G. Zémor.)

September 28th, 2015, all day. MAK hosted the Crypto Seminars Day.


July 8th, 2015, 12h00. Ignacio Cascudo (Aarhus University, Denmark): 'Server-Aided Two-Party Computation with Minimal Connectivity in the Simultaneous Corruption Model'.

We consider secure two-party computation in the client-server model. In this scenario, two parties want to securely compute a function with help from a number of servers, and two adversaries operate separately but simultaneously, each of them corrupting one of the parties and a restricted subset of servers that they interact with. We will show that information-theoretically secure two-party computation is possible if and only if there is always at least one server which remains uncorrupted and, furthermore, in the cases where it is possible, we don't need servers to communicate directly to each other. Moreover, we will discuss the communication efficiency of the protocol, and along the way show that certain family of access structures appearing in our protocol admit ideal secret sharing schemes.
(This is joint work with Ivan Damgård, Oriol Farràs, Samuel Ranellucci.)


July 18th, 2014, 12h00. Georg Fuchsbauer (Institute of Science and Technology, IST, Austria): 'Adaptive Security of Constrained PRFs'.

Constrained pseudorandom functions were introduced independently by Boneh and Waters (Asiacrypt'13), Kiayias et al. (CCS'13), and Boyle et al. (PKC'14). Whereas for standard pseudorandom functions (PRF) a key is used to evaluate the PRF on all inputs in the domain, constrained PRFs offer the additional functionality to derive ``constrained'' keys with which the PRF can be evaluated only on a subset of the domain. The three papers all show that the classical PRF construction by Goldreich, Goldwasser and Micali directly yields a constrained PRF where one can compute constrained keys to evaluate the PRF on all inputs with a given prefix. This constrained PRF has already found many interesting applications. Unfortunately, the existing security proofs only show selective security; full security can only be obtained via complexity leveraging, which loses an exponential factor $2^N$ in security, where $N$ is the input length.
We present a new reduction that only loses a quasipolynomial factor $q^{\log N}$, where $q$ is the number of adversarial queries. For this we develop a novel proof technique which constructs a distinguisher by interleaving simple guessing steps and hybrid arguments a small number of times. We then investigate another constrained PRF, due to Boneh and Waters, which allows for constrained keys for the more general class of bit-fixing functions. Their security proof also suffers from a $2^N$ loss. We construct a meta-reduction which shows that any ``simple'' reduction that proves full security from a non-interactive hardness assumption must incur an exponential security loss.
(This is joint work with Momchil Konstantinov, Krzysztof Pietrzak and Vanishree Rao, available as IACR ePrint Report 2014/416)


July 16th, 2014. Oriol Farràs (Universitat Rovira i Virgili, Spain): 'Optimal Non-Perfect Uniform Secret Sharing Schemes'.

A secret sharing scheme is a method to protect data by dividing it into pieces. These pieces are called shares and are generated in such a way that data can only be recovered from certain subsets of shares. The security of these schemes derives from information theory. The Þrst secret sharing schemes were constructed by Shamir and Blakley in 1979. The original motivation was to protect keys and to safeguard information. However, secret sharing was soon used for many different cryptographic applications and became a very important primitive in cryptography.
This talk will be dedicated to the family of non-prefect secret sharing schemes. We will present new techniques for the study of these schemes, and the main bounds on the lenght of the shares. This is a joint work with Torben Hansen, Tarik Kaced and Carles Padr—, and it will be presented at CRYPTO 2014.


June 19th, 2013. Dario Fiore (Max Planck Institute for Software Systems, Germany): 'Vector Commitments and their Applications'.

We put forward the study of a new primitive that we call {\em Vector Commitment} (VC, for short). Informally, VCs allow to commit to an ordered sequence of $q$ values $(m_1, \ldots, m_q)$ in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $i$-th committed message). For security, Vector Commitments are required to satisfy a notion that we call \emph{position binding} which states that an adversary should not be able to open a commitment to two different values at the same position. Moreover, what makes our primitive interesting is that we require VCs to be {\em concise}, i.e. the size of the commitment string and of its openings has to be independent of the vector length.
We show two realizations of VCs based on standard and well established assumptions, such as RSA, and Computational Diffie-Hellman (in bilinear groups). Next, we turn our attention to applications and we show that Vector Commitments are useful in a variety of contexts, as they allow for compact and efficient solutions which significantly improve previous works either in terms of efficiency of the resulting solutions, or in terms of "quality" of the underlying assumption, or both. These applications include: Verifiable Databases with Efficient Updates, Updatable Zero-Knowledge Databases, and Universal Dynamic Accumulators.


June 12th, 2013. Jorge Villar (UPC, Spain): 'An Algebraic Framework for Diffie-Hellman Assumptions'.

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D_{\ell,k}-MDDH Assumption states that it is hard to decide whether a vector in G^\ell is linearly dependent of the columns of some matrix in G^{\ell\times k} sampled according to distribution D_{\ell,k}. It covers known assumptions such as DDH, 2-LIN (linear assumption), and k-LIN (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D_{\ell,k}. We use the hardness results to find new distributions for which the D_{\ell,k}-MDDH Assumption holds generically in m-linear groups. In particular, our new assumptions 2-SCASC and 2-ILIN are generically hard in bilinear groups and, compared to 2-LIN, have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the 2-LIN Assumption which was already used in a large number of applications.
To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more efficient NIZK and NIWI proofs for membership in a subgroup of G^\ell, for validity of ciphertexts and for equality of plaintexts. The results imply very significant efficiency improvements for a large number of schemes, most notably Naor-Yung type of constructions.
In this talk we only address the first family of applications, not including those related to NIZK or NIWI proofs.
(Joint work with Alex Escala (UAB, Spain), Gottfried Herold, Eike Kiltz and Carla Ràfols (RUB & HGI, Germany))


June 5th, 2013. Carles Padró (Nanyang Tech. Univ., Singapore): 'Secret Sharing, Rank Inequalities and Information Inequalities'.

Optimizing the length of the shares in secret sharing schemes is a difficult open problem. There is a huge gap between the best known lower and upper bounds. The only available technique to obtain lower bounds combines polymatroids, linear programming and information inequalities. Following the works by Csirmaz (1994) and Beimel and Orlov (2008), we analyze here the limitations of this technique.
Csirmaz proved that the best lower bounds that can be obtained by using only the basic Shannon inequalities are at most linear on the number of participants. Beimel and Orlov extended that result to all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date. In this work, we prove that all (known or unknown) information inequalities on a bounded number of variables only can provide lower bounds that are polynomial on the number of participants. Our result is proved by finding solutions with small value for the involved linear programs. A simple family of uniform Boolean polymatroids is used in the search of such solutions.