IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
11 November 2015
Ivan Damgård, Jesper Buus Nielsen, and Antigoni Polychroniadou
This means that while information theoretically secure protocols are very efficient in terms of computational work, they (seem to) require more communication and more rounds than computationally secure protocols. Whether this is inherent is an open and probably very hard problem. However, in this work we show that it is indeed inherent for protocols that follow the ``gate by gate\'\' design pattern. In particular, we present the following results:
- In the honest majority setting, any gate-by-gate protocol must communicate for every multiplication gate, even if only semi-honest security is required.
- For dishonest majority with preprocessing, a different proof technique is needed. We again show that any gate-by-gate protocol must communicate for every multiplication gate when the underlying secret sharing scheme is the additive one. We obtain similar results for arbitrary secret sharing schemes.
- In the honest majority setting, we also show that amortising over several multiplication gates can at best save an O(n) factor on the computational work.
All our lower bounds are met up to a constant factor by known protocols that follow the typical gate-by-gate paradigm.
Our results imply that a fundamentally new approach must be found in order to improve the communication complexity of known protocols that are efficient in the circuit size of the function, such as GMW, SPDZ etc.
Shen Noether
10 November 2015
Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, Amit Sahai
We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs.
- We construct a protocol implementing oblivious transfer from any optimally accurate, distributed differentially private protocol for any functionality with a boolean XOR embedded on adjacent inputs.
- While the previous result holds for optimally accurate protocols for any privacy parameter \\epsilon > 0, we also give a reduction from oblivious transfer to distributed differentially private protocols computing XOR, for a constant small range of non-optimal accuracies and a constant small range of values of privacy parameter \\epsilon.
At the heart of our techniques is an interesting connection between optimally-accurate two-party protocols for the XOR functionality and noisy channels, which were shown by Crepeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.
Junwu Dong, Dingyi Pei
de Bruijn sequences has received considerable attention. There is only one full cycle in the state graph of de Bruijn sequences. Most
popular algorithms for generating de Bruijn sequences start from a nonsingular linear feedback shift register producing several shorter
cycles in its state graph, then join them into one cycle. Unfortunately, the order $n$ of the resulting de Bruijn sequence by using
this kind of algorithms is small so far (usually $n \\le 40$). We introduce a new concept of correlated cycles between the cycles
in the state graph of a LFSR. Based on this concept we present a algorithm for constructing de Bruijn sequences with large orders (such
as $n=128$). This is the first publication for designing de Bruijn sequences with such large orders.
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, Peter Schwabe
Ahmed Kosba, Zhichao Zhao, Andrew Miller, Hubert Chan, Charalampos Papamanthou, Rafael Pass, abhi shelat, Elaine Shi
(e.g., written in C) to arithmetic circuits, the native representation used by SNARK constructions. However, while we would like to use these primitives in UC-secure protocols --- which are provably-secure even when composed with other arbitrary concurrently-executing protocols --- the SNARK definition is not directly compatible with this framework, due to its use of non black-box knowledge extraction. We show several constructions to transform SNARKs into UC-secure NIZKs, along with benchmarks and an end-to-end application example showing that the
added overhead is tolerable. Our constructions rely on embedding cryptographic algorithms into the SNARK proof system. Ordinarily, cryptographic constructions are chosen and tuned for implementation on CPUs or in hardware, not as arithmetic circuits. We therefore also initiate the study of SNARK-friendly cryptography, describing several protocol parameterizations, implementations, and performance comparisons for encryption, commitments, and other tasks. This is also of independent interest for use in other SNARK-based applications.
Divesh Aggarwal, Kaave Hosseini, Shachar Lovett
We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor ($\\AmExt: \\F^n \\times \\F^d \\mapsto \\F$) where $\\AmExt(X,Y)$ is close to uniform and independent of $Y$ and has some limited dependence of $\\AmExt(X,f(Y))$ - that conditioned on $Y$, $(\\AmExt(X,Y), \\AmExt(X,f(Y)))$ is close to $(U, A \\cdot U + B)$ where $U$ is uniformly distributed in $\\F$ and $A, B \\in \\F$ are random variables independent of $\\F$.
We show under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture) that the inner-product function $\\IP{\\cdot,\\cdot}:\\F^n \\times \\F^n \\mapsto \\F$ is an affine-malleable extractor. As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture.
We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret $X$ of min-entropy $k$, and wish to agree on secret key $R$ of length $m$ over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and its many variants has been in constructing secure privacy amplification protocols.
We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. We show that our protocol, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.
Vipul Goyal, Aayush Jain, Dakshita Khurana
In this work, we formalize this notion and show that most natural definitions are impossible in the plain model without any setup assumptions. While still wanting to avoid a central trusted setup, we turn to the tamper proof hardware token model of Katz (Eurocrypt 2007). Interestingly, we show witness signatures in the hardware token model are closely related to what we call non-malleable multi-prover zero-knowledge proofs in the plain model (i.e. without hardware tokens). We initiate the study of non-malleable multi-prover zero-knowledge proofs, and, provide an unconditional construction of single round non-malleable two-prover zero-knowledge proofs. We then use this primitive to obtain an unconditional construction of witness signatures in the hardware token model.
Our construction makes a novel use of non-malleable codes. In particular, we crucially rely on the notion of many-many non-malleable codes introduced recently by Chattopadhyay, Goyal and Li (ECCC 2015). Our construction is unconditional, is extremely efficient (in terms of computation, number of tokens, and rounds of interaction with the token), and, only relies on elementary computations such as inner products.
Finally, this construction yields signatures which can only be verified a bounded number of times. Towards that end, we show how to extend it to get the unbounded (polynomial) verification property relying on the minimal additional assumption of one-way functions. We also show that obtaining unconditional unbounded-verifiable witness signatures under black-box extraction, is impossible even with access to an unbounded number of stateful tamper-proof hardware tokens- thereby giving a matching lower bound. This is done by relying on the techniques from the work of Goyal et al (Crypto 2012) (which in turn builds on techniques from the black-box separation literature). In particular, we rely on the notion of ``inaccessible entropy\" introduced in prior works.
Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs
The work of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO\'01 and Journal of 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.
Our watermarking schemes are {\\em public key}, meaning that we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against {\\em chosen program attacks} where the adversary is given 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, in contrast to the prior works (Nishimaki, EUROCRYPT \'13).
University College London
Application deadline: 10 December 2015.
Details and instructions on how to apply are available from http://preview.tinyurl.com/ovr6sfm
[For more information about security and privacy research at UCL, please visit http://sec.cs.ucl.ac.uk/people/]
Hong Kong Applied Science and Technology Research Institute Company Limited
•Develop cryptographic systems
•Develop mobile security solutions
•Develop and implement cyber intelligence and defense technologies
•Study new security threats in the cloud infrastructure
•Perform security review and assessment on information security and e-commerce systems
•Conduct R&D on various in information security
Requirements:
•Bachelor degree or above in computer science, electrical engineering or other relevant disciplines
•Experience in hands-on R&D projects, especially on software systems
•Experience in planning, organizing, leading and implementing novel R&D projects, especially on information security and data analytics related areas
•Preferably with certificates or formal training in information security or with experience in security assessment, but not a necessity
•Good knowledge of OS security and virtualization security
•Implementation experience on the cloud an advantage
•Strong interpersonal and communications skills
09 November 2015
Horst Görtz Institut, Ruhr University Bochum
Our research focus is on practice-oriented provable security. Topics of interest may include (but are not limited to):
- Provable security of cryptographic implementations
- Randomness generation
- Cryptographic protocols (e.g. cryptocurrencies)
Starting date: earliest possible
A competitive salary is offered.
Send your documents to sebastian (dot) faust (at) rub (dot) de
Applicants are required to have completed (or be close to completing) a Master or Diploma with excellent grades in Computer Science, Mathematics, or closely related areas. Additional knowledge in related disciplines such as, e.g., complexity theory or IT security is welcome.
Please send your application to Sebastian Faust via e-mail. Applications should contain a CV, a 1-page letter of motivation, copies of transcripts and certificates, and (if possible) names of references. Review of applications will start immediately until the position has been filled.
Founded in 2001, the Horst-Görtz Institute at Ruhr-University Bochum is a leading interdisciplinary research center dedicated to research and education covering all aspects of IT security, with an excellent record of research in cryptography. The Horst-Görtz Institute has 15 professors and over 80 PhD students from more than 20 different countries.
Contact: Sebastian Faust, sebastian (dot) faust (at) rub (dot) de
Closing Date for Applications: 2015-12-10
P. FREYRE, N. DIAZ, O. CUELLAR
with the use of fixed MDS matrices of size 4 x 4. In this article variations to the Cryptographics Algorithms AES and Twofish are made. They allow that the process of cipher-decipher come true with MDS matrices selected randomly from an algorithm that obtaining an MDS matrix of set of all the MDS matrices possible. A new Schedule of key with a high diffusion is designed for the Algorithm Cryptographic AES. Besides it is proposed a new S-box that he varies in function of the key.
Reza Azarderakhsh, Zhe Liu, Hwajeong Seo, and Howon Kim
share of tablet and smartphone markets due to its low cost
and high performance. This paper studies efficient techniques of
lattice-based cryptography on ARM processor and presents the
first implementation of ring-LWE encryption on ARM NEON
architecture. In particular, we propose a vectorized version of
Iterative Number Theoretic Transform (NTT) for high-speed
computation. We present a 32-bit variant of SAMS2 technique,
original proposed in CHES\'15, for fast reduction. A combination
of proposed and previous optimizations results in a very efficient
implementation. For 128-bit security level, our ring-LWE implementation
requires only 145; 200 clock cycles for encryption
and 32; 800 cycles for decryption. These result are more than
17:6 times faster than the fastest ECC implementation on ARM
NEON with same security level.
Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin, Wei-Kai Lin
Two security needs arise in this context: Ensuring {\\em Intergrity}, by designing means for the server to compute short proofs that allows the user to efficiently verify the correctness of the server computation, and {\\em privacy}, providing means for the user to hide his private databases and programs from a malicious server. In this work, we aim to address both security needs, especially in the stringent, {\\em adaptive}, setting, where the sequence of RAM
computations are (potentially) chosen adaptively by a malicious server depending on the messages from an honest user.
To this end, we construct the first RAM delegation scheme achieving both {\\em adaptive integrity} (a.k.a.\\ soundness) and {\\em adaptive privacy}, assuming the existence of indistinguishability obfuscation for circuits and a variant of the two-to-one somewhere perfectly binding hash [Okamoto et al. ASIACRYPT\'15] (the latter can be based on the decisional Diffie-Hellman assumption). Prior works focused either only on adaptive soundness [Kalai and Paneth, ePrint\'15] or on the weaker variant, selective soundness and privacy [Chen et al. ITCS\'16, Canetti and Holmgren ITCS\'16]. Our result extends to delegate parallel RAM (PRAM) computation as well.
At a high-level, our result is obtained by applying a generic ``{\\em security lifting technique}\'\' to the delegation scheme of Chen et al.\\ and its proof of selective soundness and privacy. The security lifting technique formalizes an abstract framework of selective security proofs, and generically ``lifts\'\' such proofs into proofs of adaptive security. We believe that this technique can potentially be applied to other cryptographic schemes and is of independent interest.
Mostafa Taha, Thomas Eisenbarth
Prabhanjan Ananth, Abhishek Jain, Amit Sahai
adapts the notion of indistinguishability obfuscation (iO) to a very general setting where
obfuscated software evolves over time. We model this broadly by considering
software patches P as arbitrary Turing Machines that take as input the description of a
Turing Machine M, and output a new Turing Machine description M\' = P(M).
Thus, a short patch P can cause changes everywhere in the description of M and
can even cause the description length of the machine to increase by an arbitrary polynomial amount.
We further consider the setting where a patch is applied not just to a single
machine M, but to an unbounded set of machines (M_1, \\dots, M_t) to
yield (P(M_1), \\dots, P(M_t). We call this multi-program patchable obfuscation.
We consider both patchable obfuscation and multi-program patchable obfuscation
in a setting where there are an unbounded number of patches that can be adaptively
chosen by an adversary.
We show that sub-exponentially secure iO for circuits and sub-exponentially secure one-way functions imply patchable obfuscation; and we show that
sub-exponentially secure iO for circuits, sub-exponentially secure one-way functions,
and sub-exponentially secure DDH imply multi-program patchable obfuscation.
Finally, we exhibit some simple applications
of multi-program patchable obfuscation, to demonstrate how these concepts
can be applied.
Pawel Morawiecki
Julien Allibert, Benoit Feix, Georges Gagnerot, Ismael Kane, Hugues Thiebeauld, Tiana Razafindralambo
For two decades now embedded cryptography for payment, pay tv, identity areas have been mainly focused on secure elements. However recently, alternative solutions on mobile phones appeared to offer services including payment and security solutions as the HCE and DRM products. Cryptographic operations running in such applications are then executed most often on unprotected hardware devices. Therefore the binary code is accessible to attackers who can use static and dynamic reverse engineering techniques to extract and analyse operations including data modification as faults. Hence, hiding or obfuscating secrets and/or obfuscated or whitebox-ed cryptography becomes mainly the alternatives to secure element storage for assets. Although not proven secure, attacking such implementations in practice on a binary is another story.
We explain in this paper how directly from the binary or with the extracted source code we can perform statistical and fault analysis in a manner that seems familiar with hardware side channel and fault attacks knowledge. The main difference is, using our tool and virtualization technique, an attacker can emulate and trace and modify any chosen computational data (memory or register manipulation, any machine language operation) executed in the mobile application. It means the attacker is not restricted any-more by any physical limitations as the Hamming leakage model (and additional noise) and the difficulty to fault a dedicated operation.
Hence statistical and fault attacks becomes more efficient than in standard physical devices. As a consequence, complex techniques like high order, collision and horizontal statistical attacks becomes very efficient and can be easily performed on the computational data execution traces. A similar consequence applies for fault injection attacks. Hence the word statistical and fault analysis on computational data becomes more appropriate and one can wonder who has been the first between computational data or physical attack techniques? Chicken or the Egg?
Ting Wang, Jianping Yu, Guoqiang Han, Peng Zhang