Solvability of systems of polynomial congruences modulo a large prime

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials of total degree at most d, solve the system for solution(s) in . We give a randomized algorithm for the decision version of this problem. For a fixed number of variables, the sequential version of the algorithm has expected time complexity polynomial in d, m and log p; the parallel version has expected time complexity polylogarithmic in d, m and p, using a number of processors, polynomial in d, m and log p. The only point which prevents the algorithm from being deterministic is the lack of a deterministic polynomial time algorithm for factoring univariate polynomials over . Received: April 9, 1997.     

Fast parallel polynomial division via reduction to triangular toeplitz matrix inversion and to polynomial inversion modulo a power

It is known that division with a remainder of two polynomials of degree at most s can be performed over an arbitrary field F of constants using uniform arithmetic and Boolean circuits of depth O(log s log log s) and polynomial size. A new algorithm is presented that yields those bounds via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power. (If|F| > (s?1)² or if P-uniform computation is allowed, then the depth can be reduced to O(log s).) This approach is new and makes the result conceptually simpler.     

模2n剩余类环上的多项式变换的研究

对模2ⁿ剩余类环上的多项式变换进行了详细的研究和分析。给出了模2ⁿ剩余类环上的m（m≥1）次多项式变换是置换的一个充分必要条件;给出了模2ⁿ剩余类环上的m（m≥1）次置换多项式个数的一个上界。     

Responsive security for stored data

We present the design of a distributed store that offers various levels of security guarantees while tolerating a limited number of nodes that are compromised by an adversary. The store uses secret sharing schemes to offer security guarantees, namely, availability, confidentiality, and integrity. However, a pure secret sharing scheme could suffer from performance problems and high access costs. We integrate secret sharing with replication for better performance and to keep access costs low. The trade offs involved between availability and access cost on one hand and confidentiality and integrity on the other are analyzed. Our system differs from traditional approaches such as state machine or quorum-based replication that have been developed to tolerate Byzantine failures. Unlike such systems, we augment replication with secret sharing and offer weaker consistency guarantees. We demonstrate that such a hybrid scheme offers additional flexibility that is not possible with replication alone.     

Algorithms for Exponentiation in Finite Fields

Gauss periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integersn , multiplication in a normal basis of Fqn over Fq can be computed with O(n logn loglog n), division with O(n log²n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n²loglog n) operations in Fq. We also prove that using a polynomial basis exponentiation in F 2 n can be done with the same number of operations in F 2 for all n. The previous best estimates were O(n²) for multiplication in a normal basis, andO (n²log n loglog n) for exponentiation in a polynomial basis.     

Tri-cubic polynomial natural spline interpolation for scattered data

In this paper an interpolation problem for 3D scattered data defined on a rectangular parallelepiped with natural boundary conditions is considered. By using spline function theory in Hilbert space, we discuss the existence, uniqueness and characterization of the solution of the interpolation problem as well as its convergence. We show that the solution can be constructed in a simple way without using reproducing kernel semi-Hilbert space theory. Moreover, the solution can be written as the sum of tri-linear polynomials and piecewise tri-cubic polynomials and its coefficients can be determined by solving a positive semi-definite linear system. Numerical examples are presented to illustrate the proposed approach.     

Approximation polynomial algorithm for the data editing and data cleaning problem

The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and cleaning (removal of irrelevant (not similar) elements). We consider the model of this problem, i.e., the problem of searching for a subset of maximal cardinality in a finite set of points of the Euclidean space for which quadratic variation of points with respect to its unknown centroid does not exceed a given fraction of the quadratic variation of points of the input set with respect to its centroid. It is proved that the problem is strongly NP-hard. A polynomial 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.     

快速幂乘运算的最优Window法

快速幂乘运算是公钥密码体制中的重要问题。证明了Window法优于其他各种快速幂乘算法如二进制法、b进制法等,同时给出了最优Window法的宽度范围及其平均乘法次数的估计值。     

False data separation for data security in smart grids

The smart grid is emerging as an efficient paradigm for electric power generation, transmission, and consumption, based on optimized decision making and control that leverage the measurement data of sensors and meters in the grid. False data injection is a new type of power grid attacks aiming to tamper such important data. For the security and robustness of the grid, it is critical to separate the false data injected by such attacks and recover the original measurement data. Nonetheless, the existing approaches often neglect the true changes on original measurement data that are caused by the real perturbations on grid states and hence have a risk of removing these true changes as injected false data during the data recovery. In this paper, we preserve these true changes by modeling the false data problem as a rank-bounded \(L_1\) norm optimization and propose both offline and online algorithms to filter out the injected false data and recover original measurement data. Trace-driven simulations verify the efficacy of our solution.     

Reversible data hiding scheme with edge-direction predictor and modulo operation

Since the first histogram shifting technique was proposed by Ni et al., many histogram based data hiding methods were proposed to improve their scheme. One of the methods is using difference value between cover image and prediction image. Another method is using two point pairs and absolute value for improving Ni et al.’s scheme. In this paper, novel reversible data hiding scheme with edge-direction predictor and modulo operation was proposed for improving histogram shifting technique with 3 cases. We considered as much as possible around pixels by using edge-direction predictor with odd and even line embedding Also, we utilize two point pairs and absolute value at the same time by using modulo operation with wrap around. In the experimental results, the proposed scheme shown a good quality image result about 48dB as similar as other schemes and enhanced hiding capacity over 50 % than other schemes.     

Affine-evasive sets modulo a prime

In this work, we describe a simple and efficient construction of a large subset S   of _Fp${\mathbb{F}}_p$, where p   is a prime, such that the set A(S)$A(S)$ for any non-identity affine map A   over _Fp${\mathbb{F}}_p$ has small intersection with S.     

Modelling a side channel resistant CHAN-PKC cryptomata for medical data security

Multimedia Tools and Applications - Currently, a multimedia revolution of medical data in health information becomes part of our computing environment. However, the interchange of medical...     

大数据环境下的数据安全性探讨

随着互联网的高速发展,特别是近年来云计算、物联网等新兴技术的出现,社交网络等服务的广泛应用,人类社会的数据的规模正快速地增长,大数据时代已经到来。如何获取,分析大数据已经成为广泛的问题。但随着带来的数据的安全性必须引起高度重视。本文从大数据的概念和特征说起,阐述大数据面临的安全挑战,并提出大数据的安全应对策略。     

Improved polynomial algorithms for robust bottleneck problems with interval data

To model uncertainties in a problem one can provide intervals of uncertainty specifying a range for each uncertain parameter value. To hedge against ‘worst-case scenarios’, i.e., most unwelcome realizations of the uncertain parameters after a solution has been determined, the minmax-regret criterion has been adopted in robust optimization. Within this field, we consider bottleneck problems with one or more uncertain parameter functions.We apply a known polynomial time solution scheme for a number of specific problems of this type with one uncertain parameter function. This leads to improved algorithms of reduced complexity, e.g., for the bottleneck Steiner tree problem and the bottleneck assignment problem.Further, we formulate a framework to solve single machine scheduling problems in polynomial time under the maximum tardiness criterion, with up to three uncertain parameter functions.     

基于联邦集成算法对多源数据安全性的研究

联邦学习是隐私保护领域关注的热点内容,存在难以集中本地模型参数与因梯度更新造成数据泄露的问题。提出了一种联邦集成算法,使用256 B的密钥将不同类型的初始化模型传输至各数据源并训练,使用不同的集成算法来整合本地模型参数,使数据与模型的安全性得到很大提升。仿真结果表明,对于中小数据集而言,使用Adaboost集成算法得到的模型准确率达到92.505%,标准差约为8.6×10-8,对于大数据集而言,采用stacking集成算法得到的模型的准确率达到92.495%,标准差约为8.85×10-8,与传统整合多方数据集中训练模型的方法相比,在保证准确率的同时兼顾了数据与模型的安全性。     

Visual data security and management for smart cities

This paper proposes a method to manage and utilize image and video data effectively in a smart city. Applying digital watermarking techniques, a framework for visual data security and management for smart cities is presented. In the framework, a reversible fragile or semi-fragile watermark embedded into the visual data is used to ensure trusted acquisition. Moreover, reversible metadata watermarks carrying information such as identification and other properties data is used to assist visual data management. A solution for tracing users on a large scale is presented using reversible watermarking.     

Space efficient secret sharing for implicit data security

This paper presents a k-threshold computational secret sharing technique that distributes a secret S into shares of size , where ∣S∣ denotes the secret size. This bound is close to the space optimal bound of if the secret is to be recovered from k shares. In other words, our technique can be looked upon as a new information dispersal scheme that provides near optimal space efficiency. The proposed scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in sensor networks.