Structured encryption

Last updated

Structured encryption (STE) is a form of encryption that encrypts a data structure so that it can be privately queried. Structured encryption can be used as a building block to design end-to-end encrypted databases, efficient searchable symmetric encryption (SSE) and other algorithms that can be efficiently executed on encrypted data.

Description

A structured encryption scheme [1] is a symmetric-key encryption scheme that encrypts a data structure in such a way that, given the key and a query , one can generate a query token with which the encrypted data structure can be queried. If the STE scheme is dynamic then it also supports update operations like inserts and deletes. There are several forms of STE including response-revealing STE where the response to the query is output in plaintext and response-hiding where the response to the query is output in encrypted form. STE schemes guarantee that no information about the data or queries can be recovered from the encrypted data structure and tokens beyond a well-specified and "reasonable" leakage profile.

STE schemes with a variety of leakage profiles have been designed for a wide array of abstract data types and data structures including arrays, multi-maps, [2] [1] [3] dictionaries and graphs. [1] [4]

STE is closely related to but different than searchable symmetric encryption. The purpose of SSE is to encrypt document collections in such a way that keyword search can still be executed on the encrypted documents whereas the purpose of STE is to encrypt data structures in such a way that queries can still be executed over the encrypted structure. Certain types of STE schemes like multi-map encryption schemes can be used to design sub-linear and optimal SSE schemes. [2]

Related Research Articles

<span class="mw-page-title-main">Cipher</span> Algorithm for encrypting and decrypting information

In cryptography, a cipher is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography.

<span class="mw-page-title-main">Encryption</span> Process of converting plaintext to ciphertext

In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decipher a ciphertext back to plaintext and access the original information. Encryption does not itself prevent interference but denies the intelligible content to a would-be interceptor.

<span class="mw-page-title-main">Public-key cryptography</span> Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

The Encrypting File System (EFS) on Microsoft Windows is a feature introduced in version 3.0 of NTFS that provides filesystem-level encryption. The technology enables files to be transparently encrypted to protect confidential data from attackers with physical access to the computer.

Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably.

Encryption software is software that uses cryptography to prevent unauthorized access to digital information. Cryptography is used to protect digital information on computers as well as the digital information that is sent to other computers over the Internet.

A deterministic encryption scheme is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include RSA cryptosystem, and many block ciphers when used in ECB mode or with a constant initialization vector.

Cryptovirology refers to the use of cryptography to devise particularly powerful malware, such as ransomware and asymmetric backdoors. Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. Cryptovirology employs a twist on cryptography, showing that it can also be used offensively. It can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents.

Disk encryption is a technology which protects information by converting it into code that cannot be deciphered easily by unauthorized people or processes. Disk encryption uses disk encryption software or hardware to encrypt every bit of data that goes on a disk or disk volume. It is used to prevent unauthorized access to data storage.

Email encryption is encryption of email messages to protect the content from being read by entities other than the intended recipients. Email encryption may also include authentication.

In cryptography, a hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a symmetric-key cryptosystem. Public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely. However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable symmetric-key cryptosystems. In many applications, the high cost of encrypting long messages in a public-key cryptosystem can be prohibitive. This is addressed by hybrid systems by using a combination of both.

Cloud computing security or, more simply, cloud security refers to a broad set of policies, technologies, applications, and controls utilized to protect virtualized IP, data, applications, services, and the associated infrastructure of cloud computing. It is a sub-domain of computer security, network security, and, more broadly, information security.

Database encryption can generally be defined as a process that uses an algorithm to transform data stored in a database into "cipher text" that is incomprehensible without first being decrypted. It can therefore be said that the purpose of database encryption is to protect the data stored in a database from being accessed by individuals with potentially "malicious" intentions. The act of encrypting a database also reduces the incentive for individuals to hack the aforementioned database as "meaningless" encrypted data is of little to no use for hackers. There are multiple techniques and technologies available for database encryption, the most important of which will be detailed in this article.

Attribute-based encryption is a generalisation of public-key encryption which enables fine grained access control of encrypted data using authorisation policies. The secret key of a user and the ciphertext are dependent upon attributes. In such a system, the decryption of a ciphertext is possible only if the set of attributes of the user key matches the attributes of the ciphertext.

Identity-based conditional proxy re-encryption (IBCPRE) is a type of proxy re-encryption (PRE) scheme in the identity-based public key cryptographic setting. An IBCPRE scheme is a natural extension of proxy re-encryption on two aspects. The first aspect is to extend the proxy re-encryption notion to the identity-based public key cryptographic setting. The second aspect is to extend the feature set of proxy re-encryption to support conditional proxy re-encryption. By conditional proxy re-encryption, a proxy can use an IBCPRE scheme to re-encrypt a ciphertext but the ciphertext would only be well-formed for decryption if a condition applied onto the ciphertext together with the re-encryption key is satisfied. This allows fine-grained proxy re-encryption and can be useful for applications such as secure sharing over encrypted cloud data storage.

Crypto-shredding is the practice of 'deleting' data by deliberately deleting or overwriting the encryption keys. This requires that the data have been encrypted. Data may be considered to exist in three states: data at rest, data in transit and data in use. General data security principles, such as in the CIA triad of confidentiality, integrity, and availability, require that all three states must be adequately protected.

In cryptography, a padded uniform random blob or PURB is a discipline for encrypted data formats designed to minimize unintended information leakage either from its encryption format metadata or from its total length.

<span class="mw-page-title-main">Searchable symmetric encryption</span> System allowing searching of encrypted documents

Searchable symmetric encryption (SSE) is a form of encryption that allows one to efficiently search over a collection of encrypted documents or files without the ability to decrypt them. SSE can be used to outsource files to an untrusted cloud storage server without ever revealing the files in the clear but while preserving the server's ability to search over them.

Seny Kamara is a Senegalese-French-American computer scientist best known for his work on cryptography. He has delivered multiple congressional testimonies about the potential harms and opportunities with technology. He leads or co-leads numerous centers and activities focused on cryptography and social good. His work has been covered extensively in high-profile media, including Wired and Forbes.

References

  1. 1 2 3 Chase, Melissa; Kamara, Seny (2010). "Structured Encryption and Controlled Disclosure". In Abe, Masayuki (ed.). Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Vol. 6477. Berlin, Heidelberg: Springer. pp. 577–594. doi: 10.1007/978-3-642-17373-8_33 . ISBN   978-3-642-17373-8.
  2. 1 2 Curtmola, Reza; Garay, Juan; Kamara, Seny; Ostrovsky, Rafail (2011-01-01). "Searchable symmetric encryption: Improved definitions and efficient constructions". Journal of Computer Security. 19 (5): 895–934. doi:10.3233/JCS-2011-0426. ISSN   0926-227X.
  3. "Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium" . Retrieved 2022-02-23.
  4. Meng, Xianrui; Kamara, Seny; Nissim, Kobbi; Kollios, George (2015-10-12). "GRECS: Graph Encryption for Approximate Shortest Distance Queries". Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. CCS '15. New York, NY, USA: Association for Computing Machinery: 504–517. doi:10.1145/2810103.2813672. ISBN   978-1-4503-3832-5. S2CID   6166972.