Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions

A pseudo-random function is a fundamental cryptographic primitive that is essential for encryption, identification, and authentication. We present a new cryptographic primitive called pseudo-random synthesizer and show how to use it in order to get a parallel construction of a pseudo-random function. We show severalNC¹implementations of synthesizers based on concrete intractability assumptions as factoring and the Diffie–Hellman assumption. This yields the first parallel pseudo-random functions (based on standard intractability assumptions) and the only alternative to the original construction of Goldreich, Goldwasser, and Micali. In addition, we show parallel constructions of synthesizers based on other primitives such as weak pseudo-random functions or trapdoor one-way permutations. The security of all our constructions is similar to the security of the underlying assumptions. The connection with problems in computational learning theory is discussed.     

Further Results on Asymmetric Authentication Schemes

This paper derives some further results on unconditionally secure asymmetric authentication schemes. It starts by giving a general framework for constructing A²-codes, identifying many known constructions as special cases. Then a full treatment of A³-codes (A²-codes protecting against arbiter's attacks) is given, including bounds on the parameters and optimal constructions. With these models as a basis, we proceed by giving constructions of general asymmetric authentication schemes, i.e., schemes protecting against specified arbitrary sets of participants collaborating in order to cheat someone else. As a consequence, we improve upon Chaum and Roijakkers interactive construction of unconditionally secure digital signatures and present a (noninteractive) construction in the form of a code. In addition, we also show a few bounds for this general model, proving the optimality of some constructions.     

基于双线性群的同态承诺方案

承诺方案是一种基本而用途广泛的密码学原语,其在数学签名方案、电子支付协议、零知识协议以及安全多方计算协议等方面有着重要应用,因而成为密码学领域重要的研究课题之一.从设计思想来看,大多数有效承诺方案的构造都可纳入q单向群同态这一框架.但q单向性是一种极强的要求,使得其在实例化时可供选择的群结构受到限制.如何突破限制寻求新途径就成为承诺方案构造方面的重要课题.首次基于合数阶双线性群分别构造了无条件隐藏的陷门承诺方案以及无条件绑定的承诺方案,同时证明了在子群判定假设下这两个承诺方案分别是计算上绑定和计算上隐藏的.由于双线性群支持双线性映射,这些承诺方案除具备通常的线性同态性质外还具备特有的乘性同态性质.     

Generic Transformation from Weakly to Strongly Unforgeable Signatures

Current techniques for transforming unforgeable signature schemes （the forged message has never been signed） to strongly unforgeable ones （the forged message could have been signed） require supplementary components to be added onto the original key pairs of the schemes. In addition, some of them can only be applied to a certain type of signature schemes. In this paper, we propose a new generic transformation technique which converts any unforgeable signature scheme into a strongly unforgeable one without modifying any component in the original key pair. This makes our technique especially compatible for practical use. Our technique is based on strong one-time signature schemes. We show that they can be constructed efficiently from any one-time signature scheme that is based on one-way functions. The performance of our technique also compares favorably with that of current ones. Besides, it is shown in this paper that our transformation can further be applied to schemes satisfying only a weak variant of unforgeability without any further modification. Furthermore, our technique can also be used for constructing strongly unforgeable signature schemes in other cryptographic settings which include certificateless signature, identity-based signature, and several others. To the best of our knowledge, similar extent of versatility is not known to be supported by any of those comparable techniques. Finally and of independent interest, we show that our generic transformation technique can be modified to an on-line/off-line signature scheme, which possesses a very efficient signing process.     

Robust codes and robust,fault-tolerant architectures of the Advanced Encryption Standard

Hardware implementations of cryptographic algorithms are vulnerable to fault analysis attacks. Methods based on traditional fault-tolerant architectures are not suited for protection against these attacks. To detect these attacks we propose an architecture based on robust nonlinear systematic error-detecting codes. These nonlinear codes are capable of providing uniform error detecting coverage independently of the error distributions. They make no assumptions about what faults or errors will be injected by an attacker. Architectures based on these robust constructions have fewer undetectable errors than linear codes with the same n, k. We present the general properties and construction methods of these codes as well as their application for the protection of a cryptographic devices implementing the Advanced Encryption Standard.     

Non-interactive multisignatures in the plain public-key model with efficient verification

Multisignatures extend standard digital signatures to allow an ad hoc set of users to jointly sign a message. Multisignature schemes are often evaluated from the following perspectives: (1) the cryptographic assumptions underlying the schemes; (2) the operational assumptions about the bootstrapping of the schemes in practice; (3) the number of communication rounds for signing a message; (4) the time complexity for signing a message; (5) the amount of communication for signing a message; (6) the time complexity for verifying a multisignature; (7) the length of the resulting multisignatures. Existing multisignature schemes achieve various trade-offs among these measures, but none of them can achieve simultaneously the desired properties with respect to all (or even most) of these measures. In this paper, we present a novel multisignature scheme that offers desired properties with respect to the above (1)–(7) simultaneously, except that it uses random oracles (which however are often required in order to design practical schemes). In particular, our scheme is featured by its weak operational (i.e., plain public-key) model, non-interactive signing, and efficient verification.     

Non-interactive multisignatures in the plain public-key model with efficient verification

Multisignatures extend standard digital signatures to allow an ad hoc set of users to jointly sign a message. Multisignature schemes are often evaluated from the following perspectives: (1) the cryptographic assumptions underlying the schemes; (2) the operational assumptions about the bootstrapping of the schemes in practice; (3) the number of communication rounds for signing a message; (4) the time complexity for signing a message; (5) the amount of communication for signing a message; (6) the time complexity for verifying a multisignature; (7) the length of the resulting multisignatures. Existing multisignature schemes achieve various trade-offs among these measures, but none of them can achieve simultaneously the desired properties with respect to all (or even most) of these measures. In this paper, we present a novel multisignature scheme that offers desired properties with respect to the above (1)-(7) simultaneously, except that it uses random oracles (which however are often required in order to design practical schemes). In particular, our scheme is featured by its weak operational (i.e., plain public-key) model, non-interactive signing, and efficient verification.     

Active learning for extended finite state machines

We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards.Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.     

Efficient key insulated attribute based signature without bilinear pairings for mobile communications

Attribute based signature (ABS) is a significant cryptographic notion providing secure authentication during data sharing. A signer can sign a message using the private keys he processes. However, user’s private key exposure may happen from time to time and this will bring potential threat to the whole system. Thus, key evolving mechanism should be introduced into ABS schemes. Besides, the efficiency of existing ABS schemes can be further improved since the process of signing and verification require massive bilinear pairings, which occupies costly computing resources on mobile terminal devices. To better tackle the above problems and provides a more secure data authentication method in mobile communication systems, in this paper, we firstly propose a key insulated attribute based signature scheme without pairings (KI-ABS-WP). Then we give the formalized definition as well as the concreted constructions of our scheme. In our KI-ABS-WP, uses needn’t run any bilinear pairings, thus the total computation cost has been reduced to a large extent. If key exposure occurs, key insulation mechanism guarantees system’s both backward and forward security. Finally, by security proof and efficiency comparison, our KI-ABS-WP is shown to be more superior for data authentication in mobile communication systems.     

对一种白盒SM4方案的差分计算分析

传统密码算法的安全性建立在黑盒攻击模型下. 在这种攻击模型下, 攻击者只能获取密码算法的输入输出, 而无法得知密码算法运行时的内部细节. 近年来白盒攻击模型的概念被提出. 在白盒攻击模型下, 攻击者既可以获取密码算法的输入输出, 也可以直接观测或更改密码算法运行时的内部数据. 为保证已有密码算法在白盒攻击环境下的安全性, 在不改变其功能的基础上通过白盒密码技术对其进行重新设计被称为已有密码算法的白盒实现. 研究白盒实现方案的设计与分析对于解决数字版权管理问题具有重要意义. 近年来, 出现了一类针对白盒实现方案的旁信道分析方法. 这类分析手段只需要知道很少白盒实现方案的内部细节, 却可以提取到密钥, 因此是一类对现有白盒实现方案具有实际威胁的分析手段. 对现有白盒实现方案进行此类分析对于确保方案安全性具有重要现实意义. 此类分析方法中的典型代表是基于差分功耗分析原理的差分计算分析. 基于差分计算分析, 对白-武白盒SM4方案进行了安全性分析. 基于对GF(2)上n阶均匀随机可逆矩阵统计特征的研究结果, 提出了一种改进型差分计算分析(IDCA), 可以在分析成功率几乎不变的前提下显著提升分析效率. 结果表明, 白-武白盒SM4方案在面对差分计算分析时不能保证安全性, 必须对其进行进一步改进使之满足实际应用场景下的安全性需求.