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-11-05
16:17 [Pub][ePrint] Asynchronous Computational VSS with Reduced Communication Complexity, by Michael Backes and Amit Datta and Aniket Kate

  Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and thoroughly investigating VSS in the asynchronous communication model.

In this work, we consider the communication complexity of asynchronous VSS in the com- putational setting for the optimal resilience of n = 3t + 1. The best known asynchronous VSS protocol by Cachin et al. has O(n^2) message complexity and O(kn^3) communication complexity, where k is a security parameter corresponding to the size of the secret. We close the linear complexity gap between these two measures for asynchronous VSS by presenting two protocols with O(n^2) message complexity and O(kn^2) communication complexity. Our first protocol satisfies the standard VSS definition, and can be used in stand-alone VSS scenarios as well as in applications such as Byzantine agreement. Our second and more intricate protocol satisfies a stronger VSS definition, and is useful in all VSS applications including multiparty computation and threshold cryptography.



16:17 [Pub][ePrint] Solving Subset Sum Problems of Densioty close to 1 by \"randomized\" BKZ-reduction, by Claus P. Schnorr and Taras Shevchenko

  Subset sum or Knapsack problems of dimension $n$ are known to be hardest for knapsacks of density close to 1.These problems are NP-hard for arbitrary $n$. One can solve such problems either by lattice basis reduction or by optimized birthday algorithms. Recently Becker, Coron, Jou } [BCJ10] present a birthday algorithm that

follows Schroeppel, Shamir [SS81], and Howgrave-Graham, Joux [HJ10]. This algorithm solves 50 random knapsacks of dimension 80 and density close to 1 in roughly 15 hours on a 2.67 GHz PC.

We present an optimized lattice basis reduction algorithm that follows Schnorr, Euchne} [SE03] using pruning of Schnorr, H\\\"orner [SH95] that solves such random knapsacks of dimension 80 on average in less than a minute, and 50 such problems all together about 9.4 times faster and using much less space than [BCJ10] on another 2.67 GHz PC.



16:17 [Pub][ePrint] Biclique Cryptanalysis of Lightweight Block Ciphers PRESENT, Piccolo and LED, by Kitae Jeong and HyungChul Kang and Changhoon Lee and Jaechul Sung and Seokhie Hong

  In this paper, we evaluate the security of lightweight block ciphers PRESENT, Piccolo and LED against biclique cryptanalysis. To recover the secret key of PRESENT-80/128, our attacks require $2^{79.76}$ full PRESENT-80 encryptions and $2^{127.91}$ full PRESENT-128 encryptions, respectively. Our attacks on Piccolo-80/128 require computational complexities of $2^{79.13}$ and $2^{127.35}$, respectively. The attack on a $29$-round reduced LED-64 needs $2^{63.58}$ 29-round reduced LED-64 encryptions. In the cases of LED-80/96/128, we propose the attacks on two versions. First, to recover the secret key of $45$-round reduced LED-80/96/128, our attacks require computational complexities of $2^{79.45}, 2^{95.45}$ and $2^{127.45}$, respectively. To attack the full version, we require computational complexities of $2^{79.37}, 2^{95.37}$ and $2^{127.37}$, respectively. However, in these cases, we need the full codebook. These results are superior to known biclique cryptanalytic results on them.



16:17 [Pub][ePrint] Resolving the conflict between generality and plausibility in verified computation, by Srinath Setty and Benjamin Braun and Victor Vu and Andrew J. Blumberg and Bryan Parno and Michael Walfish

  The area of proof-based verified computation (outsourced computation

built atop probabilistically checkable proofs and cryptographic

machinery) has lately seen renewed interest. Although recent work has

made great strides in reducing the overhead of naive applications of the

theory, these schemes still cannot be considered practical. The core

issue is that the work for the prover is immense, in general; it

is near-practical only for hand-compiled computations that can

be expressed in special forms.

This paper addresses that problem. Provided one is willing to batch

verification, we develop a protocol that

achieves the efficiency of the

best manually constructed protocols in the literature yet applies to all

computations.

Our protocol

is built on the observation that the

recently-proposed QAPs of Gennaro et al. (ePrint 2012/215) yield a

linear PCP that works with the efficient argument protocol of Setty et

al. (ePrint 2012/598, Security 2012, NDSS 2012), itself based on the

proposal of Ishai et al. (CCC 2007).

The consequence is a prover whose total work is not much more than

_linear_ in the running time of the computation.

We implement the protocol in the

context of a built system that includes a compiler and a parallel GPU

implementation. The result, as indicated by an experimental evaluation,

is a system that is _almost_ usable for real problems -- without

special-purpose tailoring.



16:17 [Pub][ePrint] {Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes, by David McGrew

  The block cipher modes of operation that are widely used (CBC, CTR, CFB) are secure up to

the birthday bound; with a $w$-bit block cipher, they are secure if $w2^{w}$ or fewer bits of data are encrypted, and insecure above that bound. However, the detailed security

properties close to this bound are not widely appreciated, despite the fact that $64$-bit block ciphers are sometimes used in that domain. This work addresses the issue by describing and analyzing plaintext-recovery attacks that are effective close to that bound. We describe possible-plaintext attacks, which can learn unknown plaintext values that are encrypted with CBC, CFB, or OFB. We also introduce impossible plaintext cryptanalysis, which can recover information encrypted with CTR, and can improve attacks against the aforementioned modes as well. These attacks work at the birthday bound, or even slightly below that bound, when

the target plaintext values are encrypted under a succession of keys.



16:17 [Pub][ePrint] Order-Preserving Symmetric Encryption, by Alexandra Boldyreva and Nathan Chenette and Younho Lee and Adam O\'Neill

  We initiate the cryptographic study of order-preserving symmetric encryption (OPE), a primitive suggested in the database community by Agrawal et al.~(SIGMOD \'04) for allowing efficient range queries on encrypted data. Interestingly, we first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack (IND-CPA) is unachievable by a practical OPE scheme. Instead, we propose a security notion in the spirit of pseudorandom functions (PRFs) and related primitives asking that an OPE scheme look ``as-random-as-possible\" subject to the order-preserving constraint.

We then design an efficient OPE scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. Our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution.

In particular, it makes black-box use of an efficient sampling algorithm for the latter.



16:17 [Pub][ePrint] Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions, by Alexandra Boldyreva and Nathan Chenette and Adam O\'Neill

  We further the study of order-preserving symmetric encryption (OPE), a primitive for allowing efficient range queries on encrypted data, recently initiated (from a cryptographic perspective) by Boldyreva et al.~(Eurocrypt \'09).

First, we address the open problem of characterizing what encryption via a random order-preserving function (ROPF) leaks about underlying data (ROPF being the ``ideal object\'\' in the security definition, POPF, satisfied by their scheme.)

In particular, we show that, for a database of randomly distributed plaintexts and appropriate choice of parameters, ROPF encryption leaks neither the precise value of any plaintext nor the precise distance between any two of them.

The analysis here introduces useful new techniques.

On the other hand, we show that ROPF encryption leaks approximate value of any plaintext as well as approximate distance between any two plaintexts, each to an accuracy of about square root of the domain size.

We then study schemes that are not order-preserving, but which nevertheless allow efficient range queries and achieve security notions stronger than POPF. In a setting where the entire database is known in advance of key-generation (considered in several prior works), we show that recent constructions of ``monotone minimal perfect hash functions\'\' allow to efficiently achieve (an adaptation of) the notion of IND-O(rdered) CPA also considered by Boldyreva et al., which asks that \\emph{only} the order relations among the plaintexts is leaked.

Finally, we introduce {\\em modular} order-preserving encryption (MOPE), in which the scheme of Boldyreva et al. is prepended with a random shift cipher. MOPE improves the security of OPE in a sense, as it does not leak any information about plaintext location.

We clarify that our work should not be interpreted as saying the original scheme of Boldyreva et al., or the variants that we introduce, are ``secure\'\' or ``insecure.\'\' Rather, the goal of this line of research is to help practitioners decide whether the options provide a suitable security-functionality tradeoff for a given application.



07:15 [Election] Independent verifier

  Tom Roeder at Microsoft Research has written an independent verifier for the Helios system. You can access it via the 2012 election page or via this link.



2012-11-02
17:54 [Job][Update] Cryptography Engineer/Cryptography Scientist, Mile 20 Recruiting, LLC, in Bethesda, MD/USA

  Required:

• Senior hands-on engineer with broad experience in cryptography

• Experienced with designing and implementing cryptographic algorithms and key management systems

• Must be familiar with algorithms and protocols including AES-CBC, AES-GCM, SHA, EC-DH, EC-DSA, random number generation, PKI

• Knowledge of Suite B crypto, TLS, smartcards/CAC, X.509, soft certificates, PKCS11

• Experience developing crypto APIs for both internal and external use

• Must have strong skills with C/C++ and/or Java programming languages on multiple platforms

• Ability to work with and mentor a team of programmers

• Ability to obtain US security clearance.

Highly desired:

• Familiar with FIPS 140-2 process, VPNs, S/MIME, data at rest crypto, and other cryptographic products.

• Familiar with DoD and US Federal requirements and regulations related to cryptography for SBU/CUI and classified data.

• Familiar with secure voice protocols, such as SRTP, SIP/TLS, SSIP, zRTP, etc.

• Ability to create high-level software design documents.

• Experience writing device drivers, low-level APIs, or software development kits.

• Familiar with implementing crypto in hardware in ASIC or FPGA-based systems

• BA/BS, MS, Ph.D. degree in Cryptography, Mathematics, Computer Science, Software Engineering, Computer Engineering, Electrical Engineering or equivalent experience.

• CISSP, CSSLP, or SANS certifications



12:09 [PhD][New] Shi Bai: Polynomial selection for the number field sieve

  Name: Shi Bai
Topic: Polynomial selection for the number field sieve
Category: foundations



12:08 [PhD][New] Richard Brent

  Name: Richard Brent