International Association for Cryptologic Research

# IACR News Central

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-03
15:17 [Pub][ePrint]

Depending on the application, malleability in cryptography can be viewed as either a flaw or -- especially if sufficiently understood and restricted -- a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle.

Despite these initial steps, a number of natural open problems remain: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive; and (3) their construction of a compactly verifiable shuffle has proof size O(N^2 + L) (where N is the number of votes and L is the number of mix authorities), whereas in theory such a proof could be of size O(N + L).

In this paper, we address these open problems by providing a generic construction of controlled- malleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction has the advantage that we can support a very general class of transformations (as we no longer rely on the transformations that Groth-Sahai proofs can support), and that we can use it to obtain a proof of size O(N + L) for the compactly verifiable shuffle.

15:17 [Pub][ePrint]

The pervasive diffusion of electronic devices in security and privacy sensitive applications has boosted research in cryptography. In this context, the study of lightweight algorithms has been a very active direction over the last years. In general, symmetric cryptographic primitives are good candidates for low-cost implementations. For example, several previous works have investigated the performances of block ciphers on various platforms. Motivated by the recent SHA3 competition, this paper extends these studies to another family of cryptographic primitives, namely hash functions. We implemented different algorithms on an ATMEL AVR ATtiny45 8-bit microcontroller, and provide their performance evaluation using different figures. All the implementations were carried out with the goal of minimizing the code size and memory utilization, and evaluated using a common interface. As part of our contribution, we additionally decided to make all the corresponding source codes available on a web page, under an open-source license. We hope that this paper provides a good basis for researchers and embedded system designers who need to include more and more functionalities in next generation smart devices.

15:17 [Pub][ePrint]

In 2001, a breakthrough result by Barak [FOCS 2001] showed how to

achieve public-coin zero-knowledge (ZK) arguments in constant rounds,

a feature known to be impossible using black-box simulation. In this

approach, the simulator makes use of the code of the malicious

verifier in computing the prover messages (albeit without

understanding it), and does not rewind the malicious verifier---and it

is hence called a \\emph{straight-line} simulator.

Since then, however, we have witnessed little progress on the basic

question whether Barak\'s technique can be extended to ZK {\\em proof}

systems. In this paper we make progress on this front, by providing

strong evidence that such an extension is far from likely.

Specifically, we show that for a natural class of constant-round

public-coin ZK proofs (which we call canonical,\'\' as all known

non-black-box ZK protocols fall in this category), a straight-line

simulator based on the known non-black-box technique for such a proof

system can actually be used to solve a seemingly unrelated problem,

namely, to figure out some non-trivial property of a verifier\'s

program, and {\\em without executing the targe code}, a problem

commonly viewed as notoriously hard.

A key tool in our reduction is an improved structure-preserving

version of the well-known Babai-Moran Speedup (derandomization)

Theorem, which essentially says that, for a constant-round public-coin

interactive proof system in which the verifier sends $m$ messages and

each of the prover messages is of length $p$, if the cheating

probability for an unbounded prover is $\\epsilon$, then there exist

$(p/O(\\log \\frac{1}{\\epsilon}))^m$ verifier random tapes such that the

cheating probability for the unbounded prover over these random tapes

is bounded away from 1---and this holds even when the prover knows

this small set of random tapes in advance. (In our setting, the

original Babai-Moran theorem yields a much larger size ($(O(p))^m$) of

such set of verifier random tapes.) In addition, we show that this is

tight with respect to round complexity, in the sense that there are

public-coin proof systems with a super-constant number of rounds for

which the prover\'s cheating probability is $1$, over any polynomial

number of verifier random tapes.

Finally, although the notion of straight-line simulation is

intuitively clear and has been used several times in the literature,

we are not aware of a formal definition of the process, perhaps due to

the fact that thoroughly defining (as well as enforcing) executing

the verifier only once\'\' does not appear to be straightforward. The

notion of {\\em generalized straight-line simulation} that we introduce

not only overcomes those obstacles, but enables us to expose the

limitations of the currently known non-black-box techniques.

15:17 [Pub][ePrint]

One of the most promising lightweight hardware countermeasures against SCA attacks is the so-called Threshold Implementation (TI) countermeasure. In this work we resolve many of the remaining open issues towards it\'s applicability. In particular, our contribution is

three-fold: first we define which optimal (from a cryptographic point of view)

S-boxes can be implemented with a 3-share TI. Second, we

introduce two methodologies to efficiently implement

these S-boxes. Third, as an example, we successfully apply these

methodologies to PRESENT and are able to decrease the area requirements of its protected S-box

by 57\\%.

15:17 [Pub][ePrint]

Threshold Implementation (TI) is an elegant and widely accepted countermeasure against

1-st order Differential Power Analysis (DPA) in Side Channel

Attacks. The 3-share TI is the most efficient version of TI,

but so far, it can only be applied to 50\\% of all 4-bit S-boxes.

In this paper, we study the limitations of decomposition and introduce factorization

to enable the 3-share TI for any optimal 4-bit

S-box. We propose an algorithm which can decompose any optimal 4-bit

S-box to quadratic vectorial boolean functions with a time complexity of $2^{19}$.

Furthermore, we use our new methodology in combination with decomposition to optimize ciphers utilizing many different

S-boxes, and,

to highlight the strength of our new methodology, we construct a 3-share Threshold Implementation of SERPENT which was believed to be not possible until now. Last, we show how to implemented all SERPENT S-boxes with only one mutual core.

15:17 [Pub][ePrint]

Entangled cloud storage enables a set of clients {P_i} to \"entangle\" their files {f_i} into a single clew c to be stored by a (potentially malicious) cloud provider S. The entanglement makes it impossible to modify or delete significant part of the clew without affecting all files in c. A clew keeps the files in it private but still lets each client P_i recover his own data by interacting with S; no cooperation from other clients is needed. At the same time, the cloud provider is

discouraged from altering or overwriting any significant part of c as this will imply that none of the clients can recover their files.

We provide theoretical foundations for entangled cloud storage, introducing the notion of an entangled encoding scheme that guarantees strong security requirements capturing the properties above. We also give a concrete construction based on privacy-preserving polynomial interpolation, along with protocols for using the encoding scheme in practice.

Protocols for cloud storage find application in the cloud setting, where clients store their files on a remote server and need to be ensured that the cloud provider will not delete their data illegitimately. Current solutions, e.g., based on Provable Data Possession and Proof of Retrievability, catch a malicious server \"after-the-fact\", meaning that the server needs to be challenged regularly to provide evidence that the clients\' files are stored at a given time.

Entangled storage makes all clients equal and with the same rights: It makes it financially inconvenient for a cloud provider to alter specific files and exclude certain \"average\" customers, since doing so would undermine all customers in the system, even those considered \"important\" and, thus, profitable. Therefore, entangled storage schemes offer security \"before-the-fact\".

15:17 [Pub][ePrint]

We present a protocol for securely computing a Boolean circuit $C$ in presence of a dishonest and malicious majority. The protocol is unconditionally secure, assuming access to a preprocessing functionality that is not given the inputs to compute on. For a large number of players the work done by each player is the same as the work needed to compute the circuit in the clear, up to a constant factor. Our protocol is the first to obtain these properties for Boolean circuits. On the technical side, we develop new homomorphic authentication schemes based on asymptotically good codes with an additional multiplication property. We also show a new algorithm for verifying the product of Boolean matrices in quadratic time with exponentially small error probability, where previous methods would only give a constant error.

15:17 [Pub][ePrint]

We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise ($\\LPN$) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a $\\Sigma$-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages $\\vm_0,\\ldots,\\vm_u$, are such that $\\vm_0=C(\\vm_1,\\ldots,\\vm_u)$ for any circuit $C$.

To get soundness which is exponentially small in a security parameter $t$, and when the zero-knowledge property relies on the LPN problem with secrets of length $\\ell$, our $3$ round protocol has communication complexity $\\bigO(t|C|\\ell\\log(\\ell))$ and computational complexity of $\\bigO(t|C|\\ell)$ bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.

2012-09-02
00:59 [Event][New]

Submission: 9 September 2012
From November 28 to November 30
Location: Seoul, Korea

2012-08-27
14:07 [Event][New]

From August 18 to August 22
Location: Santa Barbara, CA, USA

2012-08-26
10:36 [Job][New]

ESCRYPT is an ambitious company in the area of applied data security. Our clients include all global auto makers as well as leading global players in the area of machinery, automation, semiconductors and high-tech companies. ESCRYPT is a German company with offices in the US and Europe. ESCRYPT is leader in automotive data security and is expanding the US business. We are looking for highly motivated people who have great ideas and who want to realize those.

Your role will be developing customized software for our client projects and support our product development. You will potentially develop a Javabased enterprise security server, customized applications for JCOP-based smart-cards, and security applications for embedded devices in C. You will be located in our Ann Arbor office in Michigan, USA, and work in an international team and collaborate with our colleagues in the German offices.

REQUIREMENTS

We seek:

• Top graduates in the fields of computer science,

electrical engineering, or applied

mathematics

• Java Enterprise Edition experience

• Software development experience (C, C++,

Java)

• Industry experience is an advantage

We look for all-rounders willing to improve ESCRYPT every day. You should be able to work independently and be willing to take responsibility.