Blockchain Papers

Kaiqiang Huang, Luis Miralles-Pechuán, Susan Mckeever

No abstract is available for this record.

晓静 徐

正定矩阵是一类特殊的矩阵，作为对称矩阵的子类，在数学分析中判别多元函数极值、判断函数单调性等具有广泛的应用。他不仅具备对称矩阵可对角化的性质，而且具有对称矩阵不具备的更高的性质。但是要想运用正定矩阵的这些性质，我们就要首先会判断一个矩阵是正定矩阵。可以看到的是在一些课本中或辅导教材中给出了很多正定矩阵的证明方法。一般都是求解特征值，然后证明其特征值大于零。但在一些比较复杂的题目中往往掺杂大量的中间结论的证明，学者在思考过程中如果忽略其中的隐含结论的证明，就会导致整个题目都做不出来。因此做这种题目往往需要我们有大量的知识储备。在本文中我们将要一起讨论针对一类特殊正定矩阵的证明方法，并给出了一种简单的证明方法。 Positive definite matrix is a special kind of matrix. As a subclass of symmetric matrix, positive definite matrix has a wide range of applications in mathematical analysis, such as discriminating the extreme value of multivariate functions and judging the monotonicity of functions. It possesses not only the diagonalization property of symmetric matrices, but also the higher property that symmetric matrices do not possess. But in order to use these properties of positive definite matrices, we first have to know that a matrix is positive definite. And you can see that there are a lot of proofs for positive definite matrices that are given in some books or in some tutorial books. You usually solve for the eigenvalues, and then you prove that the eigenvalues are greater than zero. However, in some more complex topics, a large number of proofs of intermediate conclusions are often mixed in. If scholars ignore the proofs of implicit conclusions in the process of thinking, they will fail to complete the whole topic. Therefore, to do this kind of problem often requires us to have a large knowledge reserve. Today we are going to discuss the proof for a special class of matrices, and give a simple proof method.

Thomas Kerber, Aggelos Kiayias, Markulf Kohlweiss

No abstract is available for this record.

John W. Oller

Successful sharing of information-positive (actual) knowledge about facts, skills that are imparted, abilities developed and expressed-is the implicit goal of instruction in all its varied forms. It is the goal of training athletes, dancers, and professionals in every walk of life from early childhood to the most advanced level of education. PART ONE introduces mathematical proofs showing that the interactional successes engineered by instructors, other things being equal, must trend toward 100% shared information-mastery of the course of study. Failed efforts trend toward a complete absence of shared information. All this holds independently for the subject-matter, methods of instruction, and the attributes conducive to instructional success. In Part One, the underlying proofs are united by a very simple proof from the theory of true narratives showing that every iota of knowledge that might be shared in any instructional context depends on the kind of representations found in true reports of actual experience. Empirical studies in Part One confirm the predicted agreement in diverse contexts on the elements of good teaching. In Part Two, Kolmogorov's proofs from 1933 are generalized, amplified, and tested empirically showing successful instruction converging toward 100% agreement on 1) subject-matter, 2) which methods of presentation and assessment work, and even on 3) the abstract criteria for successful instruction. At the same time, as the proofs also show, the cumulative effects of failed communicative efforts must and do trend toward zero shared information.

Karan Sharma, Hemanth Dandu, Arun Kumar, Vinay Kumar · 5 authors

No abstract is available for this record.

Yan V. Fyodorov, Stephen Muirhead

No abstract is available for this record.

Behzad Abdolmaleki, Daniel Slamanig

Recently, motivated by its increased use in real-world applications, there has been a growing interest on the reduction of trust in the generation of the common reference string (CRS) for zero-knowledge (ZK) proofs. This line of research was initiated by the introduction of subversion non-interactive ZK (NIZK) proofs by Bellare et al. (ASIACRYPT’16). Here, the zero-knowledge property needs to hold even in case of a malicious generation of the CRS. Groth et al. (CRYPTO’18) then introduced the notion of updatable zk-SNARKS, later adopted by Lipmaa (SCN’20) to updatable quasi-adaptive NIZK (QA-NIZK) proofs. In contrast to the subversion setting, in the updatable setting one can achieve stronger soundness guarantees at the cost of reintroducing some trust, resulting in a model in between the fully trusted CRS generation and the subversion setting. It is a promising concept, but all previous updatable constructions are ad-hoc and tailored to particular instances of proof systems. Consequently, it is an interesting question whether it is possible to construct updatable ZK primitives in a more modular way from simpler building blocks.

Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer · 7 authors

In the Intersection Non-Emptiness problem, we are given a list of finite automata $A_1,A_2,\dots,A_m$ over a common alphabet $Σ$ as input, and the goal is to determine whether some string $w\in Σ^*$ lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-Emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels zero or one half and already PSPACE-hard when all automata accept a language from the level one. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC$^0$ when restricted to level zero; complete for LOGSPACE or NLOGSPACE, depending on the input representation, when restricted to languages in the level one half; NP-complete when the input is given as DFAs accepting a language in from level one or three half; and finally, PSPACE-complete when the input automata accept languages in level two or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in the Straubing-Thérien hierarchy levels one ore three half does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.

Nir Bitansky, Michael Kellner, Omri Shmueli

No abstract is available for this record.

Christian Badertscher, Daniel Jost, Ueli Maurer

No abstract is available for this record.

SoonHyeong Jeong, Byeongtae Ahn

No abstract is available for this record.

Tapas Pal, Ratna Dutta

No abstract is available for this record.

Veronika Kuchta, Amin Sakzad, Ron Steinfeld, Joseph K. Liu

No abstract is available for this record.

Lior Rotem, Gil Segev

No abstract is available for this record.

Gerald R. Gray

No abstract is available for this record.

Nir Bitansky, Zvika Brakerski

No abstract is available for this record.

M. Mohideen AbdulKader, S. Ganesh Kumar

No abstract is available for this record.

Gabrielle De Micheli, Pierrick Gaudry, Cécile Pierrot

No abstract is available for this record.

Yannan Li, Willy Susilo, Guomin Yang, Tran Viet Xuan Phuong · 6 authors

No abstract is available for this record.

Yunjia Zhang, Jian Wang, Xudong He, Jiqiang Liu

No abstract is available for this record.

Hanwen Feng, Qiang Tang

No abstract is available for this record.

Kyosuke Yamashita, Mehdi Tibouchi, Masayuki Abe

This paper considers the problem of expanding a language class that can be proven by a non-interactive zero-knowledge proof system (NIZK) in a black-box manner in the common reference string model. Namely, given NIZKs for two languages,L0andL1, can we construct an NIZK forL0vL1in a black-box manner? NIZKs for disjunctive languages have a large number of applications, such as electronic voting. Therefore, such a black-box construction may enable the efficient constructions of such applications. However, Abe et al. (PKC 2020) showed that this is impossible if the two given NIZKs are simulation-sound. In this paper, we prove that it is also impossible if the two given NIZKs are constructed by the commit-and-prove methodology that is typically used in many cryptographic protocols, including NIZKs. This result suggests that if we want to augment the capability of NIZKs in terms of the languages they can prove, we should rely on certain properties or structures of the underlying NIZKs, such as algebraic structures.

David Heath, Vladimir Kolesnikov

No abstract is available for this record.

Xianxian Li, Junhao Yang, Shiqi Gao, Zhenkui Shi · 6 authors

No abstract is available for this record.