Search

Learning automata (LA) with artificially absorbing barriers was a completely new horizon of research in the 1980s (Oommen, 1986). These new machines yielded properties that were previously unknown. More recently, absorbing barriers have been introduced in continuous estimator algorithms so that the proofs could follow a martingale property, as opposed to monotonicity (Zhang et al., 2014), (Zhang et al., 2015). However, the applications of LA with artificial barriers are almost nonexistent. In that regard, this article is pioneering in that it provides effective and accurate solutions to an extremely complex application domain, namely that of solving two-person zero-sum stochastic games that are provided with incomplete information. LA have been previously used (Sastry et al., 1994) to design algorithms capable of converging to the game's Nash equilibrium under limited information. Those algorithms have focused on the case where the saddle point of the game exists in a pure strategy. However, the majority of the LA algorithms used for games are absorbing in the probability simplex space, and thus, they converge to an exclusive choice of a single action. These LA are thus unable to converge to other mixed Nash equilibria when the game possesses no saddle point for a pure strategy. The pioneering contribution of this article is that we propose an LA solution that is able to converge to an optimal mixed Nash equilibrium even though there may be no saddle point when a pure strategy is invoked. The scheme, being of the linear reward-inaction ( $L_{R-I}$ ) paradigm, is in and of itself, absorbing. However, by incorporating artificial barriers, we prevent it from being ``stuck'' or getting absorbed in pure strategies. Unlike the linear reward-εpenalty ( $L_{R-ε P}$ ) scheme proposed by Lakshmivarahan and Narendra almost four decades ago, our new scheme achieves the same goal with much less parameter tuning and in a more elegant manner. This article includes the nontrial proofs of the theoretical results characterizing our scheme and also contains experimental verification that confirms our theoretical findings.

Healthcare blockchains provide an innovative way to store healthcare information, execute healthcare transactions, and build trust for healthcare data sharing and data integration in a decentralized open healthcare network environment. Although the healthcare blockchain technology has attracted broad interests and attention in industry, government and academia, the security and privacy concerns remain the focus of debate when deploying blockchains for information sharing in the healthcare sector from business operation to research collaboration. This paper focuses on the security and privacy requirements for medical data sharing using blockchain, and provides a comprehensive analysis of the security and privacy risks and requirements, accompanied by technical solution techniques and strategies. First, we discuss the security and privacy requirements and attributes required for electronic medical data sharing by deploying the healthcare blockchain. Second, we categorize existing efforts into three reference blockchain usage scenarios for electronic medical data sharing, and discuss the technologies for implementing these security and privacy properties in the three categories of usage scenarios for healthcare blockchain, such as anonymous signatures, attribute-based encryption, zero-knowledge proofs, verification techniques for smart contract security. Finally, we discuss other potential blockchain application scenarios in healthcare sector. We conjecture that this survey will help healthcare professionals, decision makers, and healthcare service developers to gain technical and intuitive insights into the security and privacy of healthcare blockchains in terms of concepts, risks, requirements, development and deployment technologies and systems.

Recent experiments reveal that 6- to 12-month-old infants can learn probabilities and reason with them. In this work, we present a novel computational system called Neural Probability Learner and Sampler (NPLS) that learns and reasons with probabilities, providing a computationally sufficient mechanism to explain infant probabilistic learning and inference. In 24 computer simulations, NPLS simulations show how probability distributions can emerge naturally from neural-network learning of event sequences, providing a novel explanation of infant probabilistic learning and reasoning. Three mathematical proofs show how and why NPLS simulates the infant results so accurately. The results are situated in relation to seven other active research lines. This work provides an effective way to integrate Bayesian and neural-network approaches to cognition., To be published in Psychological Review

Despite of its tremendous popularity and success in computer vision (CV) and natural language processing, deep learning is inherently vulnerable to adversarial attacks. Many defense solutions in CV have been proposed. However, most of them, e.g., adversarial training, suffer from a low generality due to the reliance on limited adversarial examples. Moreover, some solutions even have non-negligible negative impact on the clean example classification. Last but not least, they are impotent against the unconstrained attacks. In this paper, we propose GRIP-GAN to learn a general robust inverse perturbation (GRIP), which is not only able to offset any potential adversarial perturbations but also strengthen the target class-related features, purely from the clean images via a generative adversarial network (GAN). By feeding a random noise, GRIP-GAN is able to generate a dynamic GRIP for each input image to defend against the unconstrained attacks. To further improve the defense performance, we also enable GRIP-GAN to generate a GRIP tailored to each input image. Extensive experiments are carried out on MNIST, CIFAR10, and ImageNet datasets against 17 adversarial attacks. The results show that GRIP-GAN outperforms all the baselines. We further share insights on the success of GRIP-GAN and provide visualized proofs.

Nonlinear and nonconvex optimization problems are vital and fundamental problems in science and engineering fields. In this article, a novel finite-time circadian rhythms learning network (called FT-CRLN) is proposed for solving nonlinear and nonconvex optimization problems with periodic noises. Different from the traditional recurrent neural networks, the proposed FT-CRLN can suppress the periodic noise notably and achieve excellent convergence performance in solving nonlinear and nonconvex problems. The theoretical analysis and rigorous mathematical proof verify the superior convergence, high accuracy, and strong robustness of the proposed FT-CRLN. The simulation results demonstrate the effectiveness and robustness of the proposed FT-CRLN in solving nonlinear and nonconvex problems compared with other state-of-art neural networks.

Weather-related or other types of faults can negatively impact the continuity of electricity delivery to consumers and, lead to poorer reliability scores. 90% of customer outage-minutes are due to events which affect local distribution systems. The radial configuration is simple and has a low cost design; however, when faults occur, it often causes power outages beyond the location of the fault itself. It is beneficial for utilities to automatically isolate the fault and, thus, restore power to as many consumers as possible. The benefits of fault isolation and service restoration include: enhanced reliability and resiliency, reduced loss of revenue to the utility, and enhanced comfort and satisfaction for the utilitys consumers. This paper provides an algorithm to quickly isolate a fault and automatically restore power to as many nodes of the distribution system as possible by opening and closing switches already placed within the system. The expert model and centralized algorithm that are proposed in this paper guarantee an optimal solution and a short run-time regardless of the size of the distribution system. A mathematical proof of the optimal nature of the solution is provided. Also, the model is validated in practice, solving two different-sized systems.

Matrix calculations are often required for the analysis of any big-data cloud computing system. It is quite common to process big-data associated matrices possessing the sparsity and low-rank properties. In order to efficiently deal with big-data matrices, we propose a new divide-and-iterate framework, which can be invoked to solve an enormously large linear system of equations by taking advantage of factored matrices. The Kaczmarz algorithm (KA) is utilized here to design the parallel iterative algorithms which are capable of solving a large system of equations by iteratively updating the solution through the reduction into the factorized subsystems in parallel. The convergences of our proposed new iterative algorithms are justified by the rigorous proofs. Besides, the time- and memory-complexities are studied to demonstrate the resource efficiency of the proposed algorithms. Numerical experiments are also presented to illustrate the effectiveness of this proposed new framework.

In this paper, cooperative robotic manipulators under uncertain base coordinate are investigated. The coordinate uncertainties result in biases of cooperative robotic dynamics, which involve horizontal and vertical translational errors in the task space and rotational errors in the joint space. To the best of our knowledge, uncertainties in the base coordinate system of cooperative robotic manipulators have drawn little attention in existing literature. To solve this problem, this paper presents an adaptive robust controller for the synchronized control of two cooperative robotic manipulators. An adaptive neural network associated with base coordinate parameter adaption law is proposed to estimate the cooperative system parameters given unknown system dynamics and base coordinate uncertainties. A synchronization-factor-based robust slide mode controller is then derived to stabilize the target position and internal force between the cooperative manipulators. Mathematical proof and numerical experiments under various conditions are conducted. The results demonstrate the satisfactory and effective convergences of both the cooperative robotic trajectory and internal force despite of uncertainties in the base coordinate system.

We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point round-off errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal’s conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result, we are able to provide the first machine-assisted proof that Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less.

Comunicació presentada al AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, celebrat del 20 al 22 de juliol de 2021 al Caire, Egipte. This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size O(n+d) bilinear group elements, where d is the depth and n is the input size of the circuit. Our technical contribution is to add unbounded simulation soundness to a recent NIZK of González and Ràfols (ASIACRYPT’19) with very small overhead. Our new scheme can be used to construct the most efficient Signature-of-Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives. Karim Baghery was supported by CyberSecurity Research Flanders with reference number VR20192203.

International audience; In this paper we enhance the EasyCrypt proof assistant to reason about computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs-we also provide full semantics for the EasyCrypt module system, which was previously lacking. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class, and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and we present a new formalization of Universal Composability (UC).

This chapter defines vectors and describes their algebraic and geometric properties. It also introduces another fundamental object—matrix—whose basic properties parallel those of the vector and discusses the examination of techniques that are useful for reading and writing proofs. The link between algebraic manipulation and geometric intuition is a recurring theme in linear algebra that is used to establish many important results. The study of linear algebra begins with vectors and matrices—two of the most practical concepts in mathematics. Linear algebra, in addition to having a multitude of practical applications in science and engineering, also can be used to introduce proof-writing skills. The concept of proof is central to higher mathematics. Mathematicians claim no statement as a “fact” until it is proven true using logical deduction. Therefore, no one can succeed in higher mathematics without mastering the techniques required to supply such a proof.

The origins of proof-theoretic semantics lie in the question of what constitutes the meaning of the logical connectives and its response: the rules of inference that govern the use of the connective. However, what if we go a step further and ask about the meaning of a proof as a whole? In this paper we address this question and lay out a framework to distinguish sense and denotation of proofs. Two questions are central here. First of all, if we have two (syntactically) different derivations, does this always lead to a difference, firstly, in sense, and secondly, in denotation? The other question is about the relation between different kinds of proof systems (here: natural deduction vs. sequent calculi) with respect to this distinction. Do the different forms of representing a proof necessarily correspond to a difference in how the inferential steps are given? In our framework it will be possible to identify denotation as well as sense of proofs not only within one proof system but also between different kinds of proof systems. Thus, we give an account to distinguish a mere syntactic divergence from a divergence in meaning and a divergence in meaning from a divergence of proof objects analogous to Frege's distinction for singular terms and sentences., Comment: Post-peer-review, pre-copyedit version of article, published version available open access under DOI: 10.1007/s10992-020-09577-2

Consortium blockchain has been widely used in different scenarios, where blockchain members demand that their uploaded data could be audited based on data range under their identities without exposing the data themselves. However, so far, current solutions only support simple (e.g., standard-range) privacy-preserving data auditing, and can not be used in multi-party scenarios. To address the problem, we propose zkrpChain, which focuses on protection of the integrity and privacy of the data uploaded by blockchain members while leaving their identities public. In zkrpChain, which is based on Hyperledger Fabric and Bulletproofs, both standard-range and arbitrary-range zero-knowledge range proofs generation and verification are supported. To improve the efficiency, the aggregation of multiple proofs and batch verification are developed. Furthermore, to broaden the application scenarios, we also develop multi-party proofs generation and verification. To support further development, we provide chaincodes, related APIs together with the client codes. Finally, we conduct experiments to evaluate the performance of zkrpChain, and the results show that as the total data size grows exponentially, the proof and verification time only grow linearly while the total on-chain storage grows logarithmically.

Proof Blocks is a novel software tool which enables students to write mathematical proofs by dragging and dropping prewritten lines into the correct order, rather than writing a proof completely from scratch. We used Proof Blocks problems as exam questions for a discrete mathematics course with hundreds of students, allowing us to collect thousands of student responses to Proof Blocks problems. Using this data, we provide statistical evidence that Proof Blocks are easier than written proofs, which are typically very difficult. We also show that Proof Blocks problems provide about as much information about student knowledge as written proofs. Survey results show that students believe that the Proof Blocks user interface is easy to use, and that the questions accurately represent their ability to write proofs.

Of concern is the dynamics of anti-periodic solutions on Clifford-valued high-order Hopfield neural networks (CVHOHNNs) with multi-proportional delays. By utilizing differential inequality techniques, Lyapunov method and a rigorous mathematical proof, we establish some sufficient criteria on the existence and global stability of anti-periodic solutions. Finally, a numerical example is offered to verify and extend the analytical results and visualize the interesting phenomenon.

Password-based authenticated key exchange (PAKE) protocol allows protocol participants to establish a high entropy session key by pre-sharing a low-entropy password. Katz and Vaikuntanathan (ASIACRYPT'09) used a one-round smooth projective hash function (SPHF) over lattices to design a three-round PAKE protocol. Zhang and Yu (AISACRYPT'17) improved Katz-Vaikuntanatha's scheme by proposing a two-round PAKE with NIZK proofs, but how to construct a lattice-based simulation-sound NIZK remains an open research question. Benhamouda et al. followed the framework of Katz and Vaikuntananthan (TCC'11) and proposed a one-round PAKE via trapdoor-SPHF, but their scheme was based on conventional DDH assumption. In other words, how to design a one-round PAKE via an efficient lattice-based SPHF still remains a challenge. In this paper, we attempt to fill this gap by first proposing a new IND-CCA-secure lattice-based SPHF based on the work of Benhamouda et al. (PKC'18), and then using the proposed SPHF to construct a one-round PAKE protocol. We then prove the security of the proposed protocol. We also explore the possibilities of constructing two-round PAKE, three-round PAKE and universal composable security from our SPHF, and show the potential application of our PAKE in the Internet of Things where communication cost is the main consideration.

This letter introduces a novel approach that combines the use of exponential barrier functions and satisfiability modulo theories solving to the formal safety analysis of flight controllers. Specifically, exponential barrier functions are used to construct candidate invariant regions and proofs of invariance are constructed using satisfiability modulo theories solving. This approach is demonstrated by analyzing safety properties related to command tracking and operation in cases of rotor failures on an octorotor platform.

This article proposes a risk assessment method based on interval intuitionistic integrated cloud Petri net (IIICPN). The cloud model is widely used in data mining and knowledge discovery, especially in risk assessment problems with linguistic variables. However, the cloud models proposed in the literature do not express interval-valued intuitionistic linguistic satisfactorily, and the reasoning methods based on the cloud models cannot perform risk assessment well. The work in this article includes the definition of IIIC and IIICPN, the method of converting the interval-valued intuitionistic uncertain linguistic numbers into IIIC, and the reasoning method of IIICPN. As proofs, a subway fire accident model is adopted to confirm the feasibility of the proposed method, and comparison experiments between the IIICPN with general fuzzy Petri net and the trapezium cloud model are conducted to verify the superiority of the proposed model.

In this paper, we propose a Sybil attack detection scheme using proofs of work and location in VANETS. Each roadside unit issues signed time-stamped tag as a proof for the vehicle's anonymous location. Proofs sent from multiple consecutive RSUs are used to create a trajectory to be used as vehicle anonymous identity. Also, contributions from one RSU are not enough to create trajectories, rather contributions of several RSUs are needed. By this way, attackers need to compromise an infeasible number of RSUs to create fake trajectories. Moreover, upon receiving a proof of location from an RSU, the vehicle should solve a computational puzzle by running proof of work (PoW) algorithm. Then, it should provide a valid solution (proof of work) to the next RSU before it can obtain a proof of location. Using PoW can prevent vehicles from creating multiple trajectories in case of low-dense RSUs. Then, an event manager uses a matching technique to identify trajectories sent from Sybil vehicles. The scheme depends on the fact that Sybil trajectories are bounded physically to one vehicle, and therefore, their trajectories overlap. Extensive experiments demonstrate that our scheme achieves high detection rate of Sybil attacks and acceptable communication and computation overhead.

Model management is a central activity in Software Engineering. The most challenging aspect of model management is to keep inter-related models consistent with each other while they evolve. As a consequence, there is a lot of scientific activity in this area, which has produced an extensive body of knowledge, methods, results and tools. The majority of these approaches, however, are limited to binary inter-model relations; i.e. the synchronisation of exactly two models. Yet, not every multi-ary relation can be factored into a family of binary relations. In this paper, we propose and investigate a novel comprehensive system construction, which is able to represent multi-ary relations among multiple models in an integrated manner and thus serves as a formal foundation for artefacts used in consistency management activities involving multiple models. The construction is based on the definition of partial commonalities among a set of models using the same language, which is used to denote the (local) models. The main theoretical results of this paper are proofs of the facts that comprehensive systems are an admissible environment for (i) applying formal means of consistency verification (diagrammatic predicate framework), (ii) performing algebraic graph transformation (weak adhesive HLR category), and (iii) that they generalise the underlying setting of graph diagrams and triple graph grammars.

The article analyzes the role of the concept of understanding in mathematical proof. Understanding seems to be a natural and necessary characteristic of proof, interpreted as an argument in favor of the established result. It is shown that in general two traditions in the treatment of mathematical proofs can be distinguished, going back to Descartes and Leibniz. It arguments for conceptual treatment of category of understanding which is not connected with individual mental acts are resulted. The prospect of achieving conceptual understanding in the computational interpretation of mathematical proof is problematized.

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

Several formal systems, such as resolution and minimal model semantics, provide a framework for logic programming. In this paper, we will survey the use of structural proof theory as an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logic programming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logic programming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logic programming languages. Logic programming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logic programming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking., To appear in Theory and Practice of Logic Programming (TPLP)

Fuzzy extractor can be used to convert the reading of a noisy non-uniform source into a reliably reproducible and almost uniform string, while reusable fuzzy extractor allows multiple extractions of the same source. In this paper, we propose multi-party fuzzy extractor, called threshold reusable fuzzy extractor, whose execution requires a threshold number of members. New definition and efficient construction are given with security proofs and experimental implementations. It preserves the inherent properties of fuzzy extractor with expanded use in multi-party scenarios. Based on the proposed threshold reusable fuzzy extractor, an application in privacy protection is given to store and share sensitive data by smart contract on blockchain , achieving joint access control via biometric information.

This article documents differences between novice and experienced undergraduate students’ processes of reading mathematical proofs as revealed by moment-by-moment, think-aloud protocols. We found three key reading behaviors that describe how novices’ reading differed from that of their experienced peers: alternative task models, accrual of premises, and warranting. Alternative task models refer to the types of goals that students set up for their reading of the text, which may differ from identifying and justifying inferences. Accrual of premises refers to the way novice readers did not distinguish propositions in the theorem statement as assumptions or conclusions and thus did not use them differently for interpreting the proof. Finally, we observed variation in the type and quality of warrants, which we categorized as illustrate with examples, construct a miniproof, or state the warrant in general form.

Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

We investigate the proof complexity of modal resolution systems developed by Nalon and Dixon (J Algorithms 62(3–4):117–134, 2007) and Nalon et al. (in: Automated reasoning with analytic Tableaux and related methods—24th international conference, (TABLEAUX’15), pp 185–200, 2015), which form the basis of modal theorem proving (Nalon et al., in: Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI’17), pp 4919–4923, 2017). We complement these calculi by a new tighter variant and show that proofs can be efficiently translated between all these variants, meaning that the calculi are equivalent from a proof complexity perspective. We then develop the first lower bound technique for modal resolution using Prover–Delayer games, which can be used to establish “genuine” modal lower bounds for size of dag-like modal resolution proofs. We illustrate the technique by devising a new modal pigeonhole principle, which we demonstrate to require exponential-size proofs in modal resolution. Finally, we compare modal resolution to the modal Frege systems of Hrubeš (Ann Pure Appl Log 157(2–3):194–205, 2009) and obtain a “genuinely” modal separation.

In this paper, we explore the role of mathematical proof summaries as a tool for capturing students’ reading comprehension of a given proof. We present an interview study based on mathematicians’ pairwise evaluations of student-produced summaries of a proof demonstrating the uncountability of the open unit interval. We present a thematic analysis, exploring features of mathematicians’ pairwise decision-making and their priorities in evaluating summaries. We argue that the students’ proof summaries shared several properties with traditional modes of proof-writing and were frequently evaluated against similar conventions. We consider the consequences for research and practice with proof comprehension and conclude that proof summaries have the potential to form the basis of a new approach to assessment in this area.

Privacy-preserving federated learning is distributed machine learning where multiple collaborators train a model through protected gradients. To achieve robustness to users dropping out, existing practical privacy-preserving federated learning schemes are based on ( t, N)-threshold secret sharing. Such schemes rely on a strong assumption to guarantee security: the threshold t must be greater than half of the number of users. The assumption is so rigorous that in some scenarios the schemes may not be appropriate. Motivated by the issue, we first introduce membership proof for federated learning, which leverages cryptographic accumulators to generate membership proofs by accumulating user IDs. The proofs are issued in a public blockchain for users to verify. With membership proof, we propose a privacy-preserving federated learning scheme called PFLM. PFLM releases the assumption of threshold while maintaining the security guarantees. Additionally, we design a result verification algorithm based on a variant of ElGamal encryption to verify the correctness of aggregated results from the cloud server. The verification algorithm is integrated into PFLM as a part. Security analysis in a random oracle model shows that PFLM guarantees privacy against active adversaries. The implementation of PFLM and experiments demonstrate the performance of PFLM in terms of computation and communication.

A crucial operation of saturation theorem provers is deletion of subsumed formulas. Designers of proof calculi, however, usually discuss this only informally, and the rare formal expositions tend to be clumsy. This is because the equivalence of dynamic and static refutational completeness holds only for derivations where all deleted formulas are redundant, but the standard notion of redundancy is too weak: A clause C does not make an instance $$C\sigma $$ C σ redundant. We present a framework for formal refutational completeness proofs of abstract provers that implement saturation calculi, such as ordered resolution and superposition. The framework modularly extends redundancy criteria derived via a familiar ground-to-nonground lifting. It allows us to extend redundancy criteria so that they cover subsumption, and also to model entire prover architectures so that the static refutational completeness of a calculus immediately implies the dynamic refutational completeness of a prover implementing the calculus within, for instance, an Otter or DISCOUNT loop. Our framework is mechanized in Isabelle/HOL.

We investigate the game semantics of general references through the fully abstract game model of Abramsky, Honda and McCusker (AHM), which demonstrated that the visibility condition in games corresponds to the extra expressivity afforded by higher-order references with respect to integer references. First, we prove a stronger version of the visible factorisation result from AHM, by decomposing any strategy into a visible one and a single strategy corresponding to a reference cell of type unit → unit (AHM accounted only for finite strategies and its result involved unboundedly many cells). We show that the strengthened version of the theorem implies universality of the model and, consequently, we can rely upon it to provide semantic proofs of program transformation results. In particular, one can prove that any program with general references is equivalent to a purely functional program augmented with a single unit → unit reference cell and a single integer cell. We also propose a syntactic method of achieving such a transformation. Finally, we provide a type-theoretic characterisation of terms in which the use of general references can be simulated with an integer reference cell or through purely functional computation, without any changes to the underlying types.

Many cyber-physical systems (CPS) are safety-critical, so it is important to formally verify them, e.g. in formal logics that show a model's correctness specification always holds. Constructive Differential Game Logic (CdGL) is such a logic for (constructive) hybrid games, including hybrid systems. To overcome undecidability, the user first writes a proof, for which we present a proof-checking tool. We introduce Kaisar, the first language and tool for CdGL proofs, which until now could only be written by hand with a low-level proof calculus. Kaisar's structured proofs simplify challenging CPS proof tasks, especially by using programming language principles and high-level stateful reasoning. Kaisar exploits CdGL's constructivity and refinement relations to build proofs around models of game strategies. The evaluation reproduces and extends existing case studies on 1D and 2D driving. Proof metrics are compared and reported experiences are discussed for the original studies and their reproductions., Preprint of paper appearing in ESWEEK-TECS (EMSOFT 2021)

Visual representations, such as diagrams, are known to be valuable tools in problem solving and proof construction. However, previous studies have shown that simply having access to a diagram is not sufficient to improve students’ performance on mathematical tasks. Rather, students must actively extract information about the problem scenario from their diagrams for them to be useful. Furthermore, several studies have described the behaviors of mathematicians and students when solving problems and writing proofs, but few have discussed students’ behaviors in the context of proof writing in introductory point-set topology. We present a case study of an undergraduate, Stacey, enrolled in a general topology course. Throughout a semester, we presented Stacey with several proof-related tasks and examined how and why Stacey used diagrams when working on these tasks. Based on our analysis, we concluded that Stacey’s diagram creation and subsequent use during the construction of a given proof was an effort to identify the key idea of the proof. We describe Stacey’s overall proving behaviors through the lens of a problem-solving framework and present Stacey’s use of diagrams as an aid to discovering the key ideas of proofs in topology.

Smart city systems do not only handle information but also handle many critical aspects of citizens’ lives, including automobiles, healthcare, banking, etc. Smart city systems need to be both safe and secure systems. Therefore, this paper uses formal methods to develop safe and secure systes for smart city. However, because the creation of formal models is considered a difficult task that requires experience in modeling and a strong mathematical background, many techniques and patterns should be introduced to simplify the construction of formal models to make them more accessible for the development of systems, especially for systems pertaining to smart city services. In this paper, we propose an approach that uses Event-B theories to support data refinement and reduce the burden of proof for constructing Event-B formal models based on reused modeling components. In particular, we develop Event-B theories for common data structures based on pointers that could be used as patterns to carry out the refinement of abstract data structures, such as sets, lists and sequences. These data structures can offer solutions for the management of smart city services. We applied the proposed approach to construct Event-B models for task lists in a real-time operating system (FreeRTOS) to evaluate our approach. We successfully were able to model five task lists in FreeRTOS and developing data refinement levels without the need of spending long time in modeling or re-carrying any proofs.

Search-based satisfiability procedures try to build a model of the input formula by simultaneously proposing candidate models and deriving new formulae implied by the input. Conflict-driven procedures perform non-trivial inferences only when resolving conflicts between formulæ and assignments representing the candidate model. CDSAT (Conflict-Driven SATisfiability) is a method for conflict-driven reasoning in unions of theories. It combines inference systems for individual theories as theory modules within a solver for the union of the theories. This article augments CDSAT with a more general lemma learning capability and with proof generation. Furthermore, theory modules for several theories of practical interest are shown to fulfill the requirements for completeness and termination of CDSAT. Proof generation is accomplished by a proof-carrying version of the CDSAT transition system that produces proof objects in memory accommodating multiple proof formats. Alternatively, one can apply to CDSAT the LCF approach to proofs from interactive theorem proving, by defining a kernel of reasoning primitives that guarantees the correctness by construction of CDSAT proofs.

A key component of mathematical reasoning is the ability to formulate interesting conjectures about a problem domain at hand. In this paper, we give a brief overview of a theory exploration system called QuickSpec, which is able to automatically discover interesting conjectures about a given set of functions. QuickSpec works by interleaving term generation with random testing to form candidate conjectures. This is made tractable by starting from small sizes and ensuring that only terms that are irreducible with respect to already discovered conjectures are considered. QuickSpec has been successfully applied to generate lemmas for automated inductive theorem proving as well as to generate specifications of functional programs. We give an overview of typical use-cases of QuickSpec, as well as demonstrating how to easily connect it to a theorem prover of the user's choice., In Proceedings VPT 2021, arXiv:2109.02001

This article presents a full mathematical proof of the characteristic modeling approach for high-order linear dynamical systems. It explores the nature of the characteristic model in rigorous mathematical forms, also showing why and how the high-order dynamics can be compressed into the lower-order characteristic model. The relationships between high-order linear continuous dynamical systems, discrete-time characteristic model coefficients, and sampling-time intervals are investigated.

Memory allocation and deallocation are the fundamental operations of embedded operating systems, which have been extensively used in many safety critical systems. The correctness of the operations is of paramount importance because their failure could incur severe consequences. While the system is running, the memory state can easily grow to a gigantic amount, which means that it is impossible to verify the huge memory states one by one. Therefore, it is a challenge how to verify the correctness of running memory state of the system. In this article, we propose a novel memory state verification method based on inductive and deductive reasoning. First, we abstract the memory state as a list of memory blocks, which will transform in memory operations. Second, we construct the generic model based on the transition function of the memory management and summarize the invariant properties of the memory state. Third, we use the inductive method to calculate the changes between the memory states, and verify that the memory state of the system always satisfy the global properties. All the proofs are implemented in the interactive theorem prover Coq. On the basis of our proposed model, we verify the correctness of a two-level segregated fit (TLSF) algorithm through some extensions, and we also apply this method to verify the correctness of the memory state of the embedded system at runtime.

This paper presents a solution to the leaderless consensus of multiple spacecraft on SO(3) under a connected undirected graph. An algorithm is proposed to generate an undirected tree graph from a connected undirected communication topology. A distributed observer is designed to estimate the desired attitude and angular velocity for each spacecraft under the generated tree graph. An adaptive controller with a general connected undirected graph is developed to complete the synchronization task. Cases with zero and nonzero final angular velocities are considered. Theoretical proofs and numerical simulations are presented to demonstrate the effectiveness of the proposed controllers.

In this paper we treat metasequents—objects which stand to sequents as sequents stand to formulas—as first class logical citizens. To this end we provide a metasequent calculus, a sequent calculus which allows us to directly manipulate metasequents. We show that the various metasequent calculi we consider are sound and complete w.r.t. appropriate classes of tetravaluations where validity is understood locally. Finally we use our metasequent calculus to give direct syntactic proofs of various collapse results, closing a problem left open in French (Ergo, 3(5), 113–131 2016).

Proving and refuting are fundamental aspects of mathematical practice that are intertwined in mathematical activity in which conjectures and proofs are often produced and improved through the back-and-forth transition between attempts to prove and disprove. One aspect underexplored in the education literature is the connection between this activity and the construction by students of knowledge, such as mathematical concepts and theorems, that is new to them. This issue is significant to seeking a better integration of mathematical practice and content, emphasised in curricula in several countries. In this paper, we address this issue by exploring how students generate mathematical knowledge through discovering and handling refutations. We first explicate a model depicting the generation of mathematical knowledge throughheuristic refutation(revising conjectures/proofs through discovering and addressing counterexamples) and draw on a model representing different types of abductive reasoning. We employed both models, together with the literature on the teachers’ role in orchestrating whole-class discussion, to analyse a series of classroom lessons involving secondary school students (aged 14–15 years, Grade 9). Our analysis uncovers the process by which the students discovered a counterexample invalidating their proof and then worked via creative abduction where a certain theorem was produced to cope with the counterexample. The paper highlights the roles played by the teacher in supporting the students’ work and the importance of careful task design. One implication is better insight into the form of activity in which students learn mathematical content while engaging in mathematical practice.

The calculus of Dependent Object Types (DOT) has enabled a more principled and robust implementation of Scala, but its support for type-level computation has proven insufficient. As a remedy, we propose F ·· ω , a rigorous theoretical foundation for Scala’s higher-kinded types. F ·· ω extends F ω with interval kinds , which afford a unified treatment of important type- and kind-level abstraction mechanisms found in Scala, such as bounded quantification, bounded operator abstractions, translucent type definitions and first-class subtyping constraints. The result is a flexible and general theory of higher-order subtyping. We prove type and kind safety of F ·· ω , as well as weak normalization of types and undecidability of subtyping. All our proofs are mechanized in Agda using a fully syntactic approach based on hereditary substitution.

Formal languages are usually defined in terms of set theory. Choosing type theory instead gives us languages as type-level predicates over strings. Applying a language to a string yields a type whose elements are language membership proofs describing how a string parses in the language. The usual building blocks of languages (including union, concatenation, and Kleene closure) have precise and compelling specifications uncomplicated by operational strategies and are easily generalized to a few general domain-transforming and codomain-transforming operations on predicates. A simple characterization of languages (and indeed functions from lists to any type) captures the essential idea behind language “differentiation” as used for recognizing languages, leading to a collection of lemmas about type-level predicates. These lemmas are the heart of two dual parsing implementations—using (inductive) regular expressions and (coinductive) tries—each containing the same code but in dual arrangements (with representation and primitive operations trading places). The regular expression version corresponds to symbolic differentiation, while the trie version corresponds to automatic differentiation. The relatively easy-to-prove properties of type-level languages transfer almost effortlessly to the decidable implementations. In particular, despite the inductive and coinductive nature of regular expressions and tries respectively, we need neither inductive nor coinductive/bisimulation arguments to prove algebraic properties.

In recent years, a number of cryptographic etiquettes have been mechanically verified using a selection of inductive methods. These attestations typically want central a figure of recursive sets of messages, and need deep intuition into why the etiquette is correct. As a result, these proofs frequently require days to weeks of expert effort. We ensure advanced an involuntary verifier, which seems to overawe these glitches for many cryptographic protocols. The code of behavior text to concept a number of first-order invariant the proof commitments mitigating these invariants, along with any user-specified protocol properties are showed from the invariants with a tenacity theorem proved. The individual litheness in construction these invariants is to guesstimate, for each type of nonce and encryption engendered by the protocol, a formulary arresting conditions compulsory for that nonce encryption to be published.

Human-centered automated proof search aims to capture structures of ordinary mathematical proofs and discover human strategies that are used (implicitly) in their construction. We analyze the ways of two theorem provers for approaching that goal. One, the GG the other, Sieg’s AProS system, is described in Sieg and Walsh (Rev Symb Logic 1-35, 2019). Both systems make explicit, via their underlying logical calculi, the goal-directedness and bi-directionality of proof construction. However, the calculus for the GG AProS is to yield humanly intelligible formal proofs by logically and mathematically motivated strategies. In our final Programmatic remarks, we sketch a plausible, but difficult project for achieving more fully G&G’s broad goals by radically separating proof search from proof translation: one could use AProS for the proof search and then exploit the strategic structure of the completed proof as the deterministic underpinning for its translation into a natural language.

We formalize several regular numeral systems, state their properties and supported operations, clarify the correctness, and tabulate the proofs. Our goal is to use as few symbols in the presentation of digits and make as few digit changes as possible in every operation. Most importantly, we introduce two new systems: (1) the buffered regular system is simple and allows the increment and decrement of the least-significant digit in constant time, and (2) the strictly regular system allows the increment and decrement of a digit at arbitrary position with a constant number of digit changes while using three symbols only (instead of four symbols required by the extended regular system). To demonstrate the usefulness of the regular systems, we survey how they have been used in the design of data structures.

This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments. We refer to these as “credential-based” range proofs (CBRPs). HashWires improves upon hashchain solutions that are typically restricted to micro-payments for small interval ranges, achieving an exponential speedup in proof generation and verification time. Under reasonable assumptions and performance considerations, a Hash-Wires proof can be as small as 305 bytes for 64-bit integers. Although CBRPs are not zero-knowledge and are inherently less flexible than general zero-knowledge range proofs, we provide a number of applications in which a credential issuer can leverage HashWires to provide range proofs for private values, without having to rely on heavyweight cryptographic tools and assumptions.

Formal verification is to use mathematical methods to prove that our scheme is correct. This scheme is just a pronoun. It may be expressed as a hardware, a software or an algorithm. Errors in hardware are more difficult to modify than errors in software, so formal proofs and inspections often appear in the argument for hardware design. But, it does not mean that the software does not need to be formally verified. In addition to digital circuits or combinational circuits, cryptographic protocols also need to be formally verified. Formal proof can only ensure whether the result of logical inference is consistent with the previous stage, and can not guarantee whether there are defects in the process of logical inference. In this article the authors take as an example of Zhang-Wang's digital signature algorithm, and point out two formal proof methods of Boolean algebra and Galois field respectively.

This brief investigates consensus of multi-agent systems via asynchronous impulsive control. Firstly, the model considered in this brief accords with actual situation. Secondly, a new control scheme is proposed, which not only can greatly reduce communication and control cost, but also effectively solves the problem of excessive power. Moreover, sufficient conditions formulated by linear matrix inequalities are developed to obtain the less conservative results. The consensus error bound and the convergence rate are also given by rigorous mathematical proof. Finally, a numerical simulation is given to verify the theoretical analysis.