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

Noisy channels are a powerful resource for cryptography as they can be used to obtain

information-theoretically secure key agreement, commitment and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csisz\\\'{a}r (\\emph{ISIT\'07}) presented upper and lower bounds on the OT capacity of generalized erasure channels (GEC) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and therefore the OT capacity was determined. It was later proved by Pinto et al. (\\emph{IEEE Trans. Inf. Theory 57(8)}) that in this case there is also a protocol against malicious adversaries achieving the same lower bound, and hence the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csisz\\\'{a}r does not

match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this work we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries.

In order to obtain our results we introduce a novel use of interactive hashing that is suitable for dealing with the case of low erasure probability ($p^* 03:17 [Pub][ePrint] Demands for lawful access to encrypted data are a long standing obstacle to integrating cryptographic protections into communication systems. A common approach is to allow a trusted third party (TTP) to gain access to private data. However, there is no way to verify that this trust is well place as the TTP may open all messages indiscriminately. Moreover, existing approaches do not scale well when, in addition to the content of the conversation, one wishes to hide ones identity. Given the importance of metadata this is a major problem. We propose a new signature scheme as an accountable replacement for group signatures, accountable forward and backward tracing signatures. 03:17 [Pub][ePrint] We propose a new algorithm to solve the Implicit Factorization Problem, which was introduced by May and Ritzenhofen at PKC\'09. In 2011, Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011) improved May and Ritzenhofen\'s results by making use of the technique for solving multivariate approximate common divisors problem. In this paper, based on the observation that the desired root of the equations that derived by Sarkar and Maitra contains large prime factors, which are already determined by some known integers, we develop new techniques to acquire better bounds. We show that our attack is the best among all known attacks, and give experimental results to verify the correctness. Additionally, for the first time, we can experimentally handle the implicit factorization for the case of balanced RSA moduli. 03:17 [Pub][ePrint] We initiate the study of a novel class of group-theoretic intractability problems. Inspired by the theory of learning in presence of errors [Regev, STOC\'05] we ask if noise in the exponent amplifies intractability. We put forth the notion of Learning with Errors in the Exponent (LWEE) and rather surprisingly show that various attractive properties known to exclusively hold for lattices carry over. Most notably are worst-case hardness and post-quantum resistance. In fact, LWEE\'s duality is due to the reducibility to two seemingly unrelated assumptions: learning with errors and the representation problem [Brands, Crypto\'93] in finite groups. For suitable parameter choices LWEE superposes properties from each individual intractability problem. The argument holds in the classical and quantum model of computation. We give the very first construction of a semantically secure public-key encryption system in the standard model. The heart of our construction is an error recovery\'\' technique inspired by [Joye-Libert, Eurocrypt\'13] to handle critical propagations of noise terms in the exponent. 03:17 [Pub][ePrint] We consider interactive proof systems over adversarial communication channels. We show that the seminal result that$\\ip = \\pspace$still holds when the communication channel is malicious, allowing even a constant fraction of the communication to be arbitrarily corrupted. 00:17 [Pub][ePrint] We present a lattice-based stateless signature scheme provably secure in the standard model. Our scheme has a constant number of matrices in the public key and a single lattice vector (plus a tag) in the signatures. The best previous lattice-based encryption schemes were the scheme of Ducas and Micciancio (CRYPTO 2014), which required a logarithmic number of matrices in the public key and that of Bohl et. al (J. of Cryptology 2014), which required a logarithmic number of lattice vectors in the signature. Our main technique involves using fully homomorphic computation to compute a degree d polynomial over the tags hidden in the matrices in the public key. In the scheme of Ducas and Micciancio, only functions linear over the tags in the public key matrices were used, which necessitated having d matrices in the public key. As a matter of independent interest, we extend Wichs\' (eprint 2014) recent construction of homomorphic trapdoor functions into a primitive we call puncturable homomorphic trapdoor functions (PHTDFs). This primitive abstracts out most of the properties required in many different lattice-based cryptographic constructions. We then show how to combine a PHTDF along with a function satisfying certain properties (to be evaluated homomorphically) to give an eu-scma signature scheme. 00:17 [Pub][ePrint] We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As opposed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to further trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups. As a first application we show a first single-round universally-composable password authenticated key-exchange (UC-PAKE) protocol which is secure under dynamic corruption in the erasure model. The single message flow only requires four group elements under the SXDH assumption, which is at least two times shorter than earlier schemes. As another application we give a short keyed-homomorphic CCA-secure encryption scheme. The ciphertext in this scheme consist of only six group elements (under the SXDH assumption) and the security reduction is linear-preserving. An earlier scheme of Libert et al based on their efficient unbounded simulation-sound QA-NIZK proofs only provided a quadratic-preserving security reduction, and further had ciphertexts almost twice as long as ours. 00:17 [Pub][ePrint] The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that \"breaks symmetry\" and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gr{\\\" o}bner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size. 00:17 [Pub][ePrint] A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \\emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \\emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \\emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the k-split-state model (the most desired case being k=2). Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against both leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks). In this paper we close this gap by showing a non-malleable code in the$2$-split state model that is secure against leaking almost a$1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code$(\\Enc,\\Dec)$in the$2$-split state model, and constructs out of it another non-malleable code$(\\Enc\',\\Dec\')$in the$2$-split state model that is additionally leakage-resilient. The rate of$(\\Enc\',\\Dec\')$is linear in the rate of$(\\Enc,\\Dec)$. Our construction requires that$\\Dec$is \\emph{symmetric}, i.e., for all$x, y$, it is the case that$\\Dec(x,y) = \\Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the$2\$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).

00:17 [Pub][ePrint]

The article proposes an Online/Off-line Ring Signature Scheme in random oracle model.Security of the scheme relies on both Computational Diffie-Hellman and k-CAA problems. The proposed scheme is proven the two most important security goals Existential

Unforgeability and Signer Ambiguity. Also it has robustness property where the misbehavior of the signer can be detected. Signing process is performed in two phases online and offline. All heavy computations are performed in Off-line stage. So the overall computational cost is reduced and very less than the traditional signature scheme. The scheme can be applied to Mobile Ad Hoc Networks (MANETs) that undergo node mobility.

00:17 [Pub][ePrint]

We consider secure two-party computation in the client-server model where there are two adversaries that operate separately but simultaneously, each of them corrupting one of the parties and a restricted subset of servers that they interact with. We model security via the local universal composability framework introduced by Canetti and Vald and we show that information-theoretically secure two-party computation is possible if and only if there is always at least one server which remains uncorrupted.