Impossible shaded images

It is shown that shaded images that cannot have originated from a uniformly illuminated, smooth continuous surface with uniform albedo exist. The typical condition where this occurs is when a dark area (corresponding to a region of high gradient) is surrounded by a lighter region (with low gradient). For this to correspond to a real surface, it must be established that there is a local extremum or area of lower gradient inside the dark region. This, in turn, will show up as either a light area in the image or an orientation discontinuity in the surface (thus violating either intensity or smoothness constraints). The impossibility of a shaded image can be established by counting the number of extrema inside a region corresponding to an isolated surface patch     

Modeling and Rendering Escher-Like Impossible Scenes

Inspired by the drawings of "impossible" objects by artists such as M.C. Escher, we describe a mathematical theory which captures some of the underlying principles of their work. Using this theory, we show how impossible three-dimensional scenes may be modeled and rendered synthetically.     

Zodiac 算法的不可能差分和积分攻击

重新评估了Zodiac算法抗不可能差分攻击和积分攻击的能力.已有结果显示,Zodiac算法存在15轮不可能差分和8轮积分区分器.首先得到了算法概率为1的8轮截断差分,以此构造了Zodiac算法完整16轮不可能差分和9轮积分区分器.利用9轮积分区分器,对不同轮数Zodiac算法实施了积分攻击,对12轮、13轮、14轮、15轮和16轮Zodiac的攻击复杂度分别为234,259,293,2133和2190次加密运算,选择明文数均不超过216.结果表明,完整16轮192比特密钥的Zodiac算法也是不抗积分攻击的.     

Crypton算法的不可能差分分析

Crypton算法是基于Square算法设计的SPN结构类密码算法,由于其具备良好的软硬件性能而引起了广泛的关注.对Crypton分组密码算法在不可能差分分析下的安全性进行了研究.通过分析Crypton算法扩散层的性质,指出了现有7轮Crypton算法不可能差分分析中存在的问题,结合快速排序、分割攻击与早夭技术对7轮Crypton算法的不可能差分分析进行了改进,降低了其数据复杂度与时间复杂度;同时,通过并行使用4条不可能差分区分器,结合密钥扩展算法的性质给出了7轮Crypton算法的多重不可能差分分析结果,恢复了算法的主密钥;最后,在7轮Crypton算法的不可能差分分析的基础上向后拓展1轮,给出了8轮Crypton-256算法的不可能差分分析,恢复了其主密钥,其数据复杂度为2\\+{103}个选择明文,时间复杂度为2\\+{214}次8轮Crypton加密,存储复杂度为2\\+{154.4} B.研究结果表明:结合算法的性质及多种技术给出了Crypton算法目前最优的不可能差分分析结果.     

Resolving ambiguous identifiers

In some compilers, long identifiers are truncated, or lower case letters are converted to upper case. Such respellings can make two distinct identifiers appear identical, and under unfavourable circumstances no warning or error messages will be generated. The use of different respelling algorithms in different compilers is a hindrance to transporting software, and is a source of latent bugs. This short note suggests avoiding the problem by generating warning messages when a potentially ambiguous spelling is used in a declaration. The technique involves hashing the character and case-shift bits that would otherwise be thrown away. A program that compiles without warning messages can be safely transported.     

Height and gradient from shading

The method described here for recovering the shape of a surface from a shaded image can deal with complex, wrinkled surfaces. Integrability can be enforced easily because both surface height and gradient are represented. (A gradient field is integrable if it is the gradient of some surface height function.) The robustness of the method stems in part from linearization of the reflectance map about the current estimate of the surface orientation at each picture cell. (The reflectance map gives the dependence of scene radiance on surface orientation.) The new scheme can find an exact solution of a given shape-from-shading problem even though a regularizing term is included. The reason is that the penalty term is needed only to stabilize the iterative scheme when it is far from the correct solution; it can be turned off as the solution is approached. This is a reflection of the fact that shape-from-shading problems are not ill posed when boundary conditions are available, or when the image contains singular points.This article includes a review of previous work on shape from shading and photoclinometry. Novel features of the new scheme are introduced one at a time to make it easier to see what each contributes. Included is a discussion of implementation details that are important if exact algebraic solutions of synthetic shape-from-shading problems are to be obtained. The hope is that better performance on synthetic data will lead to better performance on real data.Massachusetts Institute of Technology     

Reflections on shading

It is demonstrated that mutual illumination can produce significant effects in real scenes. An example is presented to illustrate the difficulties that mutual illumination presents to shape recovery schemes. These effects are qualitatively modeled by the radiosity equation. Using the radiosity equation, the authors predict the occurrence of spectral events in the radiance, namely, discontinuities in the radiance and its derivatives. Experimental evidence establishes the validity of this approach. Mutual illumination can generate discontinuities in the derivatives of radiance unrelated to local geometry. It is argued that it is not possible to obtain veridical dense depth or normal maps from a shading analysis. However, discontinuities in radiance are tractably related to scene geometry and, moreover, can be detected     

Local shading analysis

Local analysis of image shading, in the absence of prior knowledge about the viewed scene, may be used to provide information about the scene. The following has been proved. Every image point has the same image intensity and first and second derivatives as the image of some point on a Lambertian surface with principal curvatures of equal magnitude. Further, if the principal curvatures are assumed to be equal there is a unique combination of image formation parameters (up to a mirror reversal) that will produce a particular set of image intensity and first and second derivatives. A solution for the unique combination of surface orientation, etc., is presented. This solution has been extended to natural imagery by using general position and regional constraints to obtain estimates of the following: ? surface orientation at each image point; ? the qualitative type of the surface, i.e., whether the surface is planar, cylindrical, convex, concave, or saddle; ? the illuminant direction within a region. Algorithms to recover illuminant direction and estimate surface orientation have been evaluated on both natural and synthesized images, and have been found to produce useful information about the scene.     

SPECK算法的不可能差分分析

分析了SPECK2n(2n=64,96,128)算法在不可能差分分析下的安全性。首先利用模加法差分的扩散性质,找到了SPECK2n(2n=64,96,128)算法的7轮不可能差分区分器。其次,基于找到的7轮不可能差分区分器,给出了SPECK64/128算法和SPECK128/256算法的11轮不可能差分分析,以及SPECK 96/144算法的10轮不可能差分分析,恢复了全部主密钥。这是SPECK2n/4n(2n=64,96,128)算法的首个不可能差分分析结果。     

ESF算法的不可能差分密码分析

分析研究了分组密码算法ESF抵抗不可能差分的能力,使用8轮不可能差分路径,给出了相关攻击结果。基于一条8轮的不可能差分路径,根据轮密钥之间的关系,通过改变原有轮数扩展和密钥猜测的顺序,攻击了11轮的ESF,改善了关于11轮的ESF的不可能差分攻击的结果。计算结果表明:攻击11轮的ESF所需要的数据复杂度为O(2⁵³),时间复杂度为O(2³²),同时也说明了11轮的ESF对不可能差分是不免疫的。     

Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia

This paper studies the security of the block ciphers ARIA and Camellia against impossible differential cryptanalysis. Our work improves the best impossible differential cryptanalysis of ARIA and Camellia known so far. The designers of ARIA expected no impossible differentials exist for 4-round ARIA. However, we found some nontrivial 4-round impossible differentials, which may lead to a possible attack on 6-round ARIA. Moreover, we found some nontrivial 8-round impossible differentials for Camellia, whereas only 7-round impossible differentials were previously known. By using the 8-round impossible differentials, we presented an attack on 12-round Camellia without FL/FL^-1 layers.     

GRANULE算法的不可能差分分析

GRANULE算法是一个超轻量分组密码算法,有着较好的软硬件实现性能,但目前尚没有该算法在不可能差分分析下的安全性评估结果。为此,利用中间相错技术,找到GRANULE64算法多条5轮不可能差分区分器,并基于得到的区分器,向上、下分别扩展3轮,给出对GRANULE64/80算法的11轮不可能差分分析。通过该算法可以恢复80-bit主密钥,时间复杂度为2~(73.3)次11轮GRANULE64算法加密,数据复杂度为2~(64)个选择明文。     

CLEFIA-128算法的不可能差分密码分析

为研究分组密码CLEFIA-128抵抗不可能差分攻击的能力,基于一条9轮不可能差分路径,分析了13轮不带白化密钥的CLEFIA-128算法。利用轮函数中S盒差分分布表恢复部分密钥,利用轮密钥之间的关系减少密钥猜测量,并使用部分密钥分别猜测(Early Abort)技术有效地降低了复杂度。计算结果表明,该方法的数据复杂度和时间复杂度分别为O(2103.2)和O(2124.1)。     

Piccolo算法的相关密钥-不可能差分攻击

现有的对于Piccolo算法的安全性分析结果中,除Biclique分析外,以低于穷举搜索的复杂度最长仅攻击至14轮Piccolo-80和18轮Piccolo-128算法.通过分析Piccolo算法密钥扩展的信息泄漏规律,结合算法等效结构,利用相关密钥-不可能差分分析方法,基于分割攻击思想,分别给出了15轮Piccolo-80和21轮Piccolo-128含前向白化密钥的攻击结果.当选择相关密钥量为2⁸时,攻击所需的数据复杂度分别为2^58.6和2^62.3,存储复杂度分别为2^60.6和2^64.3,计算复杂度分别为2⁷⁸和2^82.5;在选择相关密钥量为2⁴时,攻击所需的数据复杂度均为2^62.6和2^62.3,存储复杂度分别为2^64.6和2^64.3,计算复杂度分别为2^77.93和2^124.45.分析结果表明,仅含前向白化密钥的15轮Piccolo-80算法和21轮Piccolo-128算法在相关密钥-不可能差分攻击下是不安全的.     

低轮ARIA的不可能差分

不可能差分是对分组密码的一种有效攻击方法.它是寻找不可能出现的差分关系,并排除满足这种关系的密钥,最终恢复出秘密密钥.分析了韩国新型分组密码算法ARIA的不可能差分.首先分析了ARIA混淆层的特性,构造了ARIA的4轮不可能差分,选择225.5个明文对,使其密文异或具有低64b为零的形式,利用4轮不可能差分特性对5轮的ARIA进行了分析.选择230个明文对对6轮ARIA进行分析.     

Surface descriptions from stereo and shading

Surface reconstruction from stereo and shape-from-shading have both been discussed extensively in the literature. In this paper methods that attempt to supplement stereo with analysis of shading, are reviewed, with comments on their robustness. Theoretical results on uniqueness in shape from shading are presented, and on the difficulty of estimating surface shape with local intensity operators. Preliminary experiments based on the method of Koenderinck and van Doorn, for analysing variation of shading with viewpoint, are reported. It is concluded that there is a variety of techniques for deriving qualitative shape information, which might be sufficiently robust for use in computer vision systems.     

Linear shape from shading

In many situations the reflectance function of a surface is approximately linear, and there is an effielent closed-form solution to the shape-from-shading problem. When boundary conditions (e.g., edges, singular points) are not available, good estimates of shape may still be extracted by using the assumption of general viewing position. An improved method for estimating the illuminant direction is also presented.     

Real time discrete shading

A shading technique for voxel-based images, termedcongradient shading, is presented. As the surface information is not available in voxel representation, the surface normal must be recovered from the 3D discrete voxel map itself. The technique defines the normal as one of a finite set of neighborhood-estimated gradients and can thus employ precalculated look-up tables. Furthermore, a table-driven mechanism permits changing the light source parameters by merely redefining the look-up table. The technique uses only simple arithmetic operations and is thus suitable for hardware implementation. Since it has been implemented not as a post-processor, but as part of the projection pipeline of the cube architecture, congradient shading can be executed in real time. Two versions of the technique in real time. Two versions of the technique have been conceived and implemented:unidirectional shading, in which the gradient is estimated only from neighborhoods along the scan-lines;bidirectional shading, in which both horizontal and vertical components of the gradient are considered. In spite of the simplicity of the technique, the results are practically indistinguishable from images generated by conventional techniques.This work was supported by the National Science Foundation under grants DCR 8603603, CCR 8743478, CCR 8717016, and MIP 8805130     

LBlock算法的相关密钥不可能差分分析

LBlock算法是2011年提出的轻量级分组密码,适用于资源受限的环境.目前,关于LBlock最好的分析结果为基于14轮不可能差分路径和15轮的相关密钥不可能差分路径,攻击的最高轮数为22轮.为研究LBlock算法抵抗不可能差分性质,结合密钥扩展算法的特点和轮函数本身的结构,构造了新的4条15轮相关密钥不可能差分路径.将15轮差分路径向前扩展4轮、向后扩展3轮,分析了22轮LBlock算法.在已有的相关密钥不可能差分攻击的基础上,深入研究了轮函数中S盒的特点,使用2类相关密钥不可能差分路径.基于部分密钥分别猜测技术降低计算量,分析22轮LBlock所需数据量为261个明文,计算量为259.58次22轮加密.     

SPECK型算法的积分分析和不可能差分分析

SPECK系列算法是2013年由美国国家安全局提出的一类重要的轻量分组密码算法.算法整体采用变形的Feistel结构,轮函数是由模加,循环移位和异或组成的ARX模块,其中模加运算为算法主要的非线性部件.目前对于SPECK系列算法的研究主要分为两个方面:一是针对原始SPECK算法安全性的分析,主要的攻击方法包括差分分析、线性分析、积分分析和不可能差分分析等;二是对采用不同移位参数的SPECK型算法的分析,主要包含对它们抗差分分析能力的评估.本文在此基础上研究了采用不同移位参数的SPECK型算法的积分性质和不可能差分性质.我们先利用混合整数线性规划方法,基于可分性搜索了SPECK型算法的积分区分器;接着利用中间相错思想,基于模加运算的差分性质,搜索了SPECK型算法的不可能差分特征.结合已有的差分分析的结论,我们给出了不同分组长度下具有更强抵抗多种攻击能力的好的移位参数.特别的,在减轮情形下,当分组长度为32比特时,我们发现采用移位参数(9,2)的SPECK型算法比原始算法具有更强的抵抗差分分析、积分分析和不可能差分分析的能力.