00:17 [Pub][JoC]
Logic Minimization Techniques with Applications to Cryptology
Abstract A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the nonlinearity of a circuit—as measured by the number of nonlinear gates it contains—is reduced. The second step reduces the number of gates in the linear components of the already reduced circuit. The technique can be applied to arbitrary combinational logic problems, and often yields improvements even after optimization by standard methods has been performed. In this paper we show the results of our technique when applied to the S-box of the Advanced Encryption Standard (FIPS in Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001). We also show that, in the second step, one is faced with an NP-hard problem, the Shortest Linear Program (SLP) problem, which is to minimize the number of linear operations necessary to compute a set of linear forms. In addition to showing that SLP is NP-hard, we show that a special case of the corresponding decision problem is Max SNP-complete, implying limits to its approximability. Previous algorithms for minimizing the number of gates in linear components produced cancellation-free straight-line programs, i.e., programs in which there is no cancellation of variables in GF(2). We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to nontrivial inputs. The straight-line programs produced by our techniques are not always cancellation-free. We have experimentally verified that, for randomly chosen linear transformations, they are significantly smaller than the circuits produced by previous algorithms.
- Content Type Journal Article
- Pages 1-33
- DOI 10.1007/s00145-012-9124-7
- Authors
- Joan Boyar, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark
- Philip Matthews, Aarhus University, Aarhus, Denmark
- René Peralta, Information Technology Laboratory, NIST, Gaithersburg, MD, USA
- Journal Journal of Cryptology
- Online ISSN 1432-1378
- Print ISSN 0933-2790
From: Thu, 03 May 2012 07:37:37 GMT
12:17 [Pub][ePrint]
Cryptography from tensor problems, by Leonard J. Schulman
We describe a new proposal for a trap-door one-way function.The new proposal belongs to the ``multivariate quadratic\'\'
family but the trap-door is different from existing methods,
and is simpler.
Known quantum algorithms do not appear to help an adversary
attack this trap-door. (Beyond the asymptotic
square-root-speedup which applies to all oracle search
problems.)
12:17 [Pub][ePrint]
On the Equivalence between the Set Covering Problem and the Problem of Finding Optimal Cumulative Assignment Schemes, by Qiang Li and Xiangxue Li and Dong Zheng and Zheng Huang and Kefei Chen
A cumulative assignment scheme (CAS for short) is a special type of secret sharing schemes. For any given access structure (AS), a CAS which minimizes the cardinality of the primitive share set (the average information rate, or the worst information rate) is called an optimal CAS and can be constructed via solving some binary integer programming (BIP). The problem of finding optimal CAS\'s for complete AS\'s is solved.We consider in this paper the problem of finding optimal CAS\'s for incomplete AS\'s. The paper introduces some notions including the connected-super-forbidden-family and the lower-forbidden-family for AS\'s. We show that an optimal CAS can be derived from some smaller sized BIP whose variables (constraints, resp.) are based on the connected-super-forbidden-family (lower-forbidden-family, resp.) of the given AS. The paper further builds the close relationship between the problem of finding optimal CAS\'s and the set covering problem (SCP). We prove that the problem of finding a CAS with minimum cardinality of the primitive share set (or minimum average information rate) is equivalent to the SCP, and thus is NP-hard. Other contributions of the paper include: 1) two types of AS\'s are recognized so that we can construct the corresponding optimal CAS\'s directly; and 2) a greedy algorithm is proposed to find CAS\'s with smaller worst information rate.
12:17 [Pub][ePrint]
A Secret Sharing Scheme Based on Group Presentations and the Word Problem, by Maggie Habeeb and Delaram Kahrobaei and Vladimir Shpilrain
A $(t,n)$-threshold secret sharing scheme is a method to distribute a secret among $n$ participants in such a way that any $t$ participants can recover the secret, but no $t-1$ participants can.In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a $(t,n)$-threshold scheme that is a combination of Shamir\'s scheme and the group-theoretic scheme proposed in this paper.
12:17 [Pub][ePrint]
On Efficient Pairings on Elliptic Curves over Extension Fields, by Xusheng Zhang and Kunpeng Wang and Dongdai Lin
In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics.In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller\'s algorithm to present further advantage of pairing-friendly curves over extension fields, not relying on the much faster field arithmetic. We propose new pairings on elliptic curves over extension fields can make better use of the multi-pairing technique for the efficient implementation. By using some implementation skills, our new pairings could be implemented much more efficiently than the optimal ate pairing and the optimal twisted ate pairing on elliptic curves over extension fields. At last, we use the similar method to give more efficient pairings on Estibals\'s supersingular curves over composite extension fields in parallel implementation.
12:17 [Pub][ePrint]
Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin, by Ghassan O. Karame and Elli Androulaki and Srdjan Capkun
Bitcoin is a decentralized payment system that is based on Proof-of-Work. Bitcoin is currently gaining popularity as a digital currency; several businesses are starting to accept Bitcoin transactions. An example case of the growing use of Bitcoin was recently reported in the media; here, Bitcoins were used as a form of fast payment in a local fast-food restaurant.In this paper, we analyze the security of using Bitcoin for fast payments, where the time between the exchange of currency and goods is short (i.e., in the order of few seconds). We focus on double-
spending attacks on fast payments and demonstrate that these attacks can be mounted at low cost on currently deployed versions of Bitcoin. We further show that the measures recommended by Bitcoin developers for the use of Bitcoin in fast transactions are not always effective in resisting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending
attacks on Bitcoin will still be possible. Finally, we leverage on our findings and propose a lightweight countermeasure that enables the detection of double-spending attacks in fast transactions.
