IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
22 May 2019
Percy Deift, Stephen D. Miller, Thomas Trogdon
ePrint ReportCarsten Baum, Ariel Nof
ePrint ReportBased on specific properties of our protocol we then show how it can be used to construct an efficient Zero-Knowledge Argument of Knowledge for instances of the Short Integer Solution (SIS) problem. We present different protocols that are tailored to specific uses of SIS and show how our solution compares in terms of argument size to existing work. We moreover implemented our Zero-Knowledge argument for SIS and show that using our protocols it is possible to run a complete interactive proof, even for general SIS instances which result in a circuit with $>10^6$ gates, in less than 0.5 seconds. To the best of our knowledge, our construction outperforms all known approaches for the SIS problem with post-quantum security either in terms of computation or communication complexity.
21 May 2019
Department of CS and the School of Law at Universität Erlangen-Nürnberg
Job Posting10 PhD positions (salary level 13 TV-L) in Computer Science (full time)
within the Research Training Group 2475 \"Cybercrime and Forensic Computing\" funded by the German Research Foundation (DFG) commencing on October 1, 2019.
The Research Training Group aims to systematically analyse research questions arising from the interaction between computer science and criminal law. The principal investigators of this project offer expertise in the following areas:
o Computer security, digital forensic science
o Theoretical computer science (logic, semantics, automata)
o Pattern recognition, image processing, image forensics
o Cryptography
o Hardware-software-co-design
Applicants should have an excellent academic record, hold an MSc or an equivalent university degree in computer science or related disciplines, and have the goal to finish a PhD degree within three years.
Founded in 1743 and situated at the heart of the Nuremberg Metropolitan Region, FAU is a strong research university with an international perspective and one of the largest universities in Germany. FAU’s outstanding research and teaching is reflected in top positions in both national and international rankings, as well as the high amount of DFG funding which its researchers are able to secure.
FAU aims to increase the number of women in scientific positions. Female candidates are therefore particularly encouraged to apply. In case of equal qualifications, candidates with disabilities will take precedence.
Please mention in your application at least two research areas from the above list which you are specifically interested in. Interviews will commence between 3.7.2019 and 12.7.2019 in Erlangen. Further inquiries can be directed to Felix Freiling (felix.freiling (at) fau.de) regarding positions in computer science and Hans Kudlich (hans.kudlich (at) fau.de) regarding positions in law.
Closing date for applications: 12 June 2019
Contact: Felix Freiling (felix.freiling (at) fau.de) regarding positions in computer science and Hans Kudlich (hans.kudlich (at) fau.de) regarding positions in law.
More information: https://cybercrime.fau.de
Horst Görtz Institute for IT Security, Ruhr-Universität Bochum, Germany
Job PostingClosing date for applications: 2 June 2019
Contact: Contact: Dr. Patrick Schulte
RUHR-UNIVERSITÄT BOCHUM
Exzellenzcluster CASA / Horst Görtz Institute for IT Security
General Manager
ID 2 / 142
Universitätsstr. 150
44780 Bochum, Germany
Tel: +49-(0)234-32-27722
Email: patrick.schulte (at) rub.de
More information: https://twitter.com/HGI_Bochum/status/1087703387343331329 https://twitter.com/HGI_B /1087703387343331329
Department of Computing, The Hong Kong Polytechnic University
Job Posting- lattice-based cryptography;
- privacy-preserving cryptographic primitives (including zero-knowledge proofs, anonymous credentials, ring signatures);
- blockchain & cryptocurrency.
Candidates for research fellow/associate should have completed (or close to completing) a PhD in computer science, mathematics, or a related discipline. Research assistant are expected to have an honours degree or an equivalent qualification. Post-secondary students will be considered for the position of research/project administrative assistant.
Applicants should have solid experience in any of the following areas:
- Public key cryptography and provable security;
- post-quantum cryptography;
- Software engineering.
Post-doc applicants should have a good track record (e.g. publications in IACR conferences / workshops)
All positions has a flexible starting date. The initial appointment will be for 12 months, with a strong possibility for further appointment.
Review of applications will start immediately until the positions are filled.
Closing date for applications: 30 September 2019
Contact: Man Ho Au
More information: http://www4.comp.polyu.edu.hk/~csallen
Kaoru Kurosawa
ePrint ReportIn this paper, we show an efficient decoding algorithm for this $b$ error correcting $\ell$ server PIR scheme. It runs in time $O(\ell^3)$.
Robert Nguyen, Adrien Facon, Sylvain Guilley, Guillaume Gautier, Safwan El Assad
ePrint Report20 May 2019
Pedro Branco, Manuel Goulão, Paulo Mateus
ePrint ReportAchieving adaptive security for UC-Commitment schemes is non-trivial and, usually, comes at the price of efficiency. Phase-adaptive security stands between adaptive and static security, and may be of independent interest. In this model, adversaries can corrupt at the beginning or between the commitment and opening phases of the protocol, but not during their execution. This new model is motivated by the fact that, in practice, it is more likely that parties are corrupted between phases of the protocol (where a relatively long period may elapse) than during their execution.
Xavier Bonnetain, Léo Perrin, Shizhu Tian
ePrint ReportWe introduce various "anomalies". These real numbers are such that a property with an anomaly equal to $a$ should be found roughly once in a set of $2^{a}$ random S-boxes. First, we revisit the literature on S-box reverse-engineering to present statistical anomalies based on the distribution of the coefficients in the difference distribution table, linear approximation table, and for the first time, the boomerang connectivity table.
We then count the number of S-boxes that have block-cipher like structures to estimate the anomaly associated to those. In order to recover these structures, we show that the most general tool for decomposing S-boxes is an algorithm efficiently listing all the vector spaces of a given dimension contained in a given set, and we present such an algorithm.
Finally, we propose general methods to formally quantify the complexity of any S-box. It relies on the production of the smallest program evaluating it and on combinatorial arguments.
Combining these approaches, we show that all permutations that are actually picked uniformly at random always have essentially the same cryptographic properties, and can never be decomposed in a simpler way. These conclusions show that multiple claims made by the designers of the latest Russian standards are factually incorrect.
Olamide Omolola, Paul Plessing
ePrint ReportIn this paper, we provide solutions to the problems of PB-PKI. We suggest generating fresh keys during key update. Furthermore, we use ring signatures for authenticating the user requesting key updates and use Asynchronous accumulators to handle the deletion of revoked keys. We show that the approach is feasible and implement a proof of concept.
Cas Cremers, Dennis Jackson
ePrint ReportWhile many advances have been made in automated protocol analysis, modern tools such as Tamarin and ProVerif represent DH groups using an abstraction of prime order groups. This means they, like many cryptographic proofs, may miss practical attacks on real world protocols.
In this work we develop a novel extension of the symbolic model of Diffie-Hellman groups. By more accurately modelling internal group structure, our approach captures many more differences between prime order groups and their actual implementations. The additional behaviours that our models capture are surprisingly diverse, and include not only attacks using small subgroups and invalid curve points, but also a range of proposed mitigation techniques, such as excluding low order elements, single coordinate ladders, and checking the elliptic curve equation. Our models thereby capture a large family of attacks that were previously outside the symbolic model.
We implement our improved models in the Tamarin prover. We find a new attack on the Secure Scuttlebutt Gossip protocol, independently discover a recent attack on Tendermints secure handshake, and evaluate the effectiveness of the proposed mitigations for recent Bluetooth attacks.
Ciprian Băetu, F. Betül Durak, Loïs Huguenin-Dumittan, Abdullah Talayhan, Serge Vaudenay
ePrint ReportHao Chen, Wei Dai, Miran Kim, Yongsoo Song
ePrint ReportIn this paper, we present multi-key variants of two HE schemes with packed ciphertexts. We present new relinearization algorithms which are simpler and faster than previous method by Chen et al. (TCC 2017). We then generalize the bootstrapping techniques for HE to obtain multi-key fully homomorphic encryption schemes. We provide a proof-of-concept implementation of both MKHE schemes using Microsoft SEAL. For example, when the dimension of base ring is 8192, homomorphic multiplication between multi-key BFV (resp. CKKS) ciphertexts associated with four parties followed by a relinearization takes about 116 (resp. 67) milliseconds.
Our MKHE schemes have a wide range of applications in secure computation between multiple data providers. As a benchmark, we homomorphically classify an image using a pre-trained neural network model, where input data and model are encrypted under different keys. Our implementation takes about 1.8 seconds to evaluate one convolutional layer followed by two fully connected layers on an encrypted image from the MNIST dataset.
Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat
ePrint ReportWhereas the best current schemes for threshold-two ECDSA signing use a Diffie-Hellman Key Exchange to calculate each signature's nonce, a direct adaptation of this technique to a larger threshold $t$ would incur a round count linear in $t$; thus we abandon it in favor of a new mechanism that yields a protocol requiring $\lceil\log(t)\rceil+6$ rounds in total. We design a new consistency check, similar in spirit to that of Doerner et al., but suitable for an arbitrary number of participants, and we optimize the underlying two-party multiplication protocol on which our scheme is based, reducing its concrete communication and computation costs.
We implement our scheme and evaluate it among groups of up to 256 of co-located and geographically-distributed parties, and among small groups of embedded devices. We find that in the LAN setting, our scheme outperforms all prior works by orders of magnitude, and that it is efficient enough for use even on smartphones or hardware tokens. In the WAN setting we find that, despite its logarithmic round count, our protocol outperforms the best constant-round protocols in realistic scenarios.
Amos Beimel, Naty Peter
ePrint ReportIn this work, we construct improved secret-sharing schemes for a general access structure with share size $\tilde{O}(2^{0.762n})$. Our schemes are linear, that is, the shares are a linear function of the secret and some random elements from a finite field. Previously, the best linear secret-sharing scheme had shares of size $\tilde{O}(2^{0.942n})$. Most applications of secret-sharing require linearity. Our scheme is conceptually simpler than previous schemes, using a new reduction to two-party CDS protocols (previous schemes used a reduction to multi-party CDS protocols).
In a CDS protocol for a function $f$, there are $k$ parties and a referee; each party holds a private input and a common secret, and sends one message to the referee (without seeing the other messages). On one hand, if the function $f$ applied to the inputs returns $1$, then it is required that the referee, which knows the inputs, can reconstruct the secret from the messages. On the other hand, if the function $f$ applied to the inputs returns $0$, then the referee should get no information on the secret from the messages. However, if the referee gets two messages from a party, corresponding to two different inputs (as happens in our reduction from secret-sharing to CDS), then the referee might be able to reconstruct the secret although it should not.
To overcome this problem, we define and construct $t$-robust CDS protocols, where the referee cannot get any information on the secret when it gets $t$ messages for a set of zero-inputs of $f$. We show that if a function $f$ has a two-party CDS protocol with message size $c_f$, then it has a two-party $t$-robust CDS protocol with normalized message size $\tilde{O}(t c_f)$. Furthermore, we show that every function $f:[N] \times [N]\rightarrow \{0,1\}$ has a multi-linear $t$-robust CDS protocol with normalized message size $\tilde{O}(t+\sqrt{N})$. We use a variant of this protocol (with $t$ slightly larger than $\sqrt{N}$) to construct our improved linear secret-sharing schemes. Finally, we construct robust $k$-party CDS protocols for $k>2$.
Benjamin M. Case, Shuhong Gao, Gengran Hu, Qiuxia Xu
ePrint ReportOur contribution is to present a fully homomorphic encryption scheme based on these preceding schemes that generalizes the Gao (2018) scheme to perform operations on k-bit encrypted data and also removes the need for the Independence Heuristic of the Chillotti et al. papers. The amortized cost of computing k-bits at a time improves the efficiency. Operations supported include addition and multiplication modulo $2^k$, addition and multiplication in the integers as well as exponentiation, field inversion and the machine learning activation function RELU. The ciphertext expansion factor is also further improved, for $k = 4$ our scheme achieves a ciphertext expansion factor of 2.5 under secret key and 6.5 under public key. Asymptotically as k increases, our scheme achieves the optimal ciphertext expansion factor of 1 under private key encryption and 2 under public key encryption. We also introduces techniques for reducing the size of the bootstrapping key.
Keywords. FHE, lattices, learning with errors (LWE), ring learning with errors (RLWE), TFHE, data security, RELU, machine learning
Benjamin M. Case, Colin Gallagher, Shuhong Gao
ePrint ReportChristopher Patton, Thomas Shrimpton
ePrint ReportPayman Mohassel, Peter Rindal, Mike Rosulek
ePrint ReportIn addition to performing database joins our protocol, we implement two applications on top of our framework. The first performs joins between different governmental agencies to identify voter registration errors in a privacy-preserving manner. The second application considers the scenario where several organizations wish to compare network security logs to more accurately identify common security threats, e.g. the IP addresses of a bot net. In both, cases the practicality of these applications depends on efficiently performing joins on millions of secret shared records. For example, our three party protocol can perform a join on two sets of 1 million records in 4.9 seconds or, alternatively, compute the cardinality of this join in just 3.1 seconds.
Daniel Kales, Christian Rechberger, Matthias Senker, Thomas Schneider, Christian Weinert
ePrint ReportThe most promising approaches addressing this problem revolve around private set intersection (PSI) protocols. Unfortunately, even in a weak security model where clients are assumed to follow the protocol honestly, previous protocols and implementations turned out to be far from practical when used at scale. This is due to their high computation and/or communication complexity as well as lacking optimization for mobile devices. In our work, we remove most obstacles for large-scale global deployment by significantly improving two promising protocols by Kiss et al. (PoPETS'17) while also allowing for malicious clients.
Concretely, we present novel precomputation techniques for correlated oblivious transfers (reducing the online communication by factor 2x), Cuckoo filter compression (with a compression ratio of $\approx 70\%$), as well as 4.3x smaller Cuckoo filter updates. In a protocol performing oblivious PRF evaluations via garbled circuits, we replace AES as the evaluated PRF with a variant of LowMC (Albrecht et al., EUROCRYPT'15) for which we determine optimal parameters, thereby reducing the communication by factor 8.2x. Furthermore, we implement both protocols with security against malicious clients in C/C++ and utilize the ARM Cryptography Extensions available in most recent smartphones. Compared to previous smartphone implementations, this yields a performance improvement of factor 1000x for circuit evaluations. The online phase of our fastest protocol takes only 2.92s measured on a real WiFi connection (6.53s on LTE) to check 1024 client contacts against a large-scale database with $2^{28}$ entries. As a proof-of-concept, we integrate our protocols in the client application of the open-source messenger Signal.