International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

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-07-02
21:17 [Pub][ePrint]

We develop secure \\emph{threshold} protocols for two important

operations in lattice cryptography, namely, generating a hard lattice

$\\Lambda$ together with a strong\'\' trapdoor, and sampling from a

discrete Gaussian distribution over a desired coset of $\\Lambda$ using

the trapdoor. These are the central operations of many cryptographic

schemes: for example, they are exactly the key-generation and signing

operations (respectively) for the GPV signature scheme, and they are

the public parameter generation and private key extraction operations

(respectively) for the GPV IBE. We also provide a protocol for

trapdoor delegation, which is used in lattice-based hierarchical IBE

schemes. Our work therefore directly transfers all these systems to

the threshold setting.

Our protocols provide information-theoretic (i.e., statistical)

security against adaptive corruptions in the UC framework, and they

are private and robust against an

optimal number of semi-honest or malicious parties. Our Gaussian

sampling protocol is both noninteractive and efficient, assuming

either a trusted setup phase (e.g., performed as part of key

generation) or a sufficient amount of interactive but offline

precomputation, which can be performed before the inputs to the

sampling phase are known.

21:17 [Pub][ePrint]

We study collusion-resistant traitor tracing in the simple decoder approach, i.e. assignment of scores for each user separately.

We introduce a new score function for non-binary bias-based traitor tracing. It has three special properties that have long been sought after:

(i) The expected score of an innocent user is zero in each content position.

(ii) The variance of an innocent user\'s score is~1 in each content position.

(iii) The expectation of the coalition\'s score does not depend on the

collusion strategy.

We also find a continuous bias distribution that optimizes the asymptotic (large coalition) performance.

In the case of a binary alphabet our scheme reduces exactly to the

symmetrized Tardos traitor tracing system.

Unfortunately, the asymptotic fingerprinting rate

of our new scheme decreases with growing alphabet size.

We regret to inform you that this grail has holes.

21:17 [Pub][ePrint]

In [12], the authors present a new light-weight cryptographic primitive which supports an associated RFID-based authentication protocol. The primitive has some structural similarities to AES, but is presented as a keyed one-way function using a 128-bit key. Although a security analysis is included, this is at a high-level only. To provide a more concrete idea as to the security of this primitive, we therefore make three contributions: first, a structural attack requiring $O(2^{5})$ plaintext/ciphertext pairs (and hence effort online) plus $O(2^{21})$ effort offline, second an algebraic attack on round reduced versions of the primitive which requires only a single plaintext/ciphertext pair, and, third debunk the claimed attack of [36] on the same primitive as wishful thinking. Our structural attack completely breaks the primitive and the algebraic attack highlights a crucial weakness of the primitive: we conclude that although one can consider countermeasures against these specific attacks, the design in general is questionable and should therefore be avoided.

21:17 [Pub][ePrint]

In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier\'s

additively homomorphic system as well as Brakerski\'s somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.

21:17 [Pub][ePrint]

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $\\mathcal{H}:\\{0,1\\}^n \\rightarrow \\{0,1\\}^m$. A construction with constant \\emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this construction suffers from two limitations: (1) It can only achieve a sub-linear shrinkage of $n-m=n^{1\\epsilon}$; and (2) It has a super-constant \\emph{input locality}, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $n-m= \\epsilon n$, or UOWHFs with constant input locality and minimal shrinkage of $n-m=1$.

We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality, and constant output locality. Our construction is based on the one-wayness of random\'\' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Using a transformation of [Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2008], our UOWHFs give rise to a digital signature scheme with a minimal \\emph{additive} complexity overhead: signing $n$-bit messages with security parameter $\\kappa$ takes only $O(n+\\kappa)$ time instead of $O(n\\kappa)$ as in typical constructions. Previously, such signatures were only known to exist under an \\emph{exponential} hardness assumption.

As an additional contribution, we obtain new locally-computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.

21:17 [Pub][ePrint]

This paper provides a (standard-model) notion of security for (keyed) hash functions, called UCE, that we show enables instantiation of random oracles (ROs) in a fairly broad and systematic way. Goals and schemes we consider include deterministic PKE; message-locked encryption; hardcore functions; point-function obfuscation; OAEP; encryption secure for key-dependent messages; encryption secure under related-key attack; proofs of storage; and adaptively-secure garbled circuits with short tokens. We can take existing, natural and efficient ROM schemes and show that the instantiated scheme resulting from replacing the RO with a UCE function is secure in the standard model. In several cases this results in the first standard-model schemes for these goals. The definition of UCE-security itself is quite simple, asking that outputs of the function look random given some \'leakage\', even if the adversary knows the key, as long as the leakage does not permit the adversary to compute the inputs.

21:17 [Pub][ePrint]

The Wired Equivalent Protocol is nowadays considered as unsafe. However the only academic research that tries to break WEP has been done by Fluhrer, Mantin and Shamir, who have published a report on a specific attack. Nevertheless, an unknown person under the pseudonym Korek has published 17 attacks, which are now used by both AirCrack and WepLab. For a network with average load traffic, the FMS attack would need roughfly 40 days in order to find the key (4 millions packets needed), whereas Korek\'s attacks in addition to stimulation of the network load, reduce this time under 15 minutes (325\'000 packets needed) for a 128 bits key (104 bits secret key). We analyzed these attacks, gave a mathematical description of them and explained a new attack, in order to identify new ones.

21:17 [Pub][ePrint]

We advocate schemes based on fixed-key AES as the best route to highly

efficient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the JustGarble system, which implements our schemes.

JustGarble evaluates moderate-sized garbled-circuits at an amortized

cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

16:00 [Job][New]

The Institute of Technology at the University of Washington Tacoma is seeking applications for five full-time, tenure-track Associate/Assistant Professor positions for the Computer Science and Systems program and the Information Technology and Systems program. A Ph.D. or foreign equivalent in Computer Science, Information Technology, Information Systems or related field is required. Applicants should have experience in teaching and in externally-funded research. Our priority areas for research are (1) information assurance and cybersecurity – 2 positions, (2) data analytics – AI/intelligent systems, (3) CS theory/algorithms, and (4) spatial data/GIS; other areas will also be considered, especially if they are related to needs of the other Institute of Technology programs. Successful candidates will have demonstrated experience or promise for strong potential in research (as evidenced by publications). Evidence of potential to build strong relationships with partners in the technology industry and in developing collaborative research programs is highly desirable.

Applications should be submitted electronically to https://secure.interfolio.com/apply/21679 and include (1) a cover letter describing academic qualifications and experience for this position, (2) a statement of the candidate’s research program, (3) a list of publications, (4) a description of teaching philosophy, including a list of courses the candidate is qualified to teach, (5) evidence of teaching effectiveness, (6) a curriculum vitae, and (7) at least three letters of reference. Screening of applications will begin on October 15, 2013, and will continue until the positions are filled. Salary is competitive and will be commensurate with experience and qualifications.

2013-07-01
19:27 [PhD][Update]

Name: Viet Tung Hoang
Topic: Foundations of garbled circuits
Category:foundations

Description:

Garbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. Starting from a PRF, we give efficient schemes to achieve all security notions above, and analyze their concrete security. Our treatment of garbling schemes provides ground for more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.

On the practical side, we provide extremely efficient garbling schemes based on fixed-key AES. We justify the security of these methods in the random-permutation model, where parties have access to a public random permutation, and build the JustGarble system to implement them. JustGarble evaluates moderate-sized garbled circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

Standard constructions of garbling schemes, including ours, provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some application—notably one-time programs (Goldwasser, Kalai, and Rothblum 2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)—need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with regard to adaptive security, which signifies the absence of a good abstraction boundary. We then investigate adaptive security of garbling schemes, giving definitions encompassing privacy, authenticity, and obliviousness, wi[...]

19:11 [PhD][New]

Name: Viet Tung Hoang
Topic: Foundations of garbled circuits
Category: foundations

Description:

\r\nGarbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. Starting from a PRF, we give efficient schemes to achieve all security notions above, and analyze their concrete security. Our treatment of garbling schemes provides ground for more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.\r\n

\r\nOn the practical side, we provide extremely efficient garbling schemes based on fixed-key AES. We justify the security of these methods in the random-permutation model, where parties have access to a public random permutation, and build the JustGarble system to implement them. JustGarble evaluates moderate-sized garbled circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.\r\n

\r\nStandard constructions of garbling schemes, including ours, provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some application—notably one-time programs (Goldwasser, Kalai, and Rothblum2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)—need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with regard to adaptive security, which signifies the absence of a good abstraction boundary. We then investigate adaptive security of garbling schemes, giving definitions encompassing privacy, authenticity, and obliviousness,[...]