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

03:17 [Pub][ePrint]

In Asiacrypt 2010, Knellwolf, Meier and Naya-Plasencia proposed

distinguishing attacks on Grain v1 when (i) Key Scheduling process is

reduced to 97 rounds using $2^{27}$ chosen IVs and (ii) Key Scheduling process is

reduced to 104 rounds using $2^{35}$ chosen IVs. Using similar idea, Banik

obtained a new distinguisher for 105 rounds.

In this paper, we show similar approach can work for 106 rounds. We present

a new distinguisher on Grain v1 for 106 rounds with success probability 63\\%.

03:17 [Pub][ePrint]

Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a central hub\'\' for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. In this paper we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows:

-- There is no fully black-box construction with a polynomial security loss of a collision-resistant function family from a general-purpose indistinguishability obfuscator.

-- There is no fully black-box construction with a polynomial security loss of a key-agreement protocol with perfect completeness from a general-purpose private-key functional encryption scheme.

-- There is no fully black-box construction with a polynomial security loss of an indistinguishability obfuscator for oracle-aided circuits from a private-key functional encryption scheme for oracle-aided circuits.

Specifically, we prove that any such potential construction must suffer from at least a sub-exponential security loss. Our results are obtained within a subtle framework capturing constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.

03:17 [Pub][ePrint]

In this paper we present an identity-set-based broadcast encryption scheme with three working modes: positive membership (Select-mode), all member (All-mode), and negative membership (Cut-mode) over the user identity set, simultaneously.The core of our scheme is the implementation of cryptographic representation of subset by using two aggregation functions: Zeros-based aggregation and Poles-based aggregation. These two aggregation functions are capable of compressing any subset into one element in a bilinear map

group for determining the membership between an element and a subset. Our scheme achieves the optimal bound of O(1)-size for either ciphertext (consisting of just two elements) or decryption key (one element) for an identity set of large size. We prove that our scheme is secure under the

General Diffie-Hellman Exponent (GDHE) assumption.

03:17 [Pub][ePrint]

This paper presents new speed records for 128-bit secure elliptic-curve Diffie-Hellman key-exchange

software on three different popular microcontroller architectures. We consider a 255-bit curve proposed by Bernstein

known as Curve25519, which has also been adopted by the IETF. We optimize the X25519 key-exchange

protocol proposed by Bernstein in 2006 for AVR ATmega 8-bit microcontrollers, MSP430X 16-bit microcontrollers,

and for ARM Cortex-M0 32-bit microcontrollers. Our software for the AVR takes only 13 900 397 cycles

for the computation of a Diffe-Hellman shared secret, and is the first to perform this computation in less than

a second if clocked at 16 MHz for a security level of 128 bits. Our MSP430X software computes a shared secret

in 5 301 792 cycles on MSP430X microcontrollers that have a 32-bit hardware multiplier and in 7 933 296 cycles

on MSP430X microcontrollers that have a 16-bit multiplier. It thus outperforms previous constant-time ECDH

software at the 128-bit security level on the MSP430X by more than a factor of 1.2 and 1.15, respectively. Our

implementation on the Cortex-M0 runs in only 3 589 850 cycles and outperforms previous 128-bit secure ECDH

software by a factor of 3.

2015-04-19
21:17 [Pub][ePrint]

PAGES is a block cipher familiy basedon the design of Speck, see [1]. However, some intriguing design details of SPeck were not used in the design of PAGES. PAGES has a block size of 256 bit and comes in three versions:PAGES-512, PAGES-768 and PAGES-1024, where the number denotes the key length. The number of rounds is 64, 96, and 128, respectively. PAGES uses 128 bit variables, that is half of the block size.