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 receive updates 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).

2014-10-12
00:17 [Pub][ePrint] Circulant Matrices and Differential Privacy, by Jalaj Upadhyay

  This paper resolves an open problem raised by Blocki {\\it et al.} (FOCS 2012), i.e., whether other variants of the Johnson-Lindenstrauss transform preserves differential privacy or not? We prove that a general class of random projection matrices that satisfies the Johnson-Lindenstrauss lemma also preserves differential privacy. This class of random projection matrices requires only $n$ Gaussian samples and $n$ Bernoulli trials and allows matrix-vector multiplication in $O(n \\log n)$ time. In this respect, this work unconditionally improves the run time of Blocki {\\it et al.} (FOCS 2012) without using the graph sparsification trick of Upadhyay (ASIACRYPT 2013). For the metric of measuring randomness, we stick to the norm used by earlier researchers who studied variants of the Johnson-Lindenstrauss transform and its applications, i.e., count the number of random samples made. In concise, we improve the sampling complexity by quadratic factor, and the run time of cut queries by an $O(n^{o(1)})$ factor and that of covariance queries by an $O(n^{0.38})$ factor.

Our proof for both the privacy and utility guarantee uses several new ideas. In order to improve the dimension bound, we use some known results from the domain of statistical model selection. This makes our proof short and elegant, relying just on one basic concentration inequality. For the privacy proof, even though our mechanism closely resembles that of Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013), we cannot use their proof idea. This is because the projection matrices we are interested in introduces non-trivial correlations between any two rows of the published matrix, and, therefore, we cannot invoke the composition theorem of Dwork, Rothblum and Vadhan (STOC 2009). We argue that the published matrix is not $r$-multivariate distribution; rather one matrix-variate distribution. We compute the distribution of the published matrix and then prove it preserves differential privacy.





2014-10-10
15:17 [Pub][ePrint] Reversed Genetic Algorithms for Generation of Bijective S-boxes with Good Cryptographic Properties, by Georgi Ivanov and Nikolay Nikolov and Svetla Nikova

  Often S-boxes are the only nonlinear component in a block cipher and as such play an important role in ensuring its resistance to cryptanalysis. Cryptographic properties and constructions of S-boxes have been studied for many years. The most common techniques for constructing S-boxes are: algebraic constructions, pseudo-random generation and a variety of heuristic approaches. Among the latter are the genetic algorithms. In this paper, a genetic algorithm working in a reversed way is proposed. Using the algorithm we can rapidly and repeatedly generate a large number of strong bijective S-boxes of each dimension from $(8 \\times 8)$ to $(16 \\times 16)$, which have sub-optimal properties close to the ones of S-boxes based on finite field inversion, but have more complex algebraic structure and possess no linear redundancy.



15:17 [Pub][ePrint] Physical Characterization of Arbiter PUFs, by Shahin Tajik, Enrico Dietz, Sven Frohmann, Jean-Pierre Seifert, Dmitry Nedospasov, Clemens Helfmeier, Christian Boit, Helmar Dittrich

  As intended by its name, Physically Unclonable Functions (PUFs) are considered as an ultimate solution to deal with insecure stor- age, hardware counterfeiting, and many other security problems. How- ever, many different successful attacks have already revealed vulnera- bilities of certain digital intrinsic PUFs. Although settling-state-based PUFs, such as SRAM PUFs, can be physically cloned by semi-invasive and fully-invasive attacks, successful attacks on timing-based PUFs were so far limited to modeling attacks. Such modeling requires a large sub- set of challenge-response-pairs (CRP) to successfully model the targeted PUF. In order to provide a final security answer, this paper proves that all arbiter-based (i.e. controlled and XOR-enhanced) PUFs can be com- pletely and linearly characterized by means of photonic emission analy- sis. Our experimental setup is capable of measuring every PUF-internal delay with a resolution of 6 picoseconds. Due to this resolution we in- deed require only the theoretical minimum number of linear independent equations (i.e. physical measurements) to directly solve the underlying inhomogeneous linear system. Moreover, we neither require to know the actual PUF challenges nor the corresponding PUF responses for our physical delay extraction. On top of that devastating result, we are also able to further simplify our setup for easier physical measurement han- dling. We present our practical results for a real arbiter PUF implemen- tation on a Complex Programmable Logic Device (CPLD) from Altera manufactured in a 180 nanometer process.



15:17 [Pub][ePrint] A Decentralized Public Key Infrastructure with Identity Retention, by Conner Fromknecht, Dragos Velicanu, Sophia Yakoubov

  Public key infrastructures (PKIs) enable users to look up and verify one another\'s public keys based on identities.

Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of \\emph{identity retention}; that is, they do not effectively prevent one user from registering a public key under another\'s already-registered identity.

In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention.

Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup.



12:30 [Job][Update] Associate professor (lecturer) in Computer Security., University of Birmingham, UK

  This is a permanent research and teaching position in one of UK\\\'s top research-led universities. The Security and Privacy group undertakes research in all fields related to information and cyber security, privacy, cryptography, etc.

12:20 [Job][New] Tenure-Track Faculty Positions, Shanghai Jiao Tong University, Shanghai, China

  The Laboratory of Cryptology and Computer Security (LoCCS) at the CS Department of Shanghai Jiao Tong University invites applications for several tenure-track faculty positions in the area of cryptology, in particular (but not limited to), authenticated encryptions, leakage-resilient cryptography, side-channel attacks, obfuscation. Candidates with a proven track record (especially publications at top venues) are encouraged to apply. Salaries will be globally competitive and commensurate with candidates\' accomplishments and experience. Shanghai Jiao Tong University is a member of China\'s C9 League and she has one of the country\'s best CS schools.

06:17 [Pub][ePrint] Fault Attack revealing Secret Keys of Exponentiation Algorithms from Branch Prediction Misses, by Sarani Bhattacharya and Debdeep Mukhopadhyay

  Performance monitors are provided in modern day computers for observing various features of the underlying microarchitectures. However the combination of underlying micro-architectural features and performance counters lead to side-channels which can be exploited for attacking cipher implementations. In this paper, to the best of our knowledge we study for the first time, the combination of branch-predictor algorithms and performance counters to demonstrate a fault attack on the popular square-and-multiply based exponentiation algorithm, used in the RSA. The attacks exploiting branching event like branch taken can be foiled by Montgomery Ladder based implementation of the exponentiation algorithm, while attacks based on branch miss are more devastating. We demonstrate the power of the attack exploiting branch misses from performance monitors by formalizing a fault attack model, where the adversary is capable of performing a bit flip at a desired bit position of the secret exponent. The paper characterizes the branch predictors using the popular two-bit predictor and formulates the dependence on the number of branch misses on the fault induced. This characterization is exploited to develop an iterative attack algorithm where knowledge of the previously determined key-bits and the difference of branch misses (as gathered from the performance counters) are utilised to determine the next bit. The attack has been validated on several standard Intel platforms, and puts to threat several implementations of exponentiation algorithms ranging from standard square-and-multiply, Montgomery Ladder to RSA-CRT and which are often used as side-channel counter measures. The attacks show that using the fault attack model featuring branch predictors one can attack implementations of exponentiation: both square and multiply, and Montgomery ladder, which forms the central algorithm for several standard public key ciphers.



06:17 [Pub][ePrint] Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof, by Dongdai Lin and Yujuan Quan and Jian Weng and Jun Yan

  Watrous (STOC 2006) proved that plugging classical bit commitment scheme that is secure against quantum attack into the GMW-type construction of zero-knowledge gives a classical zero-knowledge proof that is secure against quantum attack. In this paper, we showed that plugging quantum bit commitment scheme (allowing quantum computation and communication) into the GMW-type construction also gives a quantum zero-knowledge proof, as one expects. However, since the binding condition of quantum bit commitment scheme is inherently different from its classical counterpart, compared with Watrous\' security proof, here we encounter new difficulty in soundness analysis. To overcome the difficulty, we take a geometric approach, managing to reduce quantum soundness analysis to classical soundness analysis.

We also propose a formalization of non-interactive quantum bit commitment scheme, which may come in handy in other places. Moreover, inspired by our formalization, we generalize Naor\'s construction of bit commitment scheme to the quantum setting, achieving non-interactive commit stage.

We hope quantum bit commitment scheme can find more applications in quantum cryptography.



06:17 [Pub][ePrint] Classification of the CAESAR Candidates, by Farzaneh Abed and Christian Forler and Stefan Lucks

  In this work we give an overview of the candidates submitted to the

CAESAR competition which are not withdrawn yet. Furthermore, we

propose a classification with regard to their core primitives that

includes several design characteristics.



06:17 [Pub][ePrint] Robust Authenticated-Encryption: AEZ and the Problem that it Solves, by Viet Tung Hoang and Ted Krovetz and Phillip Rogaway

  With a scheme for \\textit{robust} authenticated-encryption a user can select an arbitrary value $\\lambda \\ge 0$ and then encrypt a plaintext of any length into a ciphertext that\'s $\\lambda$ characters longer. The scheme must provide all the privacy and authenticity possible for the requested~$\\lambda$. We formalize and investigate this idea, and construct a well-optimized solution, AEZ, from the AES round function. Our scheme encrypts strings at almost the same rate as OCB-AES or CTR-AES (on Haswell, AEZ has a peak speed of about 0.7 cpb). To accomplish this we employ an approach we call \\textit{accelerated} provable security: the scheme is designed and proven secure in the provable-security tradition, but, to improve speed, one instantiates by scaling down most instances of the underlying primitive.



06:17 [Pub][ePrint] Efficient Identity-Based Encryption over NTRU Lattices, by Léo Ducas and Vadim Lyubashevsky and Thomas Prest

  Efficient implementations of lattice-based cryptographic schemes have been limited to only the most basic primitives like encryption and digital signatures. The main reason for this limitation is that at the core of many advanced lattice primitives is a trapdoor sampling algorithm(Gentry, Peikert, Vaikuntanathan, STOC 2008) that produced outputs that were too long for practical applications.

In this work, we show that using a particular distribution over NTRU lattices can make GPV-based schemes suitable for practice. More concretely, we present the first lattice-based IBE scheme with practical parameters - key and ciphertext sizes are between two and four kilobytes, and all encryption and decryption operations take approximately one millisecond on a moderately-powered laptop.

As a by-product, we also obtain digital signature schemes which are shorter than the previously most-compact ones of Ducas, Durmus, Lepoint, and Lyubashevsky from Crypto 2013.