57 results sorted by ID
Possible spell-corrected query: quality best
Unbalanced Private Set Union with Reduced Computation and Communication
Cong Zhang, Yu Chen, Weiran Liu, Liqiang Peng, Meng Hao, Anyu Wang, Xiaoyun Wang
Cryptographic protocols
Private set union (PSU) is a cryptographic protocol that allows two parties to compute the union of their sets without revealing anything else. Despite some efficient PSU protocols that have been proposed, they mainly focus on the balanced setting, where the sets held by the parties are of similar size. Recently, Tu et al. (CCS 2023) proposed the first unbalanced PSU protocol which achieves sublinear communication complexity in the size of the larger set.
In this paper, we are interested...
Falsifiability, Composability, and Comparability of Game-based Security Models for Key Exchange Protocols
Chris Brzuska, Cas Cremers, Håkon Jacobsen, Douglas Stebila, Bogdan Warinschi
Cryptographic protocols
A security proof for a key exchange protocol requires writing down a security definition. Authors typically have a clear idea of the level of security they aim to achieve. Defining the model formally additionally requires making choices on games vs. simulation-based models, partnering, on having one or more Test queries and on adopting a style of avoiding trivial attacks: exclusion, penalizing or filtering. We elucidate the consequences, advantages and disadvantages of the different possible...
Shared OT and Its Applications to Unconditional Secure Integer Equality, Comparison and Bit-Decomposition
Lucas Piske, Jeroen van de Graaf, Anderson C. A. Nascimento, Ni Trieu
Cryptographic protocols
We present unconditionally perfectly secure protocols in the
semi-honest setting for several functionalities: (1) private elementwise
equality; (2) private bitwise integer comparison; and (3) bit-decomposition.
These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo $M$ and allowing additive secret-sharing of all inputs and outputs. These extensions can be...
Efficient 2PC for Constant Round Secure Equality Testing and Comparison
Tianpei Lu, Xin Kang, Bingsheng Zhang, Zhuo Ma, Xiaoyuan Zhang, Yang Liu, Kui Ren
Cryptographic protocols
Secure equality testing and comparison are two important primitives that have been widely used in many secure computation scenarios, such as privacy-preserving machine learning, private set intersection, secure data mining, etc. In this work, we propose new constant-round two-party computation (2PC) protocols for secure equality testing and secure comparison. Our protocols are designed in the online/offline paradigm. Theoretically, for 32-bit integers, the online communication for our...
A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group Actions
Steven Galbraith, Yi-Fu Lai, Hart Montgomery
Foundations
Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions.
Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed...
PMNS revisited for consistent redundancy and equality test
Fangan Yssouf Dosso, Alexandre Berzati, Nadia El Mrabet, Julien Proy
Public-key cryptography
The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$.
The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM).
In this paper,...
On the Feasibility of Identity-based Encryption with Equality Test against Insider Attacks
Keita Emura
Cryptographic protocols
Public key encryption with equality test, proposed by Yang et al. (CT-RSA 2010), allows anyone to check whether two ciphertexts of distinct public keys are encryptions of the same plaintext or not using trapdoors, and identity-based encryption with equality test (IBEET) is its identity-based variant. As a variant of IBEET, IBEET against insider attacks (IBEETIA) was proposed by Wu et al. (ACISP 2017), where a token is defined for each identity and is used for encryption. Lee et al. (ACISP...
eSTARK: Extending STARKs with Arguments
Héctor Masip-Ardevol, Marc Guzmán-Albiol, Jordi Baylina-Melé, Jose Luis Muñoz-Tapia
Cryptographic protocols
STARK is a widely used transparent proof system that uses low-degree
tests for proving the correctness of a computer program. STARK consumes an
intermediate representation known as AIR that is more appropriate for programs
with a relatively short and structured description. However, an AIR is not able to
succinctly express non-equality constraints, leading to the incorporation of unwanted
polynomials.
We present the eSTARK protocol, a new probabilistic proof that generalizes the
STARK...
More Efficient Adaptively Secure Lattice-based IBE with Equality Test in the Standard Model
Kyoichi Asano, Keita Emura, Atsushi Takayasu
Public-key cryptography
Identity-based encryption with equality test (IBEET) is a variant of identity-based encryption (IBE), where any users who have trapdoors can check whether two ciphertexts are encryption of the same plaintext. Although several lattice-based IBEET schemes have been proposed, they have drawbacks in either security or efficiency. Specifically, most schemes satisfy only selective security, while adaptively secure schemes in the standard model suffer from large master public keys that consist of...
(Inner-Product) Functional Encryption with Updatable Ciphertexts
Valerio Cini, Sebastian Ramacher, Daniel Slamanig, Christoph Striecks, Erkan Tairi
Public-key cryptography
We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional-encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care...
Block Cipher's Substitution Box Generation Based on Natural Randomness in Underwater Acoustics and Knight's Tour Chain
Muhammad Fahad Khan, Khalid Saleem, Tariq Shah, Mohmmad Mazyad Hazzazi, Ismail Bahkali, Piyush Kumar Shukla
Secret-key cryptography
The protection of confidential information is a global issue and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on "Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a...
Speedy Error Reconciliation
Kaibo Liu, Xiaozhuo Gu, Peixin Ren, Xuwen Nie
Applications
Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can...
Fast Unbalanced Private Set Union from Fully Homomorphic Encryption
Binbin Tu, Yu Chen, Qi Liu, Cong Zhang
Cryptographic protocols
Private set union (PSU) allows two parties to compute the union of their sets without revealing anything else. It has been widely used in various applications. While several computationally efficient PSU protocols have been developed for the balanced case, they have a potential limitation in their communication complexity, which grows (super)-linearly with the size of the larger set. This poses a challenge when performing PSU in the unbalanced setting, where one party is a constrained device...
Improved Pump and Jump BKZ by Sharp Simulator
Leizhang Wang, Wenwen Xia, Geng Wang, Baocang Wang, Dawu Gu
Public-key cryptography
The General Sieve Kernel (G6K) implemented a variety of lattice reduction algorithms based on sieving algorithms. One of the representative of these lattice reduction algorithms is Pump and jump-BKZ (pnj-BKZ) algorithm which is currently considered as the fastest lattice reduction algorithm. The pnj-BKZ is a BKZ-type lattice reduction algorithm which includes the jump strategy, and uses Pump as the SVP Oracle. Here, Pump which was also proposed in G6K, is an SVP sloving algorithm that...
A Linear-Time 2-Party Secure Merge Protocol
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky
Cryptographic protocols
We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order.
Our algorithm only requires black-box use of...
Lattice-based Public Key Encryption with Multi-Ciphertexts Equality Test in Cloud Computing
Giang Linh Duc Nguyen, Dung Hoang Duong, Huy Quoc Le, Willy Susilo
Public-key cryptography
Nowadays, together with stormy technology advancement, billions of interconnected devices are constantly collecting data around us. In that fashion, privacy protection has become a major concern. The data must be in encrypted form before being stored on the cloud servers. As a result, the cloud servers are unable to perform calculations on en- crypted data, such as searching and matching keywords. In the PKE- MET setting, a cloud server can perform an equality test on a number of ciphertexts...
Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography
Jan-Pieter D'Anvers, Daniel Heinz, Peter Pessl, Michiel van Beirendonck, Ingrid Verbauwhede
Public-key cryptography
Checking the equality of two arrays is a crucial building block of the Fujisaki-Okamoto transformation, and as such it is used in several post-quantum key encapsulation mechanisms including Kyber and Saber. While this comparison operation is easy to perform in a black box setting, it is hard to efficiently protect against side-channel attacks. For instance, the hash-based method by Oder et al. is limited to first-order masking, a higher-order method by Bache et al. was shown to be flawed,...
A Generic Construction of CCA-secure Attribute-based Encryption with Equality Test
Kyoichi Asano, Keita Emura, Atsushi Takayasu, Yohei Watanabe
Public-key cryptography
Attribute-based encryption with equality test ($\mathsf{ABEET}$) is an extension of the ordinary attribute-based encryption ($\mathsf{ABE}$), where trapdoors enable us to check whether two ciphertexts are encryptions of the same message.
Thus far, several CCA-secure $\mathsf{ABEET}$ schemes have been proposed for monotone span programs satisfying selective security under $q$-type assumptions.
In this paper, we propose a generic construction of CCA-secure $\mathsf{ABEET}$ from delegatable...
Fault-Injection Attacks against NIST's Post-Quantum Cryptography Round 3 KEM Candidates
Keita Xagawa, Akira Ito, Rei Ueno, Junko Takahashi, Naofumi Homma
Public-key cryptography
We investigate __all__ NIST PQC Round 3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test with re-encryption in decapsulation is critical.
We survey effective key-recovery attacks when we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two...
Chosen Ciphertext Secure Functional Encryption from Constrained Witness PRF
Tapas Pal, Ratna Dutta
Public-key cryptography
Functional encryption generates sophisticated keys for users so that they can learn specific functions of the encrypted message. We provide a generic construction of chosen ciphertext attacks (CCA) secure public-key functional encryption (PKFE) for all polynomial-size circuits. Our PKFE produces succinct ciphertexts that are independent of the size and depth of the circuit class under consideration.
We accomplish our goal in two steps. First, we define a new cryptographic tool called...
ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation
Arpita Patra, Thomas Schneider, Ajith Suresh, Hossein Yalame
Cryptographic protocols
Secure Multi-party Computation (MPC) allows a set of mutually distrusting parties to jointly evaluate a function on their private inputs while maintaining input privacy. In this work, we improve semi-honest secure two-party computation (2PC) over rings, with a focus on the efficiency of the online phase.
We propose an efficient mixed-protocol framework, outperforming the state-of-the-art 2PC framework of ABY. Moreover, we extend our techniques to multi- input multiplication gates without...
When is a test not a proof?
Eleanor McMurtry, Olivier Pereira, Vanessa Teague
Cryptographic protocols
A common primitive in election and auction protocols is plaintext equivalence test (PET) in which two ciphertexts are tested for equality of their plaintexts, and a verifiable proof of the test's outcome is provided. The most commonly-cited PETs require at least one honest party, but many applications claim universal verifiability, at odds with this requirement. If a test that relies on at least one honest participant is mistakenly used in a place where universally verifiable proof is...
Insecurity of the Public Key Encryption with Filtered Equality Test Proposed by Huang et al.
Hyung Tae Lee, San Ling, Jae Hong Seo, Huaxiong Wang
Public-key cryptography
Recently, Huang et al. proposed a concept of public key encryption with filtered equality test (PKE-FET) that allows a tester who has a warrant for the selected message set to check equality of messages in ciphertexts that belong to that set (Journal of Computer and System Sciences, 2017). They also presented an instantiation of the PKE-FET that was asserted to achieve the indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2) in the standard model. In this note, we show...
Secure Computation with Preprocessing via Function Secret Sharing
Elette Boyle, Niv Gilboa, Yuval Ishai
Cryptographic protocols
We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al....
New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning
Ivan Damgård, Daniel Escudero, Tore Frederiksen, Marcel Keller, Peter Scholl, Nikolaj Volgushev
At CRYPTO 2018 Cramer et al. presented SPDZ2k, a new secret-sharing
based protocol for actively secure multi-party computation against a dishonest
majority, that works over rings instead of fields. Their protocol uses slightly more communication than competitive schemes working over fields. However, their approach allows for arithmetic to be carried out using native 32 or 64-bit CPU operations rather than modulo a large prime. The authors thus conjectured that the increased communication...
Efficient coding for secure computing with additively-homomorphic encrypted data
Thijs Veugen
Cryptographic protocols
A framework is introduced for efficiently computing with encrypted data. We assume a semi-honest security model with two computing parties. Two different coding techniques are used with additively homomorphic encryption, such that many values can be put into one large encryption, and additions and multiplications can be performed on all values simultaneously. For more complicated operations such as comparisons and equality tests, bit-wise secret sharing is proposed as an additional technique...
Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields
Benjamin Hong Meng Tan, Hyung Tae Lee, Huaxiong Wang, Shu Qin Ren, Khin Mi Mi Aung
Applications
To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, ``$x=y, x\neq y$'', have been widely studied with many proposals but there is much room for improvement for order comparisons, ``$x < y,~x \leq y, x > y$ and $x \geq y$''. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition,...
Ciphertext-Policy Attribute-Based Encrypted Data Equality Test and Classification
Yuzhao Cui, Qiong Huang, Jianye Huang, Hongbo Li, Guomin Yang
Thanks to the ease of access and low expenses, it is now
popular for people to store data in cloud servers. To protect sensitive
data from being leaked to the outside, people usually encrypt the data
in the cloud. However, management of these encrypted data becomes a
challenging problem, e.g. data classification. Besides, how to selectively
share data with other users is also an important and interesting problem
in cloud storage. In this paper, we focus on ciphertext-policy attribute
based...
Multi-client Predicate-only Encryption for Conjunctive Equality Tests
Tim van de Kamp, Andreas Peter, Maarten H. Everts, Willem Jonker
We propose the first multi-client predicate-only encryption scheme capable of efficiently testing the equality of two encrypted vectors. Our construction can be used for the privacy-preserving monitoring of relations among multiple clients. Since both the clients’ data and the predicates are encrypted, our system is suitable for situations in which this information is considered sensitive. We prove our construction plaintext and predicate private in the generic bilinear group model using...
Security Analysis and Modification of ID-Based Encryption with Equality Test from ACISP 2017
Hyung Tae Lee, Huaxiong Wang, Kai Zhang
At ACISP 2017, Wu et al. presented an identity-based encryption with equality test (IBEET) that considers to prevent insider attacks. To analyze its security, they proposed a new security notion for IBEET, which is slightly weaker than the indistinguishability under adaptive identity and chosen ciphertext attacks (IND-ID-CCA2) for traditional identity-based encryption. Then, they claimed that their proposed scheme achieves this new security notion under the Bilinear Diffie-Hellman (BDH)...
On Multiparty Garbling of Arithmetic Circuits
Aner Ben-Efraim
We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC '90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits...
Public Key Encryption with Equality Test in the Standard Model
Hyung Tae Lee, San Ling, Jae Hong Seo, Huaxiong Wang, Taek-Young Youn
Public-key cryptography
Public key encryption with equality test (PKEET) is a cryptosystem that allows a tester who has trapdoors issued by one or more users $U_i$ to perform equality tests on ciphertexts encrypted using public key(s) of $U_i$. Since this feature has a lot of practical applications including search on encrypted data, several PKEET schemes have been proposed so far. However, to the best of our knowledge, all the existing proposals are proven secure only under the hardness of number-theoretic...
2016/1129
Last updated: 2017-07-22
Certificateless Public Key Encryption with Equality Test
Xi-Jun Lin, Zhen Yan, Qi Zhang, Haipeng Qu
Public-key cryptography
In this paper, we propose the concept of certificateless public key encryption with equality test (CL-PKEET) to solve the key escrow problem in IBEET. More in details, we first give the definition of CL-PKEET and define the security model. Finally, we propose a concrete CL-PKEET scheme based on the Decision Bilinear Diffie-Hellman (DBDH) assumption and prove its security.
Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection
Michele Orrù, Emmanuela Orsini, Peter Scholl
Cryptographic protocols
This paper describes a 1-out-of-N oblivious transfer (OT) extension protocol with active security, which achieves very low overhead compared with the passively secure protocol of Kolesnikov and Kumaresan (Crypto 2011). Our protocol obtains active security using a consistency check which requires only simple computation and has a communication overhead that is independent of the total number of OTs to be produced. We prove its security in both the random oracle model and the standard model,...
New Protocols for Secure Equality Test and Comparison
Geoffroy Couteau
Cryptographic protocols
Protocols for securely comparing private values are among the most fundamental building blocks of multiparty computation. Introduced by Yao under the name millionaire's problem, they have found numerous applications in a variety of privacy-preserving protocols; however, due to their inherent non-arithmetic structure, existing construction often remain an important bottleneck in large-scale secure protocols.
In this work, we introduce new protocols for securely computing the greater-than and...
Public Key Encryption Supporting Equality Test and Flexible Authorization without Bilinear Pairings
Xi-Jun Lin, Haipeng Qu, Xiaoshuai Zhang
Public-key cryptography
In recent years, public key encryption with equality test (PKEET) has become a hot research topic in the cryptography community due to the advancement of cloud computing. Recently, Ma et al. proposed a new related primitive, called public key encryption with equality test supporting flexible authorization (PKEET-FA), and constructed a concrete scheme. In their proposal, four types of authorization were presented to support different authorization policies. However, their proposal is based on...
Algorithms on Ideal over Complex Multiplication order
Paul Kirchner
Public-key cryptography
We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders, previously
revisited by Lenstra-Silverberg, can be extended to complex-multiplication (CM) orders, and
even to a more general structure. This algorithm allows to test equality over the polarized ideal
class group, and finds a generator of the polarized ideal in polynomial time. Also, the algorithm
allows to solve the norm equation over CM orders and the recent reduction of principal ideals to
the real suborder can...
On the Efficiency of FHE-based Private Queries
Myungsun Kim, Hyung Tae Lee, San Ling, Huaxiong Wang
Applications
Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of \emph{equality}. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme \emph{without...
Pseudo-Free Families of Finite Computational Elementary Abelian $p$-Groups
Mikhail Anokhin
Loosely speaking, a family of computational groups is a family $(G_d)_{d\in D}$ of groups (where $D$ is a set of bit strings) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in $G_d$ can be performed efficiently when $d$ is given. A family $(G_d)_{d\in D}$ of computational groups is called pseudo-free if, given a random index $d$ (for an arbitrary value of the security...
Private Proximity Testing on Steroids: An NTRU-based Protocol
Constantinos Patsakis, Panayiotis Kotzanikolaou, M ́elanie Bouroche
Cryptographic protocols
Nowadays, most smartphones come pre-equipped with location (GPS) sensing capabilities, allowing developers to create a wide variety of location-aware applications and services. While location awareness provides novel features and functionality, it opens the door to many privacy nightmares. In many occasions, however, users do not need to share their actual location, but to determine whether they are in proximity to others, which is practically one bit of information. Private proximity...
GMU Hardware API for Authenticated Ciphers
Ekawat Homsirikamol, William Diehl, Ahmed Ferozpuri, Farnoud Farahmand, Malik Umar Sharif, Kris Gaj
In this paper, we propose a universal hardware API for authenticated ciphers, which can be used in any future implementations of authenticated ciphers submitted to the CAESAR competition. A common interface and communication protocol would help in reducing any potential biases, and would make the comparison in hardware more reliable and fair. By design, our proposed API is equally suitable for hardware implementations of authenticated ciphers developed manually (at the register-transfer...
Message-Locked Encryption for Lock-Dependent Messages
Martín Abadi, Dan Boneh, Ilya Mironov, Ananth Raghunathan, Gil Segev
Public-key cryptography
Motivated by the problem of avoiding duplication in storage systems, Bellare, Keelveedhi, and Ristenpart have recently put forward the notion of Message-Locked Encryption (MLE) schemes which subsumes convergent encryption and its variants. Such schemes do not rely on permanent secret keys, but rather encrypt messages using keys derived from the messages themselves.
We strengthen the notions of security proposed by Bellare et al. by considering plaintext distributions that may depend on the...
Adding Controllable Linkability to Pairing-Based Group Signatures For Free
Daniel Slamanig, Raphael Spreitzer, Thomas Unterluggauer
Cryptographic protocols
Group signatures, which allow users of a group to anonymously produce signatures on behalf of the group, are an important cryptographic primitive for privacy-enhancing applications. Over the years, various approaches to enhanced anonymity management mechanisms, which extend the standard feature of opening of group signatures, have been proposed.
In this paper we show how pairing-based group signature schemes (PB-GSSs) following the sign-and-encrypt-and-prove (SEP) paradigm that are secure...
Efficient Non-Interactive Zero Knowledge Arguments for Set Operations
Prastudy Fauzi, Helger Lipmaa, Bingsheng Zhang
Cryptographic protocols
We propose a non-interactive zero knowledge \emph{pairwise multiset sum equality test (PMSET)} argument in the common reference string (CRS) model that allows a prover to show that the given committed multisets $\AAA_j$ for $j \in \set{1, 2, 3, 4}$ satisfy $\AAA_1 \uplus \AAA_2 = \AAA_3 \uplus \AAA_4$, i.e., every element is contained in $\AAA_1$ and $\AAA_2$ exactly as many times as in $\AAA_3$ and $\AAA_4$.
As a corollary to the $\PUTME$ argument, we present arguments that enable to...
Practical Dual-Receiver Encryption---Soundness, Complete Non-Malleability, and Applications
Sherman S. M. Chow, Matthew Franklin, Haibin Zhang
Public-key cryptography
We reformalize and recast dual-receiver encryption (DRE) proposed in CCS '04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then...
Property Preserving Symmetric Encryption Revisited
Sanjit Chatterjee, M. Prem Laxman Das
At EUROCRYPT~2012 Pandey and Rouselakis introduced the notion of property preserving symmetric encryption which enables checking for a property on plaintexts by running a public test on the corresponding ciphertexts. Their primary contributions are: (i) a separation between `find-then-guess' and `left-or-right' security notions;
(ii) a concrete construction for left-or-right secure orthogonality testing in composite order bilinear groups.
This work undertakes a comprehensive (crypt)analysis...
Multiparty Proximity Testing with Dishonest Majority from Equality Testing
Ran Gelles, Rafail Ostrovsky, Kina Winoto
Cryptographic protocols
Motivated by the recent widespread emergence of location-based services (LBS) over mobile devices, we explore efficient protocols for proximity-testing. Such protocols allow a group of friends to discover if they are all close to each other in some physical location, without revealing their individual locations to each other. We focus on hand-held devices and aim at protocols with very small communication complexity and a small number of rounds.
The proximity-testing problem can be reduced...
Constant-Rounds, Linear Multi-party Computation for Exponentiation and Modulo Reduction with Perfect Security
Chao Ning, Qiuliang Xu
Bit-decomposition is an important primitive in multi-party computation (MPC). Given a sharing of secret $x$, it allows the parties to compute the sharings of the bits of $x$ in constant rounds. With the help of bit-decomposition, we will be able to construct constant-rounds protocols for various MPC problems, such as \emph{equality test}, \emph{comparison}, \emph{public modulo reduction} and \emph{private exponentiation}, which are four main applications of bit-decomposition. However, when...
Anonymous Fuzzy Identity-based Encryption for Similarity Search
Ye Zhang, Nikos Mamoulis, David W. Cheung, S. M. Yiu, W. K. Wong
Public-key cryptography
In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the hamming distance between the attribute $X$ of a data item and a target $V$ is equal to (or less than) a threshold $t$ where $X$ and $V$ are of length $m$. Existing solutions either do not provide attribute protection or produce a big ciphertext of size $O(m2^m)$. For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of...
One for All - All for One: Unifying Standard DPA Attacks
Stefan Mangard, Elisabeth Oswald, Francois-Xavier Standaert
Implementation
In this paper, we examine the relationship between and the efficiency of different approaches to standard (univariate) DPA attacks. We first show that, when feeded with the same assumptions about the target device (i.e. with the same leakage model), the most popular approaches such as using a distance-of-means test, correlation analysis, and Bayes attacks are essentially equivalent in this setting. Differences observed in practice are not due to differences in the statistical tests but due...
Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model
Rafael Tonicelli, Rafael Dowsley, Goichiro Hanaoka, Hideki Imai, Jörn Müller-Quade, Akira Otsuka, Anderson C. A. Nascimento
Oblivious polynomial evaluation (OPE) consists of a two-party
protocol where a sender inputs a polynomial $P$, and a receiver
inputs a single value $i$. At the end of the protocol, the
sender learns nothing and the receiver learns $P(i)$. This
paper deals with the problem of oblivious polynomial evaluation
under an information-theoretical perspective, which is based
on recent definitions of Unconditional Security
developed by Crépeau et al. (EUROCRYPT 2006). In this...
Comparing With RSA
Julien Cathalo, David Naccache, Jean-Jacques Quisquater
Public-key cryptography
A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings.
This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures.
In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution...
Mutual Information Analysis -- A Universal Differential Side-Channel Attack
Benedikt Gierlichs, Lejla Batina, Pim Tuyls
Applications
In this paper, we develop an information theoretic differential side-channel attack. An embedded device containing a secret key is modeled as a black box with a leakage function whose output is captured by an adversary through the noisy measurement of a physical observable e.g. the power consumed by the device. We assume only
that the measured values depend somehow on the leakage and thus on the word being processed by the device. Without any knowledge on the particular dependency, this fact...
An efficient way to access an array at a secret index
Timothy Atkinson, Marius C. Silaghi
Cryptographic protocols
We propose cryptographic primitives for reading and assigning the
(shared) secret found at a secret index in a vector of secrets. The
problem can also be solved in constant round with existing general
techniques based on arithmetic circuits and the ``equality test''
in [Damgard.et.al 05]. However the proposed technique requires to
exchange less bits. The proposed primitives require a number of rounds
that is independent of the size N of the vector, and only depends
(linearly) on the number...
Searchable Keyword-Based Encryption
Dong Jin Park, Juyoung Cha, Pil Joong Lee
To solve the problem of searching on encrypted data, many keyword search schemes have been proposed in recent years. The goal of such schemes is to enable a user to give an untrusted storage server the ability only to test whether an encrypted document contains a few keywords without learning anything else about the document. In this paper, we are concerned with decrypting the searched results as well as searching for desired documents. In the previously proposed schemes, except for the work...
Scan Based Side Channel Attack on Data Encryption Standard
Bo Yang, Kaijie Wu, Ramesh Karri
Applications
Scan based test is a double edged sword. On one hand, it is a powerful test technique. On the other hand, it is an equally powerful attack tool. In this paper we show that scan chains can be used as a side channel to recover secret keys from a hardware implementation of the Data Encryption Standard (DES).
By loading pairs of known plaintexts with one-bit difference in the normal mode and then scanning out the internal state in the test mode, we first determine the position of all scan...
Using Information Theory Approach to Randomness Testing
B. Ya. Ryabko, V. A. Monarev
We address the problem of detecting deviations of binary sequence
from randomness,which is very important for random number (RNG)
and pseudorandom number generators (PRNG). Namely, we consider a
null hypothesis $H_0$ that a given bit sequence is generated by
Bernoulli source with equal probabilities of 0 and 1 and the
alternative hypothesis $H_1$ that the sequence is generated by a
stationary and ergodic source which differs from the source under
$H_0$. We show that data compression methods...
Private set union (PSU) is a cryptographic protocol that allows two parties to compute the union of their sets without revealing anything else. Despite some efficient PSU protocols that have been proposed, they mainly focus on the balanced setting, where the sets held by the parties are of similar size. Recently, Tu et al. (CCS 2023) proposed the first unbalanced PSU protocol which achieves sublinear communication complexity in the size of the larger set. In this paper, we are interested...
A security proof for a key exchange protocol requires writing down a security definition. Authors typically have a clear idea of the level of security they aim to achieve. Defining the model formally additionally requires making choices on games vs. simulation-based models, partnering, on having one or more Test queries and on adopting a style of avoiding trivial attacks: exclusion, penalizing or filtering. We elucidate the consequences, advantages and disadvantages of the different possible...
We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo $M$ and allowing additive secret-sharing of all inputs and outputs. These extensions can be...
Secure equality testing and comparison are two important primitives that have been widely used in many secure computation scenarios, such as privacy-preserving machine learning, private set intersection, secure data mining, etc. In this work, we propose new constant-round two-party computation (2PC) protocols for secure equality testing and secure comparison. Our protocols are designed in the online/offline paradigm. Theoretically, for 32-bit integers, the online communication for our...
Abelian group actions appear in several areas of cryptography, especially isogeny-based post-quantum cryptography. A natural problem is to relate the analogues of the computational Diffie-Hellman (CDH) and discrete logarithm (DLog) problems for abelian group actions. Galbraith, Panny, Smith and Vercauteren (Mathematical Cryptology '21) gave a quantum reduction of DLog to CDH, assuming a CDH oracle with perfect correctness. Montgomery and Zhandry (Asiacrypt '22, best paper award) showed...
The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$. The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM). In this paper,...
Public key encryption with equality test, proposed by Yang et al. (CT-RSA 2010), allows anyone to check whether two ciphertexts of distinct public keys are encryptions of the same plaintext or not using trapdoors, and identity-based encryption with equality test (IBEET) is its identity-based variant. As a variant of IBEET, IBEET against insider attacks (IBEETIA) was proposed by Wu et al. (ACISP 2017), where a token is defined for each identity and is used for encryption. Lee et al. (ACISP...
STARK is a widely used transparent proof system that uses low-degree tests for proving the correctness of a computer program. STARK consumes an intermediate representation known as AIR that is more appropriate for programs with a relatively short and structured description. However, an AIR is not able to succinctly express non-equality constraints, leading to the incorporation of unwanted polynomials. We present the eSTARK protocol, a new probabilistic proof that generalizes the STARK...
Identity-based encryption with equality test (IBEET) is a variant of identity-based encryption (IBE), where any users who have trapdoors can check whether two ciphertexts are encryption of the same plaintext. Although several lattice-based IBEET schemes have been proposed, they have drawbacks in either security or efficiency. Specifically, most schemes satisfy only selective security, while adaptively secure schemes in the standard model suffer from large master public keys that consist of...
We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional-encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care...
The protection of confidential information is a global issue and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on "Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a...
Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can...
Private set union (PSU) allows two parties to compute the union of their sets without revealing anything else. It has been widely used in various applications. While several computationally efficient PSU protocols have been developed for the balanced case, they have a potential limitation in their communication complexity, which grows (super)-linearly with the size of the larger set. This poses a challenge when performing PSU in the unbalanced setting, where one party is a constrained device...
The General Sieve Kernel (G6K) implemented a variety of lattice reduction algorithms based on sieving algorithms. One of the representative of these lattice reduction algorithms is Pump and jump-BKZ (pnj-BKZ) algorithm which is currently considered as the fastest lattice reduction algorithm. The pnj-BKZ is a BKZ-type lattice reduction algorithm which includes the jump strategy, and uses Pump as the SVP Oracle. Here, Pump which was also proposed in G6K, is an SVP sloving algorithm that...
We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of...
Nowadays, together with stormy technology advancement, billions of interconnected devices are constantly collecting data around us. In that fashion, privacy protection has become a major concern. The data must be in encrypted form before being stored on the cloud servers. As a result, the cloud servers are unable to perform calculations on en- crypted data, such as searching and matching keywords. In the PKE- MET setting, a cloud server can perform an equality test on a number of ciphertexts...
Checking the equality of two arrays is a crucial building block of the Fujisaki-Okamoto transformation, and as such it is used in several post-quantum key encapsulation mechanisms including Kyber and Saber. While this comparison operation is easy to perform in a black box setting, it is hard to efficiently protect against side-channel attacks. For instance, the hash-based method by Oder et al. is limited to first-order masking, a higher-order method by Bache et al. was shown to be flawed,...
Attribute-based encryption with equality test ($\mathsf{ABEET}$) is an extension of the ordinary attribute-based encryption ($\mathsf{ABE}$), where trapdoors enable us to check whether two ciphertexts are encryptions of the same message. Thus far, several CCA-secure $\mathsf{ABEET}$ schemes have been proposed for monotone span programs satisfying selective security under $q$-type assumptions. In this paper, we propose a generic construction of CCA-secure $\mathsf{ABEET}$ from delegatable...
We investigate __all__ NIST PQC Round 3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test with re-encryption in decapsulation is critical. We survey effective key-recovery attacks when we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two...
Functional encryption generates sophisticated keys for users so that they can learn specific functions of the encrypted message. We provide a generic construction of chosen ciphertext attacks (CCA) secure public-key functional encryption (PKFE) for all polynomial-size circuits. Our PKFE produces succinct ciphertexts that are independent of the size and depth of the circuit class under consideration. We accomplish our goal in two steps. First, we define a new cryptographic tool called...
Secure Multi-party Computation (MPC) allows a set of mutually distrusting parties to jointly evaluate a function on their private inputs while maintaining input privacy. In this work, we improve semi-honest secure two-party computation (2PC) over rings, with a focus on the efficiency of the online phase. We propose an efficient mixed-protocol framework, outperforming the state-of-the-art 2PC framework of ABY. Moreover, we extend our techniques to multi- input multiplication gates without...
A common primitive in election and auction protocols is plaintext equivalence test (PET) in which two ciphertexts are tested for equality of their plaintexts, and a verifiable proof of the test's outcome is provided. The most commonly-cited PETs require at least one honest party, but many applications claim universal verifiability, at odds with this requirement. If a test that relies on at least one honest participant is mistakenly used in a place where universally verifiable proof is...
Recently, Huang et al. proposed a concept of public key encryption with filtered equality test (PKE-FET) that allows a tester who has a warrant for the selected message set to check equality of messages in ciphertexts that belong to that set (Journal of Computer and System Sciences, 2017). They also presented an instantiation of the PKE-FET that was asserted to achieve the indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2) in the standard model. In this note, we show...
We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al....
At CRYPTO 2018 Cramer et al. presented SPDZ2k, a new secret-sharing based protocol for actively secure multi-party computation against a dishonest majority, that works over rings instead of fields. Their protocol uses slightly more communication than competitive schemes working over fields. However, their approach allows for arithmetic to be carried out using native 32 or 64-bit CPU operations rather than modulo a large prime. The authors thus conjectured that the increased communication...
A framework is introduced for efficiently computing with encrypted data. We assume a semi-honest security model with two computing parties. Two different coding techniques are used with additively homomorphic encryption, such that many values can be put into one large encryption, and additions and multiplications can be performed on all values simultaneously. For more complicated operations such as comparisons and equality tests, bit-wise secret sharing is proposed as an additional technique...
To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, ``$x=y, x\neq y$'', have been widely studied with many proposals but there is much room for improvement for order comparisons, ``$x < y,~x \leq y, x > y$ and $x \geq y$''. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition,...
Thanks to the ease of access and low expenses, it is now popular for people to store data in cloud servers. To protect sensitive data from being leaked to the outside, people usually encrypt the data in the cloud. However, management of these encrypted data becomes a challenging problem, e.g. data classification. Besides, how to selectively share data with other users is also an important and interesting problem in cloud storage. In this paper, we focus on ciphertext-policy attribute based...
We propose the first multi-client predicate-only encryption scheme capable of efficiently testing the equality of two encrypted vectors. Our construction can be used for the privacy-preserving monitoring of relations among multiple clients. Since both the clients’ data and the predicates are encrypted, our system is suitable for situations in which this information is considered sensitive. We prove our construction plaintext and predicate private in the generic bilinear group model using...
At ACISP 2017, Wu et al. presented an identity-based encryption with equality test (IBEET) that considers to prevent insider attacks. To analyze its security, they proposed a new security notion for IBEET, which is slightly weaker than the indistinguishability under adaptive identity and chosen ciphertext attacks (IND-ID-CCA2) for traditional identity-based encryption. Then, they claimed that their proposed scheme achieves this new security notion under the Bilinear Diffie-Hellman (BDH)...
We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC '90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits...
Public key encryption with equality test (PKEET) is a cryptosystem that allows a tester who has trapdoors issued by one or more users $U_i$ to perform equality tests on ciphertexts encrypted using public key(s) of $U_i$. Since this feature has a lot of practical applications including search on encrypted data, several PKEET schemes have been proposed so far. However, to the best of our knowledge, all the existing proposals are proven secure only under the hardness of number-theoretic...
In this paper, we propose the concept of certificateless public key encryption with equality test (CL-PKEET) to solve the key escrow problem in IBEET. More in details, we first give the definition of CL-PKEET and define the security model. Finally, we propose a concrete CL-PKEET scheme based on the Decision Bilinear Diffie-Hellman (DBDH) assumption and prove its security.
This paper describes a 1-out-of-N oblivious transfer (OT) extension protocol with active security, which achieves very low overhead compared with the passively secure protocol of Kolesnikov and Kumaresan (Crypto 2011). Our protocol obtains active security using a consistency check which requires only simple computation and has a communication overhead that is independent of the total number of OTs to be produced. We prove its security in both the random oracle model and the standard model,...
Protocols for securely comparing private values are among the most fundamental building blocks of multiparty computation. Introduced by Yao under the name millionaire's problem, they have found numerous applications in a variety of privacy-preserving protocols; however, due to their inherent non-arithmetic structure, existing construction often remain an important bottleneck in large-scale secure protocols. In this work, we introduce new protocols for securely computing the greater-than and...
In recent years, public key encryption with equality test (PKEET) has become a hot research topic in the cryptography community due to the advancement of cloud computing. Recently, Ma et al. proposed a new related primitive, called public key encryption with equality test supporting flexible authorization (PKEET-FA), and constructed a concrete scheme. In their proposal, four types of authorization were presented to support different authorization policies. However, their proposal is based on...
We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders, previously revisited by Lenstra-Silverberg, can be extended to complex-multiplication (CM) orders, and even to a more general structure. This algorithm allows to test equality over the polarized ideal class group, and finds a generator of the polarized ideal in polynomial time. Also, the algorithm allows to solve the norm equation over CM orders and the recent reduction of principal ideals to the real suborder can...
Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of \emph{equality}. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme \emph{without...
Loosely speaking, a family of computational groups is a family $(G_d)_{d\in D}$ of groups (where $D$ is a set of bit strings) whose elements are represented by bit strings in such a way that equality testing, multiplication, inversion, computing the identity element, and sampling random elements in $G_d$ can be performed efficiently when $d$ is given. A family $(G_d)_{d\in D}$ of computational groups is called pseudo-free if, given a random index $d$ (for an arbitrary value of the security...
Nowadays, most smartphones come pre-equipped with location (GPS) sensing capabilities, allowing developers to create a wide variety of location-aware applications and services. While location awareness provides novel features and functionality, it opens the door to many privacy nightmares. In many occasions, however, users do not need to share their actual location, but to determine whether they are in proximity to others, which is practically one bit of information. Private proximity...
In this paper, we propose a universal hardware API for authenticated ciphers, which can be used in any future implementations of authenticated ciphers submitted to the CAESAR competition. A common interface and communication protocol would help in reducing any potential biases, and would make the comparison in hardware more reliable and fair. By design, our proposed API is equally suitable for hardware implementations of authenticated ciphers developed manually (at the register-transfer...
Motivated by the problem of avoiding duplication in storage systems, Bellare, Keelveedhi, and Ristenpart have recently put forward the notion of Message-Locked Encryption (MLE) schemes which subsumes convergent encryption and its variants. Such schemes do not rely on permanent secret keys, but rather encrypt messages using keys derived from the messages themselves. We strengthen the notions of security proposed by Bellare et al. by considering plaintext distributions that may depend on the...
Group signatures, which allow users of a group to anonymously produce signatures on behalf of the group, are an important cryptographic primitive for privacy-enhancing applications. Over the years, various approaches to enhanced anonymity management mechanisms, which extend the standard feature of opening of group signatures, have been proposed. In this paper we show how pairing-based group signature schemes (PB-GSSs) following the sign-and-encrypt-and-prove (SEP) paradigm that are secure...
We propose a non-interactive zero knowledge \emph{pairwise multiset sum equality test (PMSET)} argument in the common reference string (CRS) model that allows a prover to show that the given committed multisets $\AAA_j$ for $j \in \set{1, 2, 3, 4}$ satisfy $\AAA_1 \uplus \AAA_2 = \AAA_3 \uplus \AAA_4$, i.e., every element is contained in $\AAA_1$ and $\AAA_2$ exactly as many times as in $\AAA_3$ and $\AAA_4$. As a corollary to the $\PUTME$ argument, we present arguments that enable to...
We reformalize and recast dual-receiver encryption (DRE) proposed in CCS '04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then...
At EUROCRYPT~2012 Pandey and Rouselakis introduced the notion of property preserving symmetric encryption which enables checking for a property on plaintexts by running a public test on the corresponding ciphertexts. Their primary contributions are: (i) a separation between `find-then-guess' and `left-or-right' security notions; (ii) a concrete construction for left-or-right secure orthogonality testing in composite order bilinear groups. This work undertakes a comprehensive (crypt)analysis...
Motivated by the recent widespread emergence of location-based services (LBS) over mobile devices, we explore efficient protocols for proximity-testing. Such protocols allow a group of friends to discover if they are all close to each other in some physical location, without revealing their individual locations to each other. We focus on hand-held devices and aim at protocols with very small communication complexity and a small number of rounds. The proximity-testing problem can be reduced...
Bit-decomposition is an important primitive in multi-party computation (MPC). Given a sharing of secret $x$, it allows the parties to compute the sharings of the bits of $x$ in constant rounds. With the help of bit-decomposition, we will be able to construct constant-rounds protocols for various MPC problems, such as \emph{equality test}, \emph{comparison}, \emph{public modulo reduction} and \emph{private exponentiation}, which are four main applications of bit-decomposition. However, when...
In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the hamming distance between the attribute $X$ of a data item and a target $V$ is equal to (or less than) a threshold $t$ where $X$ and $V$ are of length $m$. Existing solutions either do not provide attribute protection or produce a big ciphertext of size $O(m2^m)$. For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of...
In this paper, we examine the relationship between and the efficiency of different approaches to standard (univariate) DPA attacks. We first show that, when feeded with the same assumptions about the target device (i.e. with the same leakage model), the most popular approaches such as using a distance-of-means test, correlation analysis, and Bayes attacks are essentially equivalent in this setting. Differences observed in practice are not due to differences in the statistical tests but due...
Oblivious polynomial evaluation (OPE) consists of a two-party protocol where a sender inputs a polynomial $P$, and a receiver inputs a single value $i$. At the end of the protocol, the sender learns nothing and the receiver learns $P(i)$. This paper deals with the problem of oblivious polynomial evaluation under an information-theoretical perspective, which is based on recent definitions of Unconditional Security developed by Crépeau et al. (EUROCRYPT 2006). In this...
A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings. This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures. In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution...
In this paper, we develop an information theoretic differential side-channel attack. An embedded device containing a secret key is modeled as a black box with a leakage function whose output is captured by an adversary through the noisy measurement of a physical observable e.g. the power consumed by the device. We assume only that the measured values depend somehow on the leakage and thus on the word being processed by the device. Without any knowledge on the particular dependency, this fact...
We propose cryptographic primitives for reading and assigning the (shared) secret found at a secret index in a vector of secrets. The problem can also be solved in constant round with existing general techniques based on arithmetic circuits and the ``equality test'' in [Damgard.et.al 05]. However the proposed technique requires to exchange less bits. The proposed primitives require a number of rounds that is independent of the size N of the vector, and only depends (linearly) on the number...
To solve the problem of searching on encrypted data, many keyword search schemes have been proposed in recent years. The goal of such schemes is to enable a user to give an untrusted storage server the ability only to test whether an encrypted document contains a few keywords without learning anything else about the document. In this paper, we are concerned with decrypting the searched results as well as searching for desired documents. In the previously proposed schemes, except for the work...
Scan based test is a double edged sword. On one hand, it is a powerful test technique. On the other hand, it is an equally powerful attack tool. In this paper we show that scan chains can be used as a side channel to recover secret keys from a hardware implementation of the Data Encryption Standard (DES). By loading pairs of known plaintexts with one-bit difference in the normal mode and then scanning out the internal state in the test mode, we first determine the position of all scan...
We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data compression methods...
