Follow blockchain research across journals, conferences, and preprint repositories.
99 results · page 4 of 5
Raimu Isuzugawa, Daiki Miyahara, Takaaki Mizuki, Hideaki Sone
No abstract is available for this record.
Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki
No abstract is available for this record.
Alexander Maletzky
No abstract is available for this record.
Oualid Benamara
We introduce in this paper the algorithmic aspect of elliptic curves together with their applications. We also recall one of the promising application in the field of zero knowledge proofs with concrete implementations.
Edgar González Fernández, Guillermo Morales-Luna, Feliú Sagols
Current requirements for ensuring data exchange over the internet to fight against security breaches have to consider new cryptographic attacks. The most recent advances in cryptanalysis are boosted by quantum computers, which are able to break common cryptographic primitives. This makes evident the need for developing further communication protocols to secure sensitive data. Zero-knowledge proof systems have been around for a while and have been considered for providing authentication and identification services, but it has only been in recent times that its popularity has risen due to novel applications in blockchain technology, Internet of Things, and cloud storage, among others. A new zero-knowledge proof system is presented, which bases its security in two main problems, known to be resistant, up to now, against quantum attacks: the graph isomorphism problem and the isomorphism of polynomials problem.
Nïkhil Gupta, Chandan Saha, Bhargav Thankey
We show an Ω̃(n^2.5) lower bound for general depth four arithmetic circuits computing an explicit n-variate degree-Θ(n) multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey [Amir Shpilka and Amir Yehudayoff, 2010], no super-quadratic lower bound was known for depth four circuits over fields of characteristic ≠ 2 before this work. The previous best lower bound is Ω̃(n^1.5) [Abhijat Sharma, 2017], which is a slight quantitative improvement over the roughly Ω(n^1.33) bound obtained by invoking the super-linear lower bound for constant depth circuits in [Ran Raz, 2010; Victor Shoup and Roman Smolensky, 1997]. Our lower bound proof follows the approach of the almost cubic lower bound for depth three circuits in [Neeraj Kayal et al., 2016] by replacing the shifted partials measure with a suitable variant of the projected shifted partials measure, but it differs from [Neeraj Kayal et al., 2016]’s proof at a crucial step - namely, the way "heavy" product gates are handled. Loosely speaking, a heavy product gate has a relatively high fan-in. Product gates of a depth three circuit compute products of affine forms, and so, it is easy to prune Θ(n) many heavy product gates by projecting the circuit to a low-dimensional affine subspace [Neeraj Kayal et al., 2016; Amir Shpilka and Avi Wigderson, 2001]. However, in a depth four circuit, the second (from the top) layer of product gates compute products of polynomials having arbitrary degree, and hence it was not clear how to prune such heavy product gates from the circuit. We show that heavy product gates can also be eliminated from a depth four circuit by projecting the circuit to a low-dimensional affine subspace, unless the heavy gates together account for Ω̃(n^2.5) size. This part of our argument is inspired by a well-known greedy approximation algorithm for the weighted set-cover problem.
Jíntai Ding
No abstract is available for this record.
Santoshi Pote, Virendra Sule, B. K. Lande
No abstract is available for this record.
Vanesa Daza, Alonso González, Zaira Pindado, Carla Ràfols · 5 authors
No abstract is available for this record.
Ramiro Martínez, Paz Morillo
No abstract is available for this record.
Juliusz Brzeziński
No abstract is available for this record.
Eli Ben‐Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev
The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to deploying such PCP/IOP systems in practice. To advance on this problem we present a new interactive oracle proof of proximity (IOPP) for RS codes; we call it the Fast RS IOPP (FRI) because (i) it resembles the ubiquitous Fast Fourier Transform (FFT) and (ii) the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic (in comparison, FFT arithmetic complexity is quasi-linear but not strictly linear). Prior RS IOPPs and PCPs of proximity (PCPPs) required super-linear proving time even for polynomially large query complexity. For codes of block-length N, the arithmetic complexity of the (interactive) FRI prover is less than 6 * N, while the (interactive) FRI verifier has arithmetic complexity <= 21 * log N, query complexity 2 * log N and constant soundness - words that are delta-far from the code are rejected with probability min{delta * (1-o(1)),delta_0} where delta_0 is a positive constant that depends mainly on the code rate. The particular combination of query complexity and soundness obtained by FRI is better than that of the quasilinear PCPP of [Ben-Sasson and Sudan, SICOMP 2008], even with the tighter soundness analysis of [Ben-Sasson et al., STOC 2013; ECCC 2016]; consequently, FRI is likely to facilitate better concretely efficient zero knowledge proof and argument systems. Previous concretely efficient PCPPs and IOPPs suffered a constant multiplicative factor loss in soundness with each round of "proof composition" and thus used at most O(log log N) rounds. We show that when delta is smaller than the unique decoding radius of the code, FRI suffers only a negligible additive loss in soundness. This observation allows us to increase the number of "proof composition" rounds to Theta(log N) and thereby reduce prover and verifier running time for fixed soundness.
Manoj Kumar
The systematic introduction to zero knowledge proof protocol has important theoretical guidance and practical significance on attracting more scholars involved in research as well as expanding application fields. Zero-knowledge proofs were first conceived in 1985 by Shafi Golwasser, Silvio Micalli and Charles Rackoff in a draft of the knowledge complexity of interactive proof systems. The goal of the present paper is to introduce a new identity based scheme which is a combination of zero-knowledge interactive proof and weil pairing on elliptic curves. The concept of weil pairing was first introduced by Andre Weil in 1940. It plays an important role in the theoretical study of the arithmetic of elliptic curves and Abelian varieties. It has also recently become extremely useful in cryptologic constructions related to these objects.
Anchal Doegar, M. Sivasankar
In this paper we propose a digital signature scheme using a two-layer multivariate polynomial system. This scheme works like a zero-knowledge proof scheme. The algorithm can be implemented in two modes, parallel mode and series mode. As Multivariate Polynomial Cryptography (MPC) is a viable choice in the post quantum era, various algorithms based on MPC are gaining importance. The proposed scheme points to a potential direction for digital signature schemes in the presence of quantum computers.
Martin Orr
Introduction This paper surveys some aspects of the theory of abelian varieties relevant to the Pila–Zannier proof of the Manin–Mumford conjecture and to the André– Oort conjecture. An abelian variety is a complete algebraic variety with a group law. The geometry of abelian varieties is tightly constrained and well-behaved, and they are important tools in algebraic geometry. Abelian varieties defined over number fields pose interesting arithmetic problems, for example concerning their rational points and associated Galois representations. The paper is in three parts: (1) an introduction to abelian varieties; (2) an outline of moduli spaces of principally polarised abelian varieties, which are the fundamental examples of Shimura varieties; (3) a detailed proof of the Ax–Lindemann–Weierstrass theorem for abelian varieties, following amethod using o-minimal geometry due to Pila, Ullmo and Yafaev. The first part assumes only an elementary knowledge of algebraic varieties and complex analytic geometry. The second part makes heavier use of algebraic geometry, but still at the level of varieties, and a little algebraic number theory. Like the first part, the algebraic geometry in the third part is elementary; the third part also assumes familiarity with the concept of semialgebraic sets, and uses cell decomposition for semialgebraic sets and the Pila–Wilkie theorem as black boxes. The second and third parts are independent of each other, so the reader interested primarily in the Ax–Lindemann–Weierstrass theorem may skip the second part (sections 4 to 6). In the first part of the paper (sections 2 and 3), we introduce abelian varieties over fields of characteristic zero, and especially over the complex numbers. The theory of abelian varieties over fields of positive characteristic introduces additional complications which we will not discuss. Our choice of topics is driven by Pila and Zannier's proof of the Manin–Mumford conjecture using o-minimal geometry. We will not discuss the Manin–Mumford conjecture or its proofs directly in this paper; aspects of the proof, and its generalisation to Shimura varieties, are discussed in other papers in this volume.
Reinhold Burger, Albert Heinle
In this paper we present a new primitive for a key exchange protocol based on multivariate non-commutative polynomial rings, analogous to the classic Diffie-Hellman method. Our technique extends the proposed scheme of Boucher et al. from 2010. Their method was broken by Dubois and Kammerer in 2011, who exploited the Euclidean domain structure of the chosen ring. However, our proposal is immune against such attacks, without losing the advantages of non-commutative polynomial rings as outlined by Boucher et al. Moreover, our extension is not restricted to any particular ring, but is designed to allow users to readily choose from a large class of rings when applying the protocol. Our primitive can also be applied to other cryptographic paradigms. In particular, we develop a three-pass protocol, a public key cryptosystem, a digital signature scheme and a zero-knowledge proof protocol.
Charanjit S. Jutla, Arnab Roy
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the parameters defining the language. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptiveNIZKs suffice, and our constructionscan lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the Symmetric eXternal Diffie Hellman (SXDH) assumption our proofs are even competitive with Random-Oracle based Σ-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective
Ketan Mulmuley
It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic varieties, the problem that lies at the heart of the foundational classification problem of algebraic geometry. Specifically: (1) It is shown that in characteristic zero black-box derandomization of PIT for diagonal depth three circuits brings the problem of derandomizing Noether's Normalization Lemma, for the ring of invariants of any explicit linear action of a classical algebraic group of constant dimension, from EXPSPACE (where it is currently) to P. Next it is shown that assuming the Generalized Riemann Hypothesis (GRH), instead of the black-box derandomization hypothesis, brings the problem from EXPSPACE to quasi-PH, instead of P. Thus black-box derandomization of diagonal depth three circuits takes us farther than GRH here on the basis of the current knowledge. Variants of the main implication are also shown assuming, instead of the black-box derandomization hypothesis in characteristic zero, Boolean lower bounds for constant-depth threshold circuits or uniform Boolean conjectures, in conjunction with GRH. These results may explain in a unified way why proving lower bounds or derandomization results for constant-depth arithmetic circuits in characteristic zero or constant-depth Boolean threshold circuits, or proving uniform Boolean conjectures without relativizable proofs has turned out to be so hard, and also why GRH has turned out to be so hard from the complexity-theoretic perspective. Thus this investigation reveals that the foundational problems of Geometry (classification and GRH) and Complexity Theory (lower bounds and derandomization) share a common root difficulty that lies at the junction of these two fields. We refer to it as the GCT chasm. (2) It is shown that black-box derandomization of PIT in a strengthened form implies derandomization of Noether's Normalization Lemma in a strict form for any explicit algebraic variety. (3) Conversely, it is shown that derandomization of Noether's Normalization Lemma in a strict form for specific explicit varieties implies this strengthened form of black box derandomization of PIT and its various variants. (4) A unified geometric complexity theory (GCT) approach to derandomization and classification is formulated on the basis of this equivalence.
Yi Deng, Juan A. Garay, San Ling, Huaxiong Wang · 5 authors
Abstract. In 2001, a breakthrough result by Barak [FOCS 2001] showed how to achieve public-coin zero-knowledge (ZK) arguments in constant rounds, a feature known to be impossible using black-box simulation. In this approach, the simulator makes use of the code of the malicious verifier in computing the prover messages (albeit without understanding it), and does not rewind the malicious verifier—and it is hence called a straight-line simulator. Since then, however, we have witnessed little progress on the basic question whether Barak’s technique can be extended to ZK proof systems. In this paper we make progress on this front, by providing strong evidence that such an extension is far from likely. Specifically, we show that for a natural class of constant-round public-coin ZK proofs (which we call “canonical, ” as all known non-black-box ZK protocols fall in this category), a straight-line simulator based on the known non-black-box technique for such a proof system can actually be used to solve a seemingly unrelated problem, namely, to figure out some non-trivial property of a verifier’s program, and without executing the target code, a problem commonly viewed as notoriously hard. A key tool in our reduction is an improved structure-preserving version of the well-known Babai-Moran Speedup (derandomization) Theorem, which essentially says that, for a constant-round public-coin interactive proof system in which the verifier sends m messages and each of the prover messages is of length p, if the cheating probability for an unbounded prover is ϵ, then there exist (p/O(log 1
Héctor Pastén, Thanases Pheidas, Xavier Vidaux
No abstract is available for this record.
Gennady Lyubeznik
Let k be a field, let R be a ring of polynomials in a finite number of variables over k, let D be the ring of k-linear differential operators of R and let f be a non-zero element of R. It is well-known that R_f, with its natural D-module structure, has finite length in the category of D-modules. We give a characteristic-free proof of this fact. To the best of our knowledge this is the first characteristic-free proof.
Mehdi Vasef
Abstract- This paper introduces a new intractable security problem whose intractability is due to the NP completeness of multivariate quadratic problem. This novel problem uses quaternion algebra in conjunction with MQ. Starting with the simultaneous multivariate equations, we transform these equations into simultaneous quaternion based multivariate quadratic equations. A new scheme for computational zero knowledge proof based on this problem is proposed. It is proved that according to black box definition of zero knowledge proof (ZKP) system, the proposed scheme is ZKP. Our proof has two lemmas. The proof is done through two lemmas. In the first lemma it is shown that expected polynomial time machine *VM halts in a polynomial time. In the second lemma, it is showed that the probability ensembles
Федюкович Вадим Евгеньевич
A new protocol is introduced to show knowledge of a Goppa polynomial and of a codeword, as well as that error is of a bounded weight. The protocol is a special honest verifier zero knowledge proof under assumption of the discrete logarithm problem hardness.
Anna Fabiańska, Alban Quadrat
The purpose of this paper is to give four new applications of the Quillen-Suslin theorem to mathematical systems theory. Using a constructive version of the Quillen-Suslin theorem, also known as Serre's conjecture, we show how to effectively compute flat outputs and injective parametrizations of flat multidimensional linear systems. We prove that a flat multidimensional linear system is algebraically equivalent to the controllable 1-D dimensional linear systems obtained by setting all but one functional operator to zero in the polynomial matrix defining the system. In particular, we show that a flat ordinary differential time-delay linear system is algebraically equivalent to the corresponding ordinary differential system without delay, i.e., the controllable ordinary differential linear system obtained by setting all the delay amplitudes to zero. We also give a constructive proof of a generalization of Serre's conjecture known as Lin-Bose's conjecture. Moreover, we show how to constructively compute (weakly) left-/right-/doubly coprime factorizations of rational transfer matrices over a commutative polynomial ring. The Quillen-Suslin theorem also plays a central part in the so-called decomposition problem of linear functional systems studied in the literature of symbolic computation. In particular, we show how the basis computation of certain free modules, coming from projectors of the endomorphism ring of the module associated with the system, allows us to obtain unimodular matrices which transform the system matrix into an equivalent block-triangular or a block-diagonal form. Finally, we demonstrate the package QuillenSuslin which, to our knowledge, contains the first implementation of the Quillen-Suslin theorem in a computer algebra system as well as the different algorithms developed in the paper.