In December of 2010 NIST selected five SHA-3 finalists - BLAKE, Grcstl, JH, Keccak, and Skein to advance to the third （and final） round of the SHA-3 competition. At present most specialists and scholars focus on the...In December of 2010 NIST selected five SHA-3 finalists - BLAKE, Grcstl, JH, Keccak, and Skein to advance to the third （and final） round of the SHA-3 competition. At present most specialists and scholars focus on the design and the attacks on these hash functions. However, it is very significant to study some properties of their primitives and underlying permutations. Because some properties reflect the pseudo-randomness of the structures. Moreover, they help us to find new cryptanalysis for some block cipher structures. In this paper, we analyze the resistance of JH and Grcstl-512 against structural properties built on integral distinguishers. And then 31.5 （out of 42） rounds integral distinguishers for JH compression function and 11.5 （out of 14） rounds for Grcstl-512 compression function are presented.展开更多
Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex s...Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.展开更多
In this note, we present some detail estimates for the integral with general integer k, as well as a singular integral formed from it, which would be useful for some nonlinear additive problems of primes.
In this paper, we present reduction algorithms based on the principle of Skowron's discernibility matrix - the ordered attributes method. The completeness of the algorithms for Pawlak reduct and the uniqueness for...In this paper, we present reduction algorithms based on the principle of Skowron's discernibility matrix - the ordered attributes method. The completeness of the algorithms for Pawlak reduct and the uniqueness for a given order of the attributes are proved. Since a discernibility matrix requires the size of the memory of U2, U is a universe of objects, it would be impossible to apply these algorithms directly to a massive object set. In order to solve the problem, a so-called quasi-discernibility matrix and two reduction algorithms are proposed. Although the proposed algorithms are incomplete for Pawlak reduct, their opimal paradigms ensure the completeness as long as they satisfy some conditions. Finally we consider the problem on the reduction of distributive object sets.展开更多
There exists a consensus that software architecture (SA) plays a central role in software development and also plays an important role in the lifecycle phases after software delivery. Particularly, SA can be used to r...There exists a consensus that software architecture (SA) plays a central role in software development and also plays an important role in the lifecycle phases after software delivery. Particularly, SA can be used to reduce the great difficulty and cost of software maintenance and evolution. In this paper, runtime software architecture (RSA) based on reflective middleware is proposed to support architecture-based software maintenance and evolution. In this approach, the actual states and behaviors of the runtime system can be observed and manipulated in a consistent and understandable way through its architectural view. Being an accurate, up-to-date, semantic and operable view of SA, RSA looks components and connectors as white-box entities to accurately and thoroughly describe the runtime system, extends traditional architecture description languages to formally describe itself and naturally inherit plentiful semantics in traditional views of SA, and utilizes reflective middleware to observe and manipulate the runtime system. In order to demonstrate the feasibility of this approach, a reflective J2EE application server, called PKUAS, is implemented to observe and manipulate the components, connectors and constraints in the runtime system. Finally, the performance evaluation proves that making RSA explicit and operable at runtime has little effect on the runtime system.展开更多
Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding ...Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpointformulas are formed using predicate variables. An algorithm is developed for model checkingfinite-control mobile ambients against formulas of the logic, providing the first decidabilityresult for model checking a spatial logic with recursion.展开更多
A new semantic model in Abstract State Model (ASM) for authentication protocols is presented. It highlights the Woo-Lam's ideas for authentication, which is the strongest one in Lowe's definition hierarchy for...A new semantic model in Abstract State Model (ASM) for authentication protocols is presented. It highlights the Woo-Lam's ideas for authentication, which is the strongest one in Lowe's definition hierarchy for entity authentication. Apart from the flexible and natural features in forming and analyzing protocols inherited from ASM, the model defines both authentication and secrecy properties explicitly in first order sentences as invariants. The process of proving security properties with respect to an authentication protocol blends the correctness and secrecy properties together to avoid the potential flaws which may happen when treated separately. The security of revised Helsinki protocol is shown as a case study. The new model is different from the previous ones in ASMs.展开更多
In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions b...In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions by monotone span programs. We construct some linear secret sharing schemes. Furthermore, we study the rearrangements of access structures that is very important in practice.展开更多
Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searc...Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searching techniques, the distinguishers are used to attack on 6, 7, 8 and 9 rounds of Camellia with 128-bit key and 8, 9 and 10 rounds of Camellia with 192/256-bit key. The 128-bit key of 6 rounds Camellia can be recovered with 210 chosen plaintexts and 215 encryptions. The 128-bit key of 7 rounds Camellia can be recovered with 212 chosen plaintexts and 254.5 encryptions. The 128-bit key of 8 rounds Camellia can be recovered with 213 chosen plaintexts and 2112.1 encryptions. The 128-bit key of 9 rounds Camellia can be recovered with 2113.6 chosen plaintexts and 2121 encryptions. The 192/256-bit key of 8 rounds Camellia can be recovered with 213 chosen plaintexts and 2111.1 encryptions. The 192/256-bit key of 9 rounds Camellia can be recovered with 213 chosen plaintexts and 2175.6 encryptions. The 256-bit key of 10 rounds Camellia can be recovered with 214 chosen plaintexts and 2239.9 encryptions.展开更多
Some properties of a finite automaton composed of two weakly invertible finite automata with delay 1 are given, where each of those two automata has the output set of each state with the same size. And for a weakly in...Some properties of a finite automaton composed of two weakly invertible finite automata with delay 1 are given, where each of those two automata has the output set of each state with the same size. And for a weakly invertible finite automaton M with delay 2 satisfying the properties mentioned in this paper, two weakly invertible finite automata with delay 1 are constructed such that M is equivalent to a sub-finite-automaton of the composition of those two. So a method to decompose this a kind of weakly invertible finite automata with delay 2 is presented.展开更多
In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily form...In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily formulated based on it. And the congruenceproperties of the bisimulation equivalence can be proved easily. To show the correspondence betweenthe proposed semantics and the well-established ones, the bisimulation is characterized as a versionof barbed equivalence and a version of context bisimulation.展开更多
In order to enforce the least privilege principle in the operating system, it is necessary for the process privilege to be effectively controlled; but this is very difficult because a process always changes as time ch...In order to enforce the least privilege principle in the operating system, it is necessary for the process privilege to be effectively controlled; but this is very difficult because a process always changes as time changes. In this paper, based on the analysis on how the process privilege is generated and how it works, a hierarchy implementing the least privilege principle with three layers, i.e. administration layer, functionality control layer and performance layer, is posed. It is clearly demonstrated that to bound privilege's working scope is a critical part for controlling privilege, but this is only mentioned implicitly while not supported in POSIX capability mechanism. Based on analysis of existing control mechanism for privilege, not only an improved capability inheritance formula but also a new complete formal model for controlling process based on integrating RBAC, DTE, and POSIX capability mechanism is introduced. The new invariants in the model show that this novel privilege control mechanism is different from RBAC's, DTE's, and POSIX's, and it generalizes subdomain control mechanism and makes this mechanism dynamic.展开更多
Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to ...Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.展开更多
Java Beans is a standard for software components. For checkingthe consistency of the Java Beaus semantic constraints with its implementation,this paper proposes a formal Java Beaus Description Language (JBDL) to speci...Java Beans is a standard for software components. For checkingthe consistency of the Java Beaus semantic constraints with its implementation,this paper proposes a formal Java Beaus Description Language (JBDL) to specifycomponent semantic constraints. The JBDL logic is based on many sorted firstorder logic and Computation Tree Logic (CTL), with extension of some facilities inspecifying object oriented features. A framework for dynamic checking Java Beaussemantic constraines in JBDL form is described in this paper and some experimentalresults are showed by examples.展开更多
Orientation update message filtering is an important issue in collaborativevirtual environments (CVEs). Dead-reckoning (DR) is a known effective mechanism for update messagefiltering. Yet, previous dead-reckoning tech...Orientation update message filtering is an important issue in collaborativevirtual environments (CVEs). Dead-reckoning (DR) is a known effective mechanism for update messagefiltering. Yet, previous dead-reckoning techniques mainly focus on the update message filtering forpositions. The existing orientation dead-reckoning algorithms are based on fixed threshold values.The drawbacks of fixed thresholding for orientations (FTO) are discussed in this paper. We propose avariable thresholding for orientations (VTO) based on average recent angular velocity. The mainadvantage of the proposed VTO is the ability of balancing the number of state update messages andshift frequency of direction and speed of rotation.展开更多
NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximati...NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximations are used to analyze NUSH with 64-bit block. When |K| = 128 bits, the complexities of three attacks are (258, 2124), (260, 278) and (262, 255) respectively. When |K| = 192 bits, the complexities of three attacks are (258, 2157) (260, 2%) and (262, 258) respectively. When |K| = 256 bits, the complexities of three attacks are (258, 2125), (260, 278) and (262, 253) respectively. Three linear approximations are used to analyze NUSH with 128-bit block. When |K|= 128 bits, the complexities of three attacks are (2122, 295), (2124, 257) and (2126, 252) respectively. When |K| = 192 bits, the complexities of three attacks are (2122, 2142), (2124, 275) and (2126, 258) respectively. When |K|= 256 bits, the complexities of three attacks are (2122, 2168), (2124, 281) and (2126, 264) respectively. Two linear approximations are used to analyze NUSH with 256-bit block. When |K|= 128 bits, the complexities of two attacks are (2252, 2122) and (2254, 2119) respectively. When |K|= 192 bits, the complexities of two attacks are (2252, 2181) and (2254, 2177) respectively. When |K|=256 bits, the complexities of two attacks are (2252, 2240) and (2254, 2219) respectively. These results show that NUSH is not immune to linear cryptanalysis, and longer key cannot enhance the security of NUSH.展开更多
Let M'=S(Mα,f)be a semi-input-memory finite automaton with input alphabet Y and output alphabet X.If X=Y={0,1},then M' is a feedforware inverse with delay 2 if and only if there exists a cycle c of state diag...Let M'=S(Mα,f)be a semi-input-memory finite automaton with input alphabet Y and output alphabet X.If X=Y={0,1},then M' is a feedforware inverse with delay 2 if and only if there exists a cycle c of state diagram of Mαsuch that f(y0,…,yc,λα（t)0 can be expressed in the form of f ^(1)(y0，…，yc-1,λα（t))+yc for any state t in C and y0,y1,…,yc in Y;or of f^(2)(y0,…，yc-2,λα（t))+yc-c for any state t in Cand y0,y1,…,yc in Y;or for any state t in Cand y0,y1,…yc,in Y,y0,y1…yc satisfies the D[t] condition.The socalled y0,y1…yc satisfying the D[t] condition is that:for some i,j,(i,j)∈{(1,2),(1,3),(2,1),(2,2),(3,1),(3,2)},there exists a (c+2-k)-ary function f^(k),k=1,2,3,such that the Equation(1)and Equation (2)hokl simultaneously for all y'c-2,…,y'c+1∈Y. Equation (1);f(y0,…,yc-i,y'c-i+1,…y'c,λα（t))=f^(j)(y0,…yc-i,λα（t））+y'c-i+1 Equation (2):f(y1,…,yc-j+1,y'c-j+2,…，y'c+1,λα（t））=f^(j)(y1,…,yc-j+1,λα（t））+y'c-j+s where t=δα（t）and if (i,j)=(1,2)then one and only one of the following conditions C1 and C2 holds for all y'c-1,y'c,y'c+1∈Y.Condition C1:there exists a c-ary function g^(1),such that f(y0，…，yc-2,y'c-1,y'c,λα（t））=g^(1),(y0,…,yc-2,λα（t））+y'c-1(+)y'c;Condition C2:there exists a (c-1)-ary functiong g^(2)such that f(y1，…,yc-2,y'c-1,y'c,y'c+1,λα（t））=g^(2)(y1,…,yc-2,λα（t））+y'c-1+y'c,where t=δα(t).展开更多
We present a class of asymptotically optimal successive overrelaxation methods for solving the large sparse system of linear equations. Numerical computations show that these new methods are more efficient and robust ...We present a class of asymptotically optimal successive overrelaxation methods for solving the large sparse system of linear equations. Numerical computations show that these new methods are more efficient and robust than the classical successive overrelaxation method.展开更多
it is of great significance to provide Chinese TrueType font support in X Window. This paper describes the work of adding a Chinese ThueType font ren- derer under X's font support mechanism. First, the origin of t...it is of great significance to provide Chinese TrueType font support in X Window. This paper describes the work of adding a Chinese ThueType font ren- derer under X's font support mechanism. First, the origin of the idea is introduced, followed by a brief study of ThueType font and its rasterization algorithm, then the font support mechanism in X Window is discussed. Finally, an overall illustration of the Chinese ThueType font renderer is given.展开更多
A type checking method for the functional language LFC is presented. A distinct feature of LFC is that it uses Context-Free (CF) languages as data types to represent compound data structures. This makes LFC a dynamica...A type checking method for the functional language LFC is presented. A distinct feature of LFC is that it uses Context-Free (CF) languages as data types to represent compound data structures. This makes LFC a dynamically typed language. To improve efficiency, a practical type checking method is presented, which consists of both static and dynamic type checking. Although the inclusion relation of CF languages is not decidable, a special subset of the relation is decidable, i.e., the sentential form relation, which can be statically checked. Moreover, most of the expressions in actual LFC programs appear to satisfy this relation according to the statistic data of experiments. So, despite that the static type checking is not complete, it undertakes most of the type checking task. Consequently the run-time efficiency is effectively improved. Another feature of the type checking is that it converts the expressions with implicit structures to structured representation. Structure reconstruction technique is presented.展开更多
基金Supported by the National Natural Science Foundation of China (No. 60873259 and No. 60903212)Knowledge Innovation Project of the Chinese Academy of Sciences
文摘In December of 2010 NIST selected five SHA-3 finalists - BLAKE, Grcstl, JH, Keccak, and Skein to advance to the third （and final） round of the SHA-3 competition. At present most specialists and scholars focus on the design and the attacks on these hash functions. However, it is very significant to study some properties of their primitives and underlying permutations. Because some properties reflect the pseudo-randomness of the structures. Moreover, they help us to find new cryptanalysis for some block cipher structures. In this paper, we analyze the resistance of JH and Grcstl-512 against structural properties built on integral distinguishers. And then 31.5 （out of 42） rounds integral distinguishers for JH compression function and 11.5 （out of 14） rounds for Grcstl-512 compression function are presented.
基金Partially supported by the National Natural Science Foundation of China( 1 0 2 71 0 65
文摘Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.
文摘In this note, we present some detail estimates for the integral with general integer k, as well as a singular integral formed from it, which would be useful for some nonlinear additive problems of primes.
文摘In this paper, we present reduction algorithms based on the principle of Skowron's discernibility matrix - the ordered attributes method. The completeness of the algorithms for Pawlak reduct and the uniqueness for a given order of the attributes are proved. Since a discernibility matrix requires the size of the memory of U2, U is a universe of objects, it would be impossible to apply these algorithms directly to a massive object set. In order to solve the problem, a so-called quasi-discernibility matrix and two reduction algorithms are proposed. Although the proposed algorithms are incomplete for Pawlak reduct, their opimal paradigms ensure the completeness as long as they satisfy some conditions. Finally we consider the problem on the reduction of distributive object sets.
文摘There exists a consensus that software architecture (SA) plays a central role in software development and also plays an important role in the lifecycle phases after software delivery. Particularly, SA can be used to reduce the great difficulty and cost of software maintenance and evolution. In this paper, runtime software architecture (RSA) based on reflective middleware is proposed to support architecture-based software maintenance and evolution. In this approach, the actual states and behaviors of the runtime system can be observed and manipulated in a consistent and understandable way through its architectural view. Being an accurate, up-to-date, semantic and operable view of SA, RSA looks components and connectors as white-box entities to accurately and thoroughly describe the runtime system, extends traditional architecture description languages to formally describe itself and naturally inherit plentiful semantics in traditional views of SA, and utilizes reflective middleware to observe and manipulate the runtime system. In order to demonstrate the feasibility of this approach, a reflective J2EE application server, called PKUAS, is implemented to observe and manipulate the components, connectors and constraints in the runtime system. Finally, the performance evaluation proves that making RSA explicit and operable at runtime has little effect on the runtime system.
文摘Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpointformulas are formed using predicate variables. An algorithm is developed for model checkingfinite-control mobile ambients against formulas of the logic, providing the first decidabilityresult for model checking a spatial logic with recursion.
基金国家自然科学基金，国家高技术研究发展计划(863计划)，国家重点基础研究发展计划(973计划)，the Foundation for Extraordinary Young Researchers under
文摘A new semantic model in Abstract State Model (ASM) for authentication protocols is presented. It highlights the Woo-Lam's ideas for authentication, which is the strongest one in Lowe's definition hierarchy for entity authentication. Apart from the flexible and natural features in forming and analyzing protocols inherited from ASM, the model defines both authentication and secrecy properties explicitly in first order sentences as invariants. The process of proving security properties with respect to an authentication protocol blends the correctness and secrecy properties together to avoid the potential flaws which may happen when treated separately. The security of revised Helsinki protocol is shown as a case study. The new model is different from the previous ones in ASMs.
文摘In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions by monotone span programs. We construct some linear secret sharing schemes. Furthermore, we study the rearrangements of access structures that is very important in practice.
基金supported by the National Natural Science Foundation of China(Grant No.60373047)the State 863 Project(Grant No.2003AA144030)973 Project(Grant No.2004CB318004)
文摘Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searching techniques, the distinguishers are used to attack on 6, 7, 8 and 9 rounds of Camellia with 128-bit key and 8, 9 and 10 rounds of Camellia with 192/256-bit key. The 128-bit key of 6 rounds Camellia can be recovered with 210 chosen plaintexts and 215 encryptions. The 128-bit key of 7 rounds Camellia can be recovered with 212 chosen plaintexts and 254.5 encryptions. The 128-bit key of 8 rounds Camellia can be recovered with 213 chosen plaintexts and 2112.1 encryptions. The 128-bit key of 9 rounds Camellia can be recovered with 2113.6 chosen plaintexts and 2121 encryptions. The 192/256-bit key of 8 rounds Camellia can be recovered with 213 chosen plaintexts and 2111.1 encryptions. The 192/256-bit key of 9 rounds Camellia can be recovered with 213 chosen plaintexts and 2175.6 encryptions. The 256-bit key of 10 rounds Camellia can be recovered with 214 chosen plaintexts and 2239.9 encryptions.
文摘Some properties of a finite automaton composed of two weakly invertible finite automata with delay 1 are given, where each of those two automata has the output set of each state with the same size. And for a weakly invertible finite automaton M with delay 2 satisfying the properties mentioned in this paper, two weakly invertible finite automata with delay 1 are constructed such that M is equivalent to a sub-finite-automaton of the composition of those two. So a method to decompose this a kind of weakly invertible finite automata with delay 2 is presented.
文摘In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily formulated based on it. And the congruenceproperties of the bisimulation equivalence can be proved easily. To show the correspondence betweenthe proposed semantics and the well-established ones, the bisimulation is characterized as a versionof barbed equivalence and a version of context bisimulation.
基金supported by the National Key Basic Research Program of China(Grant No.G1999035802)the National Natural Science Foundation of China(Grant No.60083007)
文摘In order to enforce the least privilege principle in the operating system, it is necessary for the process privilege to be effectively controlled; but this is very difficult because a process always changes as time changes. In this paper, based on the analysis on how the process privilege is generated and how it works, a hierarchy implementing the least privilege principle with three layers, i.e. administration layer, functionality control layer and performance layer, is posed. It is clearly demonstrated that to bound privilege's working scope is a critical part for controlling privilege, but this is only mentioned implicitly while not supported in POSIX capability mechanism. Based on analysis of existing control mechanism for privilege, not only an improved capability inheritance formula but also a new complete formal model for controlling process based on integrating RBAC, DTE, and POSIX capability mechanism is introduced. The new invariants in the model show that this novel privilege control mechanism is different from RBAC's, DTE's, and POSIX's, and it generalizes subdomain control mechanism and makes this mechanism dynamic.
文摘Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.
文摘Java Beans is a standard for software components. For checkingthe consistency of the Java Beaus semantic constraints with its implementation,this paper proposes a formal Java Beaus Description Language (JBDL) to specifycomponent semantic constraints. The JBDL logic is based on many sorted firstorder logic and Computation Tree Logic (CTL), with extension of some facilities inspecifying object oriented features. A framework for dynamic checking Java Beaussemantic constraines in JBDL form is described in this paper and some experimentalresults are showed by examples.
文摘Orientation update message filtering is an important issue in collaborativevirtual environments (CVEs). Dead-reckoning (DR) is a known effective mechanism for update messagefiltering. Yet, previous dead-reckoning techniques mainly focus on the update message filtering forpositions. The existing orientation dead-reckoning algorithms are based on fixed threshold values.The drawbacks of fixed thresholding for orientations (FTO) are discussed in this paper. We propose avariable thresholding for orientations (VTO) based on average recent angular velocity. The mainadvantage of the proposed VTO is the ability of balancing the number of state update messages andshift frequency of direction and speed of rotation.
基金This work was supported by 973 Project (Grant No. G1999035802) and the National Natural Science Foundation of China (Grant No. 19931010) .
文摘NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximations are used to analyze NUSH with 64-bit block. When |K| = 128 bits, the complexities of three attacks are (258, 2124), (260, 278) and (262, 255) respectively. When |K| = 192 bits, the complexities of three attacks are (258, 2157) (260, 2%) and (262, 258) respectively. When |K| = 256 bits, the complexities of three attacks are (258, 2125), (260, 278) and (262, 253) respectively. Three linear approximations are used to analyze NUSH with 128-bit block. When |K|= 128 bits, the complexities of three attacks are (2122, 295), (2124, 257) and (2126, 252) respectively. When |K| = 192 bits, the complexities of three attacks are (2122, 2142), (2124, 275) and (2126, 258) respectively. When |K|= 256 bits, the complexities of three attacks are (2122, 2168), (2124, 281) and (2126, 264) respectively. Two linear approximations are used to analyze NUSH with 256-bit block. When |K|= 128 bits, the complexities of two attacks are (2252, 2122) and (2254, 2119) respectively. When |K|= 192 bits, the complexities of two attacks are (2252, 2181) and (2254, 2177) respectively. When |K|=256 bits, the complexities of two attacks are (2252, 2240) and (2254, 2219) respectively. These results show that NUSH is not immune to linear cryptanalysis, and longer key cannot enhance the security of NUSH.
文摘Let M'=S(Mα,f)be a semi-input-memory finite automaton with input alphabet Y and output alphabet X.If X=Y={0,1},then M' is a feedforware inverse with delay 2 if and only if there exists a cycle c of state diagram of Mαsuch that f(y0,…,yc,λα（t)0 can be expressed in the form of f ^(1)(y0，…，yc-1,λα（t))+yc for any state t in C and y0,y1,…,yc in Y;or of f^(2)(y0,…，yc-2,λα（t))+yc-c for any state t in Cand y0,y1,…,yc in Y;or for any state t in Cand y0,y1,…yc,in Y,y0,y1…yc satisfies the D[t] condition.The socalled y0,y1…yc satisfying the D[t] condition is that:for some i,j,(i,j)∈{(1,2),(1,3),(2,1),(2,2),(3,1),(3,2)},there exists a (c+2-k)-ary function f^(k),k=1,2,3,such that the Equation(1)and Equation (2)hokl simultaneously for all y'c-2,…,y'c+1∈Y. Equation (1);f(y0,…,yc-i,y'c-i+1,…y'c,λα（t))=f^(j)(y0,…yc-i,λα（t））+y'c-i+1 Equation (2):f(y1,…,yc-j+1,y'c-j+2,…，y'c+1,λα（t））=f^(j)(y1,…,yc-j+1,λα（t））+y'c-j+s where t=δα（t）and if (i,j)=(1,2)then one and only one of the following conditions C1 and C2 holds for all y'c-1,y'c,y'c+1∈Y.Condition C1:there exists a c-ary function g^(1),such that f(y0，…，yc-2,y'c-1,y'c,λα（t））=g^(1),(y0,…,yc-2,λα（t））+y'c-1(+)y'c;Condition C2:there exists a (c-1)-ary functiong g^(2)such that f(y1，…,yc-2,y'c-1,y'c,y'c+1,λα（t））=g^(2)(y1,…,yc-2,λα（t））+y'c-1+y'c,where t=δα(t).
基金Subsidized by the Special Funds For Major State Basic Research Project G1999032803.
文摘We present a class of asymptotically optimal successive overrelaxation methods for solving the large sparse system of linear equations. Numerical computations show that these new methods are more efficient and robust than the classical successive overrelaxation method.
基金High Technology Key Project in the National 9th. Five-Year Plan.
文摘it is of great significance to provide Chinese TrueType font support in X Window. This paper describes the work of adding a Chinese ThueType font ren- derer under X's font support mechanism. First, the origin of the idea is introduced, followed by a brief study of ThueType font and its rasterization algorithm, then the font support mechanism in X Window is discussed. Finally, an overall illustration of the Chinese ThueType font renderer is given.
文摘A type checking method for the functional language LFC is presented. A distinct feature of LFC is that it uses Context-Free (CF) languages as data types to represent compound data structures. This makes LFC a dynamically typed language. To improve efficiency, a practical type checking method is presented, which consists of both static and dynamic type checking. Although the inclusion relation of CF languages is not decidable, a special subset of the relation is decidable, i.e., the sentential form relation, which can be statically checked. Moreover, most of the expressions in actual LFC programs appear to satisfy this relation according to the statistic data of experiments. So, despite that the static type checking is not complete, it undertakes most of the type checking task. Consequently the run-time efficiency is effectively improved. Another feature of the type checking is that it converts the expressions with implicit structures to structured representation. Structure reconstruction technique is presented.
