Blockchain Papers

Yan Gérard, Pascal Lafourcade, Lola-Baie Mallordy, Léo Robert

No abstract is available for this record.

Ngoc Khanh Nguyen, George O'Rourke

In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.

Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.

Takuma Yoshioka, Toru Nakanishi, Teruaki Kitasuka

A system of zero-knowledge proofs on graph signatures has been proposed, where a graph can be signed, and the owner of the graph signature can prove a graph relation such as the connectivity and isolation of any two vertexes on the graph without disclosing all information about the graph. The correctness of the graph information is guaranteed by the signature. One of the applications is a virtualized infrastructure, where an infrastructure provider manages a distributed system, and each tenant is allocated a specific portion of this infrastructure for use. Tenants need to check with the provider that their resources are properly connected (connectivity) and that their resources are properly separated from the resources of other tenants (isolation). On the other hand, the provider cannot simply disclose the entire infrastructure topology to each tenant. Using the zero-knowledge proof system on graph signatures, both requirements can be addressed. Previously, an efficient zero-knowledge proof system on graph signatures using a bilinear-map accumulator has been proposed, where the verification time and the size of the proof data do not depend on the number of graph vertexes and edges. However, this system has two problems. First, since the proof does not include labels, it is not possible to prove the connectivity considering network bandwidth and cost. Second, since it assumes undirected graphs, it cannot handle applications on directed graphs such as network flows. In this paper, we extend the previous system and propose a zero-knowledge proof system of the connectivity for directed graphs where each edge has labels. We implemented our system on a PC using a pairing library and evaluate it by measuring the processing times. Compared to the conference version of this paper, we show the formal definitions and the security proofs of our proposed system, and add implementation-based evaluations reflecting the application to the virtualized infrastructure.

Daniel Apon, Chloé Cachet, Benjamin Fuller, Peter Hall · 5 authors

No abstract is available for this record.

Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert · 6 authors

We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.

Suthee Ruangwises

Nonogram is a pencil puzzle consisting of a rectangular white grid where the player has to paint some cells black according to given constraints. In 2010, Chien and Hon constructed a physical card-based zero-knowledge proof protocol for Nonogram, which enables a prover to physically show that he/she knows a solution of the puzzle without revealing it. However, their protocol requires special tools such as scratch-off cards and a sealing machine, making it impractical to implement in real world. The protocol also has a nonzero soundness error. In this paper, we develop a more practical card-based protocol for Nonogram with perfect soundness that uses only regular paper cards. We also show how to modify our protocol to make it support Nonogram Color, a generalization of Nonogram where the player has to paint the cells with multiple colors.

Vadim Lyubashevsky

Digital signatures and key exchange protocols are the two most important public key cryptographic primitives used in the electronic transmission of data. The goal of key exchange is to preserve the secrecy of the communication, while the goal of digital signatures is to guarantee the authenticity of the exchanged messages. Constructions of digital signature schemes based on classical mathematical assumptions appeared shortly following the invention of public key cryptography in the late 1970s. And just like with key exchange, the most efficient variants are based on number-theoretic problems that are believed to be (sub)-exponentially hard for classical machines, but are solved in polynomial time by Shor’s algorithm on a powerful-enough quantum computer. Also, like for key exchange, the most efficient constructions that we believe to be quantum safe are based on the presumed hardness of lattice problems over polynomial rings. One interesting difference between key exchange and digital signatures is that key exchange appears to inherently require that some mathematical problem be computationally hard. Digital signatures, on the other hand, can be generically constructed from any one-way function [1,2]. So even though they certainly fall into the category of public key primitives based on their usage, their existence requires much weaker assumptions. Additionally, the transformation from a one-way function to a digital signature is not too inefficient. For example, the total parameter size (public key + signature) of the SPHINCS+ scheme [3] is around 40 kB. While these sizes are larger, and signing times considerably longer, than those of signatures based on factoring or discrete log, it is still a usable scheme for many applications. And being only based on symmetric assumptions (e.g. one wayness and collision resistance of cryptographic hash functions), its security is very attractive. In order to be considered an interesting alternative to the above-mentioned signature, a scheme based on a mathematical assumption would need to have significant performance advantages. Schemes based on factoring and the discrete logarithm problem were significantly shorter and faster, and so the generic approach lay dormant for over four decades. The new quantum-safe schemes will need to have similar performance advantages if they are to be used in lieu of this safe approach. Below, we describe two techniques for constructing lattice-based digital signatures with output sizes being just a few kilobytes. On a very high level, lattice-based signature constructions follow the two known approaches for constructing classical signatures. In the first approach, the signer outputs a function f and an image y = f(x) as his public key and keeps x as his secret key. To sign a message μ, he gives a non-interactive zero-knowledge proof that he knows an x satisfying y = f(x), using the message μ to create the ‘challenge’ H(μ) for the proof (where H is a public function that maps μ to something ‘random looking’). If the function f is one way then the verifier should be convinced that the proof could have only been created by the entity who knows x. A classic example of this type of scheme is the Schnorr signature scheme [4] based on the hardness of the discrete logarithm problem. The second approach is to create a function f together with a trapdoor f−1, output f as the public key and keep f−1 as the secret key. A message μ is signed by using the secret trapdoor to create a pre-image x such that f(x) = H(μ). Again, if the function f is one way then only someone in possession of a trapdoor should be able to invert it. An example of such a construction based on a ‘factoring-like’ assumption is the RSA signature scheme [5]. The high-level ideas for lattice-based signatures follow the above blueprints, but the technical details are significantly more involved. The main reason for the complications is the different algebraic structure of the hard one-way function underlying lattice cryptography. While the domain of the function in discrete log and RSA-based one-way functions are groups, the domains in lattice-based signatures are sets that are not closed under any operation—in particular, they are elements in a group that have small norms. This crucial small norm requirement precludes us from using uniformly random masking as in Schnorr signatures or having a trapdoor for a bijective one-way function as in RSA signatures. These barriers have, nevertheless, been overcome and the resulting digital signatures are quite practical. In 2017, the US National Institute of Standards and Technology (NIST) began a ‘competition’ for a quantum-safe key exchange and digital signatures standard. At the time of this writing, this process is in the third round and there are two lattice-based signatures remaining—each following one of the above high-level designs. The CRYSTALS-Dilithium [6] scheme follows the Schnorr framework, but adds a crucial rejection-sampling step to keep the size of the coefficients small. The FALCON scheme [7] utilizes a randomized trapdoor sampling technique that uses a secret trapdoor for f−1 to produce random pre-images from a particular distribution. Because there is no longer a bijection, it is crucial to also have the property that the distribution of the outputted pre-images does not leak information about the trapdoor. Both schemes are relatively fast and their parameters (public key + signature size) are the shortest of all quantum-safe signature schemes. While both schemes are based on lattices, they have rather different characteristics. FALCON has very short parameters (see Table 1), but entails a rather complicated procedure for signature generation. In particular, it uses (an optimized version of) the GPV sampler [8], which requires floating-point arithmetic with approximately 64 bits of precision. Requiring such high precision means that subtle implementation errors may not get detected even with rigorous testing. Dilithium, on the other hand, has larger parameters but a very simple implementation where all the sampling in the signing is done in a power-of-2 range; it is thus much less prone to implementation errors. It is quite possible that in the future both schemes will be used for different applications. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Conflict of interest statement. None declared.

Suthee Ruangwises

No abstract is available for this record.

Linge Wang

The bioinformatics features are collected by pattern recognition technology, and the digital coding and format conversion of the feature data are realized by using the theory of topological group transformation. Authentication and Signature based on Zero Knowledge Proof Technology can be used as the trusted credentials of cloud platform and cannot be forged, thus realizing trusted and secure access.

Thomas Groß

Abstract—Digital signature schemes are a founda-tional cryptographic building block in certification and the projection of trust. Based on a signature scheme on committed graphs, we propose a toolkit of certification and proof methods to sign committed topology graphs and to prove properties of their certificates in zero-knowledge. This toolkit allows an issuer, such as an auditor, to sign the topology repre-sentation of an infrastructure. The prover, such as an infrastructure provider, can then convince a verifier of topology properties, such as partitions, connectivity or isolation, without disclosing the structure of the topol-ogy itself. By that, we can achieve the certification of the structure of critical systems, such as infrastructure clouds or outsourced systems, while still maintaining confidentiality. We offer zero-knowledge proofs of knowledge for a general specification language of security goals for virtualized infrastructures, such that high-level security goals can be proven over the topology certificate. Our method builds upon the Camenisch-Lysyanskaya signature scheme, is based on honest-verifier proofs and the strong RSA assumption. I.

H. Kinoshita

In conventional digital signature techniques, secret information, which is utilized for authentication, is disclosed to the verifier. A new digital signature system for image data is proposed. This system can be used to assert the copyright of image data. In this system, a graph generated from an image which must has a signature and an isomorphic graph is concealed in this image. The ZKIP (zero knowledge interactive proof) for the graph isomorphism is applied to assert the copyright of this image. Consequently the secret information is not disclosed during the authentication process.

Khanh Quoc Nguyen, Feng Bao, Yi Mu, Vijay Varadharajan

No abstract is available for this record.