Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Semantic security
open-in-new
<h2 id="history">History</h2> <p>The notion of semantic security was first put forward by <a href="/facts/Shafi_Goldwasser/aTJJq4mB">Goldwasser</a> and <a href="/facts/Silvio_Micali/IxgCplaX">Micali</a> in 1982.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> However, the definition they initially proposed offered no straightforward means to prove the security of practical cryptosystems. Goldwasser/Micali subsequently demonstrated that semantic security is equivalent to another definition of security called <a href="/facts/Ciphertext_indistinguishability/2oumAzNt">ciphertext indistinguishability</a> under chosen-plaintext attack.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> This latter definition is more common than the original definition of semantic security because it better facilitates proving the security of practical cryptosystems. </p> <h2 id="symmetric-key-cryptography">Symmetric-key cryptography</h2> <p>In the case of <a href="/facts/Symmetric-key_algorithm/5zfe0b76">symmetric-key algorithm</a> cryptosystems, an adversary must not be able to compute any information about a plaintext from its ciphertext. This may be posited as an adversary, given two plaintexts of equal length and their two respective ciphertexts, cannot determine which ciphertext belongs to which plaintext. </p> <h2 id="public-key-cryptography">Public-key cryptography</h2> <p>For an <a href="/facts/Asymmetric_key_encryption_algorithm/gowoFTxS">asymmetric key encryption algorithm</a> cryptosystem to be semantically secure, it must be infeasible for a <a href="/facts/Analysis_of_algorithms/pStoBgBn">computationally bounded</a> adversary to derive significant information about a message (plaintext) when given only its <a href="/facts/Ciphertext/luNTs4sY">ciphertext</a> and the corresponding public encryption key. Semantic security considers only the case of a "passive" attacker, i.e., one who generates and observes ciphertexts using the public key and plaintexts of their choice. Unlike other security definitions, semantic security does not consider the case of <a href="/facts/Chosen_ciphertext_attack/l9fL7fYR">chosen ciphertext attack</a> (CCA), where an attacker is able to request the decryption of chosen ciphertexts, and many semantically secure encryption schemes are demonstrably insecure against chosen ciphertext attack. Consequently, semantic security is now considered an insufficient condition for securing a general-purpose encryption scheme. </p><p>Indistinguishability under <a href="/facts/Chosen_plaintext_attack/uTJ0XCAN">Chosen Plaintext Attack</a> (<a href="/facts/IND-CPA/2oumAzNt">IND-CPA</a>) is commonly defined by the following experiment:<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <ol><li>A random pair ( p k , s k ) {\displaystyle (pk,sk)} is generated by running G e n ( 1 n ) {\displaystyle Gen(1^{n})} .</li> <li>A probabilistic polynomial time-bounded adversary is given the public key p k {\displaystyle pk} , which it may use to generate any number of ciphertexts (within polynomial bounds).</li> <li>The adversary generates two equal-length messages m 0 {\displaystyle m_{0}} and m 1 {\displaystyle m_{1}} , and transmits them to a challenge oracle along with the public key.</li> <li>The challenge oracle selects one of the messages by flipping a fair coin (selecting a random bit b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} ), encrypts the message m b {\displaystyle m_{b}} under the public key, and returns the resulting <i>challenging ciphertext</i> c {\displaystyle c} to the adversary.</li></ol> <p>The underlying <a href="/facts/Cryptosystem/GyDVJ4D0">cryptosystem</a> is IND-CPA (and thus semantically secure under chosen plaintext attack) if the adversary cannot determine which of the two messages was chosen by the oracle, with probability significantly greater than 1 / 2 {\displaystyle 1/2} (the success rate of random guessing). Variants of this definition define indistinguishability under <a href="/facts/Chosen_ciphertext_attack/l9fL7fYR">chosen ciphertext attack</a> and <a href="/facts/Adaptive_chosen_ciphertext_attack/SCKGPjI6">adaptive chosen ciphertext attack</a> (<a href="/facts/IND-CCA/2oumAzNt">IND-CCA</a>, <a href="/facts/IND-CCA2/2oumAzNt">IND-CCA2</a>). </p><p>Because the adversary possesses the public encryption key in the above game, a semantically secure encryption scheme must by definition be <a href="/facts/Probabilistic_encryption/a52EXNPD">probabilistic</a>, possessing a component of <a href="/facts/Randomness/QJQBoEX5">randomness</a>; if this were not the case, the adversary could simply compute the deterministic encryption of m 0 {\displaystyle m_{0}} and m 1 {\displaystyle m_{1}} and compare these encryptions with the returned ciphertext c {\displaystyle c} to successfully guess the oracle's choice. </p> <h2 id="the-role-of-randomness-in-semantic-security">The Role of Randomness in Semantic Security</h2> <p>Randomness plays a key role in <a href="/facts/Cryptography/e94PEVau">cryptography</a> by preventing attackers from detecting patterns in ciphertexts. In a semantically secure cryptosystem, encrypting the same plaintext multiple times should produce different ciphertexts.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>If encryption relies on predictable or weak randomness, it becomes easier to break.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> Poor randomness can lead to patterns that attackers can analyze, potentially allowing them to recover secret <a href="/facts/Key_(cryptography)/5W5PAmT4">keys</a> or decrypt messages. Because of this, cryptographic systems must use strong and unpredictable random values to maintain security.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h3>Why Randomness Is Important</h3> <p>Strong randomness is critical in: </p> <ul><li><a href="/facts/Key_generation/WvRkaS6n">Key generation</a> – Ensures cryptographic keys are unpredictable.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>Nonce Selection – Reusing a nonce in <a href="/facts/AES-GCM/bx43MwfC">AES-GCM</a> or <a href="/facts/ElGamal_encryption/sKDVyMyR">ElGamal</a> can break security.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li><a href="/facts/Probabilistic_encryption/a52EXNPD">Probabilistic encryption</a> – Some schemes, like <a href="/facts/Goldwasser%25E2%2580%2593Micali_cryptosystem/qCyjdmt7">Goldwasser–Micali</a>, rely on randomness to ensure ciphertexts are indistinguishable.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li></ul> <h3>Failures of Randomness in the Past</h3> <p>Several cryptographic failures have resulted from weak randomness, allowing attackers to break encryption. </p> <h4>Debian OpenSSL Vulnerability (2008)</h4> <p>An error in Debian’s <a href="/facts/OpenSSL/aXvs5fo2">OpenSSL</a> removed entropy collection, producing a small set of predictable keys. Attackers could guess <a href="/facts/Secure_Shell/wjVRw5zv">SSH</a> and <a href="/facts/Transport_Layer_Security/pGy16TnA">TLS</a> keys, allowing unauthorized access.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h4>Sony PlayStation 3 ECDSA Failure (2011)</h4> <p>Sony’s <a href="/facts/PlayStation_3/obhuo97V">PlayStation 3</a> misused the <a href="/facts/Elliptic_Curve_Digital_Signature_Algorithm/gl0mfnS1">Elliptic Curve Digital Signature Algorithm</a> (ECDSA) by reusing the same <a href="/facts/Cryptographic_nonce/ENHRCGnw">nonce</a> - a random number used once in cryptographic signing - in multiple signatures. Since ECDSA relies on unique nonces for security, attackers recovered Sony’s private signing key, allowing them to sign unauthorized software.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h4>ROCA Vulnerability (2017)</h4> <p>A flaw in <a href="/facts/Infineon_Technologies/LAAXwhcC">Infineon's</a> <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA</a> key generation created weak keys that attackers could efficiently factor. This vulnerability affected smart cards and <a href="/facts/Trusted_Platform_Module/3XHCGYkX">Trusted Platform Modules</a> (TPMs), requiring widespread key replacements.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p> <h3>How to Ensure Strong Randomness</h3> <p>To prevent such failures, cryptographic systems must generate unpredictable and high-quality random values.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p> <h4>Use of Cryptographically Secure Pseudorandom Number Generators (CSPRNGs)</h4> <p>CSPRNGs provide secure random numbers resistant to attacks. Common examples include: </p> <ul><li>/dev/random and /dev/urandom (Unix)</li> <li>Windows CryptGenRandom</li> <li>NIST-approved DRBGs (Deterministic Random Bit Generators)<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a></li></ul> <h4>Entropy Collection</h4> <p>Secure randomness requires high entropy sources, such as: </p> <ul><li>Hardware-based generators (e.g., Intel <a href="/facts/RDRAND/IdeN4y36">RDRAND</a>)<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a></li> <li>Physical sources, like keystroke timing<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a></li> <li>Dedicated security hardware, including <a href="/facts/Hardware_security_module/dhpo8qoR">HSMs</a> and <a href="/facts/Trusted_Platform_Module/3XHCGYkX">TPMs</a><a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></li></ul> <h4>Avoiding Deterministic Encryption Without Randomness</h4> <p>Some encryption schemes require added randomness to maintain security: </p> <ul><li><a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA</a> with <a href="/facts/Optimal_asymmetric_encryption_padding/j5doK6YB">OAEP</a> padding introduces randomness to prevent deterministic encryption.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a></li> <li>Unique nonces in <a href="/facts/AES-GCM/bx43MwfC">AES-GCM</a> and <a href="/facts/ElGamal_encryption/sKDVyMyR">ElGamal</a> ensure encrypting the same message multiple times produces different ciphertexts.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a></li></ul> <h4>Testing and Auditing Randomness</h4> <p>To verify randomness quality, cryptographic implementations should undergo: </p> <ul><li><a href="/facts/National_Institute_of_Standards_and_Technology/gr9Fnh85">NIST</a> SP 800-90B randomness tests<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a></li> <li><a href="/facts/Diehard_tests/6jj2Kylt">Diehard tests</a><a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a></li> <li><a href="/facts/FIPS_140-2/xCKhMHnK">FIPS 140-2</a> compliance checks<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a></li></ul> <p>Semantically secure encryption algorithms include <a href="/facts/Goldwasser-Micali_cryptosystem/qCyjdmt7">Goldwasser-Micali</a>, <a href="/facts/ElGamal_encryption/sKDVyMyR">ElGamal</a> and <a href="/facts/Paillier/oLl6TR8H">Paillier</a>. These schemes are considered <a href="/facts/Provable_security/2kQS1WId">provably secure</a>, as their semantic security can be reduced to solving some hard mathematical problem (e.g., <a href="/facts/Decisional_Diffie-Hellman_assumption/n1A9uKcH">Decisional Diffie-Hellman</a> or the <a href="/facts/Quadratic_Residuosity_Problem/b8B2ptVQ">Quadratic Residuosity Problem</a>). Other, semantically insecure algorithms such as <a href="/facts/RSA_(algorithm)/XTzyfHuq">RSA</a>, can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as <a href="/facts/Optimal_Asymmetric_Encryption_Padding/j5doK6YB">Optimal Asymmetric Encryption Padding</a> (OAEP). </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Annual ACM Symposium on Theory of Computing, 1982. <a href="/wiki/Shafi_Goldwasser" target="_blank">/wiki/Shafi_Goldwasser</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Shannon, Claude (1949). "Communication Theory of Secrecy Systems". Bell System Technical Journal. 28 (4): 656–715. doi:10.1002/j.1538-7305.1949.tb00928.x. hdl:10338.dmlcz/119717. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Goldreich, Oded. Foundations of Cryptography: Volume 2, Basic Applications. Vol. 2. Cambridge university press, 2004. <a href="/wiki/Oded_Goldreich" target="_blank">/wiki/Oded_Goldreich</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Annual ACM Symposium on Theory of Computing, 1982. <a href="/wiki/Shafi_Goldwasser" target="_blank">/wiki/Shafi_Goldwasser</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Goldwasser, Shafi; Micali, Silvio (1984-04-01). "Probabilistic encryption". Journal of Computer and System Sciences. 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9. ISSN 0022-0000. <a href="https://dx.doi.org/10.1016/0022-0000%2884%2990070-9" target="_blank">https://dx.doi.org/10.1016/0022-0000%2884%2990070-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>S. Goldwasser and S. Micali, Probabilistic encryption. Journal of Computer and System Sciences, 28:270-299, 1984. <a href="/wiki/Shafi_Goldwasser" target="_blank">/wiki/Shafi_Goldwasser</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. ISBN 978-1584885511. <a href="978-1584885511" target="_blank">978-1584885511</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Menezes, Alfred; Van Oorschot, Paul C.; Vanstone, Scott (1996). Handbook of Applied Cryptography. CRC Press. <a href="https://cacr.uwaterloo.ca/hac/" target="_blank">https://cacr.uwaterloo.ca/hac/</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Menezes, Alfred; Van Oorschot, Paul C.; Vanstone, Scott (1996). Handbook of Applied Cryptography. CRC Press. <a href="https://cacr.uwaterloo.ca/hac/" target="_blank">https://cacr.uwaterloo.ca/hac/</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. ISBN 978-1584885511. <a href="978-1584885511" target="_blank">978-1584885511</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. ISBN 978-1584885511. <a href="978-1584885511" target="_blank">978-1584885511</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. ISBN 978-1584885511. <a href="978-1584885511" target="_blank">978-1584885511</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. ISBN 978-1584885511. <a href="978-1584885511" target="_blank">978-1584885511</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Bello, Luciano (2008-05-13). "Debian OpenSSL Predictable Random Number Generator". Debian Security Advisory. <a href="https://www.debian.org/security/2008/dsa-1571" target="_blank">https://www.debian.org/security/2008/dsa-1571</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Schneier, Bruce (2011-01-06). "Sony PS3 Security Broken". Schneier on Security. <a href="https://www.schneier.com/blog/archives/2011/01/sony_ps3_securi.html" target="_blank">https://www.schneier.com/blog/archives/2011/01/sony_ps3_securi.html</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>"ROCA: Infineon TPM and Secure Element RSA Vulnerability Guidance". National Cyber Security Centre. 2017-10-17. <a href="https://www.ncsc.gov.uk/guidance/roca-infineon-tpm-and-secure-element-rsa-vulnerability-guidance" target="_blank">https://www.ncsc.gov.uk/guidance/roca-infineon-tpm-and-secure-element-rsa-vulnerability-guidance</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>"Recommendation for Random Number Generation Using Deterministic Random Bit Generators". National Institute of Standards and Technology (NIST). 2012-06-11. <a href="https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>"Recommendation for Random Number Generation Using Deterministic Random Bit Generators". National Institute of Standards and Technology (NIST). 2012-06-11. <a href="https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>"Recommendation for the Entropy Sources Used for Random Bit Generation". National Institute of Standards and Technology (NIST). 2018-01-10. <a href="https://csrc.nist.gov/publications/detail/sp/800-90b/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90b/final</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>"Recommendation for the Entropy Sources Used for Random Bit Generation". National Institute of Standards and Technology (NIST). 2018-01-10. <a href="https://csrc.nist.gov/publications/detail/sp/800-90b/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90b/final</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>"Recommendation for the Entropy Sources Used for Random Bit Generation". National Institute of Standards and Technology (NIST). 2018-01-10. <a href="https://csrc.nist.gov/publications/detail/sp/800-90b/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90b/final</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>"Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography". National Institute of Standards and Technology (NIST). 2019-05-23. <a href="https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>"Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography". National Institute of Standards and Technology (NIST). 2019-05-23. <a href="https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>"Recommendation for the Entropy Sources Used for Random Bit Generation". National Institute of Standards and Technology (NIST). 2018-01-10. <a href="https://csrc.nist.gov/publications/detail/sp/800-90b/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-90b/final</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>"A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". National Institute of Standards and Technology (NIST). 2010-04-01. <a href="https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final" target="_blank">https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>"Security Requirements for Cryptographic Modules". National Institute of Standards and Technology (NIST). 2002-05-25. <a href="https://csrc.nist.gov/publications/detail/fips/140/2/final" target="_blank">https://csrc.nist.gov/publications/detail/fips/140/2/final</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> </ol>