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

2014-09-26
09:17 [Pub][ePrint]

The latest implementations of pairings allow efficient schemes for Pairing Based Cryptography. These make the use of pairings suitable for small and constrained devices (smart phones, smart cards...) in addition to more powerful platforms. As for any cryptographic algorithm which may be deployed in insecure locations, these implementations must be secure against physical attacks, and in particular fault attacks. In this paper, we present the state-of-the-art of fault attacks against pairing algorithms, more precisely fault attacks against the Miller algorithm and the final exponentiation which are the two parts of a pairing calculation.

09:17 [Pub][ePrint]

To gain strong confidence in the security of a public-key scheme, it

is most desirable for the security proof to feature a \\emph{tight}

reduction between the adversary and the algorithm solving the

underlying hard problem. Recently, Chen and Wee (Crypto\\,\'13) described the first Identity-Based Encryption scheme with almost

tight security under a standard assumption. Here, almost tight\'\'

means that the security reduction only loses a factor $O(\\lambda)$

-- where $\\lambda$ is the security parameter -- instead of a factor

proportional to the number of adversarial queries. Chen and Wee

also gave the shortest signatures whose security almost tightly

relates to a simple assumption in the standard model. Also recently,

Hofheinz and Jager (Crypto\\,\'12) constructed the first CCA-secure

public-key encryption scheme in the multi-user setting with tight

security. These constructions give schemes that are significantly

less efficient in length (and thus, processing) when compared with

the earlier schemes with loose reductions in their proof of

security. Hofheinz and Jager\'s scheme has a ciphertext of a few

hundreds of group elements, and they left open the problem of

finding truly efficient constructions. Likewise, Chen and Wee\'s

signatures and IBE schemes are somewhat less efficient than previous

constructions with loose reductions from the same assumptions. In

this paper, we consider space-efficient schemes with security almost

tightly related to standard assumptions. As a step in solving the

open question by Hofheinz and Jager, we construct an efficient

CCA-secure public-key encryption scheme whose chosen-ciphertext

security in the multi-challenge, multi-user setting almost tightly

relates to the DLIN assumption (in the standard model). Quite

remarkably, the ciphertext size decreases to $69$ group elements

under the DLIN assumption whereas the best previous solution required about $400$ group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) we develop here and which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive

non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla

and Roy (Asiacrypt\\,\'13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by $37\\%$ under the Decision Linear assumption, by almost $50\\%$ under the $K$-LIN assumption, and it becomes only $3$ group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.

09:17 [Pub][ePrint]

By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity.

09:17 [Pub][ePrint]

We introduce the concept of universal signature aggregators. In a universal signature aggregator system, a third party, using a set of common reference parameters, can aggregate a collection of signatures produced from any set of signing algorithms (subject to a chosen length constraint) into one short signature whose length is independent of the number of signatures aggregated. In prior aggregation works, signatures can only be aggregated if all signers use the same signing algorithm (e.g., BLS) and shared parameters. A universal aggregator can aggregate across schemes even in various algebraic settings (e.g., BLS, RSA, ECDSA), thus creating novel opportunities for compressing authentication overhead. It is especially compelling that existing public key infrastructures can be used and that the signers do not have to alter their behavior to enable aggregation of their signatures.

We provide multiple constructions and proofs of universal signature aggregators based on indistinguishability obfuscation and other supporting primitives. We detail our techniques as well as the tradeoffs in features and security of our solutions.

09:17 [Pub][ePrint]

In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions.

In particular, we show how this concept can be implemented to

provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.

09:17 [Pub][ePrint]

In this paper, we investigate the Mixed-integer Linear Programming (MILP) modelling of the differential and linear behavior of a wide rang of block ciphers.

The differential and linear behavior of the transformations involved in a block cipher can be described by a set $P \\subseteq \\{0,1\\}^n \\subseteq \\mathbb{R}^n$.

We show that $P$ is exactly the set of all 0-1 solutions of the H-representation of the convex hull of $P$. In addition, we can find a small number of inequalities in the H-representation of the convex hull of $P$ such that the set of all 0-1 solutions of these inequalities equals $P$.

~~~~~~Based on these discoveries and MILP technique, we propose an automatic method for finding high probability (related-key) differential or linear characteristics of block ciphers. Compared with Sun {\\it et al.}\'s {\\it heuristic} method presented in Asiacrypt 2014, the new method is {\\it exact} for most ciphers in the sense that every feasible 0-1 solution of the MILP model generated by the new method corresponds to a valid characteristic, and therefore there is no need to repeatedly add valid cutting-off inequalities into the MILP model as is done in Sun {\\it et al.}\'s method; the new method is more powerful which allows us to get the {\\it exact lower bounds} of the number of differentially or linearly active S-boxes; and the new method is more efficient which is able to obtain characteristic enjoying higher probability or covering more rounds of a cipher with less computational effort.

~~~~~Moreover, by employing a type of specially constructed linear inequalities which can remove {\\it exactly one} feasible 0-1 solution from the feasible region of an MILP problem, we propose a method for automatic enumeration of {\\it all} (related-key) differential or linear characteristics with some predefined properties, {\\it e.g.}, characteristics with given input or/and output difference/mask, or with limited number of active S-boxes. Such a method is very useful in the

automatic (related-key) differential analysis, truncated (related-key) differential analysis, linear hull analysis, and the automatic construction of (related-key) boomerang/rectangle distinguishers.

~~~~~~The methods presented in this paper are implemented and extensive experiments are performed. To demonstrate the usefulness of these methods, we apply them to SIMON, PRESENT, Serpent, LBlock, DESL, and we obtain improved cryptanalytic results. For example, we find single-key differentials covering 16 and 22 rounds of SIMON48 and SIMON64 (block ciphers designed by the U.S. National Security Agency) respectively. These are the longest differentials for SIMON48 and SIMON64 published so far.

09:17 [Pub][ePrint]

Being required in many applications, modular exponentiations form the most expensive part of modern cryptographic primitives. It is a significant challenge for resource-constrained mobile devices to perform these heavy computations (e.g., mobile devices that require secure cryptographic computations or RFID tags). Cloud services can significantly enhance the computational capability of these devices. In this way, expensive computations at client side can significantly be reduced by means of secure outsourcing modular exponentiations to a potentially untrusted server S. In this paper, we study this problem which is an active research area of mobile and cloud computing, and mostly known as secure outsourced computation. We propose new efficient outsourcing algorithms for modular exponentiations using only one untrusted cloud service provider solving an open problem highlighted in [11]. These algorithms cover each possible case ranging from public-base & private-exponent, private-base & public-exponent, private-base & private-exponent to the most general private-basis & private-exponents simultaneous modular exponentiations. Our algorithms are the most efficient outsourced computation algorithms to date which use single untrusted server and have the best checkability (verifiability) property. Finally, we give two different real-life applications for outsourcing within the realm of Oblivious Transfer protocols and Blind Signatures.

09:17 [Pub][ePrint]

Physical Unclonable Functions (PUFs) are specialized circuits with applications including key generation and challenge-response authentication. PUF properties such as low cost and resistance to invasive attacks make PUFs well-suited to embedded devices. Yet, given how infrequently the specialized capabilities of a PUF may be needed, the silicon area dedicated to it is largely idle. This inefficient resource usage is at odds with the cost minimization objective of embedded devices. Motivated by this inefficiency, we propose the Bitline PUF -- a novel PUF that uses modified wordline drivers together with SRAM circuitry to enable challenge-response authentication. The number of challenges that can be applied to the Bitline PUF grows exponentially with the number of SRAM rows, and these challenges can be applied at any time without power cycling. This paper presents in detail the workings of the Bitline PUF, and shows that it achieves high throughput, low latency, and uniqueness across instances. Circuit simulations indicate that the Bitline PUF responses have a nominal bit-error-rate (BER) of 0.023 at 1.2 V supply and 27C, and that BER does not exceed 0.076 when supply voltage is varied from 1.1 V to 1.3 V, or when temperature is varied from 0C to 80C. Because the Bitline PUF leverages existing SRAM circuitry, its area overhead is only a single flip-flop and two logic gates per row of SRAM. The combination of high performance and low cost makes the Bitline PUF a promising candidate for commercial adoption and future research.

2014-09-24
13:26 [Event][New]

Submission: 22 November 2015
From June 30 to July 2

13:26 [Event][New]

Submission: 20 October 2014
From December 16 to December 17
Location: Beijing, China