IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
25 March 2016
Emmanuel Thomé
ePrint ReportWhile the overall complexity and expected number of steps of the block Lanczos is not changed by the modifications presented in this article, we expect these to be useful for implementations of the block Lanczos algorithm where the storage of auxiliary vectors sometimes has a non-negligible cost.
Jennifer Balakrishnan, Sorina Ionica, Kristin Lauter, Christelle Vincent
ePrint ReportLe Trieu Phong , Lihua Wang, Yoshinori Aono, Manh Ha Nguyen, Xavier Boyen
ePrint ReportChristoph Dobraunig, Maria Eichlseder, Florian Mendel
ePrint ReportTaras Stanko, Fitria Nur Andini, Boris Skoric
ePrint Report23 March 2016
Oulu, Finland, 2 November - 4 November 2016
Event CalendarSubmission deadline: 1 July 2016
Notification: 15 August 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
ePrint Report1. Circuit satisfiability has 3-round IOPs with linear proof length (counted in bits) and constant query complexity. 2. Reed--Solomon codes have 2-round IOPs of proximity with linear proof length and constant query complexity. 3. Tensor product codes have 1-round IOPs of proximity with sublinear proof length and constant query complexity. For all of the above, known PCP constructions give *quaslinear* proof length and constant query complexity [BS08,Dinur07]. In addition, for circuit satisfiability, [BKKMS13] obtain PCPs with linear proof length but *sublinear* query complexity. As in [BKKMS13], we rely on algebraic-geometry codes to obtain our first result; but, unlike [BKKMS13], our use of such codes is much "lighter" because we do not rely on any automorphisms of the code.
We obtain our results in a modular way by proving and combining "IOP-analogues" of two fundamental tools:
Interactive proof composition.
Proof composition is used to reduce the query complexity of PCP verifiers, but the proof length of the composed proof system depends exponentially on the randomness complexity of the outer proof system. We prove a composition theorem for IOPs that does not suffer from this inefficiency. Sublinear sumcheck. The sumcheck protocol is an IP that enables an IP verifier to check the sum of values of a low-degree polynomial on an exponentially-large hypercube, but the verifier running time depends linearly on the individual degree. We prove a sumcheck protocol for IOPs that does not suffer from this inefficiency.
Overall, our work demonstrates that even constant-round IOPs are more efficient than known PCPs and IPs.
Chaohui Du, Guoqiang Bai
ePrint Report22 March 2016
Qualcomm Incorporated - San, Diego, CA, USA
Job PostingAbility to work in groups as well as independently with minimal supervision is a must.
This position requires some travel (up to 20% of the time). Travel may involve participating in standards meetings and/or interacting with QUALCOMM\'s customers/partners in the industry.
Minimum Qualifications
5+ years experience in one or more of the following areas :
- Embedded platforms security (e.g., ARM TrustZone, TPM, smartcards)
- Wireless communication systems and protocols (CDMA/UMTS/LTE, Bluetooth, 802.11)
- Hardware / SoC security
- Cryptography
- Participation in standards organizations like IETF/3GPP/3GPP2
Preferred Qualifications
- Prior software development experience (C, C++, C#, Java, Windows, Linux) and knowledge of software vulnerabilities
- OS architectures (e.g., Android, Linux, iOS)
- IP security protocols (IPsec, SSL/TLS)/ Packet data network security
- Multimedia systems security design (e.g.VoIP/IMS)
- Web technologies or applications (e.g., HTTP, HTML5, XML)
Education Requirements Required:
Master\'s, Computer Engineering and/or Computer Networks & Systems and/or Computer Science and/or Electrical Engineering or equivalent experience
Preferred:
Doctorate, Computer Engineering and/or Computer Networks & Systems and/or Computer Science and/or Electrical Engineering or equivalent experience
Closing date for applications: 21 March 2016
Contact: Vivian Smith, Staffing Specialist
More information: https://jobs.qualcomm.com/public/jobDetails.xhtml?requisitionId=1940091
Cappadocia, Turkey, 21 September - 22 September 2016
Event CalendarSubmission deadline: 24 June 2016
Notification: 29 July 2016
Amalfi, Italy, 31 August - 2 September 2016
Event CalendarSubmission deadline: 18 April 2016
Notification: 10 June 2016
Ghent, Belgium, 13 July - 15 July 2016
Event CalendarSubmission deadline: 18 April 2016
Notification: 6 June 2016
Marten van Dijk, Ulrich Rührmair
ePrint Report\begin{itemize}
\item {\sc PUF re-use, part I:} Any PUF that is {\it ``ideal''} and retrospectively accessible can be replaced by a standard random oracle. By applying the famous Impagliazzo-Rudich result \cite{IR}, this means that the power of plain Strong PUFs under retrospective access is severely limited; for example, it does not suffice to implement key exchange (KE) or oblivious transfer (OT).
\item {\sc PUF re-use, part II:} Any PUF that is both bad/malicious and retrospectively accessible can be completely eliminated from the protocol. The protocol can be compiled into an information-theoretically equivalent one without this PUF.
\item {\sc Bad PUFs and Simplification:} As a minor contribution, we simplify a recent OT-protocol for malicious PUFs by Dachman-Soled et al.~\cite{Dachman-Soled} from CRYPTO 2014. We can achieve the same security properties under the same assumptions, but use only one PUF instead of two.
\item {\sc PUFs-inside-PUFs, part I:} We propose the new adversarial model of {\it ``PUFs-inside-PUF attacks''}, and show that the earlier protocol of Dachman-Soled et al.\ \cite{Dachman-Soled} is vulnerable in this model (which lies outside the original framework of \cite{Dachman-Soled}).
\item {\sc PUFs-inside-PUFs, part II:} We construct a new PUF-based OT-protocol, which is secure against PUFs-inside-PUFs attacks if the used bad PUFs are stateless. Our protocol introduces the technique of interleaved challenges. We illustrate why the use of interactive hashing in the protocol is necessary, and why a first protocol attempt without interactive hashing fails.
\end{itemize}
Our findings are not restricted to the UC-framework or its peculiarities, but also apply in stand-alone settings. They have immediate relevance for PUF hardware design: The secure re-use of PUFs in protocols like KE or OT requires properties beyond unpredictability and unclonability. These include {\it reconfigurability} or {\it erasability} as well as {\it certifiability}. Their effective implementation is posed as a central new design goal by our work. Finally, we stress that the secure use of Strong PUFs in standard PUF-based identification protocols remains mostly unaffected by our results, and by attacks in the bad PUF model and the PUF re-use model alike.
Claude Carlet, Emmanuel Prouff, Matthieu Rivain, Thomas Roche
ePrint ReportLinus Feiten, Matthias Sauer, Bernd Becker
ePrint ReportBrett Hemenway, Steve Lu, Rafail Ostrovsky, William Welser IV
ePrint ReportA 2014 report from the RAND Corporation proposed using cryptographic tools from the domain of secure Multiparty Computation (MPC) to allow satellite operators to calculate collision probabilities (conjunction analyses) without sharing private information about the trajectories of their satellites.
In this work, we report on the design and implementation of a powerful new MPC framework for high-precision arithmetic on real-valued variables in a two-party setting where, unlike previous works, there is no honest majority, and where the players are not assumed to be semi-honest. We show how to apply this new solution in the domain of securely computing conjunction analyses. Our solution extends existing protocols, in particular the integer-based Goldreich-Micali-Wigderson (GMW) protocol, whereby we use combine and optimize GMW with Garbled Circuits (GC). We prove security of our protocol in the two party, semi-honest setting, assuming only the existence of one-way functions and Oblivious Transfer (the OT-hybrid model). The protocol allows a pair of satellite operators to compute the probability that their satellites will collide without sharing their underlying private orbital information. Techniques developed in this paper would potentially have a wide impact on general secure numerical analysis computations. We also show how to strengthen our construction with standard arithmetic message-authentication-codes (MACs) to enforce honest behavior beyond the semi-honest setting.
Computing a conjunction analysis requires numerically estimating a complex double integral to a high degree of precision. The complexity of the calculation, and the possibility of numeric instability presents many challenges for MPC protocols which typically model calculations as simple (integer) arithmetic or binary circuits.
Our secure numerical integration routines are extremely stable and efficient, and our secure conjunction analysis protocol takes only a few minutes to run on a commodity laptop.
Jayaprakash Kar, Sagar Naik
ePrint ReportRishab Goyal, Venkata Koppula, Brent Waters
ePrint ReportWe show how to generically transform any selectively secure ABE or FE scheme into one that is semi-adaptively secure with the only additional assumption being public key encryption, which is already naturally included in almost any scheme of interest. Our technique utilizes a fairly simple application of garbled circuits where instead of encrypting directly, the encryptor creates a garbled circuit that takes as input the public parameters and outputs a ciphertext in the underlying selective scheme. Essentially, the encryption algorithm encrypts without knowing the `real' public parameters. This allows one to delay giving out the underlying selective parameters until a private key is issued, which connects the semi-adaptive to selective security. The methods used to achieve this result suggest that the moral gap between selective and semi-adaptive security is in general much smaller than that between semi-adaptive and full security.
Finally, we show how to extend the above idea to generically bundle a family of functionalities under one set of public parameters. For example, suppose we had an inner product predicate encryption scheme where the length of the vectors was specified at setup and therefore fixed to the public parameters. Using our transformation one could create a system where for a single set of public parameters the vector length is not apriori bounded, but instead is specified by the encryption algorithm. The resulting ciphertext would be compatible with any private key generated to work on the same input length.
Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, abhi shelat
ePrint ReportIn this note, we rely on the recent result of Brakerski, Brzuska, and Fleischhacker (ePrint 2016/226) and rule out fully black-box constructions of IO from any such primitive $P$, assuming the existence of one-way functions and $\mathbf{NP} \not \subseteq \mathbf{coAM}$. At a technical level, we show that attacks in idealized (randomized) oracle models that succeed with constant advantage over the trivial bound (e.g., guessing the obfuscated circuit with probability $1/2+1/10$) would remain successful for an infinite sequence of security parameters for a non-zero measure of the oracles.