Blockchain Papers

Yuichi Komano, Takaaki Mizuki

No abstract is available for this record.

Takuro Fukasawa, Yoshifumi Manabe

No abstract is available for this record.

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).

Esra Günsay, Cansu Betin Onur, Murat Cenk

Zero-knowledge protocols (ZKPs) allow a party to prove the validation of secret information to some other party without revealing any information about the secret itself. Appropriate, effective, and efficient use of cryptographic ZKPs contributes to many novel advances in real-world privacy-preserving frameworks. One of the most important type of cryptographic ZKPs is the zero-knowledge range proofs (ZKRPs). Such proofs have wide range of applications such as anonymous credentials, cryptocurrencies, e-cash schemes etc. In many ZKRPs the secret is represented in binary then committed via a suitable commitment scheme. Though there exist different base approaches on bilinear paring-based and RSA-like based constructions, to our knowledge there is no study on investigating the discrete logarithm-based constructions. In this study, we focus on a range proof construction produced by Mao in 1998. This protocol contains a bit commitment scheme with an OR-construction. We investigate the effect of different base approach on Mao's range proof and compare the efficiency of these basis approaches. To this end, we have extended Mao's range proof to base-3 with a modified OR-proof. We derive the number of computations in modulo exponentiations and the cost of the number of integers exchanged between parties. Then, we have generalized these costs for the base-u construction. Here, we mainly show that comparing with other base approaches, the base-3 approach consistently provides approximately 12% efficiency in computation cost and 10% efficiency in communication cost. We implemented the base-3 protocol and demonstrated that the results are consistent with our theoretical computations.

Masoumeh Koochak Shooshtari, Mohammad Reza Aref

Nowadays, Smooth Projective Hash Functions (SPHFs) play an important role in constructing cryptographic tools such as secure Password-based Authenticated Key Exchange (PAKE) protocol in the standard model, oblivious transfer, and zero-knowledge proofs. Specifically, in this article, we focus on constructing PAKE protocol; that is, a kind of key exchange protocol which needs only a low entropy password to produce a cryptographically strong shared session key. In spite of relatively good progress of SPHFs in applications, it seems there has been little effort to build them upon quantum-resistant assumptions such as lattice-based cryptography and code-based cryptography to make them secure against quantum computer attacks. More precisely, there are two proposals based on lattice assumptions that utilize the SPHFs to construct PAKE secured in standard model. Considering quantum-resistant assumptions is less than straightforward and needs some relaxations. In this article, we introduce two new Approximate SPHF (ASPHFs) from error-correcting codes. Upon designing ASPHF, we can construct two efficient PAKE protocols. The security of our protocols could be proved based on the hardness of bounded decoding (BD) problem and learning with parity (LPN) problem in the standard model.

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.

Daiki Miyahara, Hiromichi Haneda, Takaaki Mizuki

No abstract is available for this record.

Raimu Isuzugawa, Daiki Miyahara, Takaaki Mizuki

No abstract is available for this record.

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.

Shuangjie Bai, Geng Yang, Chunming Rong, Guoxiu Liu · 5 authors

No abstract is available for this record.

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.

Tim Boykett

No abstract is available for this record.

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.

Jíntai Ding, Albrecht Petzoldt, Dieter Schmidt

No abstract is available for this record.

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.