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

2013-03-20
03:05 [Event][New]

Submission: 12 July 2013
From December 16 to December 20
Location: Kolkata, India

2013-03-19
21:17 [Pub][ePrint]

We describe different strategies a central authority, the boss, can use to distribute computation to untrusted contractors. Our problem is inspired by volunteer distributed computing projects such as SETI@home, which outsource computation to large numbers of participants. For many tasks, verifying a task\'s output requires as much work as computing it again; additionally, some tasks may produce certain outputs with greater probability than others. A selfish contractor may try to exploit these factors, by submitting potentially incorrect results and claiming a reward. Further, malicious contractors may respond incorrectly, to cause direct harm or to create additional overhead for result-checking.

We consider the scenario where there is a credit system whereby users can be rewarded for good work and fined for cheating. We show how to set rewards and fines that incentivize proper behavior from rational contractors, and mitigate the damage caused by malicious contractors. We analyze two strategies: random double-checking by the boss, and hiring multiple contractors to perform the same job.

We also present a bounty mechanism when multiple contractors are employed; the key insight is to give a reward to a contractor who catches another worker cheating. Furthermore, if we can assume that at least a small fraction h of the contractors are honest (1% − 10%), then we can provide graceful degradation for the accuracy of the system and the work the boss has to perform. This is much better than the Byzantine approach, which typically assumes h > 60%.

2013-03-15
06:17 [Pub][ePrint]

During an ongoing examination of the practical complexity of the Number Field Sieve (NFS) in the medium prime case we have noticed numerous interesting patterns. In this paper we present findings on the complexity in practice of an aspect of the sieving stage. The contributions of these observations to the computational mathematics community are twofold: firstly, they bring us a step closer to understanding the true practical complexity of the algorithm and secondly, they enabled the development of a test for the effectiveness of the polynomials used in the NFS. The results of this work are of particular interest to cryptographers: the practical complexity of the NFS determines directly the security level of some discrete logarithm problem based protocols, such as those arising in pairing-based cryptography.

06:17 [Pub][ePrint]

In [eprint.iacr.org/2012/663] method of virtual isomorphisms of ciphers was applied for differential/linear cryptanalysis of AES. It was shown that AES seems to be weak against those attacks. That result can be generalized to AES-like ciphers, which diffusion map is a block matrix, and its block size is the same as the S-box size. S-box is possibly weak if it is affine equivalent to a substitution that has the same cycling type as an affine substitution. Class of possibly weak S-boxes is very large; we do not know is there an S-box that is not possibly weak. Strength of AES-like cipher is defined by virtual isomorphism and not by differential/linear properties of the S-box. So we can assume that special S-boxes have little or no advantage comparatively to random nonlinear S-boxes. The conjecture is verified by experiments. If the conjecture is true, then search of the best S-boxes that maximizes the cipher strength against differential and linear attacks joined with virtual isomorphisms has no sense.

06:17 [Pub][ePrint]

Data integrity and storage efficiency are two important requirements for cloud storage. Proof of Retrievability (POR) and Proof of Data Possession (PDP) techniques assure data integrity for cloud storage. Proof of Ownership (POW) improves storage efficiency by securely removing unnecessarily duplicated data on the storage server. However, trivial combination of the two techniques, in order to achieve both data integrity and storage efficiency, results in non-trivial duplication of metadata (i.e., authentication tags), which contradicts the objectives of POW. Recent attempts to this problem introduce tremendous computational and communication costs and have been proven not secure. It calls for a new solution to support efficient and secure data integrity auditing with storage deduplication for cloud storage. In this paper we solve this open problem with a novel scheme based on techniques including polynomial-based authentication tags and homomorphic linear authenticators. Our design allows deduplication of both files and their corresponding authentication tags. Data integrity auditing and storage deduplication are achieved simultaneously. Our proposed scheme is also characterized by constant realtime communication and computational cost on the user side. Public auditing and batch auditing are both supported. Hence, our proposed scheme outperforms existing POR and PDP schemes while providing the additional functionality of deduplication. We prove the security of our proposed scheme based on the Computational Diffie-Hellman problem and the Strong Diffie-Hellman assumption. Numerical analysis and experimental results on Amazon AWS show that our scheme is efficient and scalable.

06:17 [Pub][ePrint]

TCS\\_SHA-3 is a family of four cryptographic hash functions that are covered by an US patent (US 2009/0262925). The digest sizes are 224, 256, 384 and 512 bits. The hash functions use bijective functions in place of the standard, compression functions. In this paper we describe first and second preimage attacks on the full hash functions. The second preimage attack requires negligible time and the first preimage attack requires $O(2^{36})$ time. In addition to these attacks, we also present a negligible-time second preimage attack on a strengthened variant of the TCS\\_SHA-3. All the attacks have negligible memory requirements.

06:17 [Pub][ePrint]

To against some known attacks to Secure Shell (SSH), I propose some fixes to SSH. The fixes include add a key producer function and revise the MAC.

06:17 [Pub][ePrint]

Securely deleting data from storage systems has become difficult

today. Most storage space is provided as a virtual resource and traverses

many layers between the user and the actual physical storage medium.

Operations to properly erase data and wipe out all its traces are

typically not foreseen. This paper introduces a cryptographic model

for policy-based secure deletion of data in storage systems, whose

security relies on the proper erasure of cryptographic keys.

Deletion operations are expressed in terms of a deletion policy that

describes data destruction through deletion attributes and

protection classes. A protection class is first applied to the

stored data. Later, a secure deletion operation takes attributes as

parameters and triggers the destruction of all data whose protection

class is deleted according to the policy. No stored data is ever

re-encrypted. A cryptographic construction is presented for

deletion policies given by directed acyclic graphs; it is built in a

modular way from exploiting that secure deletion schemes may be

composed with each other. Finally, the paper describes a prototype

implementation of a Linux filesystem with policy-based secure

deletion.

06:17 [Pub][ePrint]

Most of certificateless signature schemes without random oracles can not resist key replacement attack. To overcome this security weakness, Yu et al. recently propose a new certificateless signature scheme and claimed that their scheme is provably secure in the standard model. However, in this paper, we show their scheme is still insecure against key replacement attack where an adversary who replaces the public key of a signer can forge valid signatures on any messages for that signer without knowing the signer\'s partial secret key. Moreover, we show Yu et al.\'s certificateless signature scheme is vulnerable to malicious-but-passive\'\' KGC attack where a malicious KGC can forge valid signatures by embedding extra trapdoors in the system parameter.

06:17 [Pub][ePrint]

We investigate alternative suspicion functions for Tardos traitor tracing schemes. In the simple decoder approach (computation of a score for every user independently) we derive suspicion functions that optimize a performance indicator related to the sufficient code length $\\ell$ in the limit of large coalition size $c$. Our results hold for the Restricted-Digit Model as well as the Combined-Digit Model. The scores depend on information that is usually not available

to the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such results can be used in realistic contexts.

We study several combinations of coalition attack strategy vs. suspicion function optimized against some attack (another attack or the same). In many of these combinations the usual scaling $\\ell \\propto c^2$ is replaced by a lower power of $c$, e.g. $c^{3/2}$. We find that the interleaving strategy is an especially

powerful attack, and the suspicion function tailored against interleaving is effective against all considered attacks.

06:17 [Pub][ePrint]

One of the main tools to construct secure two-party computation protocols are Yao garbled circuits. Using the cut-and-choose technique, one can get reasonably efficient Yao-based protocols with security against malicious adversaries. At TCC 2009, Nielsen and Orlandi suggested to apply cut-and-choose at the gate level, while previously cut-and-choose was applied on the circuit as a whole. This appealing idea allows for a speed up with practical significance (in the order of the logarithm of the size of the circuit) and has become known as the LEGO\'\' construction. Unfortunately the construction by Nielsen and Orlandi is based on a specific number-theoretic assumption and requires public-key operations per gate of the circuit.

The main technical contribution of this work is a new XOR-homomorphic commitment scheme based on oblivious transfer, that we use to cope with the problem of connecting the gates in the LEGO construction. Our new protocol has the following advantages:

\\begin{enumerate}

\\item

It maintains the efficiency of the LEGO cut-and-choose.

\\item

After a number of seed oblivious transfers linear in the security parameter, the construction uses only primitives from Minicrypt (i.e., private-key cryptography) per gate in the circuit (hence the name MiniLEGO).

\\item

On the contrary of original LEGO, MiniLEGO is compatible with all known optimization for Yao garbled gates (row reduction, free-XORs, point-and-permute).

\\end{enumerate}