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-12-27
19:17 [Pub][ePrint]

In this work we construct an algorithm for sampling Discrete Gaussians efficiently and obliviously. Previously discrete Gaussian samplers have been constructed in \\cite{GPV08, Pei10}, where the algorithms take as input a high quality\" basis and produce an output whose quality depends on the input basis quality. Our algorithm produces a discrete Gaussian of somewhat worse quality than \\cite{GPV08,Pei10} but with the advantage that it does not require access to an explicit description of the underlying lattice, for example it suffices for our purposes to have encryptions of lattice vectors under an additively homomorphic encryption scheme. At the heart of our work is the fundamental question {\\it how do sums of discrete Gaussians behave?} Unlike their continuous counterparts, discrete Gaussians are not that well understood. We believe that our work fills in some important gaps of this understanding. Our results are already important in enabling the exciting new work on multilinear maps \\cite{GGH12}, and since the questions we resolve arise naturally, we believe that our work will find application in other areas as well.

19:17 [Pub][ePrint]

SAFER\\scriptsize + \\normalsize was a candidate block cipher for AES with 128-bit block size and a variable key sizes of 128, 192 or 256 bits. Bluetooth uses customized versions of SAFER\\scriptsize + \\normalsize for security. The numbers of rounds for SAFER\\scriptsize + \\normalsize with key sizes of 128, 192 and 256 are 8, 12 and 16, respectively. SAFER\\scriptsize ++\\normalsize, a variant of SAFER\\scriptsize +\\normalsize, was among the cryptographic primitives selected for the second phase of the NESSIE project. The block size is 128 bits and the key size can take either 128 or 256 bits. The number of rounds for SAFER\\scriptsize ++ \\normalsize is 7 for keys of 128 bits, and 10 for keys of 256 bits. Both ciphers use PHT as their linear transformation.

In this paper, we take advantage of properties of PHT and S-boxes to identify 3.75-round impossible differentials for SAFER\\scriptsize ++ \\normalsize and 2.75-round impossible differentials for SAFER\\scriptsize +\\normalsize, which result in impossible differential attacks on 4-round SAFER\\scriptsize +\\normalsize/128(256), 5-round SAFER\\scriptsize ++\\normalsize/128 and 5.5-round SAFER\\scriptsize ++\\normalsize/256. Our attacks significantly improve previously known impossible differential attacks on 3.75-round SAFER\\scriptsize +\\normalsize/128(256) and SAFER\\scriptsize ++\\normalsize/128(256). Our attacks on SAFER\\scriptsize +\\normalsize/128(256) and SAFER\\scriptsize ++\\normalsize/128(256) represent the best currently known attack in terms of the number of rounds.

19:17 [Pub][ePrint]

We introduce a broad lattice manipulation technique for expressive cryptography, and use it to realize functional encryption for access structures from post-quantum hardness assumptions.

Specifically, we build an efficient key-policy attribute-based encryption scheme, and prove its security in the selective sense from learning-with-errors intractability in the standard model.

19:17 [Pub][ePrint]

Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single humanmemorizable password, but no single server (or collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user\'s device. We achieve our results by careful protocol design and by exclusively focusing on the two-server public-key setting.

19:17 [Pub][ePrint]

\\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.

A common relaxation is a \\emph{preprocessing} SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only $O(1)$ encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have escaped the hegemony\'\' of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.

We present a general methodology for the construction of preprocessing SNARGs, as well as resulting concrete efficiency improvements. Our contribution is three-fold:

(1)

We introduce and study a natural extension of the interactive proof model that considers \\emph{algebraically-bounded} provers; this new setting is analogous to the common study of algebraically-bounded adversaries\'\' in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) \\emph{linear-interactive proofs} (LIPs) for NP. Our constructions are based on general transformations applied to both \\emph{linear} PCPs (LPCPs) and traditional unstructured\" PCPs.

(2)

We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of \\emph{linear targeted malleability} (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain \\emph{zero-knowledge} LIPs and SNARGs. Our techniques yield SNARGs \\emph{of knowledge} and thus can benefit from known recursive composition and bootstrapping techniques.

(3)

Following this methodology, we exhibit several constructions achieving new efficiency features, such as single-ciphertext preprocessing SNARGs\" and improved succinctness-soundness tradeoffs. We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

19:17 [Pub][ePrint]

How to construct an ideal multi-secret sharing scheme for general access structures is difficult. In this paper, we solve an open problem proposed by Spiez et al.recently [Finite Fields and

Their Application, 2011(17) 329-342], namely to design an algorithm of privileged coalitions of any length if such coalitions exist. Furthermore, in terms of privileged coalitions, we show that most of the existing multi-secret sharing schemes based on Shamir threshold secret sharing are not perfect by analyzing Yang et al.\'s scheme and Pang et al.\'s scheme. Finally, based on the algorithm mentioned above, we devise an ideal multi-secret sharing scheme for families of access structures, which possesses more vivid authorized sets than

that of the threshold scheme.

19:17 [Pub][ePrint]

Many index calculus algorithms generate multiplicative relations

between smoothness basis elements by using a process called {\\it

Sieving}. This process allows to filter potential candidate

relations very quickly, without spending too much time to consider bad

candidates. However, from an asymptotic point of view, there is not

much difference between sieving and straightforward testing of

candidates. The reason is that even when sieving, some small amount

time is spend for each bad candidates. Thus, asymptotically, the total

number of candidates contributes to the complexity.

In this paper, we introduce a new technique: {\\it Pinpointing}, which

allows us to construct multiplicate relations much faster, thus

reducing the asymptotic complexity of relations\'

construction. Unfortunately, we only know how to implement this

technique for finite fields which contain a medium-sized

subfield. When applicable, this method improves the asymptotic

complexity of the index calculus algorithm in the cases where the sieving

phase dominates. In practice, it gives a very interesting boost to the

performance of state-of-the-art algorithms. We illustrate the

feasability of the method with a discrete logarithm record in a

medium prime finite field of total size 1175~bits.

19:17 [Pub][ePrint]

The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001).

An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin\\rq{}s transformation can be applied to any so called 3-round Fiat-Shamir proof of knowledge\\rq{}\\rq{} and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to decouple the hash function from the protocol flow\" and hence, the counterexample in the work of Goldwaaser and Kalai does not seem to carry over to this setting.

In this work, we show a counterexample to the Fischlin\'s transformation. In particular, we construct a 3-round Fiat-Shamir proof of knowledge (on which Fischlin\'s transformation is applicable), and then, present an adversary against both - the soundness of the resulting non-interactive zero-knowledge, as well as the unforegeability of the resulting signature scheme. Our attacks are successful except with negligible probability for any hash function, that is used to instantiate the random oracle, provided that there is an apriori (polynomial) bound on the running time of the hash function. By choosing the right bound, secure instantiation of Fischlin transformation with most practical cryptographic hash functions can be ruled out.

The techniques used in our work are quite unrelated to the ones used in the work of Goldwasser and Kalai. Our primary technique is to bind the protocol flow with the hash function if the code of the hash function is available. We believe that our ideas are of independent interest and maybe applicable in other related settings.

19:17 [Pub][ePrint]

A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to hash\" the inputs into a smaller domain before applying the PRF. This approach, known as Levin\'s trick\", is used to achieve PRF domain extension\" (using a short, e.g., fixed, input length PRF to get a variable-length PRF), and more recently to transform non-adaptive PRFs to adaptive ones. Such reductions, however, are vulnerable to a birthday attack\": after $\\sqrt{|\\mathcal U|}$ queries to the resulting PRF, where $\\mathcal U$ being the hash function range, a collision (i.e., two distinct inputs have the same hash value) happens with high probability. As a consequence, the resulting PRF is insecure against an attacker making this number of queries.

In this work we show how to go beyond the birthday attack barrier, by replacing the above simple hashing approach with a variant of cuckoo hashing --- a hashing paradigm typically used for resolving hash collisions in a table, by using two hash functions and two tables, and cleverly assigning each element into one of the two tables. We use this approach to obtain: (i) A domain extension method that requires just two calls to the original PRF, can withstand as many queries as the original domain size and has a distinguishing probability that is exponentially small in the non cryptographic work. (ii) A security-preserving reduction from non-adaptive to adaptive PRFs.

19:17 [Pub][ePrint]

In order to prevent the SPA (Simple Power Analysis) attack against modular exponentiation algorithms, a multiply-always implementation is generally used. Witteman et al. introduced in \\cite{WI} a new cross-correlation power analysis attack against the multiply-always implementation. We suggest two new algorithms, resistant to this attack and also to other known attacks.

The first algorithm is an alternative approach to exponentiation algorithms used in cryptography, which usually receive as an input some representation (e.g. binary) of the exponent. In our approach both the exponent and the result are functions (not necessarily easily invertible) of the exponentiation algorithm input. We show that this approach can have a good performance and that it is also resistant to several known attacks, especially to the cross-correlation power analysis. It is particularly relevant for cryptographic schemes in which the private exponent can be chosen arbitrarily.

Another exponentiation algorithm that we present here may be preferable for use with RSA in certain settings. It is resistant to the cross-correlation power analysis attack, C safe error attack, and other attacks; although it involves squaring operations.

2012-12-23
16:51 [Job][New]

Description and Responsibilities:

Embedded platforms comprising SoCs, i.e., Tablets and Smartphones, have become important players in the products offered by Intel. One of the key component of SoC-based platforms is the baseband processor. The goal of this internship is to investigate the threats posed to/by baseband to a phone platform. In this position, you will be a member of the Security Center of Excellence (SeCoE) in the Intel Architecture Group to identify security vulnerabilities in the architecture, design and implementation of future SoC-based products. During this internship, your responsibilities will include but not be limited to:

- Performing the threat analysis of a current baseband processor,

- Driving the investigation of Intel baseband software and hardware for evaluating their security features,

- Researching literature from conferences (e.g.; BlackHat, PacSec) and technical forums to find out relevant attacks.

You will also be developing software and/or hardware solutions to hack the platform.

Qualifications:

You must be currently enrolled in a Ph.D or a Master\\\'s degree program in Computer Science, Computer Engineering or Electrical Engineering or equivalent discipline with knowledge of computer security, applied cryptography, computer architecture, hardware design (SystemVerilog or VHDL) and programming (C, Assembly). Demonstrable results in academic projects involving the above areas are essential. Exposure to security threat analysis and knowledge of existing attacks on security of System-on-chip (SoC) based platforms (For example, smartphones) would be highly desirable. Experience with hacking hardware (programming FPGAs, Flash chips etc) will be a plus. Behavioral skills include: solid analytical skills, willingness to tackle complex problems, attention to detail, self-driven, excellent written and verbal communication skills.