The term “digital signature” refers to electronic information that is used to identify signatories and indicate that they have signed a document; such information is either attached to or logically combined with a specific electronic document. However, digital signatures entail privacy infringements because it is possible to verify such signatures only when all the data are disclosed to the verifier. Zero-knowledge proofs are considered to be capable of solving this privacy problem. In general, a zero-knowledge proof can be established even if the prover hides the information required in the verification process from the verifier. Zero-knowledge succinct non-interactive argument of knowledge (ZK-SNARK), a prevalent zero-knowledge proof, has been optimized to generate non-interactive and succinct proofs; nevertheless, the generation of proofs is excessively time consuming, making the application of ZK-SNARK impractical in most scenarios. In this paper, we show that existing cryptographic algorithms, such as a one-way hash function or digital signature, can be combined with a zero knowledge proof. Particularly, we propose the multi-argument zero-knowledge argument (MAZKA) algorithm, which can verify data by exposing only the part to be verified and also verify that the part of data has not been manipulated compared to the original. In addition, the proposed algorithm satisfies the adaptive proof of knowledge, perfect zero-knowledze and combinatorial succinctness conditions.
Single- or multi-layer perceptrons, commonly known as neural networks, are universal approximators that can approximate any continuous functions arbitrarily well when the number of perceptrons is allowed to grow indefinitely. When prior knowledge about the target function is available, constraints can be imposed on the neural network to improve approximation accuracy. As an example, it is well known that convolutional neural networks (CNN) \cite{lecun1990handwritten} yield good performance on image classification. And its parameter-sharing scheme can also reduce the risk of overfitting. One of the key properties of image classification is that it is invariant to translation of input image. The translation invariance in CNN is achieved with two steps. On the one hand, the convolutional layer gives a translation equivariance as it is a linear time invariant system. The translation of the input image will be kept as a transformation of the output. On the other hand, the pooling layer will introduce local invariance. The stack of convolutional layers and pooling layers will then reach a receptive field the same size as input and also enforces global invariance. Inspired by the success of CNN on image related tasks, plenty of CNN generalizations \cite{gens2014deep, henaff2015deep, simonovsky2017dynamic, cohen2018spherical,chidester2018rotation} have been studied in other tasks. \emph{Domain invariance}, which refers to the property that the output is invariant to certain transformation of the input features is a crucial property which can help to generalize CNN to other machine learning applications. The works which introduce domain invariance fall into two categories. One of the categories introduces the invariance by injecting invariant constrains. The other category builds the equivariant network layer then achieves invariance by applying the pooling or normalization layer. In the equivariant network layer, the input is transformed by some group transformation the output is transformed correspondingly. As in the CNN example, the invariance can be achieved by first using equivariant layers then apply the pooling layer. In this dissertation, we will focus on the invariance and equivariance of neural networks and analyze the neural network architecture which can achieve invariance or equivariance. The main works can be summarized as following. \noindent\textbf{The Connections Between Convolutional Architecture and Equivariant Property} Convolutional neural networks have achieved great success in speech, image, and video signal processing tasks in recent years. There have been several attempts to justify the convolutional architecture and to generalize the convolution operation for treatment of other data types such as graphs and manifolds. Based on group representation theory and noncommutative harmonic analysis, it has recently been shown that the so-called group equivariance requirement of a feed-forward neural network necessitates the convolutional architectures. In our work, based on the familiar concepts of linear time-invariant systems, we develop an elementary proof of the same result. The nonlinear activation function, being a necessary components of practical deep neural networks, has been glossed over in previous analyses of the connection between equivariance and convolution. We identify sufficient conditions for the non-linear activation functions to preserve equivariance, and hence the necessity of the group convolution structure. Our analysis method is simple and intuitive, and holds the potential to be applied to more challenging scenarios such as non-transitive domains and multiple simultaneous equivariances. \noindent\textbf{Characteristics of Generalized Convolutional Neural Networks} Based on the analysis method above, a theoretical support for details of network architecture design is then provided in our work. We first analyze the necessary and sufficient condition for a neural network to be group equivariant when the group acts on the sub-domain of input/output. This part gives a theoretical support for how should we combine channels in a neural network layer. Meanwhile, it also gives guidelines for designing neural networks with partial equivariance/invariance. To further investigate the characteristics of generalized convolutional neural networks, we then analyze the multiple equivariance case. The result shows the connection between model parameter sharing and equivariant property. In particular, we find that a model will have more parameter sharing if more equivariances are required. Meanwhile, we establish a universality result for shallow and deep generalized group convolutional neural networks as approximators of continuous group-equivariant functions. After choosing the network architecture, one common question we need to answer is that how many neurons do we want in our hidden layer? We show that the generalized convolution mapping to a quotient space is a projection of the image of a generalized convolution which maps to the maximum quotient space. This can be used to obtain guidelines for choosing the feature size of hidden layer. \noindent\textbf{Neural Networks with Invariant Properties} In the traditional convolutional neural networks, the spatial invariant properties are introduced by adding a global pooling layer after the convolutional layers. For some specific applications, there are still some potential for us to further reduce the model complexity by introduce invariant property in earlier layers. An partial permutation invariant model for learning graph node embedding is introduced based on the classical invariant theory. In the image processing application, an affine equivariant preprocessing method is proposed to build neural networks invariant to affine transformation. \noindent\textbf{Partially Permutation Invariant Graph Node Embedding Model} Graph node embedding aims at learning a vector representation for all nodes given a graph. It is a central problem in many machine learning tasks (e.g., node classification, recommendation, community detection). The key problem in graph node embedding lies in how to define the dependence to neighbors. Existing approaches specify (either explicitly or implicitly) certain dependencies on neighbors, which may lead to loss of subtle but important structural information within the graph and other dependencies among neighbors. This intrigues us to ask the question: can we design a model to give the maximal flexibility of dependencies to each node's neighborhood. In our recent work, we propose a novel graph node embedding method (named \textbf{\OM}) via a novel notion of \textit{partial permutation invariant set function}, to capture any possible dependence. The partial permutation invariant set function is designed based on the set of \textit{invariant basis} with respect to permutation group. Our method 1) can learn an \textit{arbitrary} form of the representation function from the neighborhood, without losing any potential dependence structures, and 2) is applicable to both homogeneous and heterogeneous graph embedding, the latter of which is challenged by the diversity of node types. Furthermore, we provide theoretical guarantee for the representation capability of our method for general homogeneous and heterogeneous graphs. Empirical evaluation results on benchmark data sets show that our proposed {\OM} method outperforms the state-of-the-art approaches on producing node vectors for various learning tasks of both homogeneous and heterogeneous graphs. \noindent\textbf{Learning Models Invariant to Affine Transformations for Image Processing} The way designing invariant/partial invariant neural networks with invariant basis is difficult to extend to groups other than permutation group. Because the invariant basis is expensive to calculate. Even if we get the set of invariant basis, it will be very large and is not helpful to reduce model complexity. An alternative which can introduce invariant property to neural network is adding an equivariant transformer as a pre-processing layer. This equivariant transformer will revert all the affine transformations happens in the input. Thus the model will be invariant to affine transformations. Invariance to affine transformations is desirable property for many computer vision tasks like image classification and motion tracking. Enforcing and taking advantage of such affine invariance property is an essential part for building efficient models for machine learning. However, it has been challenging to build models that are provably affine invariant. Previous works have achieved partial invariance, such as invariance to shifting and to rotation. We propose to build an affine-invariant model in two steps. First, we apply image normalization, which renders the density function represented by the image to have zero mean and identity covariance matrix. The resulting normalized image is then processed by a second stage neural network that is either an equivariant transformer network (ETN) or group convolution networks. We provide proof of invariance and demonstrate the performance improvement of such neural networks in processing images that have been affine transformed.
In this thesis we are interested in solving a class of quasilinear parabolic partial differential equations (PDEs) for closed differential forms which exhibit a special structure, namely a gradient flow structure, and thus bringing together two major areas of mathematical analysis, the geometric theory of differential forms and the theory of gradient flows. More precisely, for a bounded domain $ \Omega \subset \mathbb{R}^n $, $ n \ge 2 $, with smooth boundary and a time-dependent differential $ k $-form $ \omega (t) \colon \Omega \rightarrow \Lambda ^k ( \mathbb{R}^n ) $ we consider the gradient flow equation $\partial _t \omega \,=\, -\mathop{}\!\mathrm{d} \Big( \nabla c^ \ast \Big[ \mathop{}\!\mathrm{d}^{\ast} \big( \nabla _ \xi F( \, \cdot \, , \omega )\big) \Big] \Big) $ und $ \mathop{}\!\mathrm{d} \omega \,=\, 0 $. Here, $ c \colon \Lambda ^ {k-1}( \mathbb{R}^n ) \rightarrow [0, \infty )$, called the dissipation potential, is a convex function with Legendre-Fenchel dual $ c^ \ast $, whereas $ \nabla _ \xi F $ denotes the derivative of the energy density $ F \colon \Omega \times \Lambda ^k( \mathbb{R}^n ) \rightarrow \mathbb{R} $ with respect to its second argument. This class of PDEs was suggested by Yann Brenier in 2014 as a general framework for dissipative equations and contains for example the $ p $-Hodge Laplace heat equation for closed differential forms $ \partial _t \omega = - \mathop{}\!\mathrm{d} ( | \mathop{}\!\mathrm{d}^{\ast} \omega | ^ {p-2} \, \mathop{}\!\mathrm{d}^{\ast} \omega ) $. The problem of finding weak solutions of the gradient flow equation is challenging not only because of its nonlinearity, but also because of its vectorial character, i.e. it is a system of scalar PDEs. The gradient flow structure appears in the form of a so-called Energy Dissipation Inequality (EDI). Although the latter is equivalent to the gradient flow equation only on a formal level, it nevertheless plays an essential role in establishing the proof of the existence of weak solutions for the PDE. In order the prove the existence of solutions of the corresponding EDI, we use a so-called minimizing movement scheme. This is a time-discrete approximation scheme in which each time-step consists of solving a variational problem. The variational problem involves the perturbation of the energy functional with the so-called dissipation functional which is defined using the dissipation potential $ c $. This dissipation functional is closely related to the norms of the duals of homogeneous Sobolev spaces for differential forms, i.e. negative homogeneous Sobolev spaces, which are introduced here. Hence, these spaces define the natural functional analytic setting for the problems addressed in this thesis. To the best of our knowledge, this concept of negative homogeneous Sobolev spaces for differential forms is new. In the limit where the time discretization parameter, used to define the perturbed energy functional, tends to zero the approximation scheme weakly converges to some limit. Since the EDI has well-suited lower semicontinuity properties with respect to the weak convergence, the limit is indeed a solution of the EDI. The limiting process also benefits from compensated compactness methods such as the Sobolev-Poincaré inequality in combination with a Minty-Browder-type argument. With some extra effort we can also prove a reversed EDI for the limit. As the main result of this thesis we conclude from this the existence of a weak solution of the gradient flow equation. In the second part of the thesis we ask for additional properties of the weak solutions of the gradient flow equation such as uniqueness, a semigroup property of the time evolution, an exponential formula as well as error estimates. These problems are very difficult to solve. Because the concept of the EDI is too weak for these questions, we invoke the stronger concept of the Evolution Variational Inequality (EVI). The latter is formally equivalent to the gradient flow equation as well. However, it is only available in the case $ c( \xi ) = \frac{1}{2}| \xi | ^2 $ in which the dissipation functional becomes, up to a scalar multiple, the negative homogeneous Sobolev norm for the case of Hilbert spaces. As the main results for the second part we prove uniqueness of the limit found before in a class of admissible solutions of the EVI, a contraction property and a semigroup property of the time evolution as well as an exponential formula together with an error estimate. The proof of the exponential formula and the error estimate is given by using two different approaches.
随着电子商务技术的不断发展与应用，物资的利用率却并未随之相应提高，因此带来的是大量价值的浪费与闲置。根据创建节约型社会的需要，如何有效提高物资的回收与流转尤为重要。而在传统的电子商务技术的物资回收流转中，如何解决因信息不对称带来的信任缺失问题非常困难。本文研究在小型区域的物资回收流转过程中如何通过区块链技术提高物资流转的多方信任程度从而提高物资回收流转概率和减少价值浪费，创新地使用零知识证明技术保证价值流转过程中地隐私。并且，本文在典型的小型特征区域进行基于区块链技术的高可信度物资回收流转系统的设计、实现与应用。结果表明，区块链技术在小型区域价值流转系统中构建了新的基于算法的信任机制体系，减少信息不对称带来的信任缺失问题，有效提高价值流转效率。 With the continuous development and application of e-commerce technology, the utilization rate of materials has not been correspondingly increased, so a large amount of value is wasted and idle. According to the needs of creating a conservation-minded society, how to effectively improve the recycling and circulation of materials is particularly important. However, in the material recycling and circulation of traditional e-commerce technology, it is very difficult to solve the problem of lack of trust caused by information asymmetry. This paper studies how to use blockchain technology to improve the multi-party trust of material circulation in the process of material recovery and circulation in small areas, thereby increasing the probability of material recovery and circulation and reducing value waste, innovatively use zero-knowledge proof technology to ensure wealth in the process of value transfer. In addition, this article designs, implements and applies a high-relia- bility material recovery and circulation system based on blockchain technology in a typical small characteristic area. The results show that blockchain technology builds a new algorithm-based trust mechanism system in a small regional value transfer system, reduces the lack of trust caused by information asymmetry, and effectively improves the efficiency of value transfer.
Public blockchains have reached high popularity among technically inclined people, laypersons and researchers alike. Similarly, privacy has gained much attention in the same circles. This attention and high sensitivity of information transmitted in blockchains, lead more and more blockchain-based systems, especially cryptocurrencies, to provide privacy for their users. Popular approaches include ring signatures or zero-knowledge proofs to achieve unlinkable payments within the blockchain. However, these systems solely examine privacy by considering the blockchain and its embedded transactions. The underlying peer-to-peer network of a public blockchain is rarely considered. This leaves the dissemination of transactions open for privacy attacks, as the IP address of the originator of a transaction can be mapped to their real-world identity. In this thesis, we look into the important privacy aspects of broadcasting blockchain transactions. We collect and analyse data of a large blockchain network and construct a privacy-preserving latency estimator. Building on the insights gained from the analysis, we combine dining-cryptographers networks with a secret sharing technique and layer a flood-and-prune broadcast on top, to provide enforced k-anonymity to network participants. To increase the flexibility of this approach, we extend two established privacy protocols. First, we extend a dining-cryptographers based group messaging protocol to transmit arbitrary length messages. Further, we optimize the protocol for common cases, to improve its performance for various environments, especially blockchain transaction dissemination. As a performant intermediate privacy layer, we transform adaptive diffusion from a contact graph protocol to a computer network protocol. We achieve this by changing the underlying network assumptions and the attacker model. We derive optimal forwarding probabilities based on a statistical network model of unstructured peer-to-peer networks. These two sub-protocols are combined in an intertwined layering approach to create 3P3, a flexible privacy-preserving broadcast protocol. Lastly, to manage the groups required for 3P3 and other proposed and common protocols, we propose Pixy. Pixy is a privacy increasing group creation scheme, allowing for filtering and testing of group participants to establish trust. The system allows for smaller group sizes while maintaining privacy guarantees of previous systems, or better privacy for same-sized groups. The software, concepts, data and models in this thesis help researchers and developers of privacy preserving network protocols. Developers can use 3P3, tuning its parameters to the needs of their network. Researchers can build on the data, concepts and models to create novel schemes and generalizations of our insights. This improves privacy for all users of modern and future networks.
Cellular networks connect nearly every human on the planet; they consequently have visibility into location data and voice, SMS, and data contacts and communications. Such near-universal visibility represents a significant threat to the privacy of mobile subscribers. In 5G networks, end-user mobile device manufacturers assign a Permanent Equipment Identifier (PEI) to every new device. Mobile operators legitimately use the PEI to blocklist stolen devices from the network to discourage device theft, but the static PEI also provides a mechanism to uniquely identify and track subscribers. Advertisers and data brokers have also historically abused the PEI for data fusion of location and analytics data, including private data sold by cellular providers. In this paper, we present a protocol that allows mobile devices to prove that they are not in the blocklist without revealing their PEI to any entity on the network. Thus, we maintain the primary purpose of the PEI while preventing potential privacy violations. We describe a provably-secure anonymous proof of blocklist non-membership for cellular network, based on the RSA accumulators and zero-knowledge proofs introduced by Camenisch and Lysyanskaya (Crypto'02) and expanded upon by Li, Li and Xue (ACNS'07). We show experimentally that this approach is viable for cellular networks: a phone can create a blocklist non-membership proof in only 3432 milliseconds of online computation, and the network can verify the proof in less than one second on average. In total this adds fewer than 4.5 seconds to the rare network attach process. This work shows that PEIs can be attested anonymously in 5G and future network generations, and it paves the way for additional advances toward a cellular network with guaranteed privacy.
In order to overcome the disadvantages of poor security and lack of trust in the traditional electronic voting system and improve the reliability of the election system, this paper proposes an electronic voting system based on blockchain. This system is divided into voting module and blockchain management module, which mainly aims at the credibility of voting data and the protection of voters' privacy. The voting module begins with the verification of voter's identity, uses Zero Knowledge Proof algorithm to prove that the entrant is the legitimate owner of part of the rights and interests, uses ECDSA to encrypt the data, and uses Digital Signature to verify the security and integrity of the data. The main purpose of the blockchain management module is to update the data in real time, make the newly added nodes complete data synchronization, check the consistency of the data, and provide the user with historical records.
Igor A. Kalmykov, Ivan Dmitrievich Efremenkov, Dmitry Vladimirovich Yurdanov, М. И. Калмыков · 6 authors
At the present stage of development, in order to ensure the fulfillment of various kinds of tasks of national importance, systems based on groups of low-orbit communication spacecraft are increasingly being used. An example of such satellite systems is the Gonets Satellite System JSC, which provides mobile satellite channels for mobile and stationary subscribers anywhere in the world and is being developed by order of the Roskosmos state corporation for comic activities. Therefore, in view of the importance and in some cases the confidentiality of the tasks performed, the requirements for stealth and noise immunity for these systems are increasing. Increasing secrecy, namely, its information component, is possible through the use of an authentication protocol based on evidence with zero knowledge disclosure, which operates on the basis of modular codes. However, the modular codes in some systems are also used to combat equipment failures and malfunctions, and when introducing more redundancy, they are also able to localize errors caused by interference in the communication channel. Thus, using modular codes to ensure stealth, to combat failures and malfunctions, as well as to provide noise immunity, it will allow you to switch to a single mathematical apparatus for constructing the system and thereby move away from the traditionally used cascade codes. Therefore, the task of developing a new method for constructing a modular composite code to ensure noise immunity is relevant.
It has become a truism that the speed of technological progress leaves law and policy scrambling to keep up. But in addition to creating new challenges, technological advances also enable new improvements to issues at the intersection of law and technology. In this thesis, I develop new cryptographic tools for informing and improving our law and policy, including specific technical innovations and analysis of the limits of possible interventions. First, I present a cryptographic analysis of a legal question concerning the limits of the Fifth Amendment: can courts legally compel people to decrypt their devices? Our cryptographic analysis is useful not only for answering this specific question about encrypted devices, but also for analyzing questions about the wider legal doctrine. The second part of this thesis turns to algorithmic fairness. With the rise of automated decision-making, greater attention has been paid to statistical notions of fairness and equity. In this part of the work, I demonstrate technical limits of those notions and examine a relaxation of those notions; these analyses should inform legal or policy interventions. Finally, the third section of this thesis describes several methods for improving zero-knowledge proofs of knowledge, which allow a prover to convince a verifier of some property without revealing anything beyond the fact of the prover's knowledge. The methods in this work yield a concrete proof size reduction of two plausibly post-quantum styles of proof with transparent setup that can be made non-interactive via the Fiat-Shamir transform: "MPC-in-the-head," which is a linear-size proof that is fast, low-memory, and has few assumptions, and "Ligero," a sublinear-size proof achieving a balance between proof size and prover runtime. We will describe areas where zero-knowledge proofs in general can provide new, currently-untapped functionalities for resolving legal disputes, proving adherence to a policy, executing contracts, and enabling the sale of information without giving it away.
Open access
Cryptography and Data Security
Digital and Cyber Forensics
Physical Unclonable Functions (PUFs) and Hardware Security