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

2015-03-13
12:17 [Pub][ePrint]

Abstract. Design of secure light-weight stream ciphers is an important area in cryptographic hardware & embedded systems and a very recent design by Armknecht and Mikhalev (FSE 2015) has received serious attention that uses shorter internal state and still claims to resist the time-memory-data-tradeoff (TMDTO) attacks. An instantiation of this design paradigm is the stream cipher named Sprout with 80-bit secret key. In this paper we cryptanalyze the cipher and refute various claims. The designers claim that the secret key of Sprout can not be recovered efficiently from the complete state information using a guess and determine attack. However, in this paper, we show that it is possible with a few hundred bits in practical time. More importantly, from around 850 key-stream bits, complete knowledge of NFSR (40 bits) and a partial knowledge of LFSR (around one third, i.e., 14 bits); we can obtain all the secret key bits. This cryptanalyzes Sprout with 2^{54} attempts (considering constant time complexity required by the SAT solver in each attempt, which is around 1 minute in a laptop). This is less than the exhaustive key search. Further, we show how related ideas can be employed to mount a fault attack against Sprout that requires around 120 faults in random locations (20 faults, if the locations are known), whereas the designers claim that such a fault attack may not be possible. Our cryptanalytic results raise quite a few questions about this design paradigm in general that should be revisited with greater care.

12:17 [Pub][ePrint]

Attribute-based credentials allow a user to prove properties about herself anonymously. Revoking such credentials, which requires singling them out, is hard because it is at odds with anonymity. All revocation schemes proposed to date either sacrifice anonymity altogether, require the parties to be online, or put high load on the user or the verifier. As a result, these schemes are either too complicated for low-powered devices like smart cards or they do not scale. We propose a new revocation scheme that has a very low computational cost for users and verifiers, and does not require users to process updates. We trade only a limited, but well-defined, amount of anonymity to make the first practical revocation scheme that is efficient at large scales and fast enough for smart cards.

12:17 [Pub][ePrint]

We reinvestigate a notion of {\\em one-time programs} introduced in the CRYPTO 2008 paper by Goldwasser {\\it et~al.} A one-time program is a device containing a program $C$, with the property that the program $C$ can be executed on at most one input. Goldwasser {\\it et~al.}~show how to implement one-time programs on devices equipped with special hardware gadgets called {\\em one-time memory} tokens.

We provide an alternative construction that does not rely on the hardware gadgets. Instead, it is based on the following assumptions: (1) the total amount of data that can leak from the device is bounded, and (2) the total memory on the device (available both to the honest user and to the attacker) is also restricted, which is essentially the model used recently by Dziembowski {\\it et al.}\\ (TCC 2011, CRYPTO 2011) to construct one-time computable {\\em pseudorandom} functions and key-evolution schemes.

04:06 [Job][New]

Design and develop security solutions utilizing vetted cryptographic primitives. Application areas include Internet of Things (IoT), sensors, cyber-physical systems, and cloud and cognitive computing. Architectures must meet security and privacy requirements that involve, in particular, device and/or user identity management under various constraints on connectivity, communications bandwidth, processing complexity, and power consumption.

The investigation may include the use of proxy devices to bridge secure authorized communications between IoT sensor endpoint nodes and data collection-, data processing/analyzing/aggregating-, and feedback/calibration- providing- systems. Robustness against various forms of denial of service should be considered.

3+ years of coding experience in C/C++ is required. Proficiency in programming devices such as Arduino, Raspberry Pi, and BeagleBone Black is a definite plus.

This is a 3-month position with flexible start/end dates during May - September 2015 time frame.

2015-03-12
09:17 [Pub][ePrint]

Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem is an instance of lattice-based cryptosystems whose security is based on the hardness of lattice problems. In fact, GGH cryptosystem is the lattice version of the first code-based cryptosystem, proposed by McEliece. However, it has a number of drawbacks such as; large public key length and low security level. On the other hand, Low Density Lattice Codes (LDLCs) are the practical classes of linear codes which can achieve capacity on the additive white Gaussian noise (AWGN) channel with low complexity decoding algorithm. This paper introduces a public key cryptosystem based on LDLCs to withdraw the drawbacks of GGH cryptosystem. To reduce the key length, we employ the generator matrix of the used LDLC in Hermite normal form (HNF) as the public key. Also, by exploiting the linear decoding complexity of the used LDLC, the decryption complexity is decreased compared to GGH cryptosystem. These increased efficiencies allow us to use the bigger values of security parameters. Moreover, we exploit the special Gaussian vector whose variance is upper bounded by the Poltyrev limit as the perturbation vector. These techniques can resist the proposed scheme against the most efficient attacks to the GGH-like cryptosystems.

09:17 [Pub][ePrint]

Motivated by the security and functional limitations of satellite positioning systems, we explore a design of a Wide-Area Secure Positioning System. The main goals of this system are strong spoofing resilience, location verification, and privacy. We propose a realization of a Wide-Area Secure Positioning System and show that this solution is viable and can fulfill our defined security goals. Specifically, our system is composed of a secure positioning infrastructure to obtain reliable location information of an entity and a location verification architecture that allows others to be convinced of certain location properties of such an entity. The proposed system enables the verification of location claims in a privacy-preserving manner, thus enhancing existing security solutions and supporting future location-based applications.

09:17 [Pub][ePrint]

Sprout is a new lightweight stream cipher proposed at FSE 2015.

According to its designers, Sprout can resist time-memory-data trade-off (TMDTO) attacks with small internal state size.

However, we find a weakness in the updating functions of Sprout and propose a related-key chosen-IV distinguishing attack on full Sprout.

Our attack enable the adversary to distinguish detect non-randomness on full 320-round Sprout with a practical complexity (no more than $2^{20}$ key-IV pairs).

09:17 [Pub][ePrint]

A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than $2^{10}$ times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack raises legitimate questions regarding the security of the proposed design method.

09:17 [Pub][ePrint]

Definitions of election verifiability in the computational model of cryptography are proposed. The definitions formalize notions of voters verifying their own votes, auditors verifying the tally of votes, and auditors verifying that only eligible voters vote. The Helios (Adida et al., 2009) and JCJ (Juels et al., 2010) election schemes are shown to satisfy these definitions. Two previous definitions (Juels et al., 2010; Cortier et al., 2014) are shown to permit election schemes vulnerable to attacks, whereas the new definitions prohibit those schemes.

2015-03-11
16:45 [Event][New]

Submission: 24 May 2015