Blockchain Papers

Emanuele Giunta, Alistair Stewart

No abstract is available for this record.

Mingjie Chen, Yi-Fu Lai, Abel Laval, Laurane Marco · 5 authors

No abstract is available for this record.

Jinrui Sha, Shengli Liu

No abstract is available for this record.

Max Kobelt, Michael Sober, Stefan Schulte

Zero-Knowledge Proofs (ZKPs) ensure privacy in sensitive applications, including blockchains, anonymous verifiable voting, and secure auctions. In recent years, a number of ZKP implementations have been presented. The diversity of available solutions raises the need to compare the implementations to discover their strengths and weaknesses. Unfortunately, the collection of ZKP implementations is highly heterogeneous, aggravating a just comparison between different implementations. Hence, there is a strong need for a benchmarking solution to measure and collect metrics to compare different ZKP implementations. Therefore, we design and implement a benchmarking solution for ZKPs. The proposed solution allows users to gather performance metrics of different ZKP implementations and aids the decision-making process of selecting the right implementation for a specific use case. The system is highly configurable and allows the integration of novel ZKP systems. Further, we demonstrate the solution’ s applicability by benchmarking two popular ZKP implementations.

Kyosuke Hatsugai, Kyoichi Asano, Yoshiki Abe

No abstract is available for this record.

X.D. Do, D. H. Mac, Quoc-Huy Vu

No abstract is available for this record.

Lennart Braun, Cyprien Delpech de Saint Guilhem, Robin Jadoul, Emmanuela Orsini · 6 authors

In this work, we extend the MPC-in-the-Head framework, used in recent efficient zero-knowledge protocols, to work over the ring $$\mathbb {Z}_{2^k}$$ , which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir’s secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Sylvain Chatel, Christian Mouchet, Ali Utkan Şahin, Apostolos Pyrgelis · 6 authors

Multiparty fully homomorphic encryption (MFHE) schemes enable multiple parties to efficiently compute functions on their sensitive data while retaining confidentiality. However, existing MFHE schemes guarantee data confidentiality and the correctness of the computation result only against honest-but-curious adversaries. In this work, we provide the first practical construction that enables the verification of MFHE operations in zero-knowledge, protecting MFHE from malicious adversaries. Our solution relies on a combination of lattice-based commitment schemes and proof systems which we adapt to support both modern FHE schemes and their implementation optimizations. We implement our construction in PELTA. Our experimental evaluation shows that PELTA is one to two orders of magnitude faster than existing techniques in the literature.

Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov · 5 authors

Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses \mathcalL _1 łor \cdots łor \mathcalL _B. Typically, ZK requires paying the price to handle all B branches. Prior works have shown how to avoid this price in communication, but not in computation.

Yuan Tian, Yongda Pang, Xinke Tian

In large-scale private computing applications, various arithmetic relations appear as or can be reduced to matrix relations. In this paper, we establish the efficient zero-knowledge proof (ZKP) for the quadratic matrix relation over finite field Fp with three or four witness matrices. In private computing tasks, lots of arithmetic relations are instances or special cases of such form, particularly some matrix structural decomposition relations. Different from the widely applied vectorspecific method, our method is matrix-specific. The matrix equation is treated as a tensor equality and probabilisticequivalent reduction techniques are applied to reduce the non-linear matrix relation to simple vector relation. To the authors’ best knowledge, currently, there are no matrix-specific methods to ZKP for nonlinear matrix relations. Compared against the current general linearization (vector-specific) method, our method substantially outperforms it in all critical aspects, e.g., for n-by-t matrix witnesses the required size of common reference string (c.r.s.) can be compressed by a factor of 2nt and the number of rounds, group and field elements in messages are all decreased by a factor of ≈2 for large-size witnesses. Computational complexities are almost the same in both methods.

Yuan Tian, Yongda Pang, Xinke Tian

In large-scale private computing applications, various arithmetic relations appear as or can be reduced to matrix relations. In this paper, we establish the efficient zero-knowledge proof (ZKP) for the quadratic matrix relation over finite field Fp with two witness matrices. In private computing tasks, lots of typical relations are instances or special cases of this form, e.g., matrix multiplicative relation, inverse relation, isometric relation, etc. Different from the widely-applied vectorspecific method, our method is matrix-specific. The matrix equation is treated as a tensor equality and probabilisticequivalent reduction techniques are applied to reduce the non-linear matrix relation to simple vector relation. To the authors’ best knowledge, currently, there are no matrix-specific methods to ZKP for nonlinear matrix relations. Compared against the current (vector-specific) method, our method substantially outperforms it in all critical aspects, e.g., for n-raw t-column matrix witnesses, the required size of common reference string (c.r.s.) can be compressed by a factor of 2nt and the number of messages, group and field elements are all reduced by a factor of ≈2 for large-size witnesses. Computational complexities in both methods are almost the same.

Ramiro Pinilla

(English) The main goal of this dissertation is to develop new lattice-based cryptographic schemes. Most of the cryptographic protocols that each and every one of us use on a daily basis are only secure under the assumption that two mathematical problems, namely the discrete logarithm on elliptic curves and the factorization of products of two primes, are computationally hard. That is believed to be true for classical computers, but quantum computers would be able to solve these problems much more efficiently, demolishing the foundations of plenty of cryptographic constructions. This reveals the importance of post-quantum alternatives, cryptographic schemes whose security relies on different problems intractable for both classical and quantum computers. The most promising family of problems widely believed to be hard for quantum computers are lattice-based problems. We increase the supply of lattice-based tools providing new Zero-Knowledge Proofs of Knowledge for the Ring Learning With Errors (RLWE) problem, perhaps the most popular lattice-based problem. Zero-knowledge proofs are protocols between a prover and a verifier where the prover convinces the verifier of the validity of certain statements without revealing any additional relevant information. Our proofs extend the literature of Stern-based proofs, following the techniques presented by Jacques Stern in 1994. His original idea involved a code-based problem, but it has been reiteratedly improved and generalized to be used with lattices. We illustrate our proposal defining a variant of the commitment scheme, a cryptographic primitive that allows us to ensure some message was already determined at some point without revealing it until a future time, defined by Benhamouda et al. in ESORICS 2015, and proving in zero-knowledge the knowledge of a valid opening. Most importantly we also show how to prove that the message committed in one commitment is a linear combination, with some public coefficients, of the committed messages from two other commitments, again without revealing any further information about the messages. Finally, we also present a zero-knowledge proof analogous to the previous one but for multiplicative relations, something much more involved that allows us to prove any arithmetic circuit. We give first an interactive version of these proofs and then show how to construct a non-interactive one. We diligently prove that both the commitment and the companion Zero-Knowledge Proofs of Knowledge are secure under the assumption of the hardness of the underlying lattice problems. Furthermore, we specifically develop such proofs so that the arising conditions can be directly used to compute parameters that satisfy them. This way we provide a general method to instantiate our commitment and proofs with any desired security level. Thanks to this practical approach we have been able to implement all the proposed schemes and benchmark the prototype im-plementation with actually secure parameters, which allows us to obtain meaningful results and compare its performance with the existing alternatives. Moreover, provided that multiplication of polynomials in the quotient ring ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, with 𝑝 prime and 𝑛 a power of two, is the most basic operation when working with ideal lattices we comprehensively study what are the necessary and sufficient conditions needed for applying (a generalized version of) the Fast Fourier Transform (FFT) to obtain an efficient multiplication algorithm in quotient rings as ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩ (where we consider any positive integer 𝑚 and generalize the quotient), as we think it is of independent interest. We believe such a theoretical analysis is fundamental to be able to determine when a given generalization can also be applied to design an efficient multiplication algorithm when the FFT is not defined for the ring we are considering. That is the case of the rings used for the commitment and proofs described before, where only a partial FFT is available. (Español) El objetivo principal de esta tesis es obtener nuevos esquemas criptográficos basados en retículos. La mayoría de los protocolos criptográficos que usamos a diario son únicamente seguros bajo la hipótesis de que el problema del logaritmo discreto en curvas elípticas y la factorización de productos de dos primos son computacionalmente difíciles. Se cree que esto es cierto para los ordenadores clásicos, pero los ordenadores cuánticos podrían resolver estos problemas de forma mucho más eficiente, acabando con las bases sobre las que se fundamenta una multitud de construcciones criptográficas. Esto evidencia la importancia de las alternativas poscuánticas, cuya seguridad se basa en problemas diferentes que sean inasumibles tanto para los ordenadores clásicos como los cuánticos. Los problemas de retículos son los candidatos más prometedores, puesto que se considera que son problemas difíciles para los ordenadores cuánticos. Presentamos nuevas herramientas basadas en retículos con unas Pruebas de Conocimiento Nulo para el problema Ring Learning With Errors (RLWE), seguramente el problema de retículos más popular. Las pruebas de Conocimiento Nulo son protocolos entre un probador y un verificador en los que el primero convence al segundo de la validez de una proposición, sin revelar ninguna información adicional relevante. Nuestras pruebas se basan en el protocolo de Stern, siguiendo sus técnicas presentadas en 1994. Su idea original involucraba un problema de códigos, pero se ha mejorado y generalizado reiteradamente para poder aplicarse a retículos. Ilustramos nuestra propuesta definiendo una variante del esquema de compromiso, una primitiva criptográfica que nos permite asegurar que un mensaje fue determinado en cierto momento sin revelarlo hasta pasado un tiempo, definido por Benhamouda et al. en ESORICS 2015, y probando que conocemos una apertura válida. Además mostramos cómo probar que el mensaje comprometido es una combinación lineal, con coeficientes públicos, de los mensajes comprometidos en otros dos compromisos. Finalmente también presentamos una prueba de Conocimiento Nulo análoga a la anterior pero para relaciones multiplicativas, algo mucho más laborioso que nos permite realizar circuitos aritméticos. Todo esto sin revelar ninguna información adicional sobre los mensajes. Mostramos tanto una versión interactiva como una no interactiva. Probamos que tanto el compromiso como las pruebas de Conocimiento Nulo que le acompañan son seguras bajo la hipótesis de que el problema de retículos subyacente sea difícil. Además planteamos estas pruebas específicamente con el objetivo de que las condiciones que surjan puedan ser utilizadas directamente para calcular los parámetros que las satisfagan. De esta forma proporcionamos un método genérico para instanciar nuestro compromiso y pruebas con cualquier nivel de seguridad. Gracias a este enfoque práctico hemos podido implementar todos los esquemas propuestos y evaluar el rendimiento con parámetros seguros, lo que nos permite obtener resultados relevantes que poder comparar con las alternativas existentes. Por otra parte, dado que la multiplicación de polinomios en el anillo cociente ℤₚ[𝑥]/⟨𝑥ⁿ + 1⟩, con 𝑝 primo y 𝑛 una potencia de 2, es la operación más utilizada al trabajar con retículos ideales, estudiamos de forma exhaustiva cuáles son las condiciones suficientes y necesarias para aplicar (una versión generalizada de) la Transformada Rápida de Fourier (FFT, por sus siglas en inglés) para obtener algoritmos de multiplicación eficientes en anillos cociente ℤₘ[𝑥]/⟨𝑥ⁿ − 𝑎⟩, (considerando cualquier 𝑚 positiva y generalizando el cociente), de interés por sí mismo. Creemos que este análisis teórico es fundamental para determinar cuándo puede diseñarse un algoritmo eficiente de multiplicación si la FFT no está definida para el anillo considerado. Es el caso de los anillos que utilizamos en el compromiso y las pruebas descritas anteriormente, donde solo es posible calcular una FFT parcial.

K. R. Raghunandan, Bhavya Kallapu, Radhakrishna Dodmane, Krishnaraj Rao N S · 6 authors

The global production of information continuously increases in quantity and variety. However, the tools and technologies developed to handle such large volumes of data have not adequately met the security and privacy requirements. Existing cloud security systems, often managed by a trusted third party, are susceptible to various security risks. To address these challenges and ensure the protection of personal information, blockchain technology emerges as a crucial solution with substantial potential. This research uses the blockchain-powered attribute-aware encryption method to establish a real-time secure communication approach over the cloud. By employing attribute-based encryption technology, data owners can implement fine-grained search permissions for data users. The proposed solution incorporates accessible encryption technology to enable secure access to encrypted data and facilitate keyword searches on the blockchain. This study provides a functional comparison of recently developed attribute-based encryption algorithms. The access control strategy comprises two access tree types and a linear secret-sharing system, serving as the main components. The elliptic curve’s base field was set to 512b, and the bilinear pairing parameter type used was Type-A. This approach involves storing keywords on a remote server and encrypting them using attribute-based encryption. Furthermore, the encrypted data blockchain and the corresponding ciphertext are stored in the blockchain. Numerical experiments were conducted to evaluate the system’s key generation, trapdoor building, and keyword retrieval capabilities.

Sergey Abrahamyan

Zero-knowledge Range Proof(ZKRP) has gained increasing interest due to its applications in blockchain and cryptocurrencies in particular.ZKRP provides a mechanism to prove that a hidden integer belongs to a given interval without revealing any information about hidden integers.Some ZKRP depends on an honest and reliable third party.Others avoid from the third party.Currently, one of the famous ZKRP is the so-called Bulletproofs proposed by Bunz et al.Applying well-known homomorphic encryption methods in realizing ZKRP is a prospective direction.This paper proposes a new ZKRP based on one of the well-known homomorphic encryption methods-the order-preserving encryption method.

Ruben De Smet, Kris Steenhaut, An Braeken

We present a novel approach to privacy preserving electronic road pricing (ERP) based on on-board units (OBUs) and zero-knowledge proofs (ZKPs), and without any need for tamper-proof elements. Since our approach issoftware-onlyandprotocol-enforced, it can be rapidly deployed on off-the-shelve or even pre-existing hardware, such as a smartphone or the on-board computer of a car. In addition, communication complexity is onlylogarithmicin function of route length, such that even for short routes the communication cost of the protocol is lower than the cost of naively transmitting the clear text route. Our implementation proves the construction to be computationally practical, especially for the verifier. Since the scheme is based on ZKPs, no unnecessary information gets leaked. At the basis of the scheme lies Bulletproofs, which is modified to provide native support for Pedersen vector commitments with logarithmic impact on proof size.

Jim Woodcock, Mikkel Schmidt Andersen, Diego F. Aranha, Stefan Hallerstede · 11 authors

This report describes the state of the art in verifiable computation. The problem being solved is the following: The Verifiable Computation Problem (Verifiable Computing Problem) Suppose we have two computing agents. The first agent is the verifier, and the second agent is the prover. The verifier wants the prover to perform a computation. The verifier sends a description of the computation to the prover. Once the prover has completed the task, the prover returns the output to the verifier. The output will contain proof. The verifier can use this proof to check if the prover computed the output correctly. The check is not required to verify the algorithm used in the computation. Instead, it is a check that the prover computed the output using the computation specified by the verifier. The effort required for the check should be much less than that required to perform the computation. This state-of-the-art report surveys 128 papers from the literature comprising more than 4,000 pages. Other papers and books were surveyed but were omitted. The papers surveyed were overwhelmingly mathematical. We have summarised the major concepts that form the foundations for verifiable computation. The report contains two main sections. The first, larger section covers the theoretical foundations for probabilistically checkable and zero-knowledge proofs. The second section contains a description of the current practice in verifiable computation. Two further reports will cover (i) military applications of verifiable computation and (ii) a collection of technical demonstrators. The first of these is intended to be read by those who want to know what applications are enabled by the current state of the art in verifiable computation. The second is for those who want to see practical tools and conduct experiments themselves.

Nicolas Aragon, Loïc Bidoux, Jesús-Javier Chi-Domínguez, Thibauld Feneuil · 7 authors

We exploit the idea of [Fen22] which proposes to build an efficient signature scheme based on a zero-knowledge proof of knowledge of a solution of a MinRank instance. The scheme uses the MPCitH paradigm, which is an efficient way to build ZK proofs. We combine this idea with another idea, the hypercube technique introduced in [AMGH+22], which leads to more efficient MPCitH-based scheme. This new approach is more efficient than classical MPCitH, as it allows to reduce the number of party computation. This gives us a first scheme called MIRA-Additive. We then present an other scheme, based on low-threshold secret sharings, called MIRA-Threshold, which is a faster scheme, at the price of larger signatures. The construction of MPCitH using threshold secret sharing is detailed in [FR22]. These two constructions allows us to be faster than classical MPCitH, with a size of signature around 5.6kB with MIRA-Additive, and 8.3kB with MIRA-Threshold. We detail here the constructions and optimizations of the schemes, as well as their security proofs.

Loïc Bidoux, Jesús-Javier Chi-Domínguez, Thibauld Feneuil, Philippe Gaborit · 7 authors

We present a signature scheme based on the Syndrome-Decoding problem in rank metric. It is a construction from multi-party computation (MPC), using a MPC protocol which is a slight improvement of the linearized-polynomial protocol used in [Fen22], allowing to obtain a zero-knowledge proof thanks to the MPCitH paradigm. We design two different zero-knowledge proofs exploiting this paradigm: the first, which reaches the lower communication costs, relies on additive secret sharings and uses the hypercube technique [AMGH+22]; and the second relies on low-threshold linear secret sharings as proposed in [FR22]. These proofs of knowledge are transformed into signature schemes thanks to the Fiat-Shamir heuristic [FS86].

Scott Ames, Carmit Hazay, Yuval Ishai, Muthuramakrishnan Venkitasubramaniam

No abstract is available for this record.

Abner F. B. Costa, Henrique Hepp, Murilo V. G. da Silva, Leandro M. Zatesko

The Hidden Subgroup Problem (HSP) generalises many problems that are candidates to be NP-intermediate. It was shown that the decision version of HSP belongs to the zero-knowledge complexity class HVPZK and that, if the size of the group is known, it also belongs to NISZK. We show that whenever we can sample uniformly at random elements of the group and of a set, with the same size of the group, that contains the image of the function that hides the subgroup, the problem is in NIPZK1 (i.e. NIPZK with perfect completeness). As a second contribution, we show that NIPZK1 has a complete promise problem that is a restricted version of a complete promise problem for the NIPZK class.

Authors unavailable

Finding efficient signature schemes based on coding theory is an important issue for post-quantum cryptography. One can build signature schemes based on zero-knowledge proofs using the Stern protocol and its variants as demonstrated both in Hamming metric [1], [2] and rank metric [3], [4]. These constructions feature a high soundness error hence have a rather large signature size. Recently, some techniques based on secure Multi-Party Computation (MPC) have made it possible to lower this soundness error thus resulting in smaller signatures in both Hamming metric [5], [6] and rank metric [7], [8]. Even more recently, a hypercube-based approach has improved the Hamming metric approach [9]. In this paper, we adapt the idea of [9] to rank metric using the protocol from [8]. Given a fixed number of parties, this hypercube-based approach improves the performances of the underlying scheme. It is thus possible to consider additional trade-offs between sizes and performances thus reducing the signature size up to 4.5kB by increasing the number of parties of the MPC protocol.

Amalan Joseph Antony, Kunwar Singh

No abstract is available for this record.

Haibo Tian, Yanchuan Wen, Fangguo Zhang, Yunfeng Shao · 5 authors

No abstract is available for this record.

Vincenzo Botta, Ivan Visconti

No abstract is available for this record.