00:17 [Pub][ePrint]
Generation of Nonlinear Feedback Shift Registers with special-purpose hardware, by Tomasz Rachwalik and Janusz Szmidt and Robert Wicik, and Janusz Zablocki
The nonlinear feedback shift registers (NLFSR) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of the linear feedback shift registers (LFSR). In general, it is not known how to construct NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. We used the implementation of NLFSRs in Field Programmable Gate Arrays (FPGA) to perform a corresponding search. We also investigated local statistical properties of the binary sequences ganerated by NLFSRs of order 25 and 27.
International Association for Cryptologic Research
IACR News Central
Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via
- eMail subscription
- RSS (select channels below)
- Web (all channels)
To receive your credentials via mail again, please click here.
Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).
2012-06-03
21:17 [Pub][ePrint]
New Transference Theorems on Lattices Possessing n^\\epsilon-unique Shortest Vectors, by Wei Wei and Chengliang Tian and Xiaoyun Wang
We prove three optimal transference theorems on lattices possessing $n^{\\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length of
We prove three optimal transference theorems on lattices possessing $n^{\\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length of
generating vectors respectively. The theorems result in reductions
between GapSVP$_{\\gamma\'}$ and GapSIVP$_\\gamma$ for this class of
lattices. Furthermore, we prove a new transference theorem giving an
optimal lower bound relating the successive minima of a lattice with
its dual. As an application, we compare the respective advantages of
current upper bounds on the smoothing parameter of discrete Gaussian
measures over lattices and show a more appropriate bound for lattices whose duals possess $\\sqrt{n}$-unique shortest vectors.
21:17 [Pub][ePrint]
Two grumpy giants and a baby, by Daniel J. Bernstein and Tanja Lange
Pollard\'s rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups.
Pollard\'s rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups.
This paper presents two reasons that Pollard\'s rho algorithm
is farther from optimality than generally believed.
First, ``higher-degree local anti-collisions\'\'
make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic.
Second, even a truly random walk is suboptimal,
because it suffers from ``global anti-collisions\'\' that can at least partially be avoided.
For example, after (1.5+o(1))\\sqrt(l) additions in a group of order l (without fast negation),
the baby-step-giant-step method has probability 0.5625+o(1)
of finding a uniform random discrete logarithm;
a truly random walk would have probability 0.6753\\ldots+o(1);
and this paper\'s new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).
21:17 [Pub][ePrint]
Broadcast-enhanced Key Predistribution Schemes, by Michelle Kendall and Keith M. Martin and Siaw-Lynn Ng and Maura B. Paterson and Douglas R. Stinson
We present a formalisation of a category of schemes which we call \\emph{Broadcast-enhanced Key Predistribution Schemes}.
We present a formalisation of a category of schemes which we call \\emph{Broadcast-enhanced Key Predistribution Schemes}.
These schemes can be used instead of a key predistribution scheme in any network which has access to a trusted base station and broadcast channel.
In such networks, broadcast-enhanced key predistribution schemes can provide advantages over key predistribution schemes including flexibility and more efficient revocation.
There are many possible applications and ways to implement broadcast-enhanced key predistribution schemes, and we propose a framework for describing, comparing and analysing them.
In their paper `From key predistribution to key redistribution\', Cicho\\\'{n}, Go{\\l}\\c{e}biewski and Kuty{\\l}owski propose a scheme for `redistributing\' keys to a wireless sensor network using a broadcast channel after an initial key predistribution.
We classify this as a broadcast-enhanced key predistribution scheme and analyse it in that context.
We provide simpler proofs of some results from their paper, give a precise analysis of the resilience of their scheme, and discuss modifications based on defining a suitable keyring intersection threshold.
In the latter half of the paper we suggest two particular scenarios where broadcast-enhanced key predistribution schemes may be particularly desirable and the relevant design goals to prioritise in each case.
For each scenario we propose a suitable family of broadcast-enhanced key predistribution schemes and our analysis demonstrates their effectiveness in achieving their aims in resource-constrained networks.
21:17 [Pub][ePrint]
In the blink of an eye: There goes your AES key, by Sergei Skorobogatov and Christopher Woods
This paper is a short summary of a real world AES key extraction performed on a military grade FPGA marketed as \'virtually unbreakable\' and \'highly secure\'. We demonstrated that it is possible to extract the AES key from the Actel/Microsemi ProASIC3 chip in a time of 0.01 seconds using a new side-channel analysis technique called Pipeline Emission Analysis (PEA). This new technique does not introduce a new form of side-channel attacks (SCA), it introduces a substantially improved method of waveform analysis over conventional attack technology. It could be used to improve upon the speed at which all SCA can be performed, on any device and especially against devices previously thought to be unfeasible to break because of the time and equipment cost. Possessing the AES key for the ProASIC3 would allow an attacker to decrypt the bitstream or authenticate himself as a legitimate user and extract the bitstream from the device where no read back facility exists. This means the device is wide open to intellectual property theft, fraud and reverse engineering of the design to allow the introduction of a backdoor or Trojan. We show that with a very low cost hardware setup made with parts obtained from a local electronics distributor you can improve upon existing SCA up to a factor of x1,000,000 in time and at a fraction of the cost of existing SCA equipment.
This paper is a short summary of a real world AES key extraction performed on a military grade FPGA marketed as \'virtually unbreakable\' and \'highly secure\'. We demonstrated that it is possible to extract the AES key from the Actel/Microsemi ProASIC3 chip in a time of 0.01 seconds using a new side-channel analysis technique called Pipeline Emission Analysis (PEA). This new technique does not introduce a new form of side-channel attacks (SCA), it introduces a substantially improved method of waveform analysis over conventional attack technology. It could be used to improve upon the speed at which all SCA can be performed, on any device and especially against devices previously thought to be unfeasible to break because of the time and equipment cost. Possessing the AES key for the ProASIC3 would allow an attacker to decrypt the bitstream or authenticate himself as a legitimate user and extract the bitstream from the device where no read back facility exists. This means the device is wide open to intellectual property theft, fraud and reverse engineering of the design to allow the introduction of a backdoor or Trojan. We show that with a very low cost hardware setup made with parts obtained from a local electronics distributor you can improve upon existing SCA up to a factor of x1,000,000 in time and at a fraction of the cost of existing SCA equipment.
21:17 [Pub][ePrint]
Tamper and Leakage Resilience in the Split-State Model, by Feng-Hao Liu and Anna Lysyanskaya
It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered \\emph{algorithmic} defenses from such attacks.
It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered \\emph{algorithmic} defenses from such attacks.
In this paper, we show how to algorithmically secure any cryptographic functionality from continual split-state leakage and tampering attacks. A split-state attack on cryptographic hardware is one that targets separate parts of the hardware separately. Our construction does not require the hardware to have access to randomness. In contrast, prior work on protecting from continual combined leakage and tampering required true randomness for each update. Our construction is in the common reference string (CRS) model; the CRS must be hard-wired into the device. We note that prior negative results show that it is impossible to algorithmically secure a cryptographic functionality against a combination of arbitrary continual leakage and tampering attacks without true randomness; therefore restricting our attention to the split-state model is justified.
Our construction is simple and modular, and relies on a new construction, in the CRS model, of non-malleable codes with respect to split-state tampering functions, which may be of independent interest.
21:17 [Pub][ePrint]
Anonymous Credentials Light , by Foteini Baldimtsi and Anna Lysyanskaya
We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement of
We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement of
anonymous credentials. Our new notion in contrast is a convenient building block for anonymous
credential systems. The construction we propose is efficient: it requires just a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard. Thus, for
the first time, we give a provably secure construction of anonymous credentials that can work in
the elliptic group setting without bilinear pairings. In contrast, prior provably secure constructions were based on the RSA group or on groups with pairings, which made them prohibitively
inefficient for mobile devices, RFIDs and smartcards. The only prior efficient construction that
could work in such elliptic curve groups, due to Brands, does not have a proof of security.
21:17 [Pub][ePrint]
Differential Power Analysis on ZUC Algorithm, by TANG Ming, CHENG PingPan ,QIU ZhenLong
Stream cipher ZUC plays a crucial role in the next generation of mobile communication as it has already been included by the 3GPP LTE-Advanced, which is a candidate standard for the 4G network. Through a long-time evaluation program, ZUC algorithm is thought to be robust enough to resist many existing cryptanalyses, but not for DPA, one of the most powerful threat of SCAs(Side Channel Analysis).Up to the present, almost all the work on DPA is for block ciphers, such as DES and AES, a very few work has been done on stream ciphers, such as ZUC algorithm, for particular reasons that would be illustrated in the later section. In this paper, we generally study the security of unprotected ZUC hardware implementation against DPA. Our theoretical analysis and experimental results show that ZUC algorithm is potentially vulnerable to this kind of attack. Furthermore, kinds of common countermeasures are discussed when we try to apply them to ZUC hardware implementations, both the security and tradeoffs are considered. The experiments are given in the last section to verify our conclusions, which would undoubtedly provide some guidance to the corresponding designers.
Stream cipher ZUC plays a crucial role in the next generation of mobile communication as it has already been included by the 3GPP LTE-Advanced, which is a candidate standard for the 4G network. Through a long-time evaluation program, ZUC algorithm is thought to be robust enough to resist many existing cryptanalyses, but not for DPA, one of the most powerful threat of SCAs(Side Channel Analysis).Up to the present, almost all the work on DPA is for block ciphers, such as DES and AES, a very few work has been done on stream ciphers, such as ZUC algorithm, for particular reasons that would be illustrated in the later section. In this paper, we generally study the security of unprotected ZUC hardware implementation against DPA. Our theoretical analysis and experimental results show that ZUC algorithm is potentially vulnerable to this kind of attack. Furthermore, kinds of common countermeasures are discussed when we try to apply them to ZUC hardware implementations, both the security and tradeoffs are considered. The experiments are given in the last section to verify our conclusions, which would undoubtedly provide some guidance to the corresponding designers.
21:17 [Pub][ePrint]
Threshold Implementations of all 3x3 and 4x4 S-boxes, by B. Bilgin and S.Nikova and V.Nikov and V.Rijmen and G.St\\\"{u}tz
Side-channel attacks have proven many hardware implementations of cryptographic algorithms to be vulnerable.
Side-channel attacks have proven many hardware implementations of cryptographic algorithms to be vulnerable.
A recently proposed masking method, based on secret sharing and multi-party computation methods, introduces a set of sufficient requirements for implementations to be provably resistant against first-order DPA with minimal assumptions on the hardware.
The original paper doesn\'t describe how to construct the Boolean functions that are to be used in the implementation. In this paper, we derive the functions for all invertible $3 \\times 3$, $4 \\times 4$ S-boxes and the $6 \\times 4$ DES S-boxes. Our methods and observations can also be used to accelerate the search for sharings of larger (e.g. $8 \\times 8$) S-boxes. Finally, we investigate the cost of such protection.
21:17 [Pub][ePrint]
A Public Shuffle without Private Permutations, by Myungsun Kim and Jinsu Kim and Jung Hee Cheon
In TCC 2007, Adida and Wikstr\\\"{o}m proposed a novel approach to
In TCC 2007, Adida and Wikstr\\\"{o}m proposed a novel approach to
shuffle, called a public shuffle,
in which a shuffler can perform shuffle publicly without needing information kept secret.
Their scheme uses an encrypted permutation matrix to shuffle
ciphertexts publicly.
This approach significantly reduces the cost of constructing a mix-net
to verifiable joint decryption. Though their method is successful in making
shuffle to be a public operation, their scheme
still requires that some trusted parties should choose a permutation
to be encrypted and construct zero-knowledge proofs on the
well-formedness of this permutation.
In this paper, we propose a method to construct a public shuffle
without relying on permutations and randomizers generated privately: Given an
$n$-tuple of ciphertext $(c_1,\\dots,c_n)$, our shuffle algorithm
computes $f_i(c_1,\\dots,c_n)$ for $i=1,\\dots,\\ell$ where each
$f_i(x_1,\\dots,x_n)$ is a symmetric polynomial in $x_1,\\dots,x_n$.
Depending on the symmetric polynomials we use, we propose two concrete constructions.
One is to use ring homomorphic encryption with constant ciphertext
complexity and the other is to use simple ElGamal encryption with
linear ciphertext complexity in the number of senders. Both
constructions are free of zero-knowledge proofs and publicly
verifiable.
21:17 [Pub][ePrint]
On instance separation in the UC-framework, by István Vajda
The UC approach of Canetti offers the advantage of stand-alone analysis while keeping security guaranties for arbitrary complex environment. When we implement by this approach first we have to ensure secure instance separation and based on this condition, we are allowed to carry out a stand-alone analysis. In this report we propose three issues related to instance separation in UC-context:
The UC approach of Canetti offers the advantage of stand-alone analysis while keeping security guaranties for arbitrary complex environment. When we implement by this approach first we have to ensure secure instance separation and based on this condition, we are allowed to carry out a stand-alone analysis. In this report we propose three issues related to instance separation in UC-context:
We consider the problem of universal composability in cases, when we cannot assume independence of instances. Next we formalize the interleaving attack and a related security notion. In time-aware protocols time-based separation of instances is one of the standard implementation techniques. We propose an event-driven clock model towards purely symbolic analysis of time-aware protocols.