International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alonso González

Publications

Year
Venue
Title
2019
PKC
Shorter Ring Signatures from Standard Assumptions
Alonso González
Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allow to sign a message on behalf of a set of users while guaranteeing authenticity and anonymity. Groth and Kohlweiss (EUROCRYPT 2015) and Libert et al. (EUROCRYPT 2016) constructed schemes with signatures of size logarithmic in the number of users. An even shorter ring signature, of size independent from the number of users, was recently proposed by Malavolta and Schröder (ASIACRYPT 2017). However, all these short signatures are obtained relying on strong and controversial assumptions. Namely, the former schemes are both proven secure in the random oracle model while the later requires non-falsifiable assumptions.The most efficient construction under mild assumptions remains the construction of Chandran et al. (ICALP 2007) with a signature of size $$\varTheta (\sqrt{n})$$, where n is the number of users, and security is based on the Diffie-Hellman assumption in bilinear groups (the SXDH assumption in asymmetric bilinear groups).In this work we construct an asymptotically shorter ring signature from the hardness of the Diffie-Hellman assumption in bilinear groups. Each signature comprises $$\varTheta (\root 3 \of {n})$$ group elements, signing a message requires computing $$\varTheta (\root 3 \of {n})$$ exponentiations, and verifying a signature requires $$\varTheta (n^{2/3})$$ pairing operations. To the best of our knowledge, this is the first ring signature based on bilinear groups with $$o(\sqrt{n})$$ signatures and sublinear verification complexity.
2019
PKC
Shorter Quadratic QA-NIZK Proofs
Despite recent advances in the area of pairing-friendly Non-Interactive Zero-Knowledge proofs, there have not been many efficiency improvements in constructing arguments of satisfiability of quadratic (and larger degree) equations since the publication of the Groth-Sahai proof system (JoC’12). In this work, we address the problem of aggregating such proofs using techniques derived from the interactive setting and recent constructions of SNARKs. For certain types of quadratic equations, this problem was investigated before by González et al. (ASIACRYPT’15). Compared to their result, we reduce the proof size by approximately 50% and the common reference string from quadratic to linear, at the price of using less standard computational assumptions. A theoretical motivation for our work is to investigate how efficient NIZK proofs based on falsifiable assumptions can be. On the practical side, quadratic equations appear naturally in several cryptographic schemes like shuffle and range arguments.
2019
ASIACRYPT
Shorter Pairing-Based Arguments Under Standard Assumptions
Alonso González Carla Ràfols
This paper constructs efficient non-interactive arguments for correct evaluation of arithmetic and boolean circuits with proof size O(d) group elements, where d is the multiplicative depth of the circuit, under falsifiable assumptions. This is achieved by combining techniques from SNARKs and QA-NIZK arguments of membership in linear spaces. The first construction is very efficient (the proof size is $$\approx 4d$$ group elements and the verification cost is $$\approx 4d$$ pairings and $$O(n+n'+d)$$ exponentiations, where n is the size of the input and $$n'$$ of the output) but one type of attack can only be ruled out assuming the knowledge soundness of QA-NIZK arguments of membership in linear spaces. We give an alternative construction which replaces this assumption with a decisional assumption in bilinear groups at the cost of approximately doubling the proof size. The construction for boolean circuits can be made zero-knowledge with Groth-Sahai proofs, resulting in a NIZK argument for circuit satisfiability based on falsifiable assumptions in bilinear groups of proof size $$O(n+d)$$.Our main technical tool is what we call an “argument of knowledge transfer”. Given a commitment $$C_1$$ and an opening x, such an argument allows to prove that some other commitment $$C_2$$ opens to f(x), for some function f, even if $$C_2$$ is not extractable. We construct very short, constant-size, pairing-based arguments of knowledge transfer with constant-time verification for any linear function and also for Hadamard products. These allow to transfer the knowledge of the input to lower levels of the circuit.
2015
EPRINT
2015
ASIACRYPT