Follow blockchain research across journals, conferences, and preprint repositories.
972 results · page 11 of 41
Kristian Gjøsteen, Thomas Haines, Johannes Müller, Peter B. Rønne · 5 authors
No abstract is available for this record.
Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki
No abstract is available for this record.
Damiano Abram, Ivan Damgård, Claudio Orlandi, Peter Schöll
No abstract is available for this record.
George TeÅŸeleanu
No abstract is available for this record.
Andrej Bogdanov
No abstract is available for this record.
Ward Beullens, Samuel Dobson, Shuichi Katsumata, Yi-Fu Lai · 5 authors
Abstract We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny and lattice assumptions. Our group signature is based on a simple generic construction that can be instantiated by cryptographically hard group actions such as the CSIDH group action or an MLWE-based group action. The signature is of size $$O(\log N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where N is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt’20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is online extractable . Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members). In comparison, our lattice-based construction has a larger signature size (e.g., either 126 KB or 89 KB for 64 members depending on the satisfied security property). However, since the $$O(\cdot )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>·</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -notation hides a very small constant factor, it remains small even for very large group sizes, say $$2^{20}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>20</mml:mn> </mml:msup> </mml:math> .
Ngoc Khanh Nguyen, Gregor Seiler
No abstract is available for this record.
Vadim Lyubashevsky, Ngoc Khanh Nguyen
No abstract is available for this record.
Benny Applebaum, Eliran Kachlon, Arpita Patra
No abstract is available for this record.
Jonathan Bootle, Alessandro Chiesa, Siqi Liu
No abstract is available for this record.
Sungwook Kim, Hyeonbum Lee, Jae Hong Seo
No abstract is available for this record.
Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla
No abstract is available for this record.
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, Michiel Verbauwhede
No abstract is available for this record.
Mei Jiang, Dung Hoang Duong, Willy Susilo
No abstract is available for this record.
Craig Gentry, Shai Halevi, Vadim Lyubashevsky
No abstract is available for this record.
Yuyu Wang, Jiaxin Pan
No abstract is available for this record.
Carsten Baum, Lennart Braun, Alexander Munch-Hansen, Peter Schöll
Zero-knowledge proof systems are usually designed to support computations for circuits over $$\mathbb {F}_2$$ or $$\mathbb {F}_p$$ for large p, but not for computations over $$\mathbb {Z}_{2^k}$$ , which all modern CPUs operate on. Although $$\mathbb {Z}_{2^k}$$ -arithmetic can be emulated using prime moduli, this comes with an unavoidable overhead. Recently, Baum et al. (CCS 2021) suggested a candidate construction for a designated-verifier zero-knowledge proof system that natively runs over $$\mathbb {Z}_{2^k}$$ . Unfortunately, their construction requires preprocessed random vector oblivious linear evaluation (VOLE) to be instantiated over $$\mathbb {Z}_{2^k}$$ . Currently, it is not known how to efficiently generate such random VOLE in large quantities. In this work, we present a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over $$\mathbb {Z}_{2^k}$$ into a much longer, pseudorandom VOLE over the same ring. Our construction borrows ideas from recent protocols over finite fields, which we non-trivially adapt to work over $$\mathbb {Z}_{2^k}$$ . Moreover, we show that the approach taken by the QuickSilver zero-knowledge proof system (Yang et al. CCS 2021) can be generalized to support computations over $$\mathbb {Z}_{2^k}$$ . This new VOLE-based proof system, which we call QuarkSilver, yields better efficiency than the previous zero-knowledge protocols suggested by Baum et al. Furthermore, we implement both our VOLE extension and our zero-knowledge proof system, and show that they can generate 13–50 million VOLEs per second for $${64}\,{\textrm{bit}}$$ to $${256}\,{\textrm{bit}}$$ rings, and evaluate $${1.3}\,\textrm{million}$$ $${64}\,{\textrm{bit}}$$ multiplications per second in zero-knowledge.
Kang Yang, Xiao Wang
No abstract is available for this record.
Aviv Bick, Gillat Kol, Rotem Oshman
Zero knowledge proofs are one of the most influential concepts in theoretical computer science. In the seminal definition due to Goldwasser, Micali and Rackoff dating back to the 1980s, a computationally-bounded verifier interacts with a powerful but untrusted prover, with the goal of becoming convinced that the input is in some language. In addition to the usual requirements of completeness and soundness, in a zero knowledge proof, we protect the prover's knowledge: assuming the prover is honest, anything that the verifier can deduce after interacting with the prover, it could have deduced by itself. Zero knowledge proofs have found many applications within theoretical computer science and beyond, e.g., in cryptography, client-cloud computing, blockchains and cryptocurrencies, electronic voting and auctions, and in the financial industry. We define and study the notion of distributed zero knowledge proofs, reconciling the computational notion of zero-knowledge with the communication-based paradigm of distributed graph algorithms. In our setting, a network of verifiers interacts with an untrusted prover to decide some distributed language. As is usually the case in distributed graph algorithms, we assume that the verifiers have local views of the network and each only knows its neighbors. The prover, on the other hand, is assumed to know the entire network graph, as well as any input that the verifier may possess. As in the computational centralized setting, the protocol we design should protect this knowledge. In particular, due to the dual role of the underlying graph in distributed graph algorithms, serving as both the communication topology and the input to the problem, our protocol must protect the graph itself. We construct communication-efficient distributed zero knowledge proofs for two central problems: the 3-coloring problem, one of the poster children of computational zero-knowledge, and for the spanning-tree verification problem, a fundamental building block for designing graph algorithms. We also give a general scheme for converting proof labeling-schemes to distributed zero-knowledge protocols with related parameters. Our protocols combine ideas from computational complexity, distributed computing, and cryptography.
Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plançon
No abstract is available for this record.
Tiancheng Xie, Yupeng Zhang, Dawn Song
No abstract is available for this record.
Suthee Ruangwises, Toshiya Itoh
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.
Léo Robert, Daiki Miyahara, Pascal Lafourcade, Luc Libralesso · 5 authors
Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fill a grid with numbers between 1 and 5 while respecting three simple constraints. We first prove the NP-completeness of Suguru puzzle. For this we design gadgets to encode the PLANAR-CIRCUIT-SAT in a Suguru grid. We then design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. This ZKP protocol allows a prover to prove that he knows a solution of a Suguru grid to a verifier without leaking any information on the solution. To construct such a physical ZKP protocol, we only rely on a few physical cards and adapted encoding. For a Suguru grid with n cells, we only use 5n+5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.
Shihui Fu, Guang Gong
Abstract We present a new zero-knowledge succinct argument of knowledge (zkSNARK) scheme for Rank-1 Constraint Satisfaction (RICS), a widely deployed NP-complete language that generalizes arithmetic circuit satisfiability. By instantiating with different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from O (log 2 N ) to <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"><m:mrow><m:mi>O</m:mi><m:mrow><m:mo>(</m:mo><m:mrow><m:msqrt><m:mi>N</m:mi></m:msqrt></m:mrow><m:mo>)</m:mo></m:mrow></m:mrow></m:math> O\left( {\sqrt N } \right) depending on the underlying polynomial commitment schemes when applied to an N -gate arithmetic circuit. All these schemes do not require a trusted setup. It is plausibly post-quantum secure when instantiated with a secure collision-resistant hash function. We report on experiments for evaluating the performance of our proposed system. For instance, for verifying a SHA-256 preimage (less than 23k AND gates) in zero-knowledge with 128 bits security, the proof size is less than 150kB and the verification time is less than 11ms, both competitive to existing systems.