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-04-23
03:17 [Pub][ePrint]

In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most $2^{65.5}$. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.

03:17 [Pub][ePrint]

In an outsourced database scheme, the data owner delegates the data management tasks to a remote service provider. At a later time, the remote service is supposed to answer any query on the database. The essential requirements are ensuring the data integrity and authenticity with efficient mechanisms. Current approaches employ authenticated data structures to store security information, generated by the client and used by the server, to compute proofs that show the answers to the queries are authentic. The existing solutions have shortcomings with multi-clause queries and duplicate values in a column.

We propose a hierarchical authenticated data structure for storing security information, which alleviates the mentioned problems. Our solution handles many different types of queries, including multi-clause selection and join queries, in a dynamic database. We provide a unified formal definition of a secure outsourced database scheme, and prove that our proposed scheme is secure according to this definition, which captures previously separate properties such as correctness, completeness, and freshness. The performance evaluation based on our prototype implementation confirms the efficiency of our proposed scheme, showing about 3x to 5x enhancement in proof size and proof generation time in comparison to previous work, and about only 4% communication overhead compared to the actual query result in a real university database.

03:17 [Pub][ePrint]

Byzantine broadcast is a distributed primitive that allows a specific party to consistently distribute a message among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. The celebrated result of \\cite{PSL80} shows that broadcast is achievable from point-to-point channels if and only if $t < n/3$.

The following two generalizations have been proposed to the original broadcast problem. In~\\cite{FM98} the authors considered a \\emph{general adversary} characterized by the sets of parties that can be corrupted. It was shown that broadcast is achievable from point-to-point channels if and only if no three possible corrupted sets can cover the whole party set. In~\\cite{CFFLMM05} the notion of point-to-point channels has been extended to the $b$-minicast channels allowing to locally broadcast among any subset of $b$ parties. It has been shown that broadcast secure against adversaries corrupting up to $t$ parties is achievable from $b$-minicast if and only if $t < \\frac{b-1}{b+1}n$.

In this paper we combine both generalizations by considering the problem of achieving broadcast from $b$-minicast channels secure against general adversaries. Our main result is a condition on the possible corrupted sets such that broadcast is achievable from $b$-minicast if and only if this condition holds.

03:17 [Pub][ePrint]

We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. This family abstracts and includes as a special case several assumptions used in the literature under different names. Given some matrix $\\matrA$ sampled from some distribution $\\mathcal{D}_{\\ell,k}$, the kernel assumption says

that it is hard to find in the exponent\'\' a nonzero vector in the kernel of $\\mathbf{A}^\\top$. Our assumption is the natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala \\textit{et al}.

We show that the $\\mathcal{D}_{\\ell,k}$ Kernel DH Assumption is a strictly increasing family of weaker computational assumptions when $k$ grows. This requires ruling out the existence of some black-box reductions between flexible problems (\\textit{i.e.}, computational problems with a non unique solution), which is specially subtle.

As opposed to the decisional MDDH Assumption, our kernel assumption might hold in the recent candidate multilinear groups.

Kernel assumptions have implicitly been used in recent works on QA-NIZK and structure-preserving signatures. We also provide a new construction of commitments to group elements in the multilinear setting, based on any kernel assumption.

03:17 [Pub][ePrint]

TinyECC 2.0 is an open source library for Elliptic Curve Cryptography (ECC) in wireless sensor networks. This paper analyzes the side channel susceptibility of TinyECC 2.0 on a LOTUS sensor node platform.

In our work we measured the electromagnetic (EM) emanation during computation of the scalar multiplication using 56 different configurations of TinyECC 2.0. All of them were found to be vulnerable, but to a different degree. The different degrees of leakage include adversary success using (i) Simple EM Analysis (SEMA) with a single measurement, (ii) SEMA using averaging, and (iii) Multiple-Exponent Single-Data (MESD) with a single measurement of the secret scalar. It is extremely critical that in 30 TinyECC 2.0 configurations a single EM measurement of an ECC private key operation is sufficient to simply read out the secret scalar. MESD requires additional adversary capabilities and it affects all TinyECC 2.0 configurations, again with only a single measurement of the ECC private key operation. These findings give evidence that in security applications a configuration of TinyECC 2.0 should be chosen that withstands SEMA with a single measurement and, beyond that, an addition of appropriate randomizing countermeasures is necessary.

2015-04-22
06:17 [Pub][ePrint]

We construct a general multiparty computation (MPC) protocol in the common random string (CRS) model with only two rounds of interaction, which is known to be optimal. In the honest-but-curious setting we only rely on the learning with errors (LWE) assumption, and in the fully malicious setting we additionally assume the existence of non-interactive zero knowledge arguments (NIZKs). Previously, Asharov et al. (EUROCRYPT \'12) showed how to achieve three rounds based on LWE and NIZKs, while Garg et al. (TCC \'14) showed how to achieve the optimal two rounds based on indistinguishability obfuscation, but it was unknown if two rounds were possible under simpler assumptions without obfuscation.

Our approach relies on \\emph{multi-key fully homomorphic encryption (MFHE)}, introduced by Lopez-Alt et al. (STOC \'12), which enables homomorphic computation over data encrypted under different keys. We simplify a recent construction of MFHE based on LWE by Clear and McGoldrick (ePrint \'14), and give a stand-alone exposition of that scheme. We then extend this construction to allow for a one-round distributed decryption of a multi-key ciphertext. Our entire MPC protocol consists of the following two rounds:

- Each party individually encrypts its input under its own key and broadcasts the ciphertext. All parties can then homomorphically compute a multi-key encryption of the output.

- Each party broadcasts a partial decryption of the output using its secret key. The partial decryptions can be combined to recover the output in plaintext.

06:17 [Pub][ePrint]

We present the cryptographic implementation of \"DEMOS\", a new e-voting system that is end-to-end verifiable in the standard model, i.e., without any additional \"setup\" assumption or access to a random oracle (RO). Previously known end-to-end verifiable e-voting systems required such additional assumptions (specifically, either the existence of a \"randomness beacon\" or were only shown secure in the RO model). In order to analyze our scheme, we also provide a modeling of end-to-end verifiability as well as privacy and receipt-freeness that encompasses previous definitions in

the form of two concise attack games.

Our scheme satisfies end-to-end verifiability information theoretically in the standard model and privacy/receipt-freeness under a computational assumption (subexponential Decisional Diffie Helman). In our construction, we utilize a number of techniques used for the first time in the context of e-voting schemes that include utilizing randomness from bit-fixing sources, zero-knowledge proofs with imperfect verifier randomness and complexity leveraging.

03:17 [Pub][ePrint]

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF key $K$, we create a marked program $\\widetilde{C}$ that evaluates the PRF $F(K,\\cdot)$. An adversary that gets $\\widetilde{C}$ cannot come up with \\emph{any} program $C^*$ in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs.

The work of Barak et al. (CRYPTO\'01 and J.ACM, 59(2)) shows that, assuming indistinguishability obfuscation (iO), such watermarking is \\textit{impossible} if the marked program $\\widetilde{C}$ evaluates the original program with {perfect correctness}. In this work we show that, assuming iO, such watermarking is \\textit{possible} if the marked program $\\widetilde{C}$ is allowed to err with even a negligible probability, which would be undetectable to the user.

We construct such a watermarking scheme with a secret-marking key used to embed marks in programs, and a public-detection key that allows anyone to detect marks in programs. For our security definition, we assume that the adversary can get oracle access to the marking functionality.

We emphasize that our security notion of watermark non-removability considers arbitrary adversarial strategies to modify the marked program -- for example, an adversary could obfuscate the marked program and this should not remove the mark. This is in contrast to the prior works, such as that of Nishimaki (EUROCRYPT \'13), which only consider restricted removal strategies that preserve the original structure of the marked program (e.g., as a vector of group elements), but do not provide security against arbitrary strategies.

2015-04-21
19:51 [Job][Update]

The successful candidate will have the following prerequisites:

• An outstanding university degree in CS, Math, EE/CE

• Oral+written English; German an advantage

• Advanced knowledge of C/C++, ideally with experience in cross-site software development

• Interest in highest-level fundamental research

Prior knowledge in at least one and interest in another of the areas below is expected:

• Cryptanalysis methods, preferably side-channel analysis

• Integrated circuit design

• Algebraic solving methods (Gröbner/border bases)

• Coding theory, error-correcting codes

To be considered, applications must make reference to skills in at least one of the specific areas above and provide details on how they were acquired or demonstrated (e.g., advanced course at uni¬versity; thesis or other research work; industrial experience; work in an open-source project).

When you join us, you will conduct world-class research in collaboration with leading scientists; you will enjoy excellent work conditions in a publication-friendly environment, a competitive salary accompanied by the German public-service benefit package and attractive living conditions in Passau, a city of 50,000, located between Munich, Nuremberg and Vienna. The post is suitable for part-time employment and may be combined with a teaching contract upon request.

The University of Passau wishes to increase the proportion of its female staff and expressly encourages women to apply. Furthermore, this post is suitable for candidates with disabilities, who will be given preference if the personal aptitudes and qualifications are equal.

To apply, please send your full application (including school, training and work certificates) as a single pdf file to ilia.polian@uni-passau.de by no later than 30 May 2015.

16:06 [Job][New]

The successful candidate will have the following prerequisites:

• An outstanding university degree in CS, Math, EE/CE

• Oral+written English; German an advantage

• Advanced knowledge of C/C++, ideally with experience in cross-site software development

• Interest in highest-level fundamental research

Prior knowledge in at least one and interest in another of the areas below is expected:

• Cryptanalysis methods, preferably side-channel analysis

• Integrated circuit design

• Algebraic solving methods (Gröbner/border bases)

• Coding theory, error-detecting and error-correcting codes

To be considered, applications must make reference to skills in at least one of the specific areas above and provide details on how they were acquired or demonstrated.

When you join us, you will conduct world-class research in collaboration with the leading scientists in Germany and elsewhere; you will enjoy excellent work conditions in a publication-friendly environment, a competitive salary accompanied by the German public-service benefit package and attractive living conditions in Passau, a city of 50,000, located between Munich, Nuremberg and Vienna. The post is suitable for part-time employment and may be combined with a teaching contract upon request.

The University of Passau wishes to increase the proportion of its female staff and expressly encourages women to apply. Furthermore, this post is suitable for candidates with disabilities, who will be given preference if the personal aptitudes and qualifications are equal.

To apply, please send your full application (including school, training and work certificates) as a single pdf file to ilia.polian (at) uni-passau.de by no later than 30 May 2015. Once the application process has been completed, we will retain your application on file for five months before deleting it.

2015-04-20
03:17 [Pub][ePrint]

With computation power in the cloud becoming a commodity, it is more and more convenient to outsource computations to external computation parties. Assuring confidentiality, even of inputs by mutually distrusting inputters, is possible by distributing computations between different parties using multiparty computation. Unfortunately, this typically only guarantees correctness if a limited number of computation parties are malicious. If correctness is needed when all computation parties are malicious, then one currently needs either fully homomorphic encryption or universally verifiable\'\' multiparty computation; both are impractical for large computations. In this paper, we show for the first time how to achieve practical privacy-friendly outsourcing with correctness guarantees, by using normal multiparty techniques to compute the result of a computation, and then using slower verifiable techniques only to verify that this result was correct. We demonstrate the feasibility of our approach in a linear programming case study.