Search

In a Eurocrypt 2006 article entitled "QUAD: A Practical Stream Cipher with Provable Security," Berbain, Gilbert, and Patarin introduced ${\texttt{QUAD}}$, a parametrized family of stream ciphers. The article stated that "the security of the novel stream cipher is provably reducible to the intractability of the MQ problem"; this reduction deduces the infeasibility of attacks on ${\texttt{QUAD}}$ from the hypothesized infeasibility (with an extra looseness factor) of attacks on the well-known hard problem of solving systems of multivariate quadratic equations over finite fields. The ${\texttt{QUAD}}$ talk at Eurocrypt 2006 reported speeds for ${\texttt{QUAD}}$ instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256). This paper discusses both theoretical and practical aspects of attacking ${\texttt{QUAD}}$ and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance ${\texttt{QUAD}}(256,20,20)$ in approximately 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles. For each of the ${\texttt{QUAD}}$ parameters presented at Eurocrypt 2006, this analysis shows the implications and limitations of the security proofs, pointing out which ${\texttt{QUAD}}$ instances are not secure, and which ones will never be proven secure. Empirical data backs up the theoretical conclusions; in particular, the 245-cycle attack was carried out successfully. [ABSTRACT FROM AUTHOR]

Electronic commerce fundamentally requires two different public-key cryptographical primitives, for key agreement and authentication. We present the new encryption scheme MFE, and provide a performance and security review. MFE belongs to the class, an alternative class of PKCs also termed Polynomial-Based, or multivariate. They depend on multivariate quadratic systems being unsolvable. The classical trapdoors central to PKC's are modular exponentiation for RSA and discrete logarithms for ElGamal/DSA/ECC. But they are relatively slow and will be obsoleted by the arrival of QC (Quantum Computers). The argument for -schemes is that they are usually faster, and there are no known QC-assisted attacks on them. There are several digital signature schemes being investigated today. But encryption (or key exchange schemes) are another story — in fact, only two other -encryption schemes remain unbroken. They are both built along "big-field" lines. In contrast MFE uses medium-sized field extensions, which makes it faster. For security and efficiency, MFE employs an iteratively triangular decryption process which involves rational functions (called by some "tractable rational maps") and taking square roots. We discuss how MFE avoids previously known pitfalls of this genre while addressing its security concerns. Keywords: multivariate () public key cryptosystem, Galois field, extended triangular form, tame-like map, tractable rational map, MFE. [ABSTRACT FROM AUTHOR]

Data security is well-recognized a vital issue in an information system that is supported in an outsource environment. However, most of conventional XML encryption proposals treat confidential parts of an XML document as whole blocks of text and apply encryption algorithms directly on them. As a result, queries involving the encrypted part cannot be efficiently processed. In order to address these problems, we propose XQEnc, a novel approach to support querying encrypted XML. XQEnc is based on two important techniques of vectorization and skeleton compression. Essentially, vectorization, which is a generalization of columns of a relational table, makes use the basic path of an XML tree to label the data values. Skeleton compression collapses the redundant paths into a multiplicity attribute. Our analysis and experimental study shows that XQEnc achieves both better query efficiency and more robust security compared with conventional methods. As an application, we show how XQEnc can be realized with relational techniques to enable secure XML data outsourcing. [ABSTRACT FROM AUTHOR]

Digital signature schemes are crucial for applications in electronic commerce. The effectiveness and security of a digital signature scheme rely on its underlying public key cryptosystem. Trapdoor functions are central to public key cryptosystems. However, the modular exponentiation for RSA or the discrete logarithms for ElGamal/DSA/ECC, as the choice of the trapdoor functions, are relatively slow in performance. Some multivariate schemes has potentially much higher performance than other public key cryptosystems. We present a new multivariate digital signature scheme (TRMS) based on tractable rational maps. We also give some security analysis and some actual implementation data in comparison to some other signature schemes. Keywords: multivariate, public key, digital signature, finite field, tractable rational maps [ABSTRACT FROM AUTHOR]

Multivariate public-key cryptosystems (sometimes polynomial-based PKC's or just multivariates) handle polynomials of many variables over relatively small fields instead of elements of a large ring or group. The "tame-like" or "sparse" class of multivariates are distinguished by the relatively few terms that they have per central equation. We explain how they differ from the "big-field" type of multivariates, represented by derivatives of C∗ and HFE, how they are better, and give basic security criteria for them. The last is shown to be satisfied by efficient schemes called "Enhanced TTS" which is built on a combination of the Oil-and-Vinegar and Triangular ideas. Their security levels are estimated. In this process we summarize and in some cases, improve rank-based attacks, which seek linear combinations of certain matrices at given ranks. These attacks are responsible for breaking many prior multivariate designs. [ABSTRACT FROM AUTHOR]

The XL (eXtended Linearization) equation-solving algorithm belongs to the same extended family as the advanced Gröbner Bases methods F4/F5. XL and its relatives may be used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many "algebraic cryptanalysis" used today. We analyze the applicability and performance of XL and its relatives, particularly for generic systems of equations over medium-sized finite fields. In examining the extended family of Gröbner Bases and XL from theoretical, empirical and practical viewpoints, we add to the general understanding of equation-solving. Moreover, we give rigorous conditions for the successful termination of XL, Gröbner Bases methods and relatives. Thus we have a better grasp of how such algebraic attacks should be applied. We also compute revised security estimates for multivariate cryptosystems. For example, the schemes SFLASHv2 and HFE Challenge 2 are shown to be unbroken by XL variants. Keywords: algebraic analysis, finite field, Gröbner Bases, multivariate quadratics, multivariate cryptography, XL. [ABSTRACT FROM AUTHOR]

With the explosive emerged Web services, the Web becomes a world of information and applications. So portals whose goal is presenting a structured view onto the Web should provide users with a single point access to multiple types of not only information but also services. Recently, many systems have been developed using ontology-driven approaches to automatically generate and manage Web portals. However, all of them lack the integration of Web services. In this paper, we describe SPortS, an OWL-DL(Web Ontology Language-Description Logics) based portal generation system that integrates semantic Web services into generated portals at the presentation level, the data level and the function level. We present the portal generation process, the query decomposition and the service recommendation algorithms through which semantic Web services are integrated tightly into the generated portal. [ABSTRACT FROM AUTHOR]