基于差分表的Blow-CAST-Fish算法的密钥恢复攻击

针对Blow-CAST-Fish算法攻击轮数有限和复杂度高等问题,提出一种基于差分表的Blow-CAST-Fish算法的密钥恢复攻击。首先,对S盒的碰撞性进行分析,分别基于两个S盒和单个S盒的碰撞,构造6轮和12轮差分特征;然后,计算轮函数f₃的差分表,并在特定差分特征的基础上扩充3轮,从而确定密文差分与f₃的输入、输出差分的关系;最后,选取符合条件的明文进行加密,根据密文差分计算f₃的输入、输出差分值,并查寻差分表找到对应的输入、输出对,从而获取子密钥。在两个S盒碰撞的情况下,所提攻击实现了9轮Blow-CAST-Fish算法的差分攻击,比对比攻击多1轮,时间复杂度由2^107.9降低到2⁷⁴;而在单个S盒碰撞的情况下,所提攻击实现了15轮Blow-CAST-Fish算法的差分攻击,与对比攻击相比,虽然攻击轮数减少了1轮,但弱密钥比例由{\mathrm{2}}^{-\mathrm{52.4}}提高到{\mathrm{2}}^{-\mathrm{42}},数据复杂度由2⁵⁴降低到2⁴⁷。测试结果表明,在相同差分特征基础上,基于差分表的攻击的攻击效率更高。     

Sentinel-1 based Soil Moisture Estimation in Middle Reaches of Heihe River Basin

In this study, a change detection model, constructed using the Sentinel-1 Synthetic Aperture Radar (SAR) data and the simultaneous Normalized Difference Vegetation Index (NDVI) products from the Moderate Resolution Imaging Spectroradiometer (MODIS) and Landsat 8 sensors, is applied to estimate soil moisture in middle reaches of the Heihe River Basin, and the effects of two key parameters on retrieval accuracy are comprehensively investigated. The results show that: (1) when constructing the empirical relationship between backscattering coefficient difference ( \mathrm{\Delta } \sigma ) and Vegetation Index (VI) required by change detection model, the optimal sampling ratios in the ( \mathrm{\Delta } \sigma - V I ) space are approximately 2% and 4% for MODIS NDVI and Landsat 8 NDVI, respectively; (2) the Landsat 8 NDVI-based change detection model slightly outperforms the MODIS NDVI-based model in soil moisture retrieval accuracy, with Root Mean Square Error(RMSE) of 0.040 m³/m³ and 0.044 m³/m³respectively; (3) for the key parameters of the change detection method, replacing the ground-based initial soil moisture and scaling factor (maximum soil moisture difference between two adjacent dates \mathrm{\Delta } M s_{max} ) by the low-resolution SMAP/Sentinel-1 L2_SM_SP data will increase the RMSE by 0.01 m³/m³ and 0.04 m³/m³ respectively. Comparing to the parameter of initial soil moisture, the error in soil moisture scaling factor will lead to more significant degradation in the performance of the change detection method, thus it is recommended to use the high precision scaling factor for soil moisture estimation. This study confirms the promising potential of Sentinel-1 data for retrieving high-resolution soil moisture via change detection method and provides practical insight into its application.     

基于Sentinel-1数据的黑河中游土壤水分反演

基于Sentinel-1合成孔径雷达 (SAR) 数据及相同时段的中分辨率成像光谱仪（MODIS）和Landsat 8两种归一化植被指数（NDVI）,构建变化检测模型以估算黑河中游的高分辨率土壤水分,并探讨模型中具体参数设置对估算精度的影响。结果表明：①在对后向散射系数时间序列的差值 ( \mathrm{\Delta } \sigma ) 和植被指数 ( \mathrm{V} \mathrm{I} ) 进行线性建模过程中,MODIS NDVI和Landsat 8 NDVI这两种植被产品所构建的模型在 \mathrm{\Delta } \sigma - \mathrm{V} \mathrm{I} 空间中所选取的采样点比例分别为2%和4%时,各自取得最优精度; ②以土壤水分反演为目标,使用Landsat 8 NDVI构建的变化检测模型略优于使用MODIS NDVI构建的变化检测模型,两种模型的均方根误差RMSE分别为0.040 m³/m³和0.044 m³/m³,相关系数R分别为0.86和0.83; ③对于变化检测方法的关键参数,若使用低分辨率的SMAP/Sentinel-1 L2_SM_SP土壤水分数据分别代替站点观测的土壤水分初始值和缩放因子 (即两个连续时相土壤水分变化的最大值 \mathrm{\Delta } M s_{max} ) 这两个参数,则土壤水分RMSE将分别增加0.01 m³/m³和0.04 m³/m³。即土壤水分缩放因子这一参数的误差对反演结果的影响大于土壤水分初始值误差对反演结果的影响,故采用高精度的缩放因子进行变化检测估算。研究结论对于利用新兴的Sentinel-1 SAR数据,通过变化检测算法准确获取高分辨率土壤水分信息具有实际参考价值。     

Local Control Lyapunov Functions for Constrained Linear Discrete-Time Systems: The Minkowski Algebra Approach

This technical note utilizes Minkowski algebra of convex sets to characterize a family of local control Lyapunov functions for constrained linear discrete-time systems. Local control Lyapunov functions are induced by parametrized contractive invariant sets. Underlying contractive invariant sets belong to a family of Minkowski decomposable convex sets and are, in fact, parametrized by a basic shape set and linear transformations of system matrices and a set of design matrices. Corresponding local control Lyapunov functions can be detected by solving a single, tractable, convex optimization problem which in case of polyhedral constraints reduces to a single linear program. The a priori complexity estimate of the characterized local control Lyapunov function is provided for some practically relevant cases. An illustrative example and relevant numerical experience are also reported.      

Application of Lie Algebras to Visual Servoing

A novel approach to visual servoing is presented, which takes advantage of the structure of the Lie algebra of affine transformations. The aim of this project is to use feedback from a visual sensor to guide a robot arm to a target position. The target position is learned using the principle of teaching by showing in which the supervisor places the robot in the correct target position and the system captures the necessary information to be able to return to that position. The sensor is placed in the end effector of the robot, the camera-in-hand approach, and thus provides direct feedback of the robot motion relative to the target scene via observed transformations of the scene. These scene transformations are obtained by measuring the affine deformations of a target planar contour (under the weak perspective assumption), captured by use of an active contour, or snake. Deformations of the snake are constrained using the Lie groups of affine and projective transformations. Properties of the Lie algebra of affine transformations are exploited to provide a novel method for integrating observed deformations of the target contour. These can be compensated with appropriate robot motion using a non-linear control structure. The local differential representation of contour deformations is extended to allow accurate integration of an extended series of small perturbations. This differs from existing approaches by virtue of the properties of the Lie algebra representation which implicitly embeds knowledge of the three-dimensional world within a two-dimensional image-based system. These techniques have been implemented using a video camera to control a 5 DoF robot arm. Experiments with this implementation are presented, together with a discussion of the results.     

Uniqueness theorems on meromorphic functions sharing one value

In this paper, we study with a weighted sharing method the uniqueness problem of [fⁿ(z)]^(k) and [gⁿ(z)]^(k) sharing one value and obtain some results which extend the theorems given by M. Fang, S. Bhoosnurmath and S. Dyavanal et al.     

A Fast and Log-Euclidean Polyaffine Framework for Locally Linear Registration

In this article, we focus on the parameterization of non-rigid geometrical deformations with a small number of flexible degrees of freedom. In previous work, we proposed a general framework called polyaffine to parameterize deformations with a finite number of rigid or affine components, while guaranteeing the invertibility of global deformations. However, this framework lacks some important properties: the inverse of a polyaffine transformation is not polyaffine in general, and the polyaffine fusion of affine components is not invariant with respect to a change of coordinate system. We present here a novel general framework, called Log-Euclidean polyaffine, which overcomes these defects. We also detail a simple algorithm, the Fast Polyaffine Transform, which allows to compute very efficiently Log-Euclidean polyaffine transformations and their inverses on regular grids. The results presented here on real 3D locally affine registration suggest that our novel framework provides a general and efficient way of fusing local rigid or affine deformations into a global invertible transformation without introducing artifacts, independently of the way local deformations are first estimated.

Meta-BN Net for few-shot learning

In this paper, we propose a lightweight network with an adaptive batch normalization module, called Meta-BN Net, for few-shot classification. Unlike existing few-shot learning methods, which consist of complex models or algorithms, our approach extends batch normalization, an essential part of current deep neural network training, whose potential has not been fully explored. In particular, a meta-module is introduced to learn to generate more powerful affine transformation parameters, known as \gamma and \beta, in the batch normalization layer adaptively so that the representation ability of batch normalization can be activated. The experimental results on miniImageNet demonstrate that Meta-BN Net not only outperforms the baseline methods at a large margin but also is competitive with recent state-of-the-art few-shot learning methods. We also conduct experiments on Fewshot-CIFAR100 and CUB datasets, and the results show that our approach is effective to boost the performance of weak baseline networks. We believe our findings can motivate to explore the undiscovered capacity of base components in a neural network as well as more efficient few-shot learning methods.     

Hermite interpolation with simple planar PH curves by speed reparametrization

We introduce a new method of solving C¹ Hermite interpolation problems, which makes it possible to use a wider range of PH curves with potentially better shapes. By characterizing PH curves by roots of their hodographs in the complex representation, we introduce PH curves of type K(t−c)²ⁿ⁺¹+d. Next, we introduce a speed reparametrization. Finally, we show that, for C¹ Hermite data, we can use PH curves of type K(t−c)²ⁿ⁺¹+d or strongly regular PH quintics satisfying the G¹ reduction of C¹ data, and use these curves to solve the original C¹ Hermite interpolation problem.     

基于公证人组的跨链交互安全模型

针对公证人机制中存在的公证人节点职能集中以及跨链交易效率较低等问题,提出一种基于公证人组的跨链交互安全模型。首先,将公证人节点分为三类角色,即交易验证者、连接者和监督者,由交易验证组成员打包经过共识的多笔交易成一笔大的交易,并利用门限签名技术对它进行签名;其次,被确认的交易会被置于跨链待转账池中,连接者随机选取多笔交易,利用安全多方计算和同态加密等技术判断交易的真实性;最后,若打包所有符合条件的交易的哈希值真实可靠且被交易验证组验证过,则连接者可以继续执行多笔跨链交易的批处理任务,并与区块链进行信息交互。安全性分析表明,该跨链机制有助于保护信息的机密性和数据的完整性,实现数据在不出库的情况下的协同计算,保障区块链跨链系统的稳定性。与传统的跨链交互安全模型相比,所提模型的签名次数和需要分配公证人组数的复杂度从O(n)降为O(\mathrm{1})。     

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties. We are given a cost graph G=(V,E;c) and an integer k. This problem determines a vertex set S\subseteq V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function. We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.     

Transformations of structures: An algebraic approach

This paper introduces a new mathematical approach to transformations of structures, where the concept of structure is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This paper presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recursively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this paper uses ideas and results from abstract algebra to minimize the need for elaborate constructions.A condensation of an earlier version of this paper was presented as [9] at the 7th Symposium on Mathematical Foundations of Computer Science, September 1978, Zakopane, Poland. Work by Ehrig was partially supported by IBM Germany and IBM World Trade Corp. Work by Rosen and Maggiolo-Schettini was partially supported by the Laboratorio di Cibernetica del C.N.R.     

基于神经正切核的多核学习方法

多核学习方法是一类重要的核学习方法,但大多数多核学习方法存在如下问题：多核学习方法中的基核函数大多选择传统的具有浅层结构的核函数,在处理数据规模大且分布不平坦的问题时表示能力较弱;现有的多核学习方法的泛化误差收敛率大多为O\left(\mathrm{1}/\sqrt[]{n}\right),收敛速度较慢。为此,提出了一种基于神经正切核（NTK）的多核学习方法。首先,将具有深层次结构的NTK作为多核学习方法的基核函数,从而增强多核学习方法的表示能力。然后,根据主特征值比例度量证明了一种收敛速率可达O\left(\mathrm{1}/n\right)的泛化误差界;在此基础上,结合核对齐度量设计了一种全新的多核学习算法。最后,在多个数据集上进行了实验,实验结果表明,相比Adaboost和K近邻（KNN）等分类算法,新提出的多核学习算法具有更高的准确率和更好的表示能力,也验证了所提方法的可行性与有效性。     

A logarithmic-time solution to the point location problem for parametric linear programming

The optimiser of a (multi) parametric linear program (pLP) is a piecewise affine function defined over a polyhedral subdivision of the set of feasible states. Once this affine function has been pre-calculated, the optimal solution can be computed for a particular parameter by determining the region that contains it. This is the so-called point location problem. In this paper, we show that this problem can be written as an additively weighted nearest neighbour search that can be solved in time linear in the dimension of the state space and logarithmic in the number of regions.

It is well-known that linear model predictive control (MPC) problems based on linear control objectives (e.g., 1- or ∞-norm) can be posed as pLPs, and on-line calculation of the control law involves the solution to the point location problem. Several orders of magnitude sampling speed improvement are demonstrated over traditional MPC and closed-form MPC schemes using the proposed scheme.     

Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

Secure k-Nearest Neighbor (k-NN) query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas, such as privacy-preserving machine learning and secure biometric identification. Several solutions have been put forward to solve this challenging problem. However, the existing schemes still suffer from various limitations in terms of efficiency and flexibility. In this paper, we propose a new encrypt-then-index strategy for the secure k-NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility). Specifically, we propose a novel algorithm to transform the encrypted database and encrypted query points in the cloud. By indexing the transformed database using spatial data structures such as the R-tree index, our strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted database. To the best of our knowledge, the proposed strategy is the first to simultaneously provide these two properties. Through theoretical analysis and extensive experiments, we formally prove the security and demonstrate the efficiency of our scheme.     

A subgraph matching algorithm based on subgraph index for knowledge graph

The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as F G q_T-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( F G q_T), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing F G q_T. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.     

Fractals and Quasi-Affine Transformations

In the continuum , contracting affine transformations have a unique fixed point. It is well known that this property is not preserved by dicretization and that the dynamics of discretized functions are very complicated. Discrete geometry allows us to start a theory for these dynamics and to illustrate some of their features by pictures. These pictures, rendered by a simple algorithm, reveal a very large spectrum of fractal structures, from the simplest to the intricatest.