Distributed cryptographic computing system plays an important role since cryptographic computing is extremely computation sensitive. However, no general cryptographic computing system is available. Grid technology can...Distributed cryptographic computing system plays an important role since cryptographic computing is extremely computation sensitive. However, no general cryptographic computing system is available. Grid technology can give an efficient computational support for cryptographic applications. Therefore, a general-purpose grid-based distributed computing system called DCCS is put forward in this paper. The architecture of DCCS is simply described at first. The policy of task division adapted in DCCS is then presented. The method to manage subtask is further discussed in detail. Furthermore, the building and execution process of a computing job is revealed. Finally, the details of DCCS implementation under Globus Toolkit 4 are illustrated.展开更多
Nonlinear feedback shift registers(NFSRs) have been used in many stream ciphers for cryptographic security. The linearization of NFSRs is to describe their state transitions using some matrices. Such matrices are call...Nonlinear feedback shift registers(NFSRs) have been used in many stream ciphers for cryptographic security. The linearization of NFSRs is to describe their state transitions using some matrices. Such matrices are called their state transition matrices. Compared to extensive work on binary NFSRs, much less work has been done on multi-valued NFSRs. This paper uses a semi-tensor product approach to investigate the linearization of multi-valued NFSRs, by viewing them as logical networks. A new state transition matrix is found for a multi-valued NFSR, which can be simply computed from the truth table of its feedback function. The new state transition matrix is easier to compute and is more explicit than the existing results. Some properties of the state transition matrix are provided as well, which are helpful to theoretically analyze multi-valued NFSRs.展开更多
Some techniques using linear algebra was introduced by Faugère in F4 to speed up the reduction process during Gr?bner basis computations.These techniques can also be used in fast implementations of F5 and some ot...Some techniques using linear algebra was introduced by Faugère in F4 to speed up the reduction process during Gr?bner basis computations.These techniques can also be used in fast implementations of F5 and some other signature-based Gr?bner basis algorithms.When these techniques are applied,a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function(given in F4).Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function,this step can be very costly when the number of involved polynomials/monomials is huge.In this paper,multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported.Many examples have been tested by using this method,and the experimental data shows that the new method is very efficient.展开更多
In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash func...In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.展开更多
Motivated by applications in advanced cryptographic protocols,research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years.In this paper,the authors f...Motivated by applications in advanced cryptographic protocols,research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years.In this paper,the authors focus on on the collision attacks for a family of arithmetization-oriented symmetric ciphers GMiMCHash.The authors firstly enhance the algebraically controlled differential attacks proposed by introducing more variables.Then,combining algebraic attacks and differential attacks,the authors propose algebraic-differential attacks on GMi MCHash.This attack method is shown to be effective by experiments on toy versions of GMi MCHash.The authors further introduce some tricks to reduce the complexities of algebraic-differential attacks and improve the success probability of finding collisions.展开更多
In this paper, we propose a new lightweight block cipher named RECTANGLE. The main idea of the design of RECTANGLE is to allow lightweight and fast implementations using bit-slice techniques. RECTANGLE uses an SP-netw...In this paper, we propose a new lightweight block cipher named RECTANGLE. The main idea of the design of RECTANGLE is to allow lightweight and fast implementations using bit-slice techniques. RECTANGLE uses an SP-network. The substitution layer consists of 16 4 × 4 S-boxes in parallel. The permutation layer is composed of 3 rotations. As shown in this paper, RECTANGLE offers great performance in both hardware and software environment, which provides enough flexibility for different application scenario. The following are3 main advantages of RECTANGLE. First, RECTANGLE is extremely hardware-friendly. For the 80-bit key version, a one-cycle-per-round parallel implementation only needs 1600 gates for a throughput of 246 Kbits/s at100 k Hz clock and an energy efficiency of 3.0 p J/bit. Second, RECTANGLE achieves a very competitive software speed among the existing lightweight block ciphers due to its bit-slice style. Using 128-bit SSE instructions,a bit-slice implementation of RECTANGLE reaches an average encryption speed of about 3.9 cycles/byte for messages around 3000 bytes. Last but not least, we propose new design criteria for the RECTANGLE S-box.Due to our careful selection of the S-box and the asymmetric design of the permutation layer, RECTANGLE achieves a very good security-performance tradeoff. Our extensive and deep security analysis shows that the highest number of rounds that we can attack, is 18(out of 25).展开更多
This paper is twofold. The first is devoted to study a class of quadratic rotation symmetric S-boxes(RSSBs) which was presented by Gao G, et al., Constructions of quadratic and cubic rotation symmetric bent functions,...This paper is twofold. The first is devoted to study a class of quadratic rotation symmetric S-boxes(RSSBs) which was presented by Gao G, et al., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Transactions on Information Theory, vol. 58, no. 7, pp. 4908 –4913, 2012, by decomposing a class of cubic rotation symmetric bent functions. The authors obtain its nonlinearity and differential uniformity of such class of S-boxes. In particular, the compositional inversion of the class of rotation symmetric S-boxes is also presented. Then the authors introduce a steepest-descent-like search algorithm for the generation of RSSBs. The algorithm finds 5,6,7,8-bit RSSBs with very good cryptographic properties which can be applied in designing cryptographical algorithms.展开更多
The GVW algorithm is an effcient signature-based algorithm for computing Gr?bner bases.In this paper, the authors consider the implementation of the GVW algorithm by using linear algebra,and speed up GVW via a substit...The GVW algorithm is an effcient signature-based algorithm for computing Gr?bner bases.In this paper, the authors consider the implementation of the GVW algorithm by using linear algebra,and speed up GVW via a substituting method. As it is well known that, most of the computing time of a Gr?bner basis is spent on reductions of polynomials. Thus, linear algebraic techniques, such as matrix operations, have been used extensively to speed up the implementations. Particularly, one-direction(also called signature-safe) reduction is used in signature-based algorithms, because polynomials(or rows in matrices) with larger signatures can only be reduced by polynomials(rows) with smaller signatures. The authors propose a new method to construct sparser matrices for signature-based algorithms via a substituting method. Speci?cally, instead of only storing the original polynomials in GVW, the authors also record many equivalent but sparser polynomials at the same time. In matrix construction, denser polynomials are substituted by sparser equivalent ones. As the matrices get sparser, they can be eliminated more effciently. Two speci?cal algorithms, Block-GVW and LMGVW, are presented, and their combination is the Sub-GVW algorithm. The correctness of the new proposed method is proved, and the experimental results demonstrate the effciency of this new method.展开更多
A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations (TDPs for short) was built to perform long messages directly. The new scheme follows the Idea "scramble all, and encrypt small",...A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations (TDPs for short) was built to perform long messages directly. The new scheme follows the Idea "scramble all, and encrypt small", using some scrambling operation on message m along with the user's Identities, and then passing, In paraliel, small parts of the scrambling result through corresponding TOPs. This design enables the scheme to flexibly perform long messages of arbitrary length while avoid repeatedly invoking TDP operations such as the CBC mode, or verbosely black-box composing symmetric encryption and slgncryption, resulting in noticeable practical sevlngs in both message bandwidth and efficiency. Concretely, the signcryptlon scheme requires exactly one computation of the "receiver's TDP" (for "encryptlon") and one Inverse computation of the "sender's TDP" (for "authentication"), which Is of great practical significance in directly performing long messages, since the major bottleneck for many public encryptlon schemes is the excessive computational overhead of performing TDP operations. Cutting out the verbosely repeated padding, the newly proposed scheme Is more efficient than a black-box hybrid scheme. Most importantly, the proposed scheme has been proven to be tightly semanUcaiiy secure under adaptive chosen clphertext attacks (iND-CCA2) and to provide integrity of clphertext (INT-CTXT) as well as non-repudiation in the random oracle model. All of these security guarantees are provided in the full multi-user, insider-security setting. Moreover, though the scheme is designed to perform long messages, it may also be appropriate for settings where It is Impractical to perform large block of messages (i.e. extremely low memory environments such as smart cards).展开更多
Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f...Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f).For a given NFSR(f),if there exists an affine Boolean function l such that G(l)?G(f),then G(l)is called an affine sub-family of NFSR(f).In this paper,by skillfully combining previous ideas,the authors give a new upper bound on the order of affine sub-families of NFSR(f).Compared with the four known bounds,the bound is better than three of them,and in some cases is also better than the rest one.展开更多
The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of cou...The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate public key cryptosystem.In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX2qi when char(Fq) = 2,which implies that these polynomials are all weak IP instances.Moreover,we study the cardinality of an equivalence class containing the binomial aX 2q i + bX 2qj(i=j) over Fqn without the restriction that char(Fq) = 2,which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.展开更多
In this paper,a new method to analyze Boolean functions is proposed.By this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial Boolean functions.The basic idea of th...In this paper,a new method to analyze Boolean functions is proposed.By this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial Boolean functions.The basic idea of this method is to compute the refined covers of some parametric Boolean polynomial systems which are equivalent to these problems.By a refined cover,the parameter space is divided into several disjoint components,and on each component,the parametric Boolean polynomial system has a fixed number of solutions.An efficient algorithm based on the characteristic set method to compute refined covers of parametric Boolean polynomial systems is presented.The experimental results about some instances generated from cryptanalysis show that this new method is efficient and can solve some instances which can not be solved in reasonable time by other methods.展开更多
Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-prot...Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.展开更多
基金Supported by the National Basic Research Program of China (973 Program 2004CB318004), the National Natural Science Foundation of China (NSFC90204016) and the National High Technology Research and Development Program of China (2003AA144030)
文摘Distributed cryptographic computing system plays an important role since cryptographic computing is extremely computation sensitive. However, no general cryptographic computing system is available. Grid technology can give an efficient computational support for cryptographic applications. Therefore, a general-purpose grid-based distributed computing system called DCCS is put forward in this paper. The architecture of DCCS is simply described at first. The policy of task division adapted in DCCS is then presented. The method to manage subtask is further discussed in detail. Furthermore, the building and execution process of a computing job is revealed. Finally, the details of DCCS implementation under Globus Toolkit 4 are illustrated.
基金supported by the National Science Foundation of China under Grant Nos.61379139and 11526215the"Strategic Priority Research Program"of the Chinese Academy of Sciences,under Grant No.XDA06010701
文摘Nonlinear feedback shift registers(NFSRs) have been used in many stream ciphers for cryptographic security. The linearization of NFSRs is to describe their state transitions using some matrices. Such matrices are called their state transition matrices. Compared to extensive work on binary NFSRs, much less work has been done on multi-valued NFSRs. This paper uses a semi-tensor product approach to investigate the linearization of multi-valued NFSRs, by viewing them as logical networks. A new state transition matrix is found for a multi-valued NFSR, which can be simply computed from the truth table of its feedback function. The new state transition matrix is easier to compute and is more explicit than the existing results. Some properties of the state transition matrix are provided as well, which are helpful to theoretically analyze multi-valued NFSRs.
基金supported by the National Key Basic Research Program of China under Grant Nos.2013CB834203 and 2011CB302400the National Nature Science Foundation of China under Grant Nos.11301523,11371356,61121062+1 种基金the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDA06010701IEE’s Research Project on Cryptography under Grant Nos.Y3Z0013102,Y3Z0018102,and Y4Z0061A02
文摘Some techniques using linear algebra was introduced by Faugère in F4 to speed up the reduction process during Gr?bner basis computations.These techniques can also be used in fast implementations of F5 and some other signature-based Gr?bner basis algorithms.When these techniques are applied,a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function(given in F4).Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function,this step can be very costly when the number of involved polynomials/monomials is huge.In this paper,multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported.Many examples have been tested by using this method,and the experimental data shows that the new method is very efficient.
基金supported by National Natural Science Foundation of China(Grant No.60970152)IIE's Research Project on Cryptography(Grant No.Y3Z0011102)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA06010701)National Key Basic Research Program of China(973 Program)(Grant No.2011CB302400)
文摘In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.
基金supported by the National Natural Science Foundation of China under Grant No.61972393the Climbing Program from Institute of Information Engineering CAS under Grant No.E3Z0221112。
文摘Motivated by applications in advanced cryptographic protocols,research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years.In this paper,the authors focus on on the collision attacks for a family of arithmetization-oriented symmetric ciphers GMiMCHash.The authors firstly enhance the algebraically controlled differential attacks proposed by introducing more variables.Then,combining algebraic attacks and differential attacks,the authors propose algebraic-differential attacks on GMi MCHash.This attack method is shown to be effective by experiments on toy versions of GMi MCHash.The authors further introduce some tricks to reduce the complexities of algebraic-differential attacks and improve the success probability of finding collisions.
基金supported by National Natural Science Foundation of China(Grant No.61379138)Research Fund KU Leuven(OT/13/071)+1 种基金"Strategic Priority Research Program"of the Chinese Academy of Sciences(Grant No.XDA06010701)National High-tech R&D Program of China(863 Program)(Grant No.2013AA014002)
文摘In this paper, we propose a new lightweight block cipher named RECTANGLE. The main idea of the design of RECTANGLE is to allow lightweight and fast implementations using bit-slice techniques. RECTANGLE uses an SP-network. The substitution layer consists of 16 4 × 4 S-boxes in parallel. The permutation layer is composed of 3 rotations. As shown in this paper, RECTANGLE offers great performance in both hardware and software environment, which provides enough flexibility for different application scenario. The following are3 main advantages of RECTANGLE. First, RECTANGLE is extremely hardware-friendly. For the 80-bit key version, a one-cycle-per-round parallel implementation only needs 1600 gates for a throughput of 246 Kbits/s at100 k Hz clock and an energy efficiency of 3.0 p J/bit. Second, RECTANGLE achieves a very competitive software speed among the existing lightweight block ciphers due to its bit-slice style. Using 128-bit SSE instructions,a bit-slice implementation of RECTANGLE reaches an average encryption speed of about 3.9 cycles/byte for messages around 3000 bytes. Last but not least, we propose new design criteria for the RECTANGLE S-box.Due to our careful selection of the S-box and the asymmetric design of the permutation layer, RECTANGLE achieves a very good security-performance tradeoff. Our extensive and deep security analysis shows that the highest number of rounds that we can attack, is 18(out of 25).
基金supported by the National Nature Science Foundation of China under Grant Nos.61872381,61872359,61862011,and 61402522supported by Guangxi Key Laboratory of Cryptography and Information Security under Grant No.GCIS201704
文摘This paper is twofold. The first is devoted to study a class of quadratic rotation symmetric S-boxes(RSSBs) which was presented by Gao G, et al., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Transactions on Information Theory, vol. 58, no. 7, pp. 4908 –4913, 2012, by decomposing a class of cubic rotation symmetric bent functions. The authors obtain its nonlinearity and differential uniformity of such class of S-boxes. In particular, the compositional inversion of the class of rotation symmetric S-boxes is also presented. Then the authors introduce a steepest-descent-like search algorithm for the generation of RSSBs. The algorithm finds 5,6,7,8-bit RSSBs with very good cryptographic properties which can be applied in designing cryptographical algorithms.
基金supported by the National Nature Science Foundation of China under Grant Nos.61877058,61872359the Strategy Cooperation Project under Grant No.AQ-1701the CAS Project under Grant No.QYZDJ-SSW-SYS022
文摘The GVW algorithm is an effcient signature-based algorithm for computing Gr?bner bases.In this paper, the authors consider the implementation of the GVW algorithm by using linear algebra,and speed up GVW via a substituting method. As it is well known that, most of the computing time of a Gr?bner basis is spent on reductions of polynomials. Thus, linear algebraic techniques, such as matrix operations, have been used extensively to speed up the implementations. Particularly, one-direction(also called signature-safe) reduction is used in signature-based algorithms, because polynomials(or rows in matrices) with larger signatures can only be reduced by polynomials(rows) with smaller signatures. The authors propose a new method to construct sparser matrices for signature-based algorithms via a substituting method. Speci?cally, instead of only storing the original polynomials in GVW, the authors also record many equivalent but sparser polynomials at the same time. In matrix construction, denser polynomials are substituted by sparser equivalent ones. As the matrices get sparser, they can be eliminated more effciently. Two speci?cal algorithms, Block-GVW and LMGVW, are presented, and their combination is the Sub-GVW algorithm. The correctness of the new proposed method is proved, and the experimental results demonstrate the effciency of this new method.
基金Supported by the National Basic Research Program (Grant No. 2004CB318004)the National Natural Science Foundation of China (Grant Nos. 60373047 and 90604036)
文摘A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations (TDPs for short) was built to perform long messages directly. The new scheme follows the Idea "scramble all, and encrypt small", using some scrambling operation on message m along with the user's Identities, and then passing, In paraliel, small parts of the scrambling result through corresponding TOPs. This design enables the scheme to flexibly perform long messages of arbitrary length while avoid repeatedly invoking TDP operations such as the CBC mode, or verbosely black-box composing symmetric encryption and slgncryption, resulting in noticeable practical sevlngs in both message bandwidth and efficiency. Concretely, the signcryptlon scheme requires exactly one computation of the "receiver's TDP" (for "encryptlon") and one Inverse computation of the "sender's TDP" (for "authentication"), which Is of great practical significance in directly performing long messages, since the major bottleneck for many public encryptlon schemes is the excessive computational overhead of performing TDP operations. Cutting out the verbosely repeated padding, the newly proposed scheme Is more efficient than a black-box hybrid scheme. Most importantly, the proposed scheme has been proven to be tightly semanUcaiiy secure under adaptive chosen clphertext attacks (iND-CCA2) and to provide integrity of clphertext (INT-CTXT) as well as non-repudiation in the random oracle model. All of these security guarantees are provided in the full multi-user, insider-security setting. Moreover, though the scheme is designed to perform long messages, it may also be appropriate for settings where It is Impractical to perform large block of messages (i.e. extremely low memory environments such as smart cards).
基金supported by the National Natural Science Foundation of China under Grant Nos.61872383,61379139,and 11701553part by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDA06010701+2 种基金supported by National Postdoctoral Program for Innovative Talents(BX201600188)China Postdoctoral Science Foundation Funded Project(2017M611035)Young Elite Scientists Sponsorship Program by CAST(2016QNRC001).
文摘Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f).For a given NFSR(f),if there exists an affine Boolean function l such that G(l)?G(f),then G(l)is called an affine sub-family of NFSR(f).In this paper,by skillfully combining previous ideas,the authors give a new upper bound on the order of affine sub-families of NFSR(f).Compared with the four known bounds,the bound is better than three of them,and in some cases is also better than the rest one.
基金supported by National Basic Research Program of China (973 Program)(Grant No. 2011CB302400)National Natural Science Foundation of China (Grant No. 60970152)Grand Project of Institute of Software (Grant No. YOCX285056)
文摘The isomorphism of polynomials(IP),one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials.Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate public key cryptosystem.In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX2qi when char(Fq) = 2,which implies that these polynomials are all weak IP instances.Moreover,we study the cardinality of an equivalence class containing the binomial aX 2q i + bX 2qj(i=j) over Fqn without the restriction that char(Fq) = 2,which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.
基金the National Natural Science Foundation of China under Grant Nos.61977060 and 61877058。
文摘In this paper,a new method to analyze Boolean functions is proposed.By this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial Boolean functions.The basic idea of this method is to compute the refined covers of some parametric Boolean polynomial systems which are equivalent to these problems.By a refined cover,the parameter space is divided into several disjoint components,and on each component,the parametric Boolean polynomial system has a fixed number of solutions.An efficient algorithm based on the characteristic set method to compute refined covers of parametric Boolean polynomial systems is presented.The experimental results about some instances generated from cryptanalysis show that this new method is efficient and can solve some instances which can not be solved in reasonable time by other methods.
基金Supported by the National Natural Science Foundation of China (Grant No. 60673069)the National Basic Research Program (Grant No. 2004CB318004)
文摘Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.