Blockchain Papers

Samuel Hand, Alexander Koch, Pascal Lafourcade, Daiki Miyahara · 5 authors

No abstract is available for this record.

Suthee Ruangwises

Ball sort puzzle is a popular logic puzzle consisting of several bins containing balls of multiple colors. Each bin works like a stack; a ball has to follow the last-in first-out order. The player has to sort the balls by color such that each bin contains only balls of a single color. In this paper, we propose a physical zero-knowledge proof protocol for the ball sort puzzle using a deck of playing cards, which enables a prover to physically show that he/she knows a solution with $t$ moves of the ball sort puzzle without revealing it. Our protocol is the first zero-knowledge proof protocol for an interactive puzzle involving moving objects.

Lorenzo Grassi, Silvia Onofri, Marco Pedicini, Luca Sozzi

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over Fp for a large prime p have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps x↦xd. In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetrickey primitives. Given a local map F : Fmp→ Fp, we limit ourselves to focus on S-Boxes over Fnp for n ≥ m defined as SF (x0, x1, . . . , xn−1) = y0|y1| . . . |yn−1 where yi := F(xi, xi+1, . . . , xi+m−1). As main results, we prove that• given any quadratic function F : F2p→ Fp, the corresponding S-Box SF over Fnp for n ≥ 3 is never invertible;• similarly, given any quadratic function F : F3p → Fp, the corresponding S-Box SF over Fnp for n ≥ 5 is never invertible.Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F : Fmp → Fp for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F : F3p → Fp such that SF over Fnp for n ∈ {3, 4} is invertible. As an open problem for future work, we conjecture that for each m ≥ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F : Fmp →Fp is not invertible for each n ≥ nmax(m). Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.

Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki

Abstract During the last years, several card-based Zero-Knowledge Proof (ZKP) protocols for Nikoli’s puzzles have been designed. Although there are relatively simple card-based ZKP protocols for a number of puzzles, such as Sudoku and Kakuro, some puzzles face difficulties in designing simple protocols. For example, Slitherlink requires novel and elaborate techniques to construct a protocol. In this study, we focus on three Nikoli puzzles: Nurikabe, Hitori, and Heyawake. To date, no card-based ZKP protocol for these puzzles has been developed, partially because they have a relatively tricky rule that colored cells should form a connected area (namely a polyomino); this rule, sometimes referred to as “Bundan-kin” (in Japanese), complicates the puzzles, as well as facilitating difficulties in designing card-based ZKP protocols. We address this challenging task and propose a method for verifying the connectivity of hidden colored cells in a ZKP manner, such that we construct card-based ZKP protocols for the three puzzles.

Shay Gueron, Edoardo Persichetti, Paolo Santini

This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent paradigm known as “Sigma protocol with helper”, and prove that the protocol’s security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the Fiat–Shamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: (a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; (b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with Fiat–Shamir schemes. We outline an initial performance estimation to confirm that our scheme is competitive with respect to existing solutions of similar type.

Jiamin Cui, Kai Hu, Meiqin Wang, Puwen Wei

No abstract is available for this record.

Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki

No abstract is available for this record.

Suthee Ruangwises, Toshiya Itoh

Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.

Nicolas Magaud

We study how to formalize in the Coq proof assistant the smallest projective space PG(3,2). We then describe formally the spreads and packings of PG(3,2), as well as some of their properties. The formalization is rather straightforward, however as the number of objects at stake increases rapidly, we need to exploit some symmetry arguments as well as smart proof techniques to make proof search and verification faster and thus tractable using the Coq proof assistant. This work can be viewed as a first step towards formalizing projective spaces of higher dimension, e.g. PG(4,2), or larger order, e.g. PG(3,3).

Justin Holmgren, Alex Lombardi, Ron D. Rothblum

In a seminal work, Goldreich, Micali and Wigderson (CRYPTO ’86) demonstrated the wide applicability of zero-knowledge proofs by constructing such a proof system for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question in the negative, assuming a standard cryptographic assumption (i.e., the hardness of learning with errors (LWE)).

Tomoyuki Morimae, Takashi Yamakawa

We propose three constructions of classically verifiable non-interactive proofs (CV-NIP) and non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. - We construct an information theoretically sound CV-NIP for QMA in the secret parameter model where a trusted party generates a quantum proving key and classical verification key and gives them to the corresponding parties while keeping it secret from the other party. Alternatively, we can think of the protocol as one in a model where the verifier sends an instance-independent quantum message to the prover as preprocessing. - We construct a CV-NIZK for QMA in the secret parameter model. It is information theoretically sound and zero-knowledge. - Assuming the quantum hardness of the leaning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model.

Suthee Ruangwises

Sudoku is a famous logic puzzle where the player has to fill a number between 1 and 9 into each empty cell of a $9 \times 9$ grid such that every number appears exactly once in each row, each column, and each $3 \times 3$ block. In 2020, Sasaki et al. developed a physical card-based protocol of zero-knowledge proof (ZKP) for Sudoku, which enables a prover to convince a verifier that he/she knows a solution of the puzzle without revealing it. Their protocol uses 90 cards, but requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (consisting of 52 different cards and two jokers). Hence, nine identical standard decks are required to perform that protocol, making the protocol not very practical. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards, regardless of whether the two decks are identical or different. In general, we also develop the first ZKP protocol for a generalized $n \times n$ Sudoku that can be performed using a deck of all different cards.

Suthee Ruangwises, Toshiya Itoh

An undirected graph $G$ is known to both the prover $P$ and the verifier $V$, but only $P$ knows a subgraph $H$ of $G$. Without revealing any information about $H$, $P$ wants to convince $V$ that $H$ is a connected spanning subgraph of $G$, i.e. $H$ is connected and contains all vertices of $G$. In this paper, we propose an unconventional zero-knowledge proof protocol using a physical deck of cards, which enables $P$ to physically show that $H$ satisfies the condition without revealing it. We also show applications of this protocol to verify solutions of three well-known NP-complete problems: the Hamiltonian cycle problem, the maximum leaf spanning tree problem, and a popular logic puzzle called Bridges.

Suthee Ruangwises, Toshiya Itoh

Ripple Effect is a logic puzzle where the player has to fill numbers into empty cells in a rectangular grid. The grid is divided into rooms, and each room must contain consecutive integers starting from 1 to its size. Also, if two cells in the same row or column contain the same number $x$, there must be a space of at least $x$ cells separating the two cells. In this paper, we develop a physical zero-knowledge proof for the Ripple Effect puzzle using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, given a secret number $x$ and a list of numbers, our protocol can physically verify that $x$ does not appear among the first $x$ numbers in the list without revealing $x$ or any number in the list.

Tatsuya Sasaki, Daiki Miyahara, Takaaki Mizuki, Hideaki Sone

In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof of knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.

Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto

The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain. This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from O(< (p log p/M) to O(p log2 p/M2) Legendre symbol evaluations when M ≤ 4√ p log2 p queries are available. The practical relevance of our improved attack is demonstrated by breaking three concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.

Suthee Ruangwises, Suthee Ruangwises, 伊東, 利哉, Toshiya Itoh

Numberlink is a logic puzzle with an objective to connect all pairs of cells with the same number by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, the protocol shows how to physically count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Finally, we show that our protocol can be modified to verify a solution of the well-known $k$ vertex-disjoint paths problem, both the undirected and directed settings.

Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige · 8 authors

Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.

Suthee Ruangwises, Toshiya Itoh

Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.

Daiki Miyahara, Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone

Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.

Erlend Lid Helland

Denne oppgaven undersøker og sammenligner trekk ved kryptovaluta basert på blokkjeder med kryptovaluta basert på Rettede Asykliske Grafer (RAG). Blokkjedebasert kryptovaluta møter utfordringer på felt som skalering, desentralisering og ressursutnyttelse. Denne oppgaven undersøker om kryptovaluta som bruker en RAG som sin datastruktur kan løse noen av disse utfordringene. For å besvare dette spørsmålet ble både en teoretisk studie og forskjellige eksperimenter på ulike kryptovalutaer gjennomført. Den teoretiske studien ble gjennomført for å skaffe data på de forskjellige systemene til bruk i sammenligninger mellom dem. Eksperimentene fokuserte på RAG-systemene, siden disse er mye nyere og har mindre forskning enn systemene basert på en blokkjede. \t\n\nResultatene i denne oppgaven viser at RAG systemer generelt sett har bedre løsninger for skalerbarhet. Oppgaven viser også til flere utfordringer disse RAG baserte systemene har, som for eksempel distribuert tjenestenektangrep og en mangel på insentiver i systemene. Oppgaven peker på demonstrert sikkerhet og lang levetid som de største fordelene blokkjedesystemene har over RAG-systemene. Oppgaven legger vekt på valgene som er gjort når man går fra blokkjede til RAG som datalager i en kryptovaluta. Det konkluderes med at RAG-systemer tilbyr bedre skalerbarhet men de har ikke samme tillit blant brukere som blokkjedesystemene.

Vibhaalakshmi Sivaraman

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.

Hankun Ko

This dissertation is concerned with the zeros of holomorphic Hecke cusp forms in the space of newforms. We estimate a lower bound for the number of zeros on the imaginary axis and on the vertical line R(z)=1/2 in the upper half plane, both of which are outside the unit circle centered at the origin, and we denote these by δ1 and δ2 respectively. Ghosh and Sarnak call those zeros that lie on the rays 'real' including the arc z=exp (iθ), π/3 ≤ θ ≤ π/2, and they showed that a lower bound for the zeros on those geodesic lines is C log k for all sufficiently large weight k for the level 1 case. We extend their results to the newforms with levels N which are positive integers not divisible by 4 on δ2, and N which are positive integers on δ1. On δ2 we have C log k zeros if the weight k is sufficiently large and on δ1 we assume a nonnegativity result on the first negative Hecke eigenvalue and get a conditional result C log k zeros as the weight k goes to infinity. The analysis is closely related to the knowledge of Hecke eigenvalues λf (n). Most importantly it requires Deligne's bound λf (n) n^e (for every e > 0) with which we look into the proof of Theorem 3.1 in Ghosh and Sarnak cite[1], and get the same the approximation theorem for any level in Chapter 2. The estimation of zeros on δ1 also requires a `good' upper bound for the first negative Hecke eigenvalue for which we investigate an upper bound for central values of Hecke L-functions and a nonnegativity result on those values. Those will be studied in Chapters 3 and 4. In Chapter 5 we estimate lower bounds for the number of zeros on δi , i = 1, 2.

Jean‐Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki · 6 authors

No abstract is available for this record.