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

2012-08-16
07:59 [Event][New]

Submission: 27 August 2012
From January 29 to February 1

07:58 [Job][New]

Topic: Lattice-based cryptography

Supervisor: Prof. Steven Galbraith

Duration: Approx 18-24 months

Salary: Approx NZ$55,000-70,000 (US$ 44K-56K) depending on the experience of the candidate and other factors

Start date: Preferably between November 2012-March 2013

Application process:

There is no formal application process. If you are interested in learning more about the position then please send a copy of your CV by email to s.galbraith (at) math.auckland.ac.nz , preferably before September 8, 2012.

Project Details:

The project will be on the security and implementation of lattice-based cryptosystems. The specific topic of the research will depend on the technical skills and experience of the successful candidate. Some possible projects might include:

• development and analysis of algorithms for lattice problems

• development and security analysis of lattice-based cryptosystems

• efficient software and/or hardware implementation of lattice systems

The successful applicant will have (or be very near to completion) a PhD in mathematics/computer science/engineering and a research track record in at least one of the following areas:

• theoretical cryptography

• computational number theory and lattices

• software/hardware implementation of cryptographic systems.

The University of Auckland is New Zealand\'s leading university and is the highest ranked New Zealand university in the major rankings of world universities.

The Mathematics Department is the strongest mathematics department in New Zealand and is situated on the main City Campus, located in the heart of Auckland.

The city of Auckland is a wonderful place to live, with a harbour setting, great sailing, mag

2012-08-14
09:17 [Pub][ePrint]

\\emph{Succinct arguments of knowledge} are computationally-sound proofs of knowledge for NP where the verifier\'s running time is independent of the time complexity $t$ of the nondeterministic NP machine $M$ that decides the given language.

Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs (PCPs). Yet, even when instantiating these constructions with state-of-the-art PCPs, the prover needs $\\Omega(t)$ space in order to run in quasilinear time (i.e., time $t \\poly(k)$), regardless of the space complexity $s$ of the machine $M$.

We say that a succinct argument is \\emph{complexity preserving} if the prover runs in time $t \\poly(k)$ and space $s \\poly(k)$ and the verifier runs in time $|x| \\poly(k)$ when proving and verifying that a $t$-time $s$-space random-access machine nondeterministically accepts an input $x$. Do complexity-preserving succinct arguments exist? To study this question, we investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs (MIPs) and stronger cryptographic techniques:

(1) We construct a one-round succinct MIP of knowledge, where each prover runs in time $t \\polylog(t)$ and space $s \\polylog(t)$ and the verifier runs in time $|x| \\polylog(t)$.

(2) We show how to transform any one-round MIP protocol to a succinct four-message argument (with a single prover), while preserving the time and space efficiency of the original MIP protocol; using our MIP protocol, this transformation yields a complexity-preserving four-message succinct argument.

As a main tool for our transformation, we define and construct a \\emph{succinct multi-function commitment} that (a) allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and (b) ensures that the receiver\'s running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption (and no additional assumptions are needed for our succinct argument).

(3) In addition, we revisit the problem of \\emph{non-interactive} succinct arguments of knowledge (SNARKs), where known impossibilities prevent solutions based on black-box reductions to standard assumptions. We formulate a natural (but non-standard) variant of homomorphic encryption having a \\emph{homomorphism-extraction property}. We show that this primitive essentially allows to squash our interactive protocol, while again preserving time and space efficiency, thereby obtaining a complexity-preserving SNARK. We further show that this variant is, in fact, implied by the existence of (complexity-preserving) SNARKs.

09:17 [Pub][ePrint]

Protocol for fair exchange of digital signatures is essential in many applications including contract signing, electronic commerce, or even peer-to-peer file sharing. In such a protocol, two parties, Alice and Bob, would like to exchange digital signatures on some messages in a fair way. It is known that a trusted arbitrator is necessary in the realization of such a protocol.

We identify that in some scenarios, it is required that prior to the completion of the protocol, no observer should be able to tell whether Alice and Bob are conducting such an exchange. Consider the following scenario in which Apple engages Intel in an exchange protocol to sign a contract that terminates their OEM agreement. The information would be of value to a third party (such as the stock broker, or other OEM companies). If the protocol transcript can serve as an evidence that such a communication is in progress, any observer of this communication, including the employees of both companies, would be tempted to capture the transcript and sell it to outsiders.

We introduce a new notion called \\emph{perfect ambiguous optimistic fair exchange} (PAOFE), which is particularly suitable to the above scenario. PAOFE fulfils all traditional requirements of cryptographic fair exchange of digital signatures and, in addition, guarantees that the communication transcript cannot be used as a proof to convince others that the protocol is in progress. Specifically, we formalize the notion of PAOFE and present a rigorous security model in the multi-user setting under the chosen-key attack. We also present a generic construction of PAOFE from existing cryptographic primitives and prove that our proposal is secure with respect to our definition in the standard model.

09:17 [Pub][ePrint]

Deterministic public key encryption (D-PKE) provides an alternative to randomized public key encryption in various scenarios (e.g. search on encrypted data) where the latter exhibits inherent drawbacks. In CRYPTO\'11, Brakerski and Segev formalized a framework for studying the security of deterministic public key encryption schemes with respect to auxiliary inputs. A trivial requirement is that the plaintext should not be efficiently recoverable from the auxiliary inputs.

In this paper, we present an efficient deterministic public key encryption scheme in the auxiliary-input setting from lattices. The public key size, ciphertext size and ciphertext expansion factor are improved compared with the scheme proposed by Brakerski and Segev. Our scheme is also secure even in the multi-user setting where related messages may be encrypted under multiple public keys. In addition, the security of our scheme is based on the hardness of the learning with errors (LWE) problem which remains hard even for quantum algorithms.

Furthermore, we consider deterministic identity-based public key encryption (D-IBE) in the auxiliary-input setting.

The only known D-IBE scheme (without considering auxiliary inputs) in the standard model was proposed by Bellare et al. in EUROCRYPT\'12. However, this scheme is only secure in the selective security setting, and Bellare et al. identified it as an open problem to construct adaptively secure D-IBE schemes. The second contribution of this work is to propose a D-IBE scheme from lattices that is adaptively secure.

2012-08-13
15:17 [Pub][ePrint]

We propose a protocol to transfer a one-time-pad (in a probabilistic manner) from Alice to Bob, over a public channel. The proposed protocol is unique because Bob merely acts as the receiver of the pad (secret key), i.e. Bob does not need to send any message back to Alice unless he detects eavesdropping. Such a secure transfer of one-time-pad, over public channel, is not possible in classical cryptography and in quantum cryptography all previous protocols require Bob to send almost as many messages back to Alice as she does to Bob, to establish a key.

15:17 [Pub][ePrint]

When Alice and Bob want to securely evaluate a function of their shared inputs, they typically first express the function as a (boolean or arithmetic) circuit and then securely evaluate that circuit, gate-by-gate. In other words, a secure protocol for evaluating $f$ is typically obtained in a {\\em non-black-box-way} from $f$ itself. Consequently, secure computation protocols have high overhead (in communication \\& computation) that is directly linked to the circuit-description complexity of $f$.

In other settings throughout cryptography, black-box constructions invariably lead to better practical efficiency than comparable non-black-box constructions. Could secure computation protocols similarly be made more practical by eliminating their dependence on a circuit representation of the target function? Or, in other words, {\\em must one know the code of $f$ to securely evaluate $f$?}

In this work we initiate the theoretical study of this question. We show the following:

1. A complete characterization of the 2-party tasks which admit such security against semi-honest adversaries. The characterization is inspired by notions of {\\em autoreducibility} from computational complexity theory. From this characterization, we show a class of pseudorandom functions that {\\em cannot} be securely evaluated (when one party holds the seed and the other holds the input) without knowing\'\' the code of the function in question. On the positive side, we show a class of functions (related to blind signatures) that can indeed be securely computed without knowing\'\' the code of the function.

2. Sufficient conditions for such security against malicious adversaries, also based on autoreducibility. We show that it is not possible to prove membership in the image of a one-way function in zero-knowledge, without knowing\'\' the code of the one-way function.

15:17 [Pub][ePrint]

We introduce a new definition of privacy called \\emph{crowd-blending privacy} that strictly relaxes the notion of differential privacy. Roughly speaking, $k$-crowd blending private sanitization of a database requires that each individual $i$ in the database blends\'\' with $k$ other individuals $j$ in the database, in the sense that the output of the sanitizer is indistinguishable\'\' if $i$\'s data is replaced by $j$\'s.

We demonstrate crowd-blending private mechanisms for histograms and for releasing synthetic data points, achieving strictly better utility than what is possible using differentially private mechanisms. Additionally, we demonstrate that if a crowd-blending private mechanism is combined with a pre-sampling\'\' step, where the individuals in the database are randomly drawn from some underlying population (as is often the case during data collection), then the combined mechanism satisfies not only differential privacy, but also the stronger notion of zero-knowledge privacy. This holds even if the pre-sampling is slightly biased and an adversary knows whether certain individuals were sampled or not. Taken together, our results yield a practical approach for collecting and privately releasing data while ensuring higher utility than previous approaches.

15:17 [Pub][ePrint]

Traditional hush functions map a large number to a small number such that the reverse-hush has an infinity of solutions, and nonetheless a collision is hard to come by. This primitive is so abundantly useful that one is tempted to extend it such that any number large or small may be mapped to any number larger, or smaller while maintaining the above conditions. This extension would increase the flexibility of the commodity hush primitive, expand its current applications, and likely suggest new ones. Additional generality may be achieved by allowing the input to determine the computational burden, and involving Turing\'s Entscheidungsproblem. We propose an algorithm where a natural number, X, is mapped to another natural number Y, referring to the mapping as a \"Crypto Square\", and to the reverse as \"Crypto Square Root\": Y = X**2|c and X = √Y|c. While the crypto-square mapping is a proper function, the square root equation has infinite solutions. There exists a deterministic solution algorithm to find any desired number of solutions to a square-root equation. This asymmetry proves itself useful, since the mapping is Z+→Z+, and hence the chance of collision for any finite size set is negligible. Unlike standard one-way functions, crypto-square shields the identity of the input (X), not by the intractability of the reverse function, but by Vernam-like equivocation per the infinity of X candidates. This prospect suggests further examination of this \"square\" algorithm for possible useful roles in various crypto protocols, especially protocols concerned with privacy, authentication and deniability.

15:17 [Pub][ePrint]

Computations of small discrete logarithms are feasible even in \"secure\" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh--Goh--Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.21*l^{2/3} multiplications, and computing a discrete logarithm in a group of order l takes only 1.77*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.24*l^{2/3} multiplications.

15:17 [Pub][ePrint]

There has been much recent progress in constructing cryptosystems that maintain their security without requiring uniform randomness and perfect secrecy. These schemes are motivated by a diverse set of problems such as providing resilience to side-channel leakage, using weak physical sources of randomness as secret keys, and allowing deterministic encryption for high-entropy messages. The study of these problems has significantly deepened our understanding of how randomness is used in cryptographic constructions and proofs.

Nevertheless, despite this progress, some basic and seemingly achievable security properties have eluded our reach. For example, we are also unable to prove the security of basic tools for manipulating weak/leaky random sources, such as as pseudo-entropy generators and seed-dependent condensers. We also do not know how to prove leakage-resilient security of any cryptosystem that has a unique secret key for each public key. In the context of deterministic encryption, we do not have a standard-model constructions achieving the strongest notion of security originally proposed by Bellare, Boldyreva and O\'Neill (CRYPTO \'07), that allows for the encryption of arbitrarily correlated messages of sufficiently large individual entropy.

In this work, we provide broad black-box separation results, showing that the security of such primitives cannot be proven under virtually \\emph{any} standard cryptographic hardness assumption via a reduction that treats the adversary as a \\emph{black box}. We do so by formalizing the intuition that the only way that a reduction can simulate the correctly distributed view for an attacker is to know all the secrets, in which case it does not learn anything useful from the attack\'\'. This intuition is often misleading and subtle ways of getting around it allow us to achieve a wealth of positive results for many cryptographic primitives with imperfect randomness. However, in this work we show that this intuition can be formalized and that it indeed presents a real barrier in many special cases involving the above-mentioned examples.