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

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-09-20
12:17 [Pub][ePrint] A Comparison of Perfect Table Cryptanalytic Tradeoff Algorithms, by Ga Won Lee and Jin Hong

  Analyses of three major time memory tradeoff algorithms were presented by a recent paper in such a way that facilitates comparisons of the algorithm performances at arbitrary choices of the algorithm parameters. The algorithms considered there were the classical Hellman tradeoff and the non-perfect table versions of the distinguished point method and the rainbow table method. This paper adds the perfect table versions of the distinguished point method and the rainbow table method to the list, so that all the major tradeoff algorithms may now be compared against each other.

The algorithm performance information provided by this and the preceding paper is aimed at making practical comparisons possible. Comparisons that take both the cost of pre-computation and the efficiency of the online phase into account, at parameters that achieve a common success rate, can now be carried out with ease. Comparisons can be based on the expected execution complexities rather than the worst case complexities, and details such as the effects of false alarms and various storage optimization techniques need no longer be ignored.

A large portion of this paper is allocated to accurately analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.



12:17 [Pub][ePrint] 2048XKS - A Software Oriented High Security Block Cipher, by Dieter Schmidt

  The block cipher 2048XKS is a derivative of the block ciphers 1024 and 1024XKS, which in turn used the block ciphers MMB, SAFER, and Blowfish as building blocks. The block cipher 2048XKS has a block size of 2048 bis and a key length of 4096 bits and 8192 bits, respectively. 2048XKS is a Substition-Permutation-Network (SPN). It is designed for 32 bit microprocessors with a hardware integer multiplier.



12:17 [Pub][ePrint] Salus: A System for Server-Aided Secure Function Evaluation, by Seny Kamara and Payman Mohassel and Ben Riva

  Secure function evaluation (SFE) allows a set of mutually distrustful parties to

evaluate a function of their joint inputs without revealing their inputs

to each other.

SFE has been the focus of active research and recent work suggests that it can

be made practical. Unfortunately, current protocols and implementations have

inherent limitations that are hard to overcome using standard and practical

techniques. Among them are: (1) requiring participants to do work linear in

the size of the circuit representation of the function; (2) requiring all

parties to do the same amount of work; and (3) not being able to provide

complete fairness.

A promising approach for overcoming these limitations is to augment the SFE

setting with a small set of untrusted servers that have no input to the

computation and that receive no output, but that make their computational

resources available to the parties. In this model, referred to as

server-aided SFE, the goal is to tradeoff the parties\' work at the

expense of the servers. Motivated by the emergence of public cloud services

such as Amazon EC2 and Microsoft Azure, recent work has explored the extent to

which server-aided SFE can be achieved with a single server.

In this work, we revisit the sever-aided setting from a practical perspective

and design single-server-aided SFE protocols that are considerably more

efficient than all previously-known protocols. We achieve this in part by

introducing several new techniques for garbled-circuit-based protocols,

including a new and efficient input-checking mechanism for cut-and-choose and a

new pipelining technique that works in the presence of malicious adversaries.

Furthermore, we extend the server-aided model to guarantee fairness which is an

important property to achieve in practice.

Finally, we implement and evaluate our constructions experimentally and show

that our protocols (regardless of the number of parties involved) yield implementations that are 4 and 6 times

faster than the most optimized two-party SFE implementation when the server is

assumed to be malicious and covert, respectively.



12:17 [Pub][ePrint] Enhanced Chosen-Ciphertext Security and Applications, by Dana Dachman-Soled and Georg Fuchsbauer and Payman Mohassel and Adam O\'Neill

  We introduce and study a new notion of enhanced chosen-ciphertext security (ECCA) for public- key encryption. Loosely speaking, in ECCA, when the decryption oracle returns a plaintext to the adversary, it also provides coins under which the returned plaintext encrypts to the queried ciphertext (when they exist). Our results mainly concern the case where such coins can also be recovered efficiently. We provide constructions of ECCA encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT 2010), resulting in ECCA encryption from standard number-theoretic assumptions. We then give two applications of ECCA encryption: (1) We use it as a unifying concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive trapdoor functions (namely, we show that both primitives are equivalent to ECCA encryption), resolving a main open question of Kiltz et al. (2) We show that ECCA encryption can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) suggested by Damg{\\aa}rd and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite different from those in prior work. We believe our results indicate that ECCA is an intriguing notion that may prove useful in further work.



12:17 [Pub][ePrint] Differential Analysis of the LED Block Cipher, by Florian Mendel and Vincent Rijmen and Deniz Toz and Kerem Varici

  In this paper, we present a security analysis of the lightweight block cipher LED proposed by Guo et al. at CHES 2011. Since the design of LED is very similar to the Even-Mansour scheme, we first review existing attacks on this scheme and extend them to related-key and related-key-cipher settings before we apply them to LED. We obtain results for $12$ and $16$ rounds (out of $32$) for LED-$64$ and $16$ and $24$ rounds (out of $48$) for LED-$128$. Furthermore, we present an observation on full LED in the related-key-cipher setting. For all these attacks we need to find good differentials for one step (4 rounds) of LED. Therefore, we extend the study of plateau characteristics for AES-like structures from two rounds to four rounds when the key addition is replaced with a constant addition. We introduce an algorithm that can be used to find good differentials and right pairs for one step of LED. To be more precise, we can find more than $2^{10}$ right pairs for one step of LED with complexity of $2^{16}$ and memory requirement of $5 \\times 2^{17}$. Moreover, a similar algorithm can also be used to find iterative characteristics for LED.



12:17 [Pub][ePrint] A Versatile Multi-Input Multiplier over Finite Fields, by Haibo Yi, Shaohua Tang

  Multiplication of three elements over finite fields is used extensively in multivariate public key cryptography and solving system of linear equations over finite fields. This contribution shows the enhancements of multiplication of three elements over finite fields by using specific architecture. We firstly propose a versatile multi-input multiplier over finite fields. The parameters of this multiplier can be changed according to the requirement of the users which makes it reusable in different applications. Our evaluation of this multiplier gives optimum choices for multiplication of three elements over finite fields. Implemented results show that we takes $22.062$ ns and $16.354$ ns to execute each multiplication of three elements over $GF((2^4)^2)$ based on table look-up and polynomial basis on a FPGA respectively. Experimental results and mathematical proofs clearly demonstrate the improvement of the proposed versatile multiplier over finite fields.



09:17 [Pub][ePrint] Pairing computation on Edwards curves with high-degree twists, by Liangze Li and Hongfeng Wu and Fan Zhang

  In this paper, we propose an elaborate geometry approach to explain the group law on twisted Edwards curves which are seen as the intersection of quadric surfaces in place. Using the geometric interpretation of the group law we obtain the Miller function for Tate pairing computation on twisted Edwards curves. Then we present the explicit formulae for pairing computation on twisted Edwards curves. Our formulae for the doubling step are a littler faster than that proposed by Arene et.al.. Finally, to improve the efficiency of pairing computation we present twists of degree 4 and 6 on twisted Edwards curves.



09:17 [Pub][ePrint] Solving Hard Lattice Problems and the Security of Lattice-Based Cryptosystems, by Thijs Laarhoven and Joop van de Pol and Benne de Weger

  This paper is a tutorial introduction to the present state-of-the-art in the field of security of lattice-based cryptosystems. After a short introduction to lattices, we describe the main hard problems in lattice theory that cryptosystems base their security on, and we present the main methods of attacking these hard problems, based on lattice basis reduction. We show how to find shortest vectors in lattices, which can be used to improve basis reduction algorithms. Finally we give a framework for assessing the security of cryptosystems based on these hard problems.



09:17 [Pub][ePrint] A Simplified Combinatorial Treatment of Constructions and Threshold Gaps of Ramp Schemes, by Maura B. Paterson and Douglas R. Stinson

  We give easy proofs of some recent results concerning threshold gaps in ramp schemes. We then give a simplified and unified treatment of construction methods for ramp schemes using error-correcting codes. Finally, as an immediate consequence of these results, we provide a new explicit bound on the the minimum length of a code having a specified distance and dual distance.



09:17 [Pub][ePrint] A Low-Area Unified Hardware Architecture for the AES and the Cryptographic Hash Function Gr{\\o}stl, by Nuray At and Jean-Luc Beuchat and Eiji Okamoto and Ismail San and Teppei Yamazaki

  This article describes the design of an 8-bit coprocessor for the AES (encryption, decryption, and key expansion) and the cryptographic hash function Gr{\\o}stl on several Xilinx FPGAs. Our Arithmetic and Logic Unit performs a single instruction that allows for implementing AES encryption, AES decryption, AES key expansion, and Gr{\\o}stl at all levels of security. Thanks to a careful organization of AES and Gr{\\o}stl internal states in the register file, we manage to generate all read and write addresses by means of a modulo-128 counter and a modulo-256 counter. A fully autonomous implementation of Gr{\\o}stl and AES on a Virtex-6 FPGA requires 169 slices and a single 36k memory block, and achieves a competitive throughput. Assuming that the security guarantees of Gr{\\o}stl are at least as good as the ones of the other SHA-3 finalists, our results show that Gr{\\o}stl is the best candidate for low-area cryptographic coprocessors.



09:17 [Pub][ePrint] Secret Sharing and Secure Computing from Monotone Formulae, by Ivan Bjerre Damgård and Jonas Kölker and Peter Bro Miltersen

  We present a construction of log-depth formulae for various threshold functions based on atomic threshold gates of constant size. From this, we build a new family of linear secret sharing schemes that are multiplicative, scale well as the number of players increases and allows to raise a shared value to the characteristic of the underlying field without interaction. Some of these schemes are in addition strongly multiplicative. Our formulas can also be used to construct multiparty protocols from protocols for a constant number of parties. In particular we implement black-box multiparty computation over non-Abelian groups in a way that is much simpler than previously known and we also show how to get a protocol in this setting that is efficient and actively secure against a constant fraction of corrupted parties, a long standing open problem. Finally, we show a negative result on usage of our scheme for pseudorandom secret sharing as defined by Cramer, Damgård and Ishai.